# Cryptography UIT Week 1
## CryptoHack Modular Arithmatic

### Greatest Common Divisor

Bài này yêu cầu ta tìm ước chung lớn nhất của 2 số nguyên. Theo gợi ý của đề bài ta sẽ áp dụng thuật toán Euclid để giải quyết.

def gcd(a,b):
    if a==0:
        return b
    return gcd(b%a,b)
print(gcd(66528,52920))

**Câu hỏi phụ**: "Think about the case for a prime and b>a, why are these not necessarily coprime?"

Đơn giản là nếu b>a thì b có thể là bội số của a (VD: a=3, b=6), khi đó gcd(a,b)=a, khiến a và b không phải là coprime

### Extended GCD
Bài này ta sẽ áp dụng thuật toán Euclid mở rộng (EEA) để giải.
EEA là thuật toán để tìm ra hệ số của a và b thoả:

$$au + bv = gcd(a, b)$$

EEA là một thuật toán quan trọng để tìm nghịch đảo modulo trong các bài về RSA về sau

def egcd(a,b):
    if a==0:
        return b,0,1
    g,y,x=egcd(b%a, a)   
    return  g,(x-(b//a)*y),y
print(egcd(26513,32321))

### Modular Arithmetic 1
Bài này giới thiệu qua về các phép tính trên modulo. Đề bài yêu cầu tìm số nào bé hơn của 2 phương trình:

\begin{aligned}
11 &\equiv x \pmod{6} \\
8146798528947 &\equiv y \pmod{17}
\end{aligned}

print(min(11%6,8136798528947%17))

### Modular Arithmetic 2
Bài này giới thiệu qua định lí Fermat nhỏ **(Fermat's Little Theorem)**. Định lí phát biểu như sau:

\begin{equation}
a^{p-1} \equiv 1 \pmod{p}
\end{equation}
Với **p phải là số nguyên tố**
Quan sát đề bài, ta nhận thấy có thể sử dụng định lí Fermat nhỏ để xử lí.
Đáp án sẽ là 1
### Modular Inverting
Bài này giới thiệu cho ta về **nghịch đảo modulo**
D được gọi là nghịch đảo của G theo modulo P nếu

\begin{equation}
G.D\equiv 1 \pmod{p}
\end{equation}

Để giải quyết bài này, ta có thể tái sử dụng **Fermat's Little Theorem (FLT)**

\begin{equation}
3^{12}\equiv 1 \pmod{13} \\
\Leftrightarrow 3 . 3^{11} \equiv 1 \pmod{13}\\
\Leftrightarrow 3 . 9 \equiv 1 \pmod{13}
\end{equation}

Vậy ta tìm được d=9.
Trong Python, có một hàm có thể tìm nghịch đảo modulo rất nhanh. Hàm pow(g,-1,p). Ta có thể làm bài bên trên bằng Python như sau:

print(pow(3,-1,13))

### Quadratic Residues
Bài này giới thiệu cách xác định thặng dư bậc 2 .
Bài toán cần giải quyết là:

$$
a^{2} \equiv b \pmod{p}
$$
Ta cần tìm số a sao cho khi bình phương a và chia p thì dư b.
Nếu phương trình trên vô nghiệm thì số a được gọi là **Quadratic Non-Residue.**
**VD:** 11 là căn bậc 2 của 5 theo mod 29. Vì:
$$
11^{2} \equiv 121 \pmod{29} \equiv 5 \pmod{29}
$$

* Đề bài cho ta số p và một list các số nguyên, yêu cầu ta tìm căn bậc 2 của số đó theo mod p nếu số đó là một Quadratic Residue
* Vì p là một số nhỏ nên ta sẽ chạy từ 1 tới p và kiểm tra trong mỗi số liệu có phải là căn bậc 2 của các số đã cho trong list hay không

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

for i in range(p):
    if pow(i,2,p) in ints:
        ans.append(i)
print(min(ans))

Lí do ta nhận được 2 số là vì căn bậc 2 của một số a trong modulo p có 2 kết quả x mod p và -x modp.
### Legendre Symbol
Ở bài trước, ta có cách để xác định 1 số là Quadratic Residue bằng việc thử từng số bé hơn p, tuy nhiên cách này lại không khả thi nếu p là một số rất lớn.

Bài này giới thiệu một phương pháp tổng quát hơn để xác định Quadratic Residue bất kể giá trị của p là bao nhiêu, gọi là **Legendre Symbol**
**Công thức:**

$$
(a/p)\equiv a^{(p-1)/2} \pmod{p}
$$

Legendre Symbol phát biểu ngắn gọn như sau:
* Nếu (a/p) = 1 và a không chia hết cho p thì a là **Quadratic Residue**
* Nếu (a/p) = -1 thì a là **Quadratic Non-Residue.**
* Nếu (a/p) = 0 thì a chia hết cho p

Thử thách cung cấp một số p và một list các số nguyên, yêu cầu ta xác định số nào là Quadratic Residue và tính căn bậc 2 của nó theo mod p, đáp án cần điền là số lớn hơn.

p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139

ints = [25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803, 45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555, 17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325, 14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863, 4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318, 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771, 50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987, 96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871, 4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721, 18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565]

qr=[]
sqr=[]

for i in ints:
    if pow(i,(p-1)//2,p)==1:
        qr.append(i)

if(p%4==3):
    for i in qr:
        res=pow(i,(p+1)//4,p)
        res2=pow(-i,(p+1)//4,p)
        sqr.append(res)
        sqr.append(res2)
print(max(sqr))

**Giải thích**
Đề bài có gợi ý trường hợp $$p\equiv 3 \pmod{4}$$
Nếu rơi vào trường hợp đó thì ta có công thức tính nhanh căn bậc 2 như sau:
$$
x=a^{(p+1)/4}\pmod{p}
$$

**Chứng minh:**
Ta cần tìm một số x sao cho $$ x^2\equiv a\pmod{p}$$
Vì a là một Quadratic Residue nên theo Legendre Symbol:
$$
a^{(p-1)/2}\equiv 1\pmod{p }
\Leftrightarrow a^{(p-1)/2} . a\equiv a \pmod{p}
\Leftrightarrow a^{(p+1)/2} \equiv a \pmod{p}
\Leftrightarrow (a^{(p+1)/4})^2 \equiv a \pmod{p}
$$
Vậy
$$
x=a^{(p+1)/4} \pmod{p}
$$
Lí do có điều kiện $$p\equiv 3 \pmod{4}$$
Là vì khi đó,
$$
p\equiv -1 \pmod{4}
\Leftrightarrow (p+1)/4=k
$$
Số mũ là số nguyên thì mới tính các phép luỹ thừa được
### Modular Square Root

Bài này giới thiệu một phương pháp tổng quát để tìm căn bậc 2 theo modulo p
**(Tonelli-Shanks)**, thay vì phải thoả mãn một số điều kiện của p như bài trước.
Chi tiết thuật toán: [Tonelli-Shanks](https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm)

a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
k=p-1
S=0
while(k%2==0):
    k=k//2
    S=S+1

Q=(p-1)//pow(2,S)
M=S
z=2

while(pow(z,(p-1)//2,p)!=p-1):
    z=z+1

c=pow(z,Q,p)
t=pow(a,Q,p)
R=pow(a,(Q+1)//2,p)

while(t!=1):
    for j in range(M):
        if(pow(t,pow(2,j),p)==1):
            i=j
            break

    b=pow(c,int(pow(2,M-i-1)),p)
    M=i
    c=pow(b,2,p)
    t=(t*c)%p
    R=(R*b)%p

print(R)

### Chinese Remainder Theorem
**Chinese Remainder Theorem (CRT)** là một phương pháp để ta có thể dễ dàng tính các phương trình modulo với một modulo rất lớn, bằng việc chia nhỏ phương trình đó ra thành nhiều phương trình con
* Xét:
\begin{cases}
x \equiv a_1 \pmod{n_1} \\
x \equiv a_2 \pmod{n_2} \\
\vdots \\
x \equiv a_k \pmod{n_k}
\end{cases}
* Biết rằng các số n1,n2,...,nk là coprime
* Tính
$$
N = \prod_{i=1}^{k} n_i,\text{ } N_i = \frac{N}{n_i}
$$
* Với mỗi Ni, tìm:
$$
y_i \equiv N_i^{-1} \pmod{n_i}
$$
* Cuối cùng, áp dụng công thức:
$$
x=(a_1.N_1.y_1+a_2.N_2.y_2+...+a_k.N_k.y_k) \pmod{N}
\Leftrightarrow x = \sum_{i=1}^{k} a_i N_i y_i \pmod{N}
$$
### Adrien's Signs

Sau khi đọc qua mã nguồn thì ta có thể hiểu quy trình mã hóa như sau:

1. Chuyển tin nhắn thành một chuỗi nhị nhân 8 bit rồi ghép lại
2. Duyệt qua từng phần tử của chuỗi đó, nếu phần tử đó bằng 1 thì ta sẽ mã hóa phần tử đó bằng n, còn nếu bằng 0 thì sẽ mã hóa bằng -n%p

Áp dụng công thức **Legendre Symbol**, ta nhận thấy a là một Quadratic Residue vì

$$
a^{(p-1)/2} \equiv 1 \pmod{p}
$$

Điều này dẫn tới các phần tử trong ciphertext có thể là **Quadratic Residue**
$$
n=a^e \rightarrow (a^{(p-1)/2})^e \equiv 1^e \equiv 1 \pmod{p}
$$
hoặc **Quadratic Non-residue**
$$
n=-a^e \rightarrow -(a^{(p-1)/2})^e \equiv -1^e \equiv -1 \pmod{p}
$$

Từ đây ta chỉ cần duyệt các phần tử của ciphertext và in ra 1 nếu đó là **Quadratic Residue**, 0 nếu là **Quadratic Non-residue**, rồi decode ra flag

from random import randint

a = 288260533169915
p = 1007621497415251

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

output=[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]
res=[]
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

for i in output:
    if pow(i, (p-1)//2, p) == 1:
        res.append('1')
    else:
        res.append('0')
print(bytes(int(''.join(res[i:i+8]), 2) for i in range(0, len(res), 8)))

### Modular Binominals
**Ý tưởng:** trước tiên ta cần biến đổi các phương trình để triệt tiêu p hoặc q. Khi đó phương trình mới, gọi là K, sẽ là q nhân cho 1 hệ số nào đó, vì q|K và q|N nên dễ dàng tìm q bằng việc tính GCD(K,N)

* Đầu tiên, ta cần làm số mũ vế phải của hai phương trình giống nhau
\begin{aligned}
c_1^{e_2} = (2p + 3q)^{e_1.e_2} \Leftrightarrow
(2p)^{e_1e_2} + (3q)^{e_1e_2} \pmod{N} \\
c_2^{e_1} = (5p + 7q)^{e_1.e_2} \Leftrightarrow
c_2^{e_1} \equiv (5p)^{e_1e_2} + (7q)^{e_1e_2} \pmod{N}
\end{aligned}

* Tiếp theo, ta cần triệt tiêu mất hệ số của p

\begin{aligned}
c_1^{e_2} . 2^{-e_1e_2} \equiv p^{e_1e_2} + (3q)^{e_1e_2} . 2^{-e_1e_2} \pmod{N} \\
c_2^{e_1} . 5^{-e_1e_2} \equiv p^{e_1e_2} + (7q)^{e_1e_2} . 5^{-e_1e_2} \pmod{N}
\end{aligned}

* Lấy hai phương trình trừ nhau để làm mất p

\begin{aligned}
c_1^{e_2} . 2^{-e_1e_2} - c_2^{e_1} . 5^{-e_1e_2} \equiv p^{e_1e_2} + (3q)^{e_1e_2} . 2^{-e_1e_2} - p^{e_1e_2} + (7q)^{e_1e_2} . 5^{-e_1e_2} \pmod{N} \\
\
\end{aligned}

* Đặt
$$
K=q^{e1.e2}.(3^{e1.e2}.2^{-e1.e2}+7^{e1.e2}.5^{-e1.e2}) = c_1^{e_2} . 2^{-e_1e_2} - c_2^{e_1} . 5^{-e_1e_2}
$$

* Ta tìm được
$$
q=GCD(K,N) \rightarrow p=N/q
$$

N = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519

from math import gcd
K=pow(2,(-e1*e2),N)*pow(c1,e2,N)-pow(5,-e1*e2,N).pow(c2,e1,N)
print(gcd(K,N))

## General Challenges
### Ascii
Bài này đơn giản ta chỉ cần chuyển các số thứ tự trong bảng ascii thành kí tự tương ứng

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

### Hex
Đề bài yêu cầu ta decode một đoạn mã hex

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

### Base64
Đề bài yêu cầu ta decode một bị mã hóa base64, nó sẽ chuyển tin nhắn sang các byte, và lấy lần lượt 6 bit để đổi sang cơ số 10 rồi dịch sang kí tự theo bảng 64

import base64
    
s = '72bca9b68fc16ac7beeb8f849dca1d8a783e8acf9679bf9269f7bf'
print(base64.b64encode(bytes.fromhex(s)).decode())

### Bytes and Big Integers
Bài này giới thiệu một số hàm của python để làm việc với số nguyên lớn

from Crypto.Util.number import long_to_bytes
print(long_to_bytes(11515195063862318899931685488813747395775516287289682636499965282714637259206269).decode())

### Encoding Challenge
Bài này cho ta làm quen với một số dạng thử thách crypto yêu cầu kết nối với máy chủ ảo.
Server sẽ trả về kiểu mã hóa và tin nhắn bị mã hóa, yêu cầu ta gửi tin nhắn sau khi được decode, khi vượt qua 100 levels sẽ nhận được flag

from pwn import * # pip install pwntools
import json
from Crypto.Util.number import *
import base64
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)

for i in range(101): 
    received = json_recv()

    print("Received type: ")
    print(received["type"])
    print("Received encoded value: ")
    print(received["encoded"])

    if(received["type"] == "base64"):
        ans = base64.b64decode(received["encoded"]).decode()

    elif(received["type"] == "hex"):
        ans = codecs.decode(received["encoded"], 'hex').decode()

    elif(received["type"] == "rot13"):
        ans = codecs.decode(received["encoded"], 'rot_13')

    elif(received["type"] == "bigint"):
        
        ans = long_to_bytes(int(received["encoded"], 16)).decode()

    elif(received["type"] == "utf-8"):
        ans = ''.join([chr(i) for i in received["encoded"]])
    to_send = {
        "decoded": ans
    }
    json_send(to_send)

final = json_recv()
print(final["flag"])

### XOR Starter
Đề bài giới thiệu về phép XOR và yêu cầu ta XOR chuỗi label với số 13

str='label'
flag='crypto{'
for i in str:
    flag+=chr(ord(i)^13)
print(flag,"}")

### XOR Properties
Bài này ta sẽ sử dụng tính chất **Self Inverse** để giải
\begin{cases}
KEY1 = a6c8b6733c9b22de7bc0253266a3867df55acde8635e19c73313 \\
KEY2 ⊕ KEY1 = 37dcb292030faa90d07eec17e3b1c6d8daf94c35d4c9191a5e1e \\
KEY2 ⊕ KEY3 = c1545756687e7573db23aa1c3452a098b71a7fbf0fddddde5fc1 \\
FLAG ⊕ KEY1 ⊕ KEY3 ⊕ KEY2 = 04ee9855208a2cd59091d04767ae47963170d1660df7f56f5faf
\end{cases}
Phương trình thứ 2: ta XOR 2 vế cho KEY1 để tìm KEY2. Sau khi có KEY2 làm tương tự đối với các phương trình dưới để tìm ra flag

from pwn import *
key1 = 'a6c8b6733c9b22de7bc0253266a3867df55acde8635e19c73313'
key2_key3 = 'c1545756687e7573db23aa1c3452a098b71a7fbf0fddddde5fc1'
flag = '04ee9855208a2cd59091d04767ae47963170d1660df7f56f5faf'
print(xor(bytes.fromhex(key1), bytes.fromhex(key2_key3), bytes.fromhex(flag)))

### Favorite byte
Đề bài bảo rằng đã encode với 1 byte nào đó, ta chạy trâu thử từng trường hợp và XOR ciphertext với 1 byte tới khi nào plaintext có dạng như đáp án thì ta ngừng, known text là crypto{

from pwn import *
a = bytes.fromhex('73626960647f6b206821204f21254f7d694f7624662065622127234f726927756d')
for i in range(300):
    b = xor(a,i)
    if b'crypto' in b:
        print(b)
        break

### You either know, XOR you don't
Đề bài có gợi ý có gì đó liên quan đến format của đáp án, ta biết đó sẽ là crypto{, vì ta đang làm các bài XOR nên ta thử ngay việc XOR đoạn cipher với crypto{ thì nhận được:
b'myXORke+y_Q\x0bHOMe$~seG8bGURN\x04DFWg)a|\x1dTM!an\x7f'. Nhận thấy được manh mối là myXORkey, ta thử XOR tiếp tục với key đó thì may mắn nhận được flag

from pwn import *
print(xor(bytes.fromhex('0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104'), b'crypto{'))
print(xor(bytes.fromhex('0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104'), b'myXORkey'))

### Lemur XOR
Đề bài cung cấp 2 hình ảnh và yêu cầu ta XOR 2 bức ảnh đó
Bài này ta có thể sử dụng một tool khá mạnh để XOR 2 bức ảnh là **gmic** :
Câu lệnh trên linux như sau:

gmic <đường dẫn hình 1> <đường dẫn hình 2> -blend xor -o flag.png

Ta nhận được hình ảnh sau khi XOR:
### Privacy-Enhanced Mail?
Bài này giới thiệu về format của mật mã khi được gửi đi, sau khi đọc các tài liệu đề bài cung cấp, ta nhận thấy **file pem** mà đề cho là một private key( nhưng đã bị mã hóa), ta sẽ dùng tool linux để nhận được private key bị giấu bên trong. Dấu hiệu nhận biết đó là private key là vì có nó có header và footer như sau:

-----BEGIN RSA PRIVATE KEY-----
-----END RSA PRIVATE KEY-----
Đầu tiên ta sẽ cần đổi đuôi file từ .pem sang .key

openssl rsa -in <đường dẫn tới file private key đuôi .key> -text -noout

ta sẽ nhận được các thông tin bao gồm public key và private key,
<details>
<summary>KEY</summary>
Private-Key: (2048 bit, 2 primes)
modulus:
00:ce:f2:83:b7:e1:0e:f8:0e:a8:13:52:c8:b5:2b:
a7:91:62:7c:bc:de:93:81:cb:bc:0a:4d:3b:ee:3a:
06:0d:f1:b6:36:dc:43:e2:fc:90:c4:64:d0:9e:0a:
fa:8c:42:89:b9:5c:f6:30:8c:03:71:d5:ed:14:b2:
05:f8:84:97:f4:77:c0:2d:0d:f2:89:e7:4d:4b:cd:
27:fd:34:75:04:d7:09:4a:5c:c8:ba:a2:e6:17:17:
5d:9a:39:9f:52:f1:c5:b8:52:ef:c6:05:d1:81:ad:
e6:83:7a:fb:a2:54:d6:fb:57:f1:39:2d:19:55:e0:
c9:a8:50:9a:39:14:6f:a0:06:0e:80:b8:2e:77:6f:
c4:d1:a6:9a:26:2f:5c:37:b0:a3:99:d2:7b:43:79:
ba:af:21:ae:0b:0a:84:bd:9d:4a:81:55:96:6b:b7:
ca:70:5a:29:9e:5f:df:72:c4:9e:73:06:c3:57:98:
56:7e:6b:f1:88:05:09:cb:59:8d:48:fc:24:7f:96:
21:19:0f:bc:de:0f:4d:e7:cf:11:a4:b2:cc:5e:68:
2d:e8:a8:a6:b6:25:a7:26:ca:ad:0c:f4:65:63:80:
63:c5:da:6e:57:74:32:51:da:36:ca:6a:a7:aa:e6:
67:13:fb:e5:53:f8:67:eb:fb:3c:f9:cb:5d:4e:a7:
d2:0b

publicExponent: 65537 (0x10001)
privateExponent:
7c:3b:1d:53:4f:29:9b:43:c1:26:08:76:30:3c:0a:
95:be:17:bf:91:a5:df:2f:1c:ac:da:7c:75:a0:23:
6e:4f:81:e1:21:0d:27:c0:12:6f:b3:4d:80:f2:7a:
41:a4:d7:e4:8c:a7:c5:b0:e7:88:78:b1:9f:d0:d6:
c0:bf:68:30:fb:8a:44:01:b1:6d:93:8a:d5:4c:4d:
0b:35:68:62:05:6c:b0:55:4e:b2:ab:83:90:ad:18:
25:b3:1d:af:bf:2f:c0:5d:19:4f:38:c2:f2:24:20:
d3:21:0a:da:02:30:24:26:40:ca:e0:05:eb:85:cb:
c8:dc:ca:18:25:ea:74:96:d9:b1:70:c5:cb:fe:35:
4f:e1:9a:63:10:2b:82:f3:8d:5d:7c:25:17:35:20:
8b:83:a5:42:40:92:7f:89:98:48:c1:6a:5f:e7:0c:
e9:50:da:ff:7b:f9:f4:b7:1b:59:81:01:a5:20:48:
cd:30:c1:6c:b9:94:33:0b:10:59:2d:2c:95:d4:d0:
e5:79:f5:28:7f:f7:4a:88:26:8d:03:89:69:8c:8f:
7b:9a:e8:13:f3:92:46:89:3d:02:66:1c:f0:8d:9c:
bc:ec:9f:72:2c:f7:6d:0e:96:f1:e1:77:37:e2:9e:
ce:86:76:76:7c:b6:e1:df:0d:bd:2d:73:1e:d8:48:
b1
prime1:
00:ed:fb:47:15:eb:a9:3b:c4:c2:cb:e7:12:c8:08:
10:27:cc:86:a8:d2:8d:2c:78:c9:72:0e:6d:e6:f6:
80:31:e0:e3:4f:fa:5e:ef:0f:d1:d0:85:ae:49:c0:
a8:00:38:8b:f7:ee:98:a9:4a:77:e1:18:1e:60:39:
24:b3:b3:bb:9d:ce:97:b8:00:62:f2:83:0c:8f:11:
98:3d:fa:dd:55:f1:f9:ce:53:62:99:2e:14:c2:5f:
77:6e:f7:da:ce:eb:71:9e:1c:f9:f2:f6:2f:4b:a6:
d0:03:de:4d:42:7e:eb:5a:4d:98:15:64:4f:ce:12:
55:93:1b:df:2b:a3:7f:c7:a7
prime2:
00:de:9d:b5:c3:5d:25:62:f1:cd:36:22:34:28:18:
c7:be:ba:03:33:20:7e:df:db:c3:f2:64:8e:6d:14:
10:b8:91:49:74:a5:ae:32:af:a8:e4:ea:e4:0b:42:
ad:a5:86:7e:1b:0e:33:2f:d0:d0:a2:c8:a9:de:1a:
db:ed:bd:81:f9:ba:b4:c8:fe:c8:ce:3e:66:01:55:
e2:cd:04:c6:92:5b:93:fd:88:af:be:05:dc:c5:52:
a8:36:e3:53:a9:31:20:9b:23:a1:3e:7e:b0:f8:fa:
91:9c:44:ac:48:5c:e3:7d:6a:da:85:30:ab:56:89:
9c:66:69:d4:4c:58:74:ae:fd
exponent1:
44:4c:de:bc:fa:d2:aa:35:b1:56:85:ee:0c:fc:cb:
6e:30:b3:e1:15:f4:b0:73:c6:14:f6:f1:31:dd:43:
33:8d:80:8f:be:a2:aa:67:d6:e6:ca:c7:17:a1:b4:
55:c3:e4:df:f6:59:58:14:e8:4c:f0:f8:1e:d3:a7:
a5:ef:8a:84:22:fb:c6:32:4e:33:9d:ca:e7:f0:bb:
c9:e6:0a:ca:14:d5:86:12:c6:74:82:16:31:26:e7:
07:31:19:5a:53:96:5b:33:a3:c4:c8:45:10:a8:42:
81:29:b6:f0:c3:ae:56:4f:78:bb:82:fb:a8:7f:f8:
91:6c:e9:63:03:dc:b3:77
exponent2:
00:d3:f4:f7:3e:16:ee:e4:e1:73:51:0a:89:fc:6f:
73:a7:9e:36:33:b4:c9:f8:5c:a7:99:9f:b2:98:1a:
d5:bc:d5:e0:49:a7:02:50:12:3e:4e:0f:73:a7:61:
0a:32:a2:f6:68:ce:41:60:52:82:83:ab:69:49:26:
eb:a5:d5:9c:ee:68:9d:7f:0e:4f:a5:47:76:19:e9:
6b:73:67:0b:a6:08:79:c4:99:23:33:5b:23:93:e1:
1a:76:80:45:84:bf:58:db:3d:b6:65:e9:7c:98:e3:
02:46:f6:7f:ce:ba:5a:83:6c:7c:b8:f9:d8:f9:21:
36:ff:af:dd:c9:ff:22:c2:05
coefficient:
76:bc:5d:83:0b:cc:7e:b7:21:e8:7a:f5:56:45:ff:
b8:ce:dd:dd:e5:67:82:e5:30:46:13:d0:11:7b:b3:
29:df:7b:da:ba:c7:bb:34:89:af:5b:7f:af:d0:0a:
49:8e:c4:f0:bc:eb:ca:a1:38:c8:12:4b:8f:0b:f9:
33:0a:99:03:50:4a:6f:5b:f6:8c:b6:20:b9:4b:03:
42:83:b1:7e:4e:fc:5a:32:8b:3d:6c:73:0a:fb:9e:
1e:ad:67:eb:55:40:24:6f:16:f8:88:10:69:1a:5d:
d1:22:04:de:1e:4d:b7:23:7d:ce:66:77:fb:bd:78:
0e:4d:db:53:f3:81:df:c6
</details>

Sau đó ta sẽ decode mã hex của private exponent là ra đáp án:

privateexponent = """
7c:3b:1d:53:4f:29:9b:43:c1:26:08:76:30:3c:0a:
    95:be:17:bf:91:a5:df:2f:1c:ac:da:7c:75:a0:23:
    6e:4f:81:e1:21:0d:27:c0:12:6f:b3:4d:80:f2:7a:
    41:a4:d7:e4:8c:a7:c5:b0:e7:88:78:b1:9f:d0:d6:
    c0:bf:68:30:fb:8a:44:01:b1:6d:93:8a:d5:4c:4d:
    0b:35:68:62:05:6c:b0:55:4e:b2:ab:83:90:ad:18:
    25:b3:1d:af:bf:2f:c0:5d:19:4f:38:c2:f2:24:20:
    d3:21:0a:da:02:30:24:26:40:ca:e0:05:eb:85:cb:
    c8:dc:ca:18:25:ea:74:96:d9:b1:70:c5:cb:fe:35:
    4f:e1:9a:63:10:2b:82:f3:8d:5d:7c:25:17:35:20:
    8b:83:a5:42:40:92:7f:89:98:48:c1:6a:5f:e7:0c:
    e9:50:da:ff:7b:f9:f4:b7:1b:59:81:01:a5:20:48:
    cd:30:c1:6c:b9:94:33:0b:10:59:2d:2c:95:d4:d0:
    e5:79:f5:28:7f:f7:4a:88:26:8d:03:89:69:8c:8f:
    7b:9a:e8:13:f3:92:46:89:3d:02:66:1c:f0:8d:9c:
    bc:ec:9f:72:2c:f7:6d:0e:96:f1:e1:77:37:e2:9e:
    ce:86:76:76:7c:b6:e1:df:0d:bd:2d:73:1e:d8:48:
    b1"""
a = privateexponent.replace('\n', '').replace(' ', '').replace(':', '')
res = int(a, 16)
print(res)

### CERTainly not
Bài này sẽ đổi qua làm việc với file đuôi der, der là file chỉ bao gồm các kí tự mà chỉ có máy mới hiểu, thường ta sẽ chuyển từ der sang pem cho dễ thao tác. Sau khi chuyển sang file pem thì ta làm tương tự như bài trên.
* Lệnh linux chuyển từ file der sang pem:

openssl x509 -inform der -in 2048b-rsa-example-cert.der -out 2048b-rsa-example-cert.pem

* Ta tìm modulo N trong file pem đó

openssl x509 -in 2048b-rsa-example-cert_3220bd92e30015fe4fbeb84a755e7ca5.pem -noout -modulus

N="""B4CFD15E3329EC0BCFAE76F5FE2DC899C67879B918F80BD4BAB4D79E02520609F418934CD470D142A0291392735077F60489AC032CD6F106ABAD6CC0D9D5A6ABCACD5AD2562651E54B088AAFCC190F253490B02A29410F55F16B93DB9DB3CCDCECEBC75518D74225DE49351432929C1EC669E33CFBF49AF8FB8BC5E01B7EFD4F25BA3FE596579A2479491727D7894B6A2E0D8751D9233D068556F858310EEE81997868CD6E447EC9DA8C5A7B1CBF24402948D1039CEFDCAE2A5DF8F76AC7E9BCC5B059F695FC16CBD89CEDC3FC129093785A75B45683FAFC4184F6647934351CAC7A850E73787201E72489259EDA7F65BCAF8793198CDB7515B6E030C708F859"""

print(int(str(N), 16))

### SSH Keys

SSH sử dụng một cặp private key và public key để xác thực người dùng với các trang web. File mà đề cung cấp là một bản sao của public key. Ta cần tìm modulo N của public key đó.
Ta tiếp tục sử dụng tool linux ( :crying_cat_face: ) để làm bài này:
* Đầu tiên ta cần đổi quyền truy cập của file sang 600, vì nếu là 777 theo như mặc định của linux thì SSH không chấp nhận

cp <đường dẫn tới file.pub> ~
cd ~
chmod 600 bruce_rsa_6e7ecd53b443a97013397b1a1ea30e14.pub

* Tiếp theo ta dùng lệnh sau để chuyển từ dạng .pub sang .pem

ssh-keygen -e -m pem -f bruce_rsa_6e7ecd53b443a97013397b1a1ea30e14.pub > bruce_output.pem

* Khi đã có file.pem ta thực hiện như cũ để lấy N

openssl rsa -pubin -in bruce_output.pem -text -noout

N="""00:ad:3c:ba:9b:6b:e1:85:bc:31:dd:15:5b:35:56:
    f7:64:e7:a7:0a:aa:ac:39:71:da:26:96:ed:37:e3:
    ae:ba:52:ca:05:22:a9:22:83:c1:f9:90:db:0d:79:
    f4:a9:69:1f:e2:53:b1:b4:64:a0:a2:59:14:6e:01:
    b4:ec:b8:73:7e:0b:3e:76:e9:78:50:bf:38:0a:4c:
    19:13:19:85:dd:17:f5:9d:1b:fe:bf:ba:6a:2e:dd:
    9d:3e:c0:9b:d3:66:0b:c4:99:e1:1c:96:f8:ad:06:
    b3:d9:93:38:40:2b:53:39:ca:98:0d:47:8a:7c:b1:
    c2:69:95:38:12:49:bf:38:0a:4a:ae:97:f0:e3:fd:
    28:7e:7f:0a:3a:b1:4d:d2:de:3f:76:a9:cd:bb:05:
    51:82:86:94:22:1b:08:e3:ba:de:02:90:76:ae:cd:
    00:3f:80:a0:81:22:22:f2:ce:81:5c:2c:41:e1:8c:
    e0:4e:10:4a:e7:be:b4:4f:58:22:00:26:10:0b:93:
    05:76:ad:46:c3:e2:0d:48:59:ae:d0:23:6a:b7:9c:
    1d:27:96:78:cf:9e:38:f0:69:1e:d3:a4:7e:20:cb:
    63:52:21:83:43:74:2d:4f:67:ca:de:05:a1:67:19:
    35:e0:ce:14:36:b7:44:4e:04:d6:fe:64:38:07:f0:
    5c:be:29:31:be:80:46:a4:a6:ed:b4:6d:1a:81:f3:
    a3:4d:e9:fa:c3:2c:e9:19:f7:1d:f0:df:6b:49:b6:
    aa:ab:25:30:0b:cb:83:a2:dc:c5:b4:5c:f3:ba:d5:
    40:53:d7:7d:d5:36:a0:1b:35:81:84:da:0c:7e:99:
    70:55:39:ec:db:b1:8e:3a:0b:f5:76:7e:6c:41:24:
    92:98:fd:21:4d:b3:cc:0e:54:e1:ca:c2:a4:47:d0:
    62:39:56:c1:b5:61:90:a5:5f:77:ea:93:c1:83:25:
    84:44:6a:8c:a8:2f:71:ca:42:dd:54:7b:f6:56:ed:
    39:4f:45:8c:c0:a0:80:7a:d8:2d"""
N = N.replace('\n', '').replace(' ', '').replace(':', '').replace('\t', '')
print(int(str(N), 16))

### Transparency
Bài này yêu cầu ta tìm subdomain của cryptohack.org. Ta biết rằng mỗi subdomain sẽ gồm public key và certificate. Nên ta sẽ tìm certificate bằng crt.sh. Nó sẽ yêu cầu ta nhập Certificate Fingerprint, ta có thể lấy nó qua file.pem đề cho như sau:

openssl pkey -in <đường dẫn tới file.pem> -pubin -outform DER | openssl sha256

lệnh này sẽ chuyển file pem sang file der ( để tăng độ chính xác khi hash), rồi hash nó theo sha256, ta dùng kết quả đó vào crt.sh để tìm subdomain.