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
Where And – prime numbers. We need to find And the 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:
Let me also remind you that
An important point in the binomial formula is that all terms, except the two extreme ones, contain the product . To understand why this is important, let’s break down the first comparison from the condition using the formula:
Since all terms except two contain the product A And all such terms ultimately reduce to and the comparison is miraculously simplified
The same can be done with the second comparison
Next we will transform expressions. Some operations may not be obvious, but eventually their meaning will become clear.
We are building to the degree
Now multiply by
Because we get
Transform accordingly . Those. raise to a power and multiply by .
And now from subtract
Finally we know that which means
Knowing find is not difficult
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)