Kewiri

#

Подготовлено:rasti

Автор задания:rasti

Уровень сложности: Очень легко

Описание

#

• Великие учёные Элдории подготовили серию испытаний, каждое из которых проверит глубину вашего понимания древних математических искусств. Тем, кто ответит мудро, будет даровано прозрение, а недостойные будут низвергнуты в пучину невежества. Примите ли вы вызов, или ваш разум дрогнет под тяжестью забытых знаний?

Вопрос 1

#

При подключении к экземпляру (server.py , но в таске достаточно числа p) мы ждём несколько секунд, пока инициализируется среда, а затем нам задают первый вопрос. Оказывается, у нас есть всего две секунды, чтобы ответить на каждый вопрос, иначе мы получим Too slow… Автоматизация возможна через pwntools.

[!] The ancient texts are being prepared...
You have entered the Grand Archives of Eldoria! The scholars shall test your wisdom. Answer their questions to prove your worth and claim the hidden knowledge.
You are given the sacred prime: p = 21214334341047589034959795830530169972304000967355896041112297190770972306665257150126981587914335537556050020788061
[1] How many bits is the prime p? >

[!] Древние тексты готовятся... Вы вошли в Великие Архивы Эльдории! Ученые будут испытывать вашу мудрость. Ответьте на их вопросы, чтобы доказать свою ценность и получить скрытое знание.
Вам вручается священное простое число: p = 21214334341047589034959795830530169972304000967355896041112297190770972306665257150126981587914335537556050020788061
[1] Насколько много бит в простом числе p? >

Решение 1

#

Открываем оболочку python либо sage и используем метод bit_length()

p = 21214334341047589034959795830530169972304000967355896041112297190770972306665257150126981587914335537556050020788061
print(p.bit_length())

Вопрос 2

#

...
[2] Enter the full factorization of finite field F_p in ascending order of factors (format: p0,e0_p1,e1_ ..., where pi are the distinct factors and ei the multiplicities of each factor) 

[2] Введите полную факторизацию мультипликативной группы конечного поля F_p в порядке возрастания множителей (формат: p0,e0_p1,e1_ ..., где pi — различные простые множители, а ei — кратности каждого множителя) >

Решение 2

#

Чтобы ответить на это, можно использовать SageMath или любой онлайн‑сервис факторизации, например factordb. В этом пояснении мы покажем SageMath в образовательных целях. В Sage определённое конечное поле задаётся конструктором GF. Важный факт: порядок мультипликативной группы конечного поля над простым p равен p-1. Следовательно, задача сводится к факторизации p-1. GF это класс конечного поля над p.

F = GF(p)
print(factor(p-1))

Вопрос 3

#

> [3] For this question, you will have to send 1 if the element is a generator of the finite field F_p, otherwise 0.

[3] Для этого вопроса нужно отправить 1, если элемент является генератором конечного поля F_p, иначе 0. >

Решение 3

#

Похоже на задачу поиска решения. Нам будут даны несколько целых чисел, и требуется определить, являются ли они генераторами, за ограниченное время.

Отныне мы будем ссылаться только на мультипликативную группу конечного поля F_p. Следовательно, операция в группе — умножение, а не сложение.

Напомним, что генератор g ∈ F_p — это элемент порядка p-1; то есть наименьшее целое k такое, что g^k ≡ 1, равно p-1. Проще говоря, последовательными возведениями в степени он порождает всю группу. Существуют разные подходы; наивный — перечислять все степени g^1, g^2, …, g^k до появления 1. Но для столь больших p это практически невыполнимо, поэтому нужен оптимизированный метод. Здесь полезна теорема Лагранжа. Она гласит:

Пусть G — группа и a ∈ G. Порядок элемента a делит порядок группы G.

Ответы, такие как [1] и [2], показывают, как можно использовать эту теорему для проверки, является ли элемент генератором. Основная сложность — факторизация p-1, которую мы уже знаем из вопроса (2).

Следовательно, можно записать следующий метод проверки, является ли элемент g генератором поля

