CryptoHack. Решение Modular Binomials

Кто такой я?

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

Привет! Меня зовут Александр и большую часть своего времени я занимаюсь разработкой ПО в общем, а разработкой под 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 нас не интересует в том смысле, что расшифровывать ничего не нужно и в целом знание алгоритма для решения не пригодится.

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

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

выражение — ничто иное как бином Ньютона, который по своей сути раскладывается в сумму произведений и в модульных вычислениях не требует какого-либо особенного отношения
,а $N \equiv 0 \pmod N$
применяя вышесказанное можно вывести формулу для вычисления или , а дальше воспользоваться тем, что , а
для любого числа , такого что ,

Погружаемся

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

$(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 \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_1e_2} \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} \equiv 1 \mod N$ , получаем

$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)

ссылка на оригинал статьи https://habr.com/ru/articles/848252/