# Cryptohack: MODULAR ARITHMETIC
## Greatest Common Divisor
### Description
- Now calculate gcd(a,b) for a = 66528, b = 52920 and enter it below.
### Solution
```python
import math
print(math.gcd(66528, 52920))
```
```python
1512
```
## Extended GCD
### Description
- Using the two primes p = 26513, q = 32321, find the integers u,v such that
- ``p * u + q * v = gcd(p,q)``
- Enter whichever of ``u`` and ``v`` is the lower number as the flag.
### Solution
```python
def egcd(a, b):
if a == 0:
return b, 0, 1
else:
gcd, x, y = egcd(b % a, a)
return gcd, y - (b // a) * x, x
gcd, u, v = egcd(26513, 32321)
print(min(u, v))
```
```python
-8404
```
## Modular Arithmetic 1
### Description
- Calculate the following integers:
```
11 ≡ x mod 6
8146798528947 ≡ y mod 17
```
- The solution is the smaller of the two integers.
### Solution
```python
print(min(11 % 6, 8146798528947 % 17))
```
```python
4
```
## Modular Arithmetic 2
### Description
Lets say we pick $p = 17$. Calculate $3 ^ {17} \mod 17$. Now do the same but with $5^{17} \mod 17$.
What would you expect to get for $7^{16} \mod 17$? Try calculating that.
This interesting fact is known as Fermat's little theorem. We'll be needing this (and its generalisations) when we look at RSA cryptography.
Now take the prime $p = 65537$. Calculate $27324678765465536 \mod 65537$.
Did you need a calculator?
### Solution
```python
print(pow(273246787654, 65536, 65537))
```
```python
1
```
## Modular Inverting
### Description
- What is the inverse element: ``3 * d ≡ 1 mod 13?``
### Solution
```python
print(pow(3, -1, 13))
```
```python
9
```
## Quadratic Residues
### Description
- In the below list there are two non-quadratic residues and one quadratic residue.
- Find the quadratic residue and then calculate its square root. Of the two possible roots, submit the smaller one as the flag.
```python
p = 29
ints = [14, 6, 11]
```
### Solution
```python
p = 29
ints = [14, 6, 11]
qr = [a for a in range(p) if pow(a, 2, p) in ints]
print(min(qr))
```
```python
8
```
## Legendre Symbol
### Description
Now for the flag. Given the following 1024 bit prime and 10 integers, find the quadratic residue and then calculate its square root; the square root is your flag. Of the two possible roots, submit the larger one as your answer.
- [output.txt](https://cryptohack.org/static/challenges/output_479698cde19aaa05d9e9dfca460f5443.txt)
### Solution
```python
p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139
ints = [25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803, 45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555, 17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325, 14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863, 4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318, 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771, 50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987, 96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871, 4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721, 18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565]
quadr_res = [n for n in ints if pow(n, (p - 1) // 2, p) == 1][0]
print(pow(quadr_res, (p + 1) // 4, p))
```
```python
93291799125366706806545638475797430512104976066103610269938025709952247020061090804870186195285998727680200979853848718589126765742550855954805290253592144209552123062161458584575060939481368210688629862036958857604707468372384278049741369153506182660264876115428251983455344219194133033177700490981696141526
```
## Modular Square Root
### Description
Find the square root of $a$ modulo the 2048-bit prime $p$. Give the smaller of the two roots as your answer.
[output.txt](https://cryptohack.org/static/challenges/output_abe0beb359a950c8a0a9300897528a9d.txt)
### Solution
```python
from sympy import *
a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
print(sqrt_mod(a, p))
```
```python
2362339307683048638327773298580489298932137505520500388338271052053734747862351779647314176817953359071871560041125289919247146074907151612762640868199621186559522068338032600991311882224016021222672243139362180461232646732465848840425458257930887856583379600967761738596782877851318489355679822813155123045705285112099448146426755110160002515592418850432103641815811071548456284263507805589445073657565381850521367969675699760755310784623577076440037747681760302434924932113640061738777601194622244192758024180853916244427254065441962557282572849162772740798989647948645207349737457445440405057156897508368531939120
```
## Chinese Remainder Theorem
### Description
- In cryptography, we commonly use the Chinese Remainder Theorem to help us reduce a problem of very large integers into a set of several, easier problems.
-Given the following set of linear congruences:
```
x ≡ 2 mod 5
x ≡ 3 mod 11
x ≡ 5 mod 17
```
- Find the integer a such that ``x ≡ a mod 935``
### Solution
```python
print(crt([2, 3, 5], [5, 11, 17]) % 935)
```
```python
872
```
## Adrien's Signs
### Description
- Adrien's been looking at ways to encrypt his messages with the help of symbols and minus signs. Can you find a way to recover the flag?
[source.py](https://cryptohack.org/static/challenges/source_734d7e14251f950935f83d228f8694ab.py)
[output.txt](https://cryptohack.org/static/challenges/output_80fc6398d2fd9f272186d0af510323f9.txt)
### Solution
```python
a = 288260533169915
p = 1007621497415251
def descrypt_flag(hehe):
plaintext = []
for i in hehe:
if pow(i, (p - 1) // 2, p) == 1:
plaintext.append('1')
else:
plaintext.append('0')
plaintext = ''.join(plaintext)
reversed(plaintext)
plaintext = ''.join([chr(int(plaintext[i:i + 8], 2)) for i in range(0, len(plaintext), 8)])
return plaintext
hehe = [...]
print(descrypt_flag(hehe))
```
```python
crypto{p4tterns_1n_re5idu3s}
```
## Modular Binomials
### Description
Rearrange the following equations to get the primes `p,q`
```
N = p*q
c1 = (2*p + 3*q)**e1 mod N
c2 = (5*p + 7*q)**e2 mod N
```
[data.txt](https://cryptohack.org/static/challenges/data_04a0fe134cf31a6c941377aad75db81c.txt)
### Solution
```python
from math import gcd
n = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519
q1 = pow(c1, e2, n)
q2 = pow(c2, e1, n)
d = pow(5, e1 * e2, n) * q1 - pow(2, e1 * e2, n) * q2
q = gcd(d, n)
p = n // q
assert(p * q == n)
print(p)
print(q)
```
```python
112274000169258486390262064441991200608556376127408952701514962644340921899196091557519382763356534106376906489445103255177593594898966250176773605432765983897105047795619470659157057093771407309168345670541418772427807148039207489900810013783673957984006269120652134007689272484517805398390277308001719431273
132760587806365301971479157072031448380135765794466787456948786731168095877956875295282661565488242190731593282663694728914945967253173047324353981530949360031535707374701705328450856944598803228299967009004598984671293494375599408764139743217465012770376728876547958852025425539298410751132782632817947101601
```
Sign in with Wallet
Connect another wallet