\forall f \in \text{простые множители}(p-1): 
\left(g^{\frac{p-1}{f}} \mod p \neq 1 \text{ или } f = p-1\right)

def is_generator(g):
		p_1_factors = list(factor(p-1))
    for f,_ in p_1_factors:
      	# игнорируем мультипликативность
        # важны только простые множители 
        if pow(g, (p-1)//f, p) == 1 and f != p-1:
            # g является генератором поля 
            return False
		return True

Вопрос 4

#

> The scholars present a sacred mathematical construct, a curve used to protect the most guarded secrets of the realm. Only those who understand its nature may proceed.
> a = 408179155510362278173926919850986501979230710105776636663982077437889191180248733396157541580929479690947601351140
> b = 8133402404274856939573884604662224089841681915139687661374894548183248327840533912259514444213329514848143976390134
> [4] What is the order of the curve defined over F_p? > 

Первые три вопроса касались конечных полей простого порядка, обозначаемых как $\mathbb{F}_p$. Следующие три вопроса — об эллиптических кривых, определённых над простыми конечными полями, обозначаемыми $\mathbb{F}_p$.

> Учёные представляют священную математическую конструкцию — кривую, используемую для охраны самых охраняемых тайн королевства. Только те, кто понимает её природу, могут продолжить.  
> a = 408179155510362278173926919850986501979230710105776636663982077437889191180248733396157541580929479690947601351140
> b = 8133402404274856939573884604662224089841681915139687661374894548183248327840533912259514444213329514848143976390134
> [4] Каков порядок кривой, определённой над F_p?

Решение 4

#

Опять же, с помощью SageMath можно построить эллиптические кривые с помощью конструктора EllipticCurve.

E = EllipticCurve(GF(p), [a,b])

Порядок может быть получен через

print(E.order())

Вопрос 5

#

[5] Enter the full factorization of the order of the elliptic curve defined over the finite field F_{p^3}. Follow the same format as in question 2 >

[5] Введите полную факторизацию порядка эллиптической кривой, определённой над конечным полем F_{p^3}. Используйте тот же формат, что и в вопросе (2) >

Решение 5

#

Здесь нужно работать с группой $E(\mathbb{F}_{p^3})$. Если попытаться объявить кривую так:

E3 = EllipticCurve(GF(p^3), [a,b])

это может занять неопределённо много времени, потому что, как указано в документации SageMath docs, при отсутствии имени переменной в конструкторе GF Sage пытается вычислить псевдо‑Конвейевы многочлены, что обычно дорогостоящая задача.

Если для расширенного поля не задано имя переменной, Sage подбирает поле в совместимую решётку расширений, определённую псевдо‑Конвейевыми многочленами.

и

Учтите, что вычисление псевдо‑Конвейевых многочленов дорого, когда степень велика и сильно составна. Если указать имя переменной, то вместо этого используется случайный многочлен, который находится гораздо быстрее.

Поэтому решение — передать имя переменной в конструктор GF, например:

E3 = EllipticCurve(GF(p^3, 'x'), [a,b])

Это занимает пару секунд, тогда порядок кривой $E3$ будет:

9547468349770605965573984760817208987986240857800275642666264260062210623470017904319931275058250264223830562439645572562493214488086970563135688265933076141657703804791593446020774169988605421998202682898213433784381043211278976059744771523119218399190407965593665262490269084642700982261912090274007278407746985341700600062580644280196871035164

Это относительно большое число для факторизации. Однако кривая определена над расширением поля $\mathbb{F}_p$, и поэтому само $p$ гарантированно является делителем порядка $E3$. Если мы явно знаем простой множитель большого целого, можно определить его в Sage как пользовательское простое:

pari.addprimes(p)

Документация этого метода здесь. Будет понятнее в действии:

sage: from Crypto.Util.number import *
sage: p = getPrime(1024) # получение партиального простого числа/вектора из таблицы user-defined primes
sage: q = getPrime(1024)
sage: n = p*q
sage: n
20757129878476196263766872240356958683650945798076285374429775626750970675513949330074446501516100612855517734182615205487375158770547675863132057845044511253612104340755258134472492863749974099238393211422482063848956290097603703403564775164108269935134123533832551877277983143057277347519638492514730585441221489703011952662960160030649683727711868449437792977325313522208091595856156628129900905301736295843987380979447190397144712286376614669181013408381064404716330492150142662639295566001441283955619169309869318853752127302884843929101272094587621444078042154214135497915486825032223429010111980881109120894619
sage: factor(n)

обычно факторизация большого n займёт вечность. Но если вручную добавить простые числа p (или q) в таблицу партиальных простых, вызов factor сразу использует это. При вызове factor SageMath сначала проверяет таблицу пользовательских простых, а затем выполняет основную фазу факторизации.

sage: pari.addprimes(p)
[135297421183906417726626566740392626259579894073148661948890956451534112118754812518541726232569467292282889478862196473691620312949705365444531155604964232384414519054467223902773473493544417851262252940216993215948007127456493797866112761691339199411393341226367641871932959447890003835446238132539812721059]
sage: factor(n)
135297421183906417726626566740392626259579894073148661948890956451534112118754812518541726232569467292282889478862196473691620312949705365444531155604964232384414519054467223902773473493544417851262252940216993215948007127456493797866112761691339199411393341226367641871932959447890003835446238132539812721059 * 153418518230746956832407389341510432321776318039049791930350617730834744222389125421305520696017649557031736476686177322840802928919743226100290944901830004530993711798893449524808895430620967209398867996295438442523055241368009393199337777457108938262414406752504285077712759094370202179724398445117658076841

Для нашей задачи достаточно добавить p в таблицу — это позволит сразу получить факторизацию порядка кривой.

sage: pari.addprimes(p)
[21214334341047589034959795830530169972304000967355896041112297190770972306665257150126981587914335537556050020788061]
sage: factor(E3.order())
2^2 * 7^2 * 21214334341047589034959795830530169972304000967355896041112297190770972306665257150126981587914335537556050020788061 * <large_prime_factor>

Эта факторизация и будет ответом, формат как в вопросе 2

Вопрос 6

#

The final trial awaits. You must uncover the hidden multiplier “d” such that A = d * G. ⚔️ The chosen base point G has x-coordinate: 10754634945965100597587232538382698551598951191077578676469959354625325250805353921972302088503050119092675418338771 🔮 The resulting point A has x-coordinate: 776741307896310549358901148397047715054445374890300753826496778948879054114421829863318830784216542919559209003815

Последнее испытание ждёт. Вы должны раскрыть скрытый множитель «d» такой, что A = d * G.
⚔️ Выбранная базовая точка G имеет (x‑координату): 10754634945965100597587232538382698551598951191077578676469959354625325250805353921972302088503050119092675418338771
🔮 Результирующая точка A имеет (x‑координату): 776741307896310549358901148397047715054445374890300753826496778948879054114421829863318830784216542919559209003815

Решение 6

#

Для этого случая игрок может просто определить точки на кривой $E$ и выполнить log(A, G), чтобы решить задачу дискретного логарифмирования:

sage: G = E.lift_x(10754634945965100597587232538382698551598951191077578676469959354625325250805353921972302088503050119092675418338771)
sage: A = E.lift_x(776741307896310549358901148397047715054445374890300753826496778948879054114421829863318830784216542919559209003815)
sage: %time log(A,G)
CPU times: user 257 ms, sys: 1.82 ms, total: 259 ms
Wall time: 258 ms
10467269628793371276566698866836952927307367226151628920389303503200368737798238832516990930420184955214737647295096

Однако обычно ECDLP трудно решить, тогда как здесь секретный множитель был восстановлен за несколько миллисекунд. Причина в том, что кривая $E$ является аномальной: порядок $E$ равен простому $p$. Это можно проверить как:

sage: E.order() == p
True

В таком случае ECDLP решается с помощью атаки Smart.

После ответа на последний вопрос мы наконец получаем флаг.

В решении solver.py используются сетевой сервис , к которому по порядку через pwntools посылают ответы на вопросы выше. Без pwntools суть кода польностью та же.