# CRYPTOHACK Writeup
# Introduction to CryptoHack
## XOR Starter
**Solution**
string = label
key =13
要求做XOR
```pyton= !
a = "label"
for i in range(0,5,1):
print(chr(ord(a[i]) ^ 13),end='')
```
## XOR Properties
**Solution**
這題看起來複雜，~~事實上很複雜~~
**KEY２:**
KEY2 ⊕ KEY1可以等於
`(KEY2 ⊕ KEY1) ⊕ (KEY1 ⊕ KEY1)＝(KEY2 ⊕ KEY1) ⊕ KEY1`
接著根據結合律
`KEY2 ⊕ (KEY1 ⊕ KEY1)= KEY2`
所以：`KEY2= 37dcb292030faa90d07eec17e3b1c6d8daf94c35d4c9191a5e1e`
**KEY3:**
跟KEY2原理一樣
KEY2 ⊕ KEY3可以等於
`(KEY3 ⊕ KEY2) ⊕ (KEY2 ⊕ KEY2)＝(KEY3 ⊕ KEY2) ⊕ KEY2`
接著根據結合律
`KEY3 ⊕ (KEY2 ⊕ KEY2)= KEY3`
所以：`KEY3= c1545756687e7573db23aa1c3452a098b71a7fbf0fddddde5fc1`
最後我們有了KEY1,KEY2,KEY3了
只要把KEY都帶進去就可以得到FLAG
記得在做XOR要先做位元換算
```pyton= !
from pwn import *
KEY1 = bytes.fromhex("a6c8b6733c9b22de7bc0253266a3867df55acde8635e19c73313")
KEY2_KEY1 = bytes.fromhex("37dcb292030faa90d07eec17e3b1c6d8daf94c35d4c9191a5e1e")
KEY2_KEY3 = bytes.fromhex("c1545756687e7573db23aa1c3452a098b71a7fbf0fddddde5fc1")
FLAG_KEY123 = bytes.fromhex("04ee9855208a2cd59091d04767ae47963170d1660df7f56f5faf")
flag = xor(FLAG_KEY123, KEY2_KEY3, KEY1)
print(flag.decode())
```
## **Favourite byte**
這題給了KEY是single byte(單字節)的提示
所以可以用暴力破解，把密文跑過1個byte
```pyton=
b = "73626960647f6b206821204f21254f7d694f7624662065622127234f726927756d"
c = bytes.fromhex(b)
for key in range(256):
d = bytes([b ^ key for b in c])
print(d.decode())
```
## You either know, XOR you don't
這題的key並沒有直接表示，但我們可以知道明文的開頭一定是`crypto{`
所以我們只要把開頭帶進去就可以得知KEY
```pyton=
b = "0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104"
c = bytes.fromhex(b)
key = "crypto{"
d = bytearray(byte ^ ord(key[i % len(key)]) for i, byte in enumerate(c))
print(d.decode())
```
接著再帶進去，FALG就出來了
```pyton= !
b="0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104"
c = bytes.fromhex(b)
key = "myXORkey"
# 解密：利用 XOR 解密每個字節
d = bytearray(byte ^ ord(key[i % len(key)]) for i, byte in enumerate(c))
# 輸出解密後的明文
print(d.decode())
```
# Modular Arithmetic
## Greatest Common Divisor
這題要找最大公因數
### 輾轉相除法(歐幾里得算法，Euclidean algorithm)
1. 取A,B兩個不為0的整數，並A>=B
2. A÷B的商與餘(A=Bq+r)
3. 如果r=0，那B就是A最大公因數
4. 如果r≠0，則A=B，B=r，繼續計算下去
## Extended GCD
這題要用擴充歐基里得演算法，求u,v
> pip python -m pip install egcd
```pyton= !
from egcd import egcd
a = 26513
b = 32321
print(egcd(a, b))
```
output：(1, 10245, -8404)
> https://www.youtube.com/watch?v=Au0zVvkmvr0 參考影片
## Modular Arithmetic 1
**模的概念**
```
print(11%6)
print(8146798528947%17)
```
## Modular Arithmetic 2
這題要用費馬小定理(Fermat's little theorem)
p = 65537
根據費馬小定理：**對於一個質數𝑝 和任何不被𝑝 整除的整數𝑎**
最小公因數必定會是1，gcd(a,p)=1
```pyton= !
aᵖ⁻¹≡1(mod p)
65537是質數，所以
a⁶⁵⁵³⁶ ≡ 1 (mod 65537)
```
aᵖ≡a(mod p)
> 費馬小定理：https://ithelp.ithome.com.tw/articles/10205906
## Modular Inverting
這題給你：3*d ≡ 1(mod 13)
把d逆推回去就可以知道答案了。
## Quadratic Residues
**二次剩餘定義：
有一個數 X，X²≡d(mod p)成立時，d是模p的二次剩餘(quadratic residues)
反之不成立，則稱d是模p的二次非剩餘(non-quadratic)**
題目給了3個數字，兩個二次非剩餘，一個二次剩餘。
不知道是哪個，我們直接用python帶進去迴圈看。
```pyton= !
p = 29
ints = [14, 6, 11]
flag = 100000 # max
for n in ints:
for a in range(1,29):
if pow(a,2,p) == n:
flag = min(flag,a)
print(flag)
```
## Legendre Symbol
```pyton= !
p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139
ints = [25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803, 45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555, 17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325, 14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863, 4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318, 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771, 50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987, 96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871, 4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721, 18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565]
a = 0
for i in ints:
if pow(i,(p-1)//2,p) == 1:
a = i
break
print(pow(a,(p+1)//4,p))
```
# Symmetric Cryptography
## Keyed Permutations
## Resisting Bruteforce
## Structure of AES
前面兩題都是在講簡單的概念，這題要你知道AES的原理以及怎麼去做加密的，
總共有四個步驟：
(PS：題目有附影片看下面講得會借用圖片來解釋：https://www.youtube.com/watch?v=gP4PqVGudtg)
1. SubBytes（字節代換）
2. ShiftRows（行位移）
3. MixColumns（列混合）
4. AddRoundKey（輪密鑰加）
左邊輸入，右邊是鑰匙
# RSA
## 1. Modular Exponentiation
**Solution**
題目要求使用mod，將101¹⁷ mod 22663
> pow(base, exponent, modulus)
```pyton= !
b = 101
e = 17
m = 22663
print(pow(b,e,m))
```
## 2. Public Keys
**Solution**
題目要求我們將12加密，並給了我們Keyp=17、q=23、e=65537
```pyton= !
p=17
q=23
e=65537
n = p*q
m = 12
print(pow(m,e,n))
```
## 3. Euler's Totient
**Solution**
給了 P和Q兩個質數，要求帶入歐拉函式算出N
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
```pyton= !
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
print((p-1)*(q-1))
```
歐拉函式：https://zh.wikipedia.org/zh-tw/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0
## 4. Private Keys
**Solution**
求私鑰 d，
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e = 65537
```pyton= !
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e = 65537
n = (p-1)*(q-1)
print(pow(e,-1,n))
```
數論倒數：https://www.youtube.com/watch?v=C7Kuo0e9s6Y
## 5. RSA Decryption
**Solution**
與上一題結合，解密密文
```pyton= !
key = 121832886702415731577073962957377780195510499965398469843281
n = 882564595536224140639625987659416029426239230804614613279163
e = 65537
c = 77578995801157823671636298847186723593814843845525223303932
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
pq = (p-1) * (q-1)
d = pow(e,-1,pq)
print(pow(c,d,n))
```
---
Sign in with Wallet
Connect another wallet