CryptoHack. Решение Modular Binomials

в 12:15, , рубрики: cryptography, cryptohack, ctf, информационная безопасность, криптография, математика

Кто такой я?

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

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

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

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

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

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

  • выражение (a + b)^n - ничто иное как бином Ньютона, который по своей сути раскладывается в сумму произведений и в модульных вычислениях не требует какого-либо особенного отношения

  • pq=N,а N equiv 0 pmod N

  • применяя вышесказанное можно вывести формулу для вычисления p или q, а дальше воспользоваться тем, что p=N / q, а q=N / p

  • для любого числа a, такого что a < p, НОД(ap, N)=p

Погружаемся

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

(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

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

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

Так как все слагаемые, кроме двух содержат произведение pq, а N=pq и N equiv 0 mod N, все такие слагаемые в итоге сводятся к CryptoHack. Решение Modular Binomials - 23 и сравнение чудесным образом упрощается

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

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

  1. Возводим c_1 в степень e_2

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

  1. Теперь домножаем на 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

  1. Так как 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

  1. Соответствующим образом преобразовываем c_2. Т.е. возводим в степень e_1, и домножаем на 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

  1. А теперь из 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

  1. Наконец мы знаем, что q > 7, и всё выражение делится на q, а значит НОД(2^{-e_1e_2} c_1^{e_2}- 5^{-e_1e_2}c_2^{e_1}, N)=q

  2. Зная q, найти p не составляет труда, p=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)

Автор: awawa

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js