# TRAINING WCO4 #1 - Mathematics in Cryptography
## Lý thuyết
https://giapppp.notion.site/Mathematic-in-Cryptography-01a27fda51a943d2b04fbe840e5dd26b
## Bài tập CryptoHack
### Greatest Common Divisor
Đề bài yêu cầu tự code GCD( 66528, 52920 ).
#### Script giải :

def GCD( a, b ):
	if( a < b ):
		a, b = b, a
	while( b ):
		a = a % b
		a, b = b, a
	return a
a = 66528
b = 52920
print( GCD( a, b ) )

### Extended GCD
https://wiki.vnoi.info/algo/algebra/euclid
ECD cho phép ta tính được phương trình 2 ẩn a, b
$$ u * a + v * b = gcd( u, v ) $$
Đề bài yêu cầu tìm u, v với p=26513, q=32321 thỏa phương trình
$$ p⋅u+q⋅v=gcd(p,q) $$
Trả kết quả là số nhỏ hơn trong 2 số u, v.
#### Script giải :

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while( a ):
        q, r = b // a, b % a
        m, n = x - u * q, y - v * q
        b, a, x, y, u, v = a, r, u, v, m, n
    gcd = b
    return gcd, x, y
p = 26513
q = 32321
_, x, y = egcd( p, q )
print( min (x , y) )

### Modular Arithmetic 1
#### Đề :
Đây là một hệ quả của lí thuyết đồng dư
$$
a \equiv b \pmod{c} \;\Longleftrightarrow\; b \equiv a \pmod{c}
$$

#### Script giải :

x = 11 % 6
y = 8146798528947 % 17
print( min(x, y) ) 

### Modular Arithmetic 2
#### Đề :
Theo định lí Fermat nhỏ ( Little Fermat Theorem )
$$a^p \equiv a \pmod{p} $$
$$a^{p-1} \equiv 1 \pmod{p}$$
Vậy nên đáp án là 1
### Modular Inverting
#### Đề :
Áp dụng Little Fermat Theorem
$$ 3^{p-1} \equiv 1 \pmod{p}$$
Nhân 2 vế cho 3^(-1) ta được
$$3^{p-2} \equiv 3^{-1} \pmod{p} $$
Vậy d = 3^(p-2) với p = 13
### Quadratic Residues
#### Đề :
Tìm số là thặng dư bậc 2 trong danh sách ints, sau đó tìm căn bậc 2 của số đó, trả về kết quả nhỏ hơn.
Thặng dư bậc 2 ( quadratic residue ) là số q có nghiệm x thỏa
$$ x^{2} \equiv q \pmod{n}$$
Tìm số thặng dư bậc 2 bằng cách tìm từ 1 đến n, nếu tồn tại 1 nghiệm x thỏa điều kiện thì q là thặng dư bậc 2
#### Script giải :

p = 29
ints = [ 14, 6, 11 ]
root = []
for i in ints:
	for j in range(p):
		if( pow(j,2,p) == i  ):
			root.append(j)
print(min(root))

### Legendre Symbol
#### Đề :
File output :
https://cryptohack.org/static/challenges/output_479698cde19aaa05d9e9dfca460f5443.txt
Thay vì brute-force để tìm thặng dư bậc 2, ta có một cách nhanh hơn đó là Legendre, với 2 số a và p, xét
$$(a/p) = a^{(p-1)/2} \pmod{p}$$
Nếu
$$(a/p) = 1 \Rightarrow \; a \; là \; quadratic \; residue, \; a \not\equiv 0 \pmod{p}$$
$$(a/p) = -1\Rightarrow \; a \; không \; phải \; là \; quadratic \; residue $$
$$(a/p) = 0 \Rightarrow a \equiv 0 \pmod{p} $$
Ta có một tính chất khi kết hợp 2 số

Đề yêu cầu tìm thặng dư bậc 2, sau đó tìm căn của nó, trả kết quả là số lớn hơn. Đề bài giống với câu trước nhưng độ khó cao hơn khiến brute-force tốn nhiều thời gian.
Vì p = 3 mod 4 nên ta có công thức tìm căn bậc 2 nhanh
$$ x = a^{(p+1)/4} \pmod{p} $$
#### Script giải :

p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139

