CryptoHack. Решение Modular Binomials04.10.2024 15:30

Кто такой я?

Скрытый текст

Привет! Меня зовут Александр и большую часть своего времени я занимаюсь разработкой ПО в общем, а разработкой под Android профессионально.

Но так вышло, что я получил образование по специальности «Информационная безопасность» и за 6 лет успел значительно увлечься этой темой, а в большей степени криптографией и её математическими основами.

Другие мои статьи по этой теме также можно найти на английском на моей странице в Medium, возможно их переводы в будущем появятся и здесь.

Что такое CryptoHack?

На этот вопрос лучше меня могут ответить сами создатели сервиса, за чем отсылаю в FAQ. Тем не менее, в двух словах CryptoHack это сервис, позволяющий (хоть и поверхностно) изучить современную криптографию и математику в её основе. Но недостатки теоретической части они в достаточной мере перекрывают большим набором практических задач, многие из которых требуют глубоких математических знаний (но не на уровне доктора наук, конечно).

Задача

Формулировка задачи, которую рассматорим сегодня, максимально проста. Даны уравнения

$N = pq\\c_1 \equiv (2p + 3q)^{e_1} \mod N\\c_2 \equiv (5p + 7q)^{e_2} \mod N$

где и — простые числа. Нам необходимо найти и , остальные значение нам известны.

Для тех, кто знаком с RSA, это выглядит подозрительно похожим, однако сам RSA нас не интересует в том смысле, что расшифровывать ничего не нужно и в целом знание алгоритма для решения не пригодится.

Дай человеку удочку

Но прежде чем я перейду к решению, я предлагаю читателю, не глядя в следующий раздел, самостоятельно его вывести, используя несколько подсказок:

Погружаемся

Ну, а теперь давайте вместе разберёмся в чём же тут дело. Сперва вспомним формулу бинома Ньютона:

$(a + b)^n = \sum_{k = 0}^n \begin{pmatrix} n \\ k \end{pmatrix}a^{n - k}b^k = \\ \begin{pmatrix} n \\ 0 \end{pmatrix}a^n + \begin{pmatrix} n \\ 1 \end{pmatrix}a^{n - 1}b + ... + \begin{pmatrix} n \\ n - 1 \end{pmatrix}ab^{n - 1} + \begin{pmatrix} n \\ n \end{pmatrix}b^n$

Также напомню, что

$\begin{pmatrix} n \\ k \end{pmatrix} = \frac{n!}{k!(n - k)!} \implies \\ \begin{pmatrix} n \\ 0 \end{pmatrix} = 1; \\ \begin{pmatrix} n \\ n \end{pmatrix} = 1$

Важным моментом в формуле бинома является то, что все слагаемые, кроме двух крайних, имеют в себе произведение . Чтобы понять почему это важно разложим первое сравнение из условия по формуле:

$(2p + 3q)^{e_1} = 2^{e_1}p^{e_1} + \begin{pmatrix}e_1 \\ 1\end{pmatrix}2^{e_1 - 1}p^{e_1 - 1} \cdot 3q + ... \\+ \begin{pmatrix}e_1 \\e_1 - 1\end{pmatrix}2p \cdot 3^{e_1 - 1}q^{e_1 - 1} + 3^{e_1}q^{e_1}$

Так как все слагаемые, кроме двух содержат произведение , а N = pq и $N \equiv 0 \mod N$ , все такие слагаемые в итоге сводятся к и сравнение чудесным образом упрощается

$c_1 \equiv 2^{e_1}p^{e_1} + 3^{e_1}q^{e_1} \mod N$

То же самое можно проделать со вторым сравнением

$c_2 \equiv 5^{e_2} p^{e_2} + 7^{e_2}q^{e_2} \mod N$

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

Возводим в степень

$c_1^{e_2} \equiv (2p + 3q)^{e_1} \mod N \\ c_1^{e_2} \equiv 2^{e_1e_2}p^{e_1e_2} + 3^{e_1e_2}p^{e_1e_2} \mod N$

Теперь домножаем на $2^{-e_1e_2}$

$2^{-e_1e_2}c_1^{e_2} \equiv 2^{-e_1e_2}\cdot2^{e_1e_2}p^{e_1e_2} + 2^{-e_1e_2}\cdot3^{e_1e_2}p^{e_1e_2} \mod N$

Так как $2^{-e_1e_2} \cdot 2^{e_1e_2} = 1$ , получаем

$2^{-e_1e_2}c_1^{e_2} \equiv p^{e_1e_2} + 2^{-e_1e_2} \cdot 3^{e_1e_2}p^{e_1e_2} \mod N$

Соответствующим образом преобразовываем . Т.е. возводим в степень , и домножаем на $5^{−e_1e_2}$ .

$5^{-e_1e_2}c_2^{e_1} \equiv p^{e_1e_2} + 5^{-e_1e_2} \cdot 7^{e_1e_2}q^{e_1e_2} \mod N$

А теперь из $2^{−e_1e_2}c_1^{e_2}$ вычтем $5^{−e_1e_2}c_2^{e_1}$

$2^{-e_1e_2}c_1^{e_2} - 5^{-e_1e_2}c_2^{e_1} \equiv \\ 2^{-e_1e_2}\cdot3^{e_1e_2}q^{e_1e_2} - 5^{-e_1e_2} \cdot 7^{e_1e_2}q^{e_1e_2} \mod N$

Наконец мы знаем, что , а значит $НОД(2^{-e_1e_2} c_1^{e_2}- 5^{-e_1e_2}c_2^{e_1}, N) = q$
Зная , найти не составляет труда,

Код

Теоретическое решение это хорошо, а практическое ещё лучше! С условием задачи также предоставляются реальные числа, которые нужно вычислить. Для этого я набросал небольшой скрипт на Python. Здесь я использую свою библиотеку ptCrypt, для вычисления НОД, но это тривиальный алгоритм, его можно реализовать самостоятельно.

from ptCrypt.Math.base import gcd

# Условия
N = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519

# Преобразования
c1e2 = pow(2, -e1 * e2, N) * pow(c1, e2, N)
c2e1 = pow(5, -e1 * e2, N) * pow(c2, e1, N)

# Здесь можно заметить, что я вычитаю не так, как описал в решении, а наоборот
# Это необходимо только чтобы получить решение в положительных числах
# Математика от этого никак не страдает
q = gcd(c2e1 - c1e2, N)
p = N // q

# Проверяем решение
assert(p * q == N)

print(p)
print(q)