CryptoHack Mathematics Write-up

CTF write-up Crypto
Crypto
Publish Date:   2022-05-10
Word Count:   1.1k
Read Times:   6 Min
Read Count:  
作者: Gunjyo

Modular Math

Quadratic Residues

We say that an integer x is a Quadratic Residue if there exists an a such that a2 = x mod p.
If there is no such solution, then the integer is a Quadratic Non-Residue.

If a^2 = x then (-a)^2 = x. So if x is a quadratic residue in some finite field, then there are always two solutions for a.

We can start with a = 1 and loop to a = p-1 to see if a^2 == x (mod p).
In this discussion p isn’t too large and we can quickly look.

p = 29
ints = [14, 6, 11]

for i in ints:
    for a in range(1,p-1):
        if(i == pow(a,2,p)):
            print(i,a)

Ans 8

Legendre Symbol

The Legendre Symbol gives an efficient way to determine whether an integer is a quadratic residue modulo an odd prime p.

An interesting property of quadratic (non-)residues.

  • Quadratic Residue * Quadratic Residue = Quadratic Residue
  • Quadratic Residue * Quadratic Non-residue = Quadratic Non-residue
  • Quadratic Non-residue * Quadratic Non-residue = Quadratic Residue
    (We can consider Quadratic Residue as 1 and Quadratic Non-residue as -1)

Legendre’s Symbol: (a / p) ≡ a(p-1)/2 mod p obeys:

  • (a / p) = 1 if a is a quadratic residue and a != 0 mod p
  • (a / p) = -1 if a is a quadratic non-residue mod p
  • (a / p) = 0 if a ≡ 0 mod p

Which means given any integer a, calculating pow(a,(p-1)/2,p) is enough to determine if a is a quadratic residue.

After we find the integer that is a quadratic residue, we can use Fermat’s little theorem to figure out the square root.
Reference

p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139
ints = [25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803, 45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555, 17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325, 14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863, 4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318, 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771, 50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987, 96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871, 4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721, 18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565]
y = -1
for a in ints:
    if pow(a,(p-1)//2,p) == 1:
        y = a
print(y)
x = pow(y,(p+1)//4,p)
print(x)

Ans: 

93291799125366706806545638475797430512104976066103610269938025709952247020061090804870186195285998727680200979853848718589126765742550855954805290253592144209552123062161458584575060939481368210688629862036958857604707468372384278049741369153506182660264876115428251983455344219194133033177700490981696141526

Modular Square Root

There are algorithms for efficiently calculating such roots.
The best one in practice is called Tonelli-Shanks

All primes that aren’t 2 are of the form p ≡ 1 mod 4 or p ≡ 3 mod 4, since all odd numbers obey these congruences.
In the p ≡ 3 mod 4 case, a really simple formula for computing square roots can be derived directly from Fermat’s little theorem.

That leaves us still with the p ≡ 1 mod 4 case, so a more general algorithm is required.
In a congruence of the form r2 ≡ a mod p, Tonelli-Shanks calculates r.
Reference of Tonelli-Shanks algorithm implement

def Legendre(n,p): # make sure n is quadratic residues (modp)
    return pow(n,(p - 1) // 2,p)
def Tonelli_Shanks(n,p):
    assert Legendre(n,p) == 1
    if p % 4 == 3:
        return pow(n,(p + 1) // 4,p)
    q = p - 1
    s = 0
    while q % 2 == 0:
        q = q // 2
        s += 1
    for z in range(2,p):
        if Legendre(z,p) == p - 1:
            c = pow(z,q,p)
            break
    r = pow(n,(q + 1) // 2,p)
    t = pow(n,q,p)
    m = s
    if t % p == 1:
        return r
    else:
        i = 0
        while t % p != 1: # outer loop 
            temp = pow(t,2**(i+1),p) # i+1 is to make sure i(used in inner loop) is equal to i+1(here)
            i += 1
            if temp % p == 1: # inner loop
                b = pow(c,2**(m - i - 1),p)
                r = r * b % p
                c = b * b % p
                t = t * c % p
                m = i
                i = 0 # to notice that i have to reset after inner loop
        return r

a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161

print(Tonelli_Shanks(a,p))

Ans

2362339307683048638327773298580489298932137505520500388338271052053734747862351779647314176817953359071871560041125289919247146074907151612762640868199621186559522068338032600991311882224016021222672243139362180461232646732465848840425458257930887856583379600967761738596782877851318489355679822813155123045705285112099448146426755110160002515592418850432103641815811071548456284263507805589445073657565381850521367969675699760755310784623577076440037747681760302434924932113640061738777601194622244192758024180853916244427254065441962557282572849162772740798989647948645207349737457445440405057156897508368531939120

Chinese Remainder Theorem

The Chinese Remainder Theorem gives a unique solution to a set of linear congruences if their moduli are coprime.
This means, that given a set of arbitrary integers ai, and pairwise coprime integers ni, such that the following linear congruences hold:

x ≡ a1 mod n1
x ≡ a2 mod n2
...
x ≡ an mod nn

There is a unique solution x ≡ a mod N where N = n1 * n2 * ... * nn.

Sol1

import gmpy2, libnum
from functools import reduce

def CRT(r, mod):
    M = reduce(lambda x,y:x*y, mod)

    ans = 0
    
    for i in range(len(r)):
        m = M // mod[i]
        ans += r[i] * m * gmpy2.invert(m, mod[i])
    
    return ans % M

a = [2,3,5]
n = [5,11,17]
print(CRT(a,n))

Sol2

We can directly use crt() in sympy

from sympy.ntheory.modular import crt
a = [2,3,5]
n = [5,11,17]
print(crt(n,a))

Ans 872

Lattices

Vectors

Given a three dimensional vector space defined over the reals, where v = (2,6,3), w = (1,0,0) and u = (7,7,2), calculate 3*(2*v - w) ∙ 2*u.

basic vector arithmetic.
3*(2*v - w) ∙ 2*u = (9,36,18) ∙ (14,14,4) = 45*14 + 18*4 = 702

Size and Basis

Given the vector v = (4, 6, 2, 5), calculate its size.

basic vector arithmetic.
(4^2 + 6^2 + 2^2 + 5^2)^(1/2) = 9

Gram Schmidt

Algorithm for Gram-Schmidt
u1 = v1
Loop i = 2,3…,n
Compute μij = vi ∙ uj / ||uj||2, 1 ≤ j < i.
Set ui = vi - μij * uj (Sum over j for 1 ≤ j < i)
End Loop

Author: Gunjyo
Link: https://gunjyo0817.github.io/2022/05/10/CryptoHack-Mathematics-Write-up/
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint policy. If reproduced, please indicate source Gunjyo !
CTF write-up Crypto
  TOC