ints = [25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803, 45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555, 17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325, 14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863, 4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318, 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771, 50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987, 96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871, 4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721, 18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565]
quad = []
for i in ints:
    x = pow( i , (p - 1) // 2 , p )
    if( x == 1 and i % p != 0):
        quad.append(i)
        print("int: ", i)
roots = []
for num in quad:
    root = pow( num , (p + 1) // 4 , p )
    roots.append(root)
    roots.append(p - root)
print( max(roots) )

### Modular Square Root
#### Đề :
Ở bài này, p không ở dạng đặc biệt như câu trước nên ta dùng Tonelli-Shanks, điều kiện là p phải là số nguyên tố.
#### Script giải :

import math


a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
def check_quadratic_residue( a , p ):
    return pow(a, (p - 1) // 2, p) == 1
def split_QS(p:int):
    n=p-1
    np= n & -n
    S= np.bit_length() -1 
    Q=n >> S
    return Q,S

def tonelli_shanks(a, p, z):
    Q, S = split_QS(p)
    M = S
    c = pow(z, Q, p)
    t = pow(a, Q, p)
    x = pow(a, (Q + 1) // 2, p)

    if t == 0:
        return 0

    while t != 1:
        i = 0
        temp = t
        while temp != 1:
            temp = pow(temp, 2, p)
            i += 1
            if i == M:
                raise ValueError("No solution")

        b = pow(c, 1 << (M - i - 1), p)
        x = (x * b) % p
        t = (t * b * b) % p
        c = (b * b) % p
        M = i

    return x, p - x

z=2
while (z<=(p-1)):
    if pow(z,(p-1)//2,p) == p-1:
        break
    z+=1

#z=29
if( check_quadratic_residue( a, p )):
    print(min( tonelli_shanks(a,p,z)))

### chinese Remainder Theorem
#### Đề :
CRT là cách giải hệ nhiều phương trình cùng 1 ẩn,với các modul đôi một cùng nguyên tố, từ đó ta xác định được duy nhất 1 nghiệm thỏa tất cả các phương trình
#### Script giải :

def Crt(a,n):
    N = 1
    for i in n:
        N *= i
    x = 0
    for i,j in zip(a,n):
        Ni = N // j
        Yi = pow(Ni,-1,j)
        x += i * Ni * Yi
    return x % N


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

### Adrien's Symbol
#### Đề :

from random import randint

a = 288260533169915
p = 1007621497415251

FLAG = b'crypto{????????????????????}'


def encrypt_flag(flag):
    ciphertext = []
    plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag])
    for b in plaintext:
        e = randint(1, p)
        n = pow(a, e, p)
        if b == '1':
            ciphertext.append(n)
        else:
            n = -n % p
            ciphertext.append(n)
    return ciphertext


print(encrypt_flag(FLAG))

output.txt
https://pastebin.com/52UYTRZa
Bài này có đặc điểm là p = 3 mod 4, và a là một thặng dư bậc 2 ( (a|p) = 1 ).
Qua đó ta thấy với mọi số mũ e thì cũng sẽ trở thành thặng dư bậc 2.
Vậy (-a|p) = -1, không là thặng dư bậc 2.
Đề bài mã hóa từng bit của flag bằng cách: nếu bit là 1 thì thêm vào n là một số thặng dư bậc 2 mod p, nếu bit là 0 thì thêm vào -n là một số không phải thặng dư bậc 2 mod p.
Từ các điều trên ta có thể suy ra được bit là 1 hay 0 chỉ nhờ vào Legendre symbol chứ không cần suy ngược ra là n hay -n mod p.
#### Script giải :

encFlag = [67594220461269, 501237540280788, 718316769824518, 296304224247167, 48290626940198, 30829701196032, 521453693392074, 840985324383794, 770420008897119, 745131486581197, 729163531979577, 334563813238599, 289746215495432, 538664937794468, 894085795317163, 983410189487558, 863330928724430, 996272871140947, 352175210511707, 306237700811584, 631393408838583, 589243747914057, 538776819034934, 365364592128161, 454970171810424, 986711310037393, 657756453404881, 388329936724352, 90991447679370, 714742162831112, 62293519842555, 653941126489711, 448552658212336, 970169071154259, 339472870407614, 406225588145372, 205721593331090, 926225022409823, 904451547059845, 789074084078342, 886420071481685, 796827329208633, 433047156347276, 21271315846750, 719248860593631, 534059295222748, 879864647580512, 918055794962142, 635545050939893, 319549343320339, 93008646178282, 926080110625306, 385476640825005, 483740420173050, 866208659796189, 883359067574584, 913405110264883, 898864873510337, 208598541987988, 23412800024088, 911541450703474, 57446699305445, 513296484586451, 180356843554043, 756391301483653, 823695939808936, 452898981558365, 383286682802447, 381394258915860, 385482809649632, 357950424436020, 212891024562585, 906036654538589, 706766032862393, 500658491083279, 134746243085697, 240386541491998, 850341345692155, 826490944132718, 329513332018620, 41046816597282, 396581286424992, 488863267297267, 92023040998362, 529684488438507, 925328511390026, 524897846090435, 413156582909097, 840524616502482, 325719016994120, 402494835113608, 145033960690364, 43932113323388, 683561775499473, 434510534220939, 92584300328516, 763767269974656, 289837041593468, 11468527450938, 628247946152943, 8844724571683, 813851806959975, 72001988637120, 875394575395153, 70667866716476, 75304931994100, 226809172374264, 767059176444181, 45462007920789, 472607315695803, 325973946551448, 64200767729194, 534886246409921, 950408390792175, 492288777130394, 226746605380806, 944479111810431, 776057001143579, 658971626589122, 231918349590349, 699710172246548, 122457405264610, 643115611310737, 999072890586878, 203230862786955, 348112034218733, 240143417330886, 927148962961842, 661569511006072, 190334725550806, 763365444730995, 516228913786395, 846501182194443, 741210200995504, 511935604454925, 687689993302203, 631038090127480, 961606522916414, 138550017953034, 932105540686829, 215285284639233, 772628158955819, 496858298527292, 730971468815108, 896733219370353, 967083685727881, 607660822695530, 650953466617730, 133773994258132, 623283311953090, 436380836970128, 237114930094468, 115451711811481, 674593269112948, 140400921371770, 659335660634071, 536749311958781, 854645598266824, 303305169095255, 91430489108219, 573739385205188, 400604977158702, 728593782212529, 807432219147040, 893541884126828, 183964371201281, 422680633277230, 218817645778789, 313025293025224, 657253930848472, 747562211812373, 83456701182914, 470417289614736, 641146659305859, 468130225316006, 46960547227850, 875638267674897, 662661765336441, 186533085001285, 743250648436106, 451414956181714, 527954145201673, 922589993405001, 242119479617901, 865476357142231, 988987578447349, 430198555146088, 477890180119931, 844464003254807, 503374203275928, 775374254241792, 346653210679737, 789242808338116, 48503976498612, 604300186163323, 475930096252359, 860836853339514, 994513691290102, 591343659366796, 944852018048514, 82396968629164, 152776642436549, 916070996204621, 305574094667054, 981194179562189, 126174175810273, 55636640522694, 44670495393401, 74724541586529, 988608465654705, 870533906709633, 374564052429787, 486493568142979, 469485372072295, 221153171135022, 289713227465073, 952450431038075, 107298466441025, 938262809228861, 253919870663003, 835790485199226, 655456538877798, 595464842927075, 191621819564547]
flag = ""
a = 288260533169915
p = 1007621497415251
for ch in encFlag:
    if pow(ch,(p-1)//2,p)==1:
        flag += '1'
    else:
        flag += '0'
ls = [chr(int(flag[i:i+8],2)) for i in range(0,len(flag),8)]
result = ""
for i in ls:
    result += i
print( result )

### Modular Binomials
#### Đề :
data.txt
https://pastebin.com/BDX0t4Cy
Ta có dạng tổng quát
$$
c_1 = (a_1 \cdot p + b_1 \cdot q)^{e_1} \pmod{N}
$$

$$
c_2 = (a_2 \cdot p + b_2 \cdot q)^{e_2} \pmod{N}
$$

Mũ e2 cho c1, và e1 cho c2 để 2 vế bên phải đều có mũ e1e2.
$$
c_1^{e_2} = (a_1 * p + b_1 * q)^{\,e_1 e_2} \pmod{N}
$$

$$
c_1^{e_2} = (a_1 * p)^{\,e_1 e_2} + (b_1 * q)^{\,e_1 e_2} \pmod{N}
$$

$$
a_1^{-e_1 e_2} * c_1^{e_2} = a_1^{-e_1 e_2} * (a_1 * p)^{\,e_1 e_2} + a_1^{-e_1 e_2} * (b_1 * q)^{\,e_1 e_2} \pmod{N}
$$

$$
a_1^{-e_1 e_2} * c_1^{e_2} = p^{\,e_1 e_2} + a_1^{-e_1 e_2} * (b_1 * q)^{\,e_1 e_2}
\pmod{N}
$$
Và
$$
c_2^{e_1} = (a_2 * p + b_2 * q)^{\,e_2 e_1} \pmod{N}
$$

$$
c_2^{e_1} = (a_2 * p)^{\,e_2 e_1} + (b_2 * q)^{\,e_2 e_1} \pmod{N}
$$

$$
a_2^{-e_2 e_1} * c_2^{e_1}= a_2^{-e_2 e_1} * (a_2 * p)^{\,e_2 e_1}+ a_2^{-e_2 e_1} * (b_2 * q)^{\,e_2 e_1}
\pmod{N}
$$

$$
a_2^{-e_2 e_1} * c_2^{e_1}= p^{\,e_2 e_1}+ a_2^{-e_2 e_1} * (b_2 * q)^{\,e_2 e_1}
\pmod{N}
$$

Trừ 2 vế với nhau

$$
a_2^{-e_2 e_1} * c_2^{e_1} \;-\;a_1^{-e_1 e_2} * c_1^{e_2}=p^{\,e_2 e_1}+ a_2^{-e_2 e_1} * (b_2 * q)^{\,e_2 e_1}- p^{\,e_1 e_2}- a_1^{-e_1 e_2} * (b_1 * q)^{\,e_1 e_2}\pmod{N}
$$
$$
=a_2^{-e_2 e_1} * (b_2 * q)^{\,e_2 e_1}\;-\;a_1^{-e_1 e_2} * (b_1 * q)^{\,e_1 e_2}\pmod{N}
$$
Gọi
$$
A =a_2^{-e_2 e_1} * c_2^{e_1} \;-\;a_1^{-e_1 e_2} * c_1^{e_2}
$$
$$ \Rightarrow A =a_2^{-e_2 e_1}\; * \;(b_2 * q)^{\,e_2 e_1}\;-\;a_1^{-e_1 e_2}\; * \;(b_1 * q)^{\,e_1 e_2}\pmod{N} $$
$$ = q^{\,e_1 e_2}\; * \;(\; a_2^{-e_2 e_1}\;*\;b_2^{\,e_1 e_2} \; - \; a_1^{-e_1 e_2}\;*\;b_1^{\,e_1 e_2} ) \pmod{N}$$
Xét lần lượt trên GF( p ) và GF( q )
Vì
$$ q^{\,e_1 e_2} = 0 \pmod{q }$$
$$ \Rightarrow A = 0 \pmod{q} $$
mà $$ N = \pmod{q} $$
Nên **q là ước chung của N và A**
Tương tự với GF( p )
Vì q và p là 2 số cùng nguyên tố ( coprime ) nên GCD( p, q ) = 1, mà A = 0 ( mod q )
$$ \Rightarrow A \not= 0 \pmod{p} $$
Vậy **p không phải là ước chung của N và A**
**Suy ra q là ước chung lớn nhất của N và A**
Từ đó ta tìm được q, p = N // q.
#### Script giải :

from math import gcd
n = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519
a1, b1, a2, b2 = 2, 3, 5, 7
q = gcd(pow(a2,(-e2 * e1),n) * pow(c2, e1, n) - pow(a1, (-e1 * e2), n) * pow(c1, e2, n), n)
p = n // q
print( p )
print( q )

### Lo-Hi card
#### Đề :

from functools import total_ordering
from Crypto.Random import random
from utils import listener

FLAG = 'crypto{?????????????????????????????}'
VALUES = ['Ace', 'Two', 'Three', 'Four', 'Five', 'Six',
          'Seven', 'Eight', 'Nine', 'Ten', 'Jack', 'Queen', 'King']
SUITS = ['Clubs', 'Hearts', 'Diamonds', 'Spades']


class RNG:
    mul = random.getrandbits(60)
    inc = random.getrandbits(60)
    mod = 2**61 - 1  # 9th mersenne prime

    def __init__(self, seed):
        self.state = seed

    def next(self):
        self.state = (self.state * self.mul + self.inc) % self.mod
        return self.state


@total_ordering
class Card:
    def __init__(self, value, suit):
        self.value = value
        self.suit = suit

    def __str__(self):
        return f"{self.value} of {self.suit}"

    def __eq__(self, other):
        return self.value == other.value

    def __gt__(self, other):
        return VALUES.index(self.value) > VALUES.index(other.value)


class Game:
    def __init__(self):
        self.rng = RNG(random.getrandbits(60))
        self.deck = [Card(value, suit) for suit in SUITS for value in VALUES]
        self.num_deals = self.shuffle()

    def rebase(self, n, b=52):
        if n < b:
            return [n]
        else:
            return [n % b] + self.rebase(n//b, b)

    def shuffle(self):
        self.deals = self.rebase(self.rng.next())
        return len(self.deals)

    def deal_card(self):
        index = self.deals.pop()
        if self.deals == []:
            self.num_deals = self.shuffle()

        return self.deck[index]


class Challenge():
    def __init__(self):
        self.no_prompt = True
        self.game = Game()
        self.funds = 20
        self.dollars = self.funds
        self.round = 0
        self.hidden = self.game.deal_card()

    def play_round(self, msg=None):
        self.round += 1
        self.hand = self.hidden # move last round's hidden card to player's hand
        self.hidden = self.game.deal_card() # deal new hidden card
        self.shuffle_msg = ""
        if self.game.num_deals: # dealer shuffled deck
            self.shuffle_msg = f"I will reshuffle the deck after {self.game.num_deals} rounds. "
            self.game.num_deals = None

        if self.round == 1:
            msg = f"Welcome to my virtual casino! You are sitting down for a game of lo-hi. {self.shuffle_msg}Your hand is the {self.hand}. Lower or higher?"
            self.shuffle_msg = ""

        return {
            "round": self.round,
            "$": self.dollars,
            "hand": str(self.hand),
            "msg": msg
        }

    def win(self):
        self.dollars += 1
        msg = f"Correct! Hidden card was {self.hidden}. {self.shuffle_msg}Lower or higher?"
        return self.play_round(msg)

    def lose(self):
        self.dollars -= 2 # house edge
        msg = f"Incorrect! Hidden card was {self.hidden}. {self.shuffle_msg}Lower or higher?"
        return self.play_round(msg)

    def challenge(self, your_input):
        if self.round == 0:
            return self.play_round()

        elif self.dollars <= 0:
            self.exit = True
            return {"error": "You're broke!"}

        elif self.round == 200:
            self.exit = True
            if self.dollars >= 130:
                return {"msg": f"You pulled a 21! Here's a flag: {FLAG}"}
            elif self.dollars > self.funds:
                return {"msg": f"Nice, you beat the house!"}
            else:
                return {"msg": f"Aww, have a free drink!"}

        elif not 'choice' in your_input:
            self.exit = True
            return {"error": "You must make a choice"}

        else:
            if self.hidden == self.hand:
                return self.lose() # house edge

            choice = your_input['choice']
            if choice.lower().startswith('l'):
                if self.hidden < self.hand:
                    return self.win()
                else:
                    return self.lose()
            elif choice.lower().startswith('h'):
                if self.hidden > self.hand:
                    return self.win()
                else:
                    return self.lose()
            else:
                self.exit = True
                return {"error": "Invalid input"}


import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
listener.start_server(port=13383)

Tóm tắt đề: Đây là 1 trò chơi dự đoán giá trị lá bài hidden và chọn "higher" hoặc "lower", nếu hidden có giá trị lớn hơn hand ( lá bài đang ở tay ) thì là "higher", ngược lại là "lower", nếu bằng là house edge.
Đoán đúng +1 dollar, sai -2 dollars, house edge -2 dollards.
Mỗi lần sẽ có 1 deck bài được bốc dần, khi hết deck sẽ tráo lại bộ bài và lấy một deck khác.
Mỗi deck có khoảng 10 - 11 lá bài ( log256(2^61) ~ 10 - 11 ).
Điều kiện để thắng là chơi hết 200 ván và số tiền kiếm được trên 130 dollards.
#### Phân tích :
Đề có 1 điểm đặc biệt là sau khi biết được kết quả, đề luôn cho biết lá hidden là gì và lá hand tiếp theo của mình luôn là lá hidden của vòng trước.
Để ý ở class Game, khi bắt đầu sẽ gọi class RNG random với seed dài 60 bit, gọi hàm shuffle 1 lần để lấy số lượng bài trong deck đầu. Hàm rebase là hàm biến 1 số từ hệ 10 sang hệ cơ số 52. Hàm deal_card trả về lá bài từ deck, nếu deck đó hết bài thì shuffle để đổi lại deck khác.
Trong class RNG có hàm next liên quan mật thiết với class Game. State lúc đầu là seed, sau đó được tinh theo công thức
$$ state = (state * mul + inc )\; \% \; mod $$
Tức là nếu ta biết được vài state thì có thể xây dựng lại công thức để tạo lại mul và inc, cuối cùng là seed. Khi biết seed thì toàn bộ game đã bị phá. Ta có thể đọc trước các kết quả để tính toán và gửi đi.
Gọi X1, X2, X3 lần lượt là 3 state đầu.
Công thức xây lại seed
$$ X3 - X2 = mul * (X2-X1)\; \% \;mod$$
$$ \Rightarrow mul = (X3-X2)*(X2-X1)^{-1} \; \% \; mod$$
$$inc = (X3-X2*mul) \; \% \; mod$$
$$seed = (X1-inc)*mul^{-1} \; \% \; mod $$
Sau khi tìm seed thì chạy game local và đọc kết quả, sau đó gửi cho sv
#### Script giải :

from pwn import *
import re
import json
HOST = "socket.cryptohack.org"
PORT =  13383
r = remote( HOST , PORT )

def recv_json():
    return json.loads(r.recvline().decode())
def send_json(msg):
    data = json.dumps(msg)          
    r.sendline(data.encode())       
receive = recv_json()
money = receive["$"]
hand = receive["hand"]
msg = receive["msg"]  

m = re.search(r"after (\d+) rounds", msg)
if m:
    num_deals = int(m.group(1))
class Card:
    def __init__(self, value, suit):
        self.value = value
        self.suit = suit

    def __str__(self):
        return f"{self.value} of {self.suit}"

    def __eq__(self, other):
        return self.value == other.value

    def __gt__(self, other):
        return VALUES.index(self.value) > VALUES.index(other.value)
VALUES = ['Ace', 'Two', 'Three', 'Four', 'Five', 'Six',
          'Seven', 'Eight', 'Nine', 'Ten', 'Jack', 'Queen', 'King']
SUITS = ['Clubs', 'Hearts', 'Diamonds', 'Spades']
deck = [Card(value, suit) for suit in SUITS for value in VALUES]
def value_index_from_name( name ) :
    value_str, _, _ = name.partition(" of ")
    return VALUES.index(value_str)

def choose( hand ):
        value = value_index_from_name( hand )
        if( value > 6 ):
            return "lower"
        else:
            return "higher"
def index_from_name( name ) :
    value_str, _, suit_str = name.partition(" of ")
    v = VALUES.index(value_str)
    s = SUITS.index(suit_str)
    return s * 13 + v

mapping = [[] for _ in range(3)]
for i in range(3 * num_deals):

    idx = index_from_name(hand)
    print( idx, hand)
    mapping[ i // num_deals ].append(idx)

    choice = choose(hand)
    send_json({"choice": choice})

    receive = recv_json()
    money = receive["$"]
    hand = receive["hand"]
    msg = receive["msg"]

mod = 2**61 - 1

def reconstruct_state( digits ):
    s = 0
    k = len( digits )
    for i in range(k):
        s = (s + digits[k - 1 - i] * pow(52, i, mod)) % mod
    return s

states = []
for deck_idx in range(3):
    st = reconstruct_state(mapping[deck_idx])
    states.append(st)
mul = (states[2] - states[1]) * pow(states[1] - states[0], -1, mod) % mod
inc = (states[1] - mul * states[0]) % mod
seed = (states[0] - inc) * pow(mul, -1, mod) % mod
class RNG:
    def __init__(self, seed, mul, inc, mod):
        self.state = seed
        self.mul = mul
        self.inc = inc
        self.mod = mod

    def next(self):
        self.state = (self.state * self.mul + self.inc) % self.mod
        return self.state

class Game:
    def __init__(self, seed, mul, inc, mod):
        self.rng = RNG(seed, mul, inc, mod)
        self.deck = [Card(value, suit) for suit in SUITS for value in VALUES]
        self.num_deals = self.shuffle()

    def rebase(self, n, b=52):
        if n < b:
            return [n]
        else:
            return [n % b] + self.rebase(n//b, b)

    def shuffle(self):
        self.deals = self.rebase(self.rng.next())
        return len(self.deals)

    def deal_card(self):
        index = self.deals.pop()
        if self.deals == []:
            self.num_deals = self.shuffle()
        return self.deck[index]             
game = Game(seed, mul, inc, mod)
send = []
for i in range( 201 ):
    name = game.deal_card()
    if( i == 0 ):
        send.append("higher")
        last = value_index_from_name( str(name) )
        continue
    value = value_index_from_name( str(name) )
    if( value > last ):
        send.append("higher")
    else:
        send.append("lower")
    last = value
for i in range( 3 * num_deals + 1, 201 ):
    send_json({"choice": send[i]})
    print(recv_json())

### ASCII
#### Script giải :

m = [99, 114, 121, 112, 116, 111, 123, 65, 83, 67, 73, 73, 95, 112, 114, 49, 110, 116, 52, 98, 108, 51, 125]
for i in m:
	print(chr(i), end="")

### Hex
#### Script giải :

ct = "63727970746f7b596f755f77696c6c5f62655f776f726b696e675f776974685f6865785f737472696e67735f615f6c6f747d"
print(bytes.fromhex(ct).decode())

### Base64
#### Script giải :

import base64

ct = "72bca9b68fc16ac7beeb8f849dca1d8a783e8acf9679bf9269f7bf"
ct = bytes.fromhex( ct )
print( base64.b64encode( ct ).decode())

### Bytes and Big Integers
#### Đề :

#!/usr/bin/env python3

from Crypto.Util.number import bytes_to_long, long_to_bytes
from utils import listener # this is cryptohack's server-side module and not part of python
import base64
import codecs
import random

FLAG = "crypto{????????????????????}"
ENCODINGS = [
    "base64",
    "hex",
    "rot13",
    "bigint",
    "utf-8",
]
with open('/usr/share/dict/words') as f:
    WORDS = [line.strip().replace("'", "") for line in f.readlines()]


class Challenge():
    def __init__(self):
        self.no_prompt = True # Immediately send data from the server without waiting for user input
        self.challenge_words = ""
        self.stage = 0

    def create_level(self):
        self.stage += 1
        self.challenge_words = "_".join(random.choices(WORDS, k=3))
        encoding = random.choice(ENCODINGS)

        if encoding == "base64":
            encoded = base64.b64encode(self.challenge_words.encode()).decode() # wow so encode
        elif encoding == "hex":
            encoded = self.challenge_words.encode().hex()
        elif encoding == "rot13":
            encoded = codecs.encode(self.challenge_words, 'rot_13')
        elif encoding == "bigint":
            encoded = hex(bytes_to_long(self.challenge_words.encode()))
        elif encoding == "utf-8":
            encoded = [ord(b) for b in self.challenge_words]

        return {"type": encoding, "encoded": encoded}

    #
    # This challenge function is called on your input, which must be JSON
    # encoded
    #
    def challenge(self, your_input):
        if self.stage == 0:
            return self.create_level()
        elif self.stage == 100:
            self.exit = True
            return {"flag": FLAG}

        if self.challenge_words == your_input["decoded"]:
            return self.create_level()

        return {"error": "Decoding fail"}


import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
listener.start_server(port=13377)

Chỉ cần sử dụng pwntool để đọc type và encode, sau đó decode theo từng loại và đưa ra đúng chuỗi sau khi decode theo từng type
#### Script giải :

from pwn import * # pip install pwntools
import json
import base64
from Crypto.Util.number import long_to_bytes
import codecs

r = remote('socket.cryptohack.org', 13377, level = 'debug')

def json_recv():
    line = r.recvline()
    return json.loads(line.decode())

def json_send(hsh):
    request = json.dumps(hsh).encode()
    r.sendline(request)
def decoded( ct, type ):
    if( type == "base64"):
        return base64.b64decode( ct ).decode()
    elif( type == "hex" ):
        return bytes.fromhex( ct ).decode()
    elif( type == "rot13" ):
        return codecs.decode( ct, 'rot_13' )
    elif( type == "bigint" ):
        ct = int( ct, 16 )
        return long_to_bytes( ct ).decode()
    elif( type == "utf-8" ):
        pt = ""
        for i in ct:
            pt += chr(i)
        return pt
for i in range(100):
    received = json_recv()
    type = received["type"]
    encoded = received["encoded"]
    print("Received type: ")
    print(type)
    print("Received encoded value: ")
    print(encoded)
    pt = decoded( encoded , type )
    to_send = {
        "decoded":pt 
    }
    json_send(to_send)

print( json_recv() )

### XOR Starter
#### Script giải :

def xor(a, b):
    return "".join(chr(ord(x) ^ ord(y)) for x, y in zip(a, b))
string = "label"
pt = ""
for i in string:
    pt += xor( i, chr(13) )
print( pt )

### XOR Properties
#### Đề :

Dựa theo tính chất Commutative và Associative để giải


#### Script giải :

def xor(a, b):
    return bytes([x ^ y for x, y in zip(a, b)])
KEY1 = "a6c8b6733c9b22de7bc0253266a3867df55acde8635e19c73313"
KEY21 = "37dcb292030faa90d07eec17e3b1c6d8daf94c35d4c9191a5e1e"
KEY23 = "c1545756687e7573db23aa1c3452a098b71a7fbf0fddddde5fc1"
FLAG123 = "04ee9855208a2cd59091d04767ae47963170d1660df7f56f5faf"

key1 = bytes.fromhex( KEY1 )
key2 = xor( key1 , bytes.fromhex( KEY21 ))
key3 = xor( key2 , bytes.fromhex( KEY23 ))
flag = xor( bytes.fromhex( FLAG123 ), xor( key1, xor( key2, key3 ) ) )
print( flag.decode() )

### Favourite byte
#### Đề :
Ta chỉ cần xor string đề cho với từng byte từ 0 - 256, nếu có chuỗi "crypto" trong đó thì in ra.
#### Script giải :

def xor( a, b ):
    return bytes([ x ^ y for x, y in zip( a, b )])
ct = "73626960647f6b206821204f21254f7d694f7624662065622127234f726927756d"
ct = bytes.fromhex( ct )
for i in range( 256 ):
    pt = b""
    for char in ct :
        pt += xor( bytes([ char ]), bytes([ i ]) )
    if( b"crypto" in pt ):
        print( pt.decode() )
        break

### You either know, XOR you don't
#### Đề :

Biết được format của flag bắt đầu là "crypto{", ta có thể tìm được đoạn key đầu bằng cách xor đoạn flag đã biết với ciphertext, được kết quả là "myXORke", đoán vội key là "myXORkey". Từ đó xor cho đến hết đoạn ciphertext
#### Scrip giải :

def xor( a, b ):
    return bytes([ x ^ y for x, y in zip( a, b )])
ct = "0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104"
ct = bytes.fromhex( ct )

known = b"crypto{"

key = xor( known, ct )
print( key )
key = b"myXORkey"
pt = b"".join( xor( key, ct[ i: i + len(key) ]) for i in range(0, len( ct ), len( key )) )
print(pt.decode())

### Lemur XOR
#### Đề :
lemur.png
https://cryptohack.org/static/challenges/lemur_ed66878c338e662d3473f0d98eedbd0d.png
flag.png
https://cryptohack.org/static/challenges/flag_7ae18c704272532658c10b5faad06d74.png

Xor 2 ảnh lại với nhau theo RGB bytes, sau đó tạo thành 1 ảnh mới.

from PIL import Image

def xor_images(img1_path, img2_path, out_path):
    img1 = Image.open(img1_path).convert("RGB")
    img2 = Image.open(img2_path).convert("RGB")

    w, h = img1.size
    px1 = img1.load()
    px2 = img2.load()

    out = Image.new("RGB", (w, h))
    px_out = out.load()

    for x in range(w):
        for y in range(h):
            r1, g1, b1 = px1[x, y]
            r2, g2, b2 = px2[x, y]

            px_out[x, y] = (
                r1 ^ r2,
                g1 ^ g2,
                b1 ^ b2
            )
    out.save(out_path)
    print(f"Saved XOR image -> {out_path}")
xor_images( "flag.png", "lemur.png", "solve.png" )

### Privacy-Enhanced Mail?
#### Đề :
file .pem
https://cryptohack.org/static/challenges/privacy_enhanced_mail_1f696c053d76a78c2c531bb013a92d4a.pem
#### Script giải :

from Crypto.PublicKey import RSA
with open("privacy.pem", "rb") as f:
    key = RSA.import_key(f.read())
print( key.d )

### CERTainly not
#### Đề :
file.der
https://cryptohack.org/static/challenges/2048b-rsa-example-cert_3220bd92e30015fe4fbeb84a755e7ca5.der
Chạy lênh openssl để đọc modul từ file, sau đó chuyển sang int

# openssl x509 -inform DER -in 2048b-rsa-example-cert.der -modulus -noout
n = "B4CFD15E3329EC0BCFAE76F5FE2DC899C67879B918F80BD4BAB4D79E02520609F418934CD470D142A0291392735077F60489AC032CD6F106ABAD6CC0D9D5A6ABCACD5AD2562651E54B088AAFCC190F253490B02A29410F55F16B93DB9DB3CCDCECEBC75518D74225DE49351432929C1EC669E33CFBF49AF8FB8BC5E01B7EFD4F25BA3FE596579A2479491727D7894B6A2E0D8751D9233D068556F858310EEE81997868CD6E447EC9DA8C5A7B1CBF24402948D1039CEFDCAE2A5DF8F76AC7E9BCC5B059F695FC16CBD89CEDC3FC129093785A75B45683FAFC4184F6647934351CAC7A850E73787201E72489259EDA7F65BCAF8793198CDB7515B6E030C708F859"
print( int( n, 16 ))

### SSH Keys
### Big - CryptoCTF 2023
#### Đề :

#!/usr/bin/env sage

from Crypto.Util.number import *
from hashlib import sha512
from flag import flag

def genkey(nbit):
	while True:
		p = getPrime(nbit)
		if p % 4 == 3:
			q = int(str(p)[::-1])
			if isPrime(q):
				return p * q, (p, q)

def setup(msg, pkey):
	hid = sha512(msg).digest()
	while True:
		a = bytes_to_long(hid)
		if kronecker(a, pkey) == 1:
			return a
		else:
			hid = sha512(hid).digest()

def encrypt(msg, pkey):
	a, m = setup(msg, pkey), bytes_to_long(msg)
	B, C = bin(m)[2:], []
	for b in B:
		while True:
			t = randint(1, pkey)
			if kronecker(t, pkey) == 2 * int(b) - 1:
				C.append((t - a * inverse(t, pkey)) % pkey)
				break
	return (a, C)


pkey, privkey = genkey(512)
E = encrypt(flag, pkey)

print(f'pkey = {pkey}')
print(f'E = {E}')

output.txt
https://pastebin.com/pbA1SyDL
#### Phân tích :
Hàm genkey tạo một p là số nguyên tố 522 bit, đảm bảo p mod 4 = 3, tạo một q là số đảo của p, đảm bảo q cũng là số nguyên tố.
Hàm setup tạo một biến hid là giá trị băm sha256 của msg, chuyển thành số nguyên a, đảm bảo kronecker của a với pkey bằng 1.
Hàm quan trọng nhất là encrypt, tạo biến a theo hàm setup, m là bytes của flag, B là chuỗi bit của flag, và mảng C trống. Xét từng bit của m, tạo giá trị t ngẫu nhiên từ 1 đến pkey, đảm bảo kronecker( t, pkey ) = 2 * int( bit ) - 1. Sau đó thêm vào C một giá trị theo công thức
$$c=t-a*t^{-1} \pmod{pkey}$$
Xét phần đảm bảo của hàm encrypt: kronecker( t, pkey ) = 2 * int( bit ) - 1, nếu bit = 1 thì kronecker( t, pkey ) = 1, nếu bit = 0 thì kronecker( t, pkey ) = -1
Công thức trên có thể biến đổi
$$ c*t = t^2-a \pmod{pkey}$$
$$t^2-c*t-a = 0 \pmod{pkey}$$
Vậy ta được phương trình bậc 2 theo ẩn t
$$\Rightarrow t=(c \pm \sqrt{c^2+4*a})/2 \pmod{pkey}$$
Ta có thể tách modul pkey ra thành 2 modul p và q, sau đó gộp lại tính Crt để tìm t.
Từ t có thể tìm lại từng bit của flag bằng cách kiểm tra lại kronecker( t, pkey )
Về phần tính căn bậc 2, vì p được đảm bảo p = 3 mod 4 nên ta dùng công thức
$$ x = a^{(p+1)/4} \pmod{p}$$
Với x là căn bậc 2 của a
Còn q không chắc chắn sẽ có dạng mod 4 = 3 nên dùng tonelli shanks.
#### Script giải :
https://pastebin.com/ZnPyaeuf
> Flag : CCTF{_Cocks_18e_5chEm3}
>