CryptoHack. Решение Modular Binomials / forpes.ru

Главная
CryptoHack. Решение Modular Binomials

CryptoHack. Решение Modular Binomials +2

04.10.2024 12:15

awawa 2 393 Источник

Кто такой я?

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

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

Комментарии (2)

RodionGork
04.10.2024 18:23
#27378764
Плюсую статью ибо дело хорошее - но помните что говорил Стивен Хокинг - как только в книжку добавляют хоть одну формулу - её продажи падают на треть. В идеале желательно уметь подать подобный материал максимально удобоваримо, объяснить суть а формулы привести как приложение или что-то в этом духе. Понимаю что в первый момент это кажется прям как-то неосуществимо, но надо пробовать :)
1. awawa Автор
  04.10.2024 18:23
  #27380416
  Спасибо за замечание :) Коненчо, я согласен с тем, что, преследуя цели популяризации, необходимо было бы выбирать другой подход, с большим погружением в контекст области и объяснением определений. Вообще говоря, я думаю, что при написании любого текста следует держать в уме уровень осведомлённости целевого читателя материала и упрощать до терминов, ему понятных.
  
  Что касается этой статьи, то целевым читателем при её написании, я видел людей владеющих базовыми понятиями модульной арифметики и уже предпринимающих самостоятельные попытки решения подобных задач. Т.е. материал рассчитан на людей примерно моего уровня (а может и большего), но недостающих инсайта для решения конкретно этой задачи.
  
  Именно поэтому я нарочно опускаю определение кольца, не говорю об алгоритме НОД, не говорю почему я использую символы и $\equiv$ и т. п. И конечно я совершенно не касаюсь ключевой для популяризации темы - "а зачем это нужно?"