CryptoHack. Modular Binomials Solution

Who am I?

Hidden text

Hello! My name is Alexander and most of my time I do software development in general, and Android development professionally.

But it so happened that I received an education in the specialty “Information Security” and in 6 years I managed to become significantly interested in this topic, and to a greater extent in cryptography and its mathematical foundations.

My other articles on this topic can also be found in English on my page in Mediumperhaps their translations will appear here in the future.

What is CryptoHack?

The creators of the service themselves can answer this question better than me, for which I send to FAQ. However, in a nutshell, CryptoHack is a service that allows you (albeit superficially) to study modern cryptography and the mathematics behind it. But the shortcomings of the theoretical part are sufficiently covered by a large set of practical problems, many of which require deep mathematical knowledge (but not at the level of a doctor of science, of course).

Task

The formulation of the problem that we will consider today is as simple as possible. Equations given

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

Where p And q – prime numbers. We need to find p And qthe remaining meanings are known to us.

For those familiar with RSA, this looks suspiciously similar, but RSA itself does not interest us in the sense that nothing needs to be decrypted and, in general, knowledge of the algorithm is not useful for the solution.

Give the man a fishing rod

But before I move on to the solution, I suggest that the reader, without looking at the next section, deduce it for himself using a few hints:

Let's dive in

Well, now let’s figure out together what’s going on here. First, let's remember Newton's binomial formula:

(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

Let me also remind you that

\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

An important point in the binomial formula is that all terms, except the two extreme ones, contain the product ab. To understand why this is important, let’s break down the first comparison from the condition using the formula:

(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}

Since all terms except two contain the product pqA N = pq And N\equiv 0\mod Nall such terms ultimately reduce to 0 and the comparison is miraculously simplified

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

The same can be done with the second comparison

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

Next we will transform expressions. Some operations may not be obvious, but eventually their meaning will become clear.

  1. We are building c_1 to the degree 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. Now multiply by 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. Because 2^{-e_1e_2} \cdot 2^{e_1e_2} = 1we get

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. Transform accordingly c_2. Those. raise to a power e_1and multiply by 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. And now from 2^{−e_1e_2}c_1^{e_2} subtract 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. Finally we know that q > 7″ src=”https://habrastorage.org/getpro/habr/upload_files/b23/3cf/e8c/b233cfe8ccf2ed4be5915b94c124f877.svg” width=”45″ height=”20″/>and the entire expression is divided by <img data-lazyloaded=which means GCD(2^{-e_1e_2} c_1^{e_2}- 5^{-e_1e_2}c_2^{e_1}, N) = q

  2. Knowing qfind p is not difficult p = N/q

Code

The theoretical solution is good, but the practical one is even better! The problem statement also provides the actual numbers to be calculated. To do this, I wrote a small Python script. Here I use my ptCrypt library to calculate GCD, but this is a trivial algorithm, you can implement it yourself.

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)

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *