CryptoHack WriteUps

CryptoHack 裡面我覺得值得記錄的題目的解法,順便作為和 CTF crypto 有關的筆記本,方便我日後查詢相關的資訊,

RSA

Factoring

丟到 FactorDB 上去解決。

Inferius Prime

這題我一開始的想法是想用e=3e=3 的方法去弄,不過發現到它的 n 很小就一樣是去 FactorDB 處裡。然後後來算了一下C+k×N3\sqrt[3]{C+k\times{N}} 是整數的kk 大小發現也只能用直接分解來做。

Monoprime

只有一個質數,也不相乘,即N=pN=p,所以ϕ(N)=p1\phi(N)=p-1,然後算出dd 之後解密就完成了。

Square Eyes

一樣是一個質數,不過是N=p2N=p^2,所以ϕ(N)=p×(p1)\phi(N)=p\times{(p-1)},然後一樣算出dd 就搞定了。

Manyprime

有很多個質數,一樣去 FactorDB 查一下就能搞定。要在自己的電腦上算的話可以用 ECM 的算法,而這個在 Sage 裡面就有提供

Salty

e=1e=1,所以d=1d=1,因此mc(modN)m\equiv c\pmod{N}cm(modN)c\equiv m\pmod{N}

Modulus Inutilis

這題才是真正的e=3e=3 攻擊,不過它的CC 本身就是立方數了,所以k=0k=0 就好了。

Everything is Big

ee 很大代表的是dd 很小,當dd 很小的時候可以用 Wiener’s Attack,而這個算法在 RsaCtfTool 就有提供了。

Crossed Wires

這題它給你了N,e,dN, e, d,然後 flag 是用(N,e1)(N,e5)(N, e_1) \dots (N, e_5) 加密的,所以要解密回來就先想辦法求出d1d5d_1 \dots d_5,而這個就需要有p,qp, q 才行,所以目標就是把NN 分解。

查了一下可以很容易的找到說已知(N,e,d)(N, e, d) 是能很容易的分解出p,qp, q 的,所以就去查了一下那個算法自己實作一遍就好了,它的計算速度非常的快:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import gmpy2
from Crypto.Util import number

e = 65537
d = 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097
n = 21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771

def factor(n, e, d):
f = e*d-1
lsb = gmpy2.bit_scan1(f)
t = f >> lsb
a = 2
while True:
ap = pow(a, t, n)
for i in range(1, lsb+1):
if ap == 1:
break
if ap == n-1:
break
ap2 = pow(ap, 2, n)
if ap2 == 1:
p = gmpy2.gcd(ap-1, n)
return p, n//p
ap = ap2

p, q = factor(n, e, d)
r = (p-1)*(q-1)
friend_keys = [106979, 108533, 69557, 97117, 103231]
flag = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
for pk in friend_keys:
d = pow(pk, -1, r)
flag = pow(flag, d, n)
print(number.long_to_bytes(flag))

Everything is Still Big

這題一樣是很大的ee,但是它多加了一個要求就是要d>13N14d>\frac{1}{3}N^{\frac{1}{4}},所以不符合上面使用的 Wiener’s attack 的條件。不過這其實也很明顯的告訴我們這題還是和這個攻擊有關,所以查了一些資訊之後會發現還有個改善過的 Wiener’s attack 叫 Boneh and Durfee,可以適用在d<N0.292d<N^{0.292} 的情況下。

使用這個的話有很多方法,有 Sage 的實現,不過我是直接用 RsaCtfTool--attack boneh_durfee 就能搞定了。

Endless Emails

這題的題目敘述有說 students are all asking the same questions,所以大概是告訴我們說它加密的訊息中有重複的項目出現。然後如果同個訊息重複出現三次以上的話可以我們可以列出下面的式子。

mec1(modn1)mec2(modn2)mec3(modn3)m^e\equiv c_1\pmod{n_1} \\ m^e\equiv c_2\pmod{n_2} \\ m^e\equiv c_3\pmod{n_3}

注意到那個mem^e 是固定的,所以問題就被轉化成熟悉的中國餘數定理(CRT)了,然後因為e=3e=3所以檢查求出來之後的值是不是完全立方數就可以了。

不過這題它一共給了 7 組(nk,ck)(n_k,c_k),所以就(73)\binom{7}{3} 種組合都給它算過一次看看哪一組的結果是完全立方數,然後再轉成字串後就是 flag 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from itertools import combinations
import requests
from functools import reduce
import operator
import gmpy2
from Crypto.Util import number

resp = requests.get('https://cryptohack.org/static/challenges/output_0ef6d6343784e59e2f44f61d2d29896f.txt')

lines = resp.text.splitlines()

params = []

for i in range(0, len(lines), 5):
n = int(lines[i].split(' ')[-1])
e = int(lines[i+1].split(' ')[-1])
c = int(lines[i+2].split(' ')[-1])
params.append([n, c])

def solve(ns, cs):
M = reduce(operator.mul, ns)
Mi = [M//n for n in ns]
ti = [pow(Mi, -1, n) for Mi, n in zip(Mi, ns)]
x = sum([c*t*m for c, t, m in zip(cs, ti, Mi)]) % M
r, exact = gmpy2.iroot(x, 3)
if exact:
return r

for cb in combinations(params, 3):
ns = [x[0] for x in cb]
cs = [x[1] for x in cb]
r = solve(ns, cs)
if r == None:
continue
print(number.long_to_bytes(r))

Infinite Descent

根據它生成ppqq 的函數可以看出兩個的差應該不大,因為是先生成一個比較大的數之後再往上加直到是質數為止,而這種情況下能用的是 Fermat’s factorization method。這個的的算法蠻短的,可以直接用 Sage 裡面的函數簡單實作或是直接用 RsaCtfTool 裡面的就可以了。

Marin’s Secrets

看它的質數生成方法可以明顯的看出它是 Mersenne prime,即形式為2p12^p-1 的質數。這類型的質數最大的問題是數量不多,很容易直接暴力破解,而且計算又快。

用 Sage 的解法非常短:

1
2
3
4
n = # ...
# OEIS A000668 = Mersenne primes
p, q = [p for p in sloane.A000668.list(20) if n % p == 0]
assert(p * q == n)

RsaCtfTool 也是能解這題的。

Fast Primes

稍微查一下它的生成方法可以找到 ROCA,不過用 RsaCtfTool 裡面的不知為何解不開,所以找了另一個版本的 Sage ROCA,在我的電腦上花三分多鐘才分解出ppqq

不想跑或是電腦跑不動的可以直接上 FactorDB

然後解密時要注意一下,要按照原本的 script 的加密方法反過來解,不要直接把 hex string 當數字直接解。

Ron was Wrong, Whit is Right

題目給了一大堆 key 和 ciphertext,然後查一下題目名稱會找到一篇文章,大致上是在說當兩個 key 的 N 共享了同個質數的話問題會很大,因為當N1=pqN_1=pqN2=prN_2=pr 的情況下有gcd(N1,N2)=p\gcd(N_1,N_2)=p,所以一下子就分解完了。

所以合理推測這個題目裡面大概有些 key 使用了相同的pp,所以就寫個腳本來試試看,也真的能找到 flag。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from itertools import combinations
from math import gcd

keys = []
for i in range(1, 51):
with open(f'{i}.pem') as f:
keys.append((i, RSA.import_key(f.read())))

for (i, k1), (j, k2) in combinations(keys, 2):
p = gcd(k1.n, k2.n)
if p == 1:
continue
q1 = k1.n//p
q2 = k2.n//p
pk1 = RSA.construct((k1.n, k1.e, pow(k1.e, -1, (p-1)*(q1-1)), p, q1))
pk2 = RSA.construct((k2.n, k2.e, pow(k2.e, -1, (p-1)*(q2-1)), p, q2))
with open(f'{i}.ciphertext') as f:
print(PKCS1_OAEP.new(pk1).decrypt(bytes.fromhex(f.read())))
with open(f'{j}.ciphertext') as f:
print(PKCS1_OAEP.new(pk2).decrypt(bytes.fromhex(f.read())))

RSA Backdoor Viability

這題看他的程式碼會發現它的質數pp 符合427s2+14\frac{427s^2+1}{4} 的格式,單這個並看不出什麼。之後去查一下這個題目名稱會查到一些相關的論文,之後篩選之後我找到了這三篇,依先後排序:

這三篇討論4p1=Ds24p-1=Ds^2 形式有關的質數pp 的分解方法,第一篇的方法在 RsaCtfTool 裡面裡面被稱為 qicheng,不過它的DD 不包含427427,所以無法處裡。

第二篇是第一篇的推廣裡面有包含427427,不過427427 似乎是屬於在某種二次多項式有關的類別中,所以似乎沒辦法透過修改原本的 qichenge 方法來解,而它也沒有提供 implementation。

第三篇是前兩篇的進一步推廣,可以處裡更多的DD,而且還有提供 implementation 直接能用(用 Sage),不過需要你知道DD 的值為多少才能處裡。

使用的話可能要修一下 indentation 的問題還有一個整數除法的問題才能正常使用,不過一下子就分解出來了。

修正方法可以參考這個 commit

Bespoke Padding

這題我們可以得到無限組使用同組 public key,但 padding 不同的密文,而它 padding 的方法是ax+bax+b,所以取兩組密文的話我們可以得到以下的方程式

(a1m+b1)ec1(modN)(a_1*m+b_1)^e\equiv c_1\pmod{N}

(a2m+b2)ec2(modN)(a_2*m+b_2)^e\equiv c_2\pmod{N}

經過整理後可以得到下面的兩個多項式:

f(x)=(a1x+b1)ec1f(x)=(a_1*x+b_1)^e-c_1

g(x)=(a2x+b2)ec1g(x)=(a_2*x+b_2)^e-c_1

我們知道它有兩組方程式都有個根mm,所以都會有因式xmx-m,而這個因式可以透過 gcd 得到,然後也就得到mm 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from sage.all import *
from pwn import *
import json
from Crypto.Util.number import long_to_bytes

def getData():
s = json.dumps({"option": "get_flag"})
p = remote("socket.cryptohack.org", 13386)
p.recvuntil(b"flag.\n")
p.sendline(s)
d1 = json.loads(p.recvline())
p.sendline(s)
d2 = json.loads(p.recvline())
p.close()
return d1, d2

def extract(d):
return d["encrypted_flag"], d["modulus"], d["padding"][0], d["padding"][1]

e = 11
d1, d2 = getData()
c1, n, a1, b1 = extract(d1)
c2, n, a2, b2 = extract(d2)

z = Zmod(n)
P = PolynomialRing(z, "m")
m = P.gen()

f = (a1 * m + b1) ** e - c1
g = (a2 * m + b2) ** e - c2

def gcd(g1, g2):
# Sage doesn't have gcd for polynomial ring
while g2:
g1, g2 = g2, g1 % g2
return g1.monic()

r = m - gcd(f, g)
print(long_to_bytes(r))

Null or Never

這題的 padding 是直接在 message 的右邊補一堆 0,直到長度為 100 bytes,所以可以寫成(m0x100100l)ec(modN)(m*\mathtt{0x100}^{100-l})^e\equiv c\pmod{N},其中的 l 是 flag 的長度。這個基本上可以透過 Coppersmith’s method 讓它去求比較小的根而找到 m,不過經過測試會發現單純這樣所產生的多項式沒辦法找到解,因為這題的 flag 似乎比較長,不符合x<N1/ex<N^{1/e},所以沒辦法單純的使用這個方法去找。

不過這題是找 flag,所以知道它的格式是 crypto{x} 的格式,所以可以弄出一個不同的多項式,裡面的 x 只需要找比較小的部分,說不定就能在 Coppersmith’s method 的範圍內了,然後經過測試這個方法也確實沒問題。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from Crypto.Util.number import bytes_to_long, long_to_bytes

n = 95341235345618011251857577682324351171197688101180707030749869409235726634345899397258784261937590128088284421816891826202978052640992678267974129629670862991769812330793126662251062120518795878693122854189330426777286315442926939843468730196970939951374889986320771714519309125434348512571864406646232154103
e = 3
c = 63476139027102349822147098087901756023488558030079225358836870725611623045683759473454129221778690683914555720975250395929721681009556415292257804239149809875424000027362678341633901036035522299395660255954384685936351041718040558055860508481512479599089561391846007771856837130233678763953257086620228436828
Z = Zmod(n)
P.<x> = PolynomialRing(Z)
# In pure python:
# P = PolynomialRing(Z, 'x')
# x = P.gen()


def crack(l): # l = length of x in crypto{x}
prefix = b"crypto{"
top = bytes_to_long(prefix + b"\x00" * (100 - len(prefix)))
suffix = b"}"
bottom = bytes_to_long(suffix + b"\x00" * (100 - len(prefix) - l - len(suffix)))
f = (top + x * (0x100 ** (100 - len(prefix) - l)) + bottom) ** e - c
return f.monic().small_roots(X=1 << (l * 8))


for i in range(1, 50):
r = crack(i)
if len(r) > 0:
print(b"crypto{" + long_to_bytes(r[0]) + b"}")

Signing Server

這題很簡單,因為它都提供了你 sign 的函數能讓你計算xdmodNx^d\mod{N} 了,所以把得到的memodNm^e\mod{N} 放進去之後自然就得到 flag 了,不過是 16 進位的數字,所以稍微轉換一下就好了。

Let’s Decrypt

這題讀一下程式碼可以得知這些東西:

1
2
3
4
SIG = encode(MSG)^D % N
calculated_digest = SIG^e % n
digest = encode(msg)
need digest == calculated_digest

裡面的大寫的都是它本來就有的,小寫的是我們能控制的

接下來整理一下可以簡化成msg=SIGemodn\mathtt{msg}=\mathtt{SIG}^e\mod{n},裡面的eennmsgmsg 都是我們能控制的。然後要得到 flag 的條件是要讓msgmsg 符合某個 regex 才行。

首先是當e=1e=1 的情況會有msg=SIGmodn\mathtt{msg}=\mathtt{SIG}\mod{n},所以只要找到nn 就好了,而nn 需要符合下面的兩個條件n(SIGm)n\vert(\mathtt{SIG}-m)n>mn>m 才行。

實際上算算看會發現最簡單的nn 就是直接取MSGmMSG-m,直接符合上面的兩個條件,不過想用 z3 去算也是可以,它也能很快的找出結果來。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from pwn import *
import json
from pkcs1 import emsa_pkcs1_v15
from Crypto.Util.number import bytes_to_long

p = remote("socket.cryptohack.org", 13391)
print(p.recvline())
p.sendline(json.dumps({"option": "get_signature"}))
sig = json.loads(p.recvline().decode())
print(sig)
SIG = int(sig["signature"], 16)

msg = b"I am Mallory C8763 own CryptoHack.org"
m = bytes_to_long(emsa_pkcs1_v15.encode(msg, 256))
N = SIG - m

p.sendline(
json.dumps({"option": "verify", "N": hex(N), "e": "0x1", "msg": msg.decode()})
)
print(p.recvline())

Blinding Light

它這次只讓你提供 msg 和 sig,而 pubkey 本身都是固定的,而 sign 的地方除了 ADMIN_TOKEN 以外都讓你 sign。既然如此我們的目標就是想辦法繞過它很直接的檢查要 sign 的訊息是不是 ADMIN_TOKEN,所以檢查一下 bytes_to_long(ADMIN_TOKEN) 看看能不能分解,結果正好能分成兩個質數。

因為(ab)dmodn=((admodn)×(bdmodn))modn(ab)^d\mod{n}=((a^d\mod{n})\times(b^d\mod{n}))\mod{n},所以分開 sign 之後乘起來再modn\mod{n} 就能得到 signed 的 ADMIN_TOKEN 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from pwn import *
import json

p = remote("socket.cryptohack.org", 13376)
p.recvline()
p.sendline(json.dumps({"option": "get_pubkey"}))
pubkey = json.loads(p.recvline().decode())


def sign(m):
h = hex(m)[2:]
if len(h) % 2 == 1:
h = "0" + h
p.sendline(json.dumps({"option": "sign", "msg": h}))
r = json.loads(p.recvline().decode())
print(r)
return int(r["signature"], 16)


ADMIN_TOKEN = b"admin=True"
[a, b] = [211578328037, 2173767566209] # a*b == bytes_to_long(ADMIN_TOKEN)

token_signature = (sign(a) * sign(b)) % int(pubkey["N"], 16)

p.sendline(
json.dumps(
{
"option": "verify",
"msg": ADMIN_TOKEN.hex(),
"signature": hex(token_signature),
}
)
)
print(p.recvline())

這題除了把 token 分解以外之後還有個方法是把 token 加上 n,因為(token+n)dmodn=tokenmodn(\mathtt{token}+n)^d\mod{n}=\mathtt{token}\mod{n}。 (由 mod 可以移入次方中的性質或是直接展開多項式都能得到)

Vote for Pedro

這題基本上能控制的只有 msg,並且要讓msg3target(modN)\mathtt{msg}^3\equiv\mathtt{target}\pmod{N},不過它的 target 只會取 null byte 分隔之後的最後一個區塊而已,所以有不少的操作空間。

再來是我們發現 bytes_to_long(b"\x00VOTE FOR PEDRO")**3 的值遠遠小於NN,所以如果加點東西上去之後應該也是沒問題的。把modN\mod{N} 當沒看見,整理一下會得到以下的方程式:

1
2
3
4
5
6
7
msg = b"\x00VOTE FOR PEDRO"
msgn = bytes_to_long(msg)
b = 0x100 ** len(msg)
x, p = var("x p")
assume(x, 'integer')
assume(p, 'integer')
print(x * x * x == msgn + b * p)

最後的方程式是個丟番圖方程,不過 Sage 裡面的 solver 沒辦法解開,因為 sympy 裡面並沒有 cubic_thue 類別的求解器。但是 Sage 並不是什麼唯一的求解方法,把得到的方程丟上去 WolframAlpha 之後它直接給你了通解,找個 X 比較小的解出來就好了。

Let’s Decrypt Again

這題是前面的 Let’s Decrypt 的延伸,不過這次簡化後變成有三個方程式要處裡:

k0=SIGe0modnk_0=\mathtt{SIG}^{e_0}\mod{n}

k1=SIGe1modnk_1=\mathtt{SIG}^{e_1}\mod{n}

k2=SIGe2modnk_2=\mathtt{SIG}^{e_2}\mod{n}

裡面的kik_i 是要得到的目標訊息,nneie_i 都是可以自己決定的,不過nn 只能設定一次,所以不能像前面一樣直接設e=1e=1 處裡。所以需要想辦法找個nn,和有個固定nn 的情況下能找到eie_i 的方法。

首先是那個nn 很明顯要符合n>kin>k_i,而找eie_i 的這個問題是 Discrete Logarithm Problem,而這類問題有個
Pohlig–Hellman algorithm
可以在nn 是光滑數(可以分解成很多小質數的一個數)的情況下快速的算出 log。

所以固定好nn,確定它會大於kik_i 後再去拿 suffix,之後算出kik_i 的質後用求出eie_i,最後得到sis_i 做 xor 後就能得到 flag 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
from pwn import *
import json
from Crypto.Util.number import bytes_to_long
from pkcs1 import emsa_pkcs1_v15
from sage.all import Zmod, discrete_log

BIT_LENGTH = 768

p = remote("socket.cryptohack.org", 13394)
p.recvline()
p.sendline(json.dumps({"option": "get_signature"}))
SIG = int(json.loads(p.recvline().decode())["signature"], 16)

# Randomly chosen smooth p^k so that Pohlig–Hellman will work (If p is too small, it is likely that discrete_log will fail)
N = 97 ** 200
p.sendline(json.dumps({"option": "set_pubkey", "pubkey": hex(N)}))
suffix = json.loads(p.recvline().decode())["suffix"].encode()

m0 = b"This is a test for a fake signature." + suffix
m1 = b"My name is kirito and I own CryptoHack.org" + suffix
m2 = b"Please send all my money to 3FZbgi29cpjq2GjdwV8eyHuJJnkLtktZc5" + suffix


def encode(m):
return bytes_to_long(emsa_pkcs1_v15.encode(m, BIT_LENGTH // 8))


k0 = encode(m0)
k1 = encode(m1)
k2 = encode(m2)

assert k0 < N
assert k1 < N
assert k2 < N

Z = Zmod(N)
ZS = Z(SIG)
e0 = discrete_log(Z(k0), ZS)
e1 = discrete_log(Z(k1), ZS)
e2 = discrete_log(Z(k2), ZS)


def claim(msg, e, index):
p.sendline(
json.dumps(
{"option": "claim", "msg": msg.decode(), "e": hex(e), "index": index}
)
)
return bytes.fromhex(json.loads(p.recvline().decode())["secret"])


def xor(a, b):
assert len(a) == len(b)
return bytes(x ^ y for x, y in zip(a, b))


s0 = claim(m0, e0, 0)
s1 = claim(m1, e1, 1)
s2 = claim(m2, e2, 2)

# flag ^ s0 ^ s1 == s2
flag = xor(xor(s2, s1), s0)
print(flag)

ELLIPTIC CURVES

Point Negation

因為是要找相反的點,所以 y 改負的就好了,不過因為是在GF(p)GF(p) 下的運算所以負的要加回正的。

Point Addition

實作一下就好了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
a = 497
b = 1768
p = 9739

O = (0, 0)

def div(u, v):
return u*pow(v, -1, p)

def add(P, Q):
if P == O:
return Q
if Q == O:
return P
if P[0] == Q[0] and (P[1]+Q[1]) % p == 0:
return O
if P != Q:
l = div(Q[1]-P[1], Q[0]-P[0]) % p
else:
l = div(3*P[0]**2+a, 2*P[1]) % p
x = l**2-P[0]-Q[0]
y = l*(P[0]-x)-P[1]
return (x % p, y % p)

X = (5274, 2841)
Y = (8669, 740)
print(add(X, Y))
print(add(X, X))

P = (493, 5564)
Q = (1539, 4742)
R = (4403, 5202)
print(add(add(add(P, P), Q), R))

或是用 Sage 也可以:

1
2
3
4
5
6
F = GF(9739)
C = EllipticCurve(F, [497, 1768])
P = C(493,5564)
Q = C(1539,4742)
R = C(4403,5202)
print(P + P + Q + R)

Scalar Multiplication

用剛剛的 add 函數繼續實作整數乘法而已,很簡單:

1
2
3
4
5
6
7
8
9
10
11
def mul(P, s):
if s == 1:
return P
Y = mul(P, s//2)
X = add(Y, Y)
if s % 2 == 1:
X = add(X, P)
return X

P = (2339, 2213)
print(mul(P, 7863))

Sage 的話直接用乘的就 ok:

1
C(2339, 2213) * 7863

Curves and Logs

前一題的簡單延伸

1
2
3
4

from hashlib import sha1

print(sha1(str(mul((815, 3190), 1829)[0]).encode()).hexdigest())

Efficient Exchange

這題關於在GF(p)GF(p)y2y^2yy 的方法需要前面 Quadratic ResiduesLegendre Symbol 兩題的知識。

1
2
3
4
5
6
x = 4726
y_2 = (x**3 + a*x+b) % p
y = pow(y_2, (p+1)//4, p) # p = 3 (mod 4)
assert((y**2) % p == y_2)
shared_secret = mul((x, y), 6534)[0]
print(shared_secret)

Smooth Criminal

關於 DLP 的簡單介紹: Discrete Logarithm ProblemElliptic Curve Discrete Logarithm Problem

這題的題目名稱就已經提示了 Smooth,而一個數字被稱作 Smooth 的意思代表它能被分解成比較小的質數的乘積,一個數字叫 k-smooth 代表它所有的質因數都<=k<=k

再來是一個有限域上的橢圓曲線的點可以構成一個循環群,而這個群中的元素個數叫 Order。若 Order 是 Smooth 的話存在一個比較好的算法可以讓你去算 DLP(類似除法),叫 Pohlig Hellman Algorithm,而 Sage 裡面的 DLP 預設算法就是用這個算的,所以在 Sage 裡面很容易就能算出這題的 Private key (兩個人的都可以),然後就能得到 flag。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import hashlib

p = 310717010502520989590157367261876774703
a = 2
b = 3

F = GF(p)
C = EllipticCurve(F, [a, b])
print(prime_factors(C.order())) # Smooth

G = C(179210853392303317793440285562762725654,
105268671499942631758568591033409611165)
P = C(280810182131414898730378982766101210916,
291506490768054478159835604632710368904)
B = C(272640099140026426377756188075937988094,
51062462309521034358726608268084433317)

# Pohlig Hellman Algorithm + Baby step giant step
n_my = discrete_log(P, G, operation='+')

S = n_my*B
print(S)
shared_secret = S[0]

key = hashlib.sha1(str(shared_secret).encode()).digest()[:16]
iv = bytes.fromhex('07e2628b590095a5e332d397b8a59aa7')
aes = AES.new(key, AES.MODE_CBC, iv)
cipherText = bytes.fromhex(
'8220b7c47b36777a737f5ef9caa2814cf20c1c1ef496ec21a9b4833da24a008d0870d3ac3a6ad80065c138a2ed6136af')
print(unpad(aes.decrypt(cipherText), 16))

Exceptional Curves

這題的 title 可以查到一個論文,只是那個方法基本上和這題無關,反而要去找其他方法才能處裡,向是我是在這篇找到解決這題的方法的,因為這題的特點是 curve 的 order 和 field 的 order 是相同的,正好可以使用一個叫做 SMART Attack 的方法去在線性時間內解決 DLP。

需要使用這個方法可以使用這邊使用的 Sage code: Why Smart’s attack doesn’t work on this ECDLP?

或是也可以使用 elliptic-shiho/ecpy 所提供的實現也可以

像是使用上面的解答的 code 大概就像下方這樣就能算出 DLP 了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
p = 0xA15C4FB663A578D8B2496D3151A946119EE42695E18E13E90600192B1D0ABDBB6F787F90C8D102FF88E284DD4526F5F6B6C980BF88F1D0490714B67E8A2A2B77
a = 0x5E009506FCC7EFF573BC960D88638FE25E76A9B6C7CAEEA072A27DCD1FA46ABB15B7B6210CF90CABA982893EE2779669BAC06E267013486B22FF3E24ABAE2D42
b = 0x2CE7D1CA4493B0977F088F6D30D9241F8048FDEA112CC385B793BCE953998CAAE680864A7D3AA437EA3FFD1441CA3FB352B0B710BB3F053E980E503BE9A7FECE

F = GF(p)
E = EllipticCurve(F, [a, b])
assert E.order() == p

G = E(
0x39F15E024D44228FD11C58A71C312FD64167C7D249D5677DA0DFB4B9C3ED0F90701837A5E77B5A2B74433D7FBE027CD0C73B5AA7B300F7384521AF0DC283DC6D,
0x5F3636A89167A6FBB7B7D1AD97D11C70756835B5F1273E20C06D9E022D74648EC22A3F92C378196D137C3F2027A67381BE79E1C0D65CD9B61211A77A3842C8B2,
)
A = E(
0x5AA8B5CF3124C552881BA67C14C863BB2FF30D960FE41B61123D2025CDDDF0EA75E92D76326BE9FB09B9A32373FC278AC8D5CF5CA83B9E517CE347C6879BEF51,
0x2E3DDEC1B35930B1039351B2814252186B30CE27CE15EDA4351428868AE8593AB8C61C034BA10041CCE205D7F7102C292F30AC5F3D2A2C2F3A463D837DF070CD,
)
B = E(
0x7F0489E4EFE6905F039476DB54F9B6EAC654C780342169155344ABC5AC90167ADC6B8DABACEC643CBE420ABFFE9760CBC3E8A2B508D24779461C19B20E242A38,
0xDD04134E747354E5B9618D8CB3F60E03A74A709D4956641B234DAA8A65D43DF34E18D00A59C070801178D198E8905EF670118C15B0906D3A00A662D3A2736BF,
)


def SmartAttack(P, Q, p):
E = P.curve()
Eqp = EllipticCurve(Qp(p, 2), [ZZ(t) + randint(0, p) * p for t in E.a_invariants()])

P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
for P_Qp in P_Qps:
if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
break

Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
for Q_Qp in Q_Qps:
if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
break

p_times_P = p * P_Qp
p_times_Q = p * Q_Qp

x_P, y_P = p_times_P.xy()
x_Q, y_Q = p_times_Q.xy()

phi_P = -(x_P / y_P)
phi_Q = -(x_Q / y_Q)
k = phi_Q / phi_P
return ZZ(k)


nA = SmartAttack(G, A, p)
nB = SmartAttack(G, B, p)

assert nA * G == A
assert nB * G == B

這題還有個比較不一樣的解法是利用兩個 group 是同構的這個性質,想辦法找個映射把曲線上的點轉換到Fp\mathbf F_p 的加法群,這樣的話原本困難的 DLP 就能變成簡單的計算 mod inverse 的問題。

首先是先要把曲線上的點PP 表示為[P,α][P, \alpha] 一樣的形式,其中的α\alphaFp\mathbf F_p 的一個數。接下來定義它的加法為

[P,α]+[Q,β]=[P+Q,α+β+a0(P,Q)][P, \alpha]+[Q,\beta]=[P+Q,\alpha+\beta+a_0(P,Q)]

a0a_0 是一個函數代表的是過PPQQ 兩點的直線斜率,如果P=QP=Q 則給切線斜率,若P=QP=-Q 或是有任一點是無窮遠點的時候就回傳00

接下來可以定義ϕ(P)=α\phi(P)=\alpha 的函數代表那個映射:

p[P,0]=[O,α]p[P, 0]=[O,\alpha]

他是先從[P,0][P,0] 開始,然後做用加法定義的純量乘法,然後因為是在 orderpp 的 group 之下所以pP=OpP=O,而後面那項α\alpha 就是ϕ(P)\phi(P) 的值。

這種情況下的 DLPA=kBA=kB 就能用下面的方法解決了:

ϕ(A)=ϕ(kB)=kϕ(B)\phi(A)=\phi(kB)=k\phi(B)

所以

k=ϕ(A)ϕ(B)1k=\phi(A)\phi(B)^{-1}

此方法來自 solution 裡面看到的不同做法,不是我想出來的,可以在Attacks on the Elliptic Curve Discrete Logarithm Problem找到更詳細的說明 (Semaev’s Isomorphism)

Elliptic Nodes

這題雖然沒有給aabb,但是因為有兩點GGPP 所以很容易解聯立方程找出參數,然後用 Pohlig Hellman 去算 DLP 就好了(p1p-1 正好是 smooth 的)。本來應該是這樣的…

實際上解出aabb 之後會發現它根本沒辦法弄出橢圓曲線,因為4a3+27b2=04a^3+27b^2=0 所以這條其實是 singular 的。一條 singular 的橢圓曲線除了上面 singular 的點以外還是能用一般的橢圓曲線加法去構造出一個群,但是在密碼學上根本不會使用 singular 的曲線,這是因為這類的曲線有辦法找到 isomorphism 把點轉到 DLP 比較好計算的 group 去。Source

singular 的曲線基本上可以分成二重根和三重根的兩種,有不同的 mapping 方法可以做到,而這題是二重根的情況,可以參考這個問題的回答去做就好了。

這種方法在 Elliptic Curves: Number Theory and Cryptography 的 2.10 章有比較詳細的說明,含證明

它的方法簡單來說就是對於y2=(xα)2(xβ)y^2=(x-\alpha)^2(x-\beta) 的橢圓曲線有辦法用下面的映射做轉換,然後 DLP 就會變的比較簡單:

(x,y)y+αβ(xα)yαβ(xα)(x,y)\mapsto\frac{y+\sqrt{\alpha-\beta}(x-\alpha)}{y-\sqrt{\alpha-\beta}(x-\alpha)}

其實可以注意到分子和分母正好和x=αx=\alpha 時的切線方程式有關係,然後如果αβ\sqrt{\alpha-\beta}Fp\mathbf F_p 下不存在的話會變成映射會變的比較麻煩,不過和這題無關

解這題的 Sage code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
p = 4368590184733545720227961182704359358435747188309319510520316493183539079703
F = GF(p)
gx = F(8742397231329873984594235438374590234800923467289367269837473862487362482)
gy = F(225987949353410341392975247044711665782695329311463646299187580326445253608)
px = F(2582928974243465355371953056699793745022552378548418288211138499777818633265)
py = F(2421683573446497972507172385881793260176370025964652384676141384239699096612)

a = ((gy ^ 2 - py ^ 2) - (gx ^ 3 - px ^ 3)) / (gx - px)
b = gy ^ 2 - (gx ^ 3 + a * gx)
print(a, b)

D = 4 * a ^ 3 + 27 * b ^ 2
assert D == 0 # Singular, double or triple root on 0 = x^3 + ax + b

P.<x> = F[]
f = x ^ 3 + a * x + b
ff = f.factor()
print(ff)

r = F(ff[1][0] - x)
f = f.subs(x=x - r) # Makes (x + r) -> x
ff = f.factor()
print(ff) # x^2*(x-r)

a = ff[0][0] - x
print(a)
assert kronecker(a, p) == 1
k = sage.rings.finite_rings.integer_mod.square_root_mod_prime(Mod(a, p), p)
assert k ^ 2 == a
print(k)


def maps(x, y):
x = x + r
return (y + k * x) / (y - k * x)


mg = maps(gx, gy)
mp = maps(px, py)
n = discrete_log(mp, mg)
print(n)

from Crypto.Util.number import long_to_bytes

print(long_to_bytes(n))

Moving Problems

這題題目就有提示了 Moving,介紹中也有 pairing 出現,去查一下可以查到 MOV Attack

Pairing 的介紹可以參考 Exploring Elliptic Curve Pairings,簡單來說把它想成一個特別的雙線性映射就好了,符合e(aP,Q)=e(P,Q)ae(aP,Q)=e(P,Q)^ae(P,bQ)=e(P,Q)be(P,bQ)=e(P,Q)^b

這題的話是因為曲線的 embedding degree 只有 2,所以找 pairing 是容易達成的事,之後可以計算e(P,Q)=e(nG,Q)=e(G,Q)ne(P,Q)=e(nG,Q)=e(G,Q)^ne(G,Q)e(G,Q),然後 DLP 就被化簡了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
p = 1331169830894825846283645180581
a = -35
b = 98
E = EllipticCurve(GF(p), [a, b])
G = E.gens()[0]
A = E(1110072782478160369250829345256, 800079550745409318906383650948)
B = E(1290982289093010194550717223760, 762857612860564354370535420319)


def find_embedding_degree(E):
p = E.base().order()
n = E.order()
for k in range(1, 12):
if (p ^ k - 1) % n == 0:
return k


def mov_attack(E, P, G):
k = find_embedding_degree(E)
K.<a> = GF(p**k)
EK = E.base_extend(K)
PK = EK(P)
GK = EK(G)
QK = EK.random_point() # Assuming QK is linear independent to PK
egqn = PK.tate_pairing(QK, E.order(), k) # e(P,Q)=e(G,Q)^n
egq = GK.tate_pairing(QK, E.order(), k) # e(G,Q)
return egqn.log(egq)


nA = mov_attack(E, A, G)
assert nA * G == A
print(nA)

一些可能有用的其他資源:

Curveball

這個題目的問題還蠻明顯的,就是要想辦法生出一組自己決定的 private key 和 generator 使得nG=PnG=PPP 是目標的 public key。至於生成方法也很簡單,利用nP=OnP=O 的性質就好了,其中的nn 是 group order 而PP 是曲線上一點。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
a = -3
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951

target = (
0x3B827FF5E8EA151E6E51F8D0ABF08D90F571914A595891F9998A5BD49DFA3531,
0xAB61705C502CA0F7AA127DEC096B2BBDC9BD3B4281808B3740C320810888592A,
)

E = EllipticCurve(GF(p), [a, b])
priv = E.order() + 1
P = E(*target)
assert P * priv == P

import json

print(
json.dumps(
{
"private_key": int(priv),
"host": "c8763",
"curve": "no",
"generator": list(map(int, target)),
}
)
)

ProSign 3

這題的關鍵是它在取得時間的時候會把 global 的 n 給蓋掉,所以 k = randrange(1, n) 的值是可以知道的,然後根據維基百科所說的方法就能找到 private key。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# Get a signed time, and keep the connection
data = {
"msg": "Current time is 1:2",
"r": "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012",
"s": "0x40172380812cba86fa2f7a24ad9e40a8a6d5eb63a2574e6b",
}

import hashlib
from Crypto.Util.number import bytes_to_long, long_to_bytes
from ecdsa.ecdsa import Public_key, Private_key, Signature, generator_192


def sha1(data):
sha1_hash = hashlib.sha1()
sha1_hash.update(data)
return sha1_hash.digest()


g = generator_192
n = g.order()

z = bytes_to_long(sha1(data["msg"].encode()))
s = int(data["s"], 16)
r = int(data["r"], 16)
sig = Signature(r, s)
possible_pubs = sig.recover_public_keys(z, g)
k = 1 # Guess this by time, or bruteforcing works too
d = ((s * k - z) * pow(r, -1, n)) % n
print(d)

pub = Public_key(g, g * d)
assert pub in possible_pubs
print(pub.point.to_affine())
priv = Private_key(pub, d)
msg = "unlock"
sig = priv.sign(bytes_to_long(sha1(msg.encode())), 1)

import json

print(json.dumps({"option": "verify", "msg": msg, "r": hex(sig.r), "s": hex(sig.s)}))

Edwards Goes Degenerate

這題是和 Twisted Edwards curve 有關的題目,即形式為ax2+y2=1+dx2y2ax^2+y^2=1+dx^2y^2 的曲線,而它們和某類的橢圓曲線 birationally equivalent。 (這可視為幾乎是同構的,詳見)

然後根據標題我查到了這篇,讀了一下會發現它所說的 degenerate 是指這類曲線的加法在(0,y)(0,y) 的情況。因為(0,y1)+(0,y2)=(0,y1y2)(0,y_1)+(0,y_2)=(0,y_1y_2)n(0,y)=(0,yn)n(0,y)=(0,y^n),所以原本橢圓曲線的效果就不見了,整個變成了FpF_p 上的 DLP 問題。

然後簡單的檢查一下會發現說它的 curve.decompress(curve.base_point) 的結果正好是(0,y)(0,y),因為 recover_x 函數裡面的 if x**2 == xsqr : 判斷忘記要 mod,所以都回傳 0。所以這個題目就直接 DLP 下去解決就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
from Crypto.Util.number import inverse, bytes_to_long
from random import randint


class TwistedEdwards:
# Elliptic curve in Edwards form:
# -x**2 + y**2 = 1 + d*x**2*y**2
# birationally equivalent to the Montgomery curve:
# y**2 = x**3 + 2*(1-d)/(1+d)*x**2 + x

def __init__(self, p, d, order, x0bit, y0):
self.p = p
self.d = d
self.order = order
self.base_point = (x0bit, y0)

def recover_x(self, xbit, y):
xsqr = (y ** 2 - 1) * inverse(1 + self.d * y ** 2, self.p) % self.p
x = pow(xsqr, (self.p + 1) // 4, self.p)
if x ** 2 == xsqr:
if x & 1 != xbit:
return p - x
return x
return 0

def decompress(self, compressed_point):
xbit, y = compressed_point
x = self.recover_x(xbit, y)
return (x, y)

# complete point addition formulas
def add(self, P1, P2):
x1, y1 = P1
x2, y2 = P2

C = x1 * x2 % self.p
D = y1 * y2 % self.p
E = self.d * C * D
x3 = (1 - E) * ((x1 + y1) * (x2 + y2) - C - D) % self.p
y3 = (1 + E) * (D + C) % self.p
z3 = 1 - E ** 2 % self.p
z3inv = inverse(z3, self.p)
return (x3 * z3inv % self.p, y3 * z3inv % self.p)

# left-to-right double-and-add
def single_mul(self, n, compressed_point):
P = self.decompress(compressed_point)
t = n.bit_length()
if n == 0:
return (0, 1)
R = P
for i in range(t - 2, -1, -1):
bit = (n >> i) & 1
R = self.add(R, R)
if bit == 1:
R = self.add(R, P)
return (R[0] & 1, R[1])


p = 110791754886372871786646216601736686131457908663834453133932404548926481065303
order = 27697938721593217946661554150434171532902064063497989437820057596877054011573
d = 14053231445764110580607042223819107680391416143200240368020924470807783733946
x0bit = 1
y0 = 11
curve = TwistedEdwards(p, d, order, x0bit, y0)

print(curve.decompress(curve.base_point)) # (0, 11)

# (0, y1) + (0, y2) = (0, y1 * y2)
# n * (0, y) = (0, y^n)
# So it becomes a discrete logarithm over F_p, and p-1 is smooth too

Ay = 109790246752332785586117900442206937983841168568097606235725839233151034058387
By = 45290526009220141417047094490842138744068991614521518736097631206718264930032

from sage.all import discrete_log, Zmod

Z = Zmod(p)
G = Z(y0)
n_A = int(discrete_log(Z(Ay), G))
n_B = int(discrete_log(Z(By), G))

assert curve.single_mul(n_A, curve.base_point)[1] == Ay
assert curve.single_mul(n_B, curve.base_point)[1] == By

MATHEMATICS

Quadratic Residues

給個列表,問你哪個數字是 Quadratic Residues,即是否存在一個xx 使得x2a(modp)x^2\equiv a\pmod{p}

這題因為pp 很小直接枚舉就好了:

1
2
3
s = set((x * x) % 29 for x in range(29))
ints = set([14, 6, 11])
print(s & int)

Legendre Symbol

這題類似上一題,但是這次的pp 很大,所以要使用到 Legendre symbol 去判斷一個數是不是 Quadratic Residues。這個在 Sage 裡面叫做 kronecker,使用方法見此

判斷出是不是 Quadratic Residues 之後它還要你把xx 算出來,然後給了個提示p3(mod4)p\equiv 3\pmod{4},去查了一下會發現說在這個情況下xap+14(modp)x\equiv a^{\frac{p+1}{4}}\pmod{p} 的。因為x2ap+12ap12×aa(modp)x^2\equiv a^{\frac{p+1}{2}}\equiv a^{\frac{p-1}{2}}\times{a}\equiv a\pmod{p}

Modular Square Root

上一題的延伸,只是這次是p1(mod4)p\equiv 1\pmod{4},所以上面的那個公式沒有用,需要改用 Tonelli–Shanks algorithm,然後這個算法在 Sage 也是有直接能用的函數的:

1
sage.rings.finite_rings.integer_mod.square_root_mod_prime(Mod(a,p),p)

前一題也能用這個函數計算

Chinese Remainder Theorem

中國餘數定理,自己手算或是用其他工具都可以,例如 z3 的解法:

1
2
3
4
from z3 import *
x = Int('x')
solve(x % 5 == 2, x % 11 == 3, x % 17 == 5)
# 然後把得到的 x mod 935 就是答案了

Gram Schmidt

把向量正規化而已,不過記得不要用 numpy 裡面的 QR,因為它會直接把矩陣變成 orthonormal 的,但是題目沒有要你標準化。

What’s a Lattice?

它討論的 Lattice 並不是和偏序集有關的那個,而是和線性代數比較相關的。就我的理解 Lattice 有點類似一個集合的 Span,不過它的係數都只能是整數,所以比較不同。

求 flag 的地方直接 np.linalg.det 下去解決就好了。

Gaussian Reduction

算 R^2 上的 Lattice 的最小基底,它的方法看起來有點類似算正交化的算法和 gcd 結合。

1
2
3
4
5
6
7
8
9
10
11
12
import numpy as np

u = np.array((87502093, 123094980))
v = np.array((846835985, 9834798552))
while True:
if np.linalg.norm(v) < np.linalg.norm(u):
u, v = v, u
m = np.dot(u, v) // np.dot(u, u)
if m == 0:
print(np.dot(u, v))
break
v = v - m * u

注意不要用 np.floor,結果會不同

附個 Sage 算法做參考:

1
2
3
M = matrix([[846835985, 9834798552], [87502093, 123094980]])
ML = M.LLL()
print(ML[0] * ML[1])

Find the Lattice

這題的生成 key、加密與解密流程大致可以表示如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
keygen()=
q is prime
ub=sqrt(q//2)
lb=sqrt(q//4)
f in [2,ub]
g in [lb,ub]
gcd(f,g)=1
h=g/f %q

pub=(q,h)
priv=(f,g)
return pub, priv

encrypt(q,h,m)=(rh+m)%q where r in [2,ub] (requirement: m<lb<g)
decrypt(q,h,f,g,e)=a/f %g where a=(f*e)%q

然後驗證一下正確性:

a(fe)(f(rh+m))(gr+fm)(modq)a\equiv(fe)\equiv(f(rh+m))\equiv(gr+fm)\pmod{q}

mgr+fmfgrf+mm(modg)m\equiv\frac{gr+fm}{f}\equiv\frac{gr}{f}+m\equiv m\pmod{g}

所以要找到這題的私鑰(f,g)(f,g) 需要滿足gcd(f,g)=1\gcd(f,g)=1fgg(modq)fg\equiv g\pmod{q}

沒什麼想法的情況下就去找了一下和 Lattice 有關的加密方法,發現到了一個叫 NTRUEncrypt 的一種加密方法和這個基本上長的很像,只是裡面的參數都是在多項式環上的多項式。

之後再去找找看對於這個加密方法和 Lattice 有關的攻擊方法,找到了 NTRUEncrypt and Lattice Attacks。裡面的第四章就有寫這個加密的 Lattice 長怎樣,而這題似乎是它在N=1N=1 的情形,所以可以產生下面的 basis。

[1h0q]\begin{bmatrix} 1 & h \\ 0 & q \end{bmatrix}

所以就對(1,h)(1,h)(0,q)(0,q) 做 reduction 之後就發現 basis 的其中一個向量的兩個分量正好是(f,g)(f,g),也符合前面要求的條件,所以就能這樣去解密得到 flag。

不過為什麼這樣能成功又是一個問題了,所以試著想辦法利用原本的式子去湊那組 basis 看看:

kZ,fh=qk+g\exists{k}\in\Z, fh=qk+g

f(1,h)=(f,fh)=(f,qk+g)=(f,g)+k(0,q)f(1,h)=(f,fh)=(f,qk+g)=(f,g)+k(0,q)

f(1,h)+k(0,q)=(f,g)f(1,h)+k'(0,q)=(f,g)

所以我們知道(f,g)(f,g)(1,h)(1,h)(0,q)(0,q) 所張的 Lattice 中,然後透過觀察還會發現hqf,g,kh\approx q\gg f,g,k。(不懂的可以看一下生成 key 的函數和它給的數字)

所以我們知道(1,h)(1,h)(0,q)(0,q) 是組很大的 basis,而(f,g)(f,g) 是所張的 Lattice 中的一個比較小的向量,所以 reduce 之後有機會出現(f,g)(f,g)

至於為什麼會正好出現(f,g)(f,g),而不會跑到其他更小的向量我就不清楚了。

Backpack Cryptography

這題是關於 Merkle–Hellman knapsack cryptosystem 的問題,是透過 Subset sum problem 問題來達成 trapdoor 的性質的。

這種密碼可以透過構造 Lattice 來解,像是最原始的版本大概像是下面這樣:

[In×nPn×1O1×nC1×1]\begin{bmatrix} I_{n\times n} & P_{n\times1} \\ O_{1\times n} & -C_{1\times1} \end{bmatrix}

其中的II 是單位矩陣,PP 是 public key,OO 是零矩陣,而CC 是 ciphertext 的值,不過要加個負號。這個其實蠻能直觀理解的,因為CC 比其他的向量都要大,在做 LLL 的時候為了要最小化自然會利用PP 去把C-C 消成 0,然後II 就是用來記錄最後的結果的,所以裡面應該會有一個 row 全部都是 0 和 1,那個就是 subset sum 的解了,也就是 plaintext。

不過這題如果用這個方法構造的是解不出來的,雖然不知道原因是為什麼,去網路上找其他的構造方法就可以了,例如我用的是這篇底下的構造方法解的,最後有一行都會是 -1 和 1,分別代表 1 和 0 然後轉換一下就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import long_to_bytes

pubkey = [...] # Fill this
n = len(pubkey)

I2 = matrix.identity(n) * 2
K = matrix.ones(1, n)
T = matrix(pubkey).T
C = matrix([c])

M = block_matrix([[I2, T], [K, C]])
R = M.LLL()

A = R[:-1, :-1]
valid_rows = [r for r in A if all(x == -1 or x == 1 for x in r)]
for C in valid_rows:
C = [1 if y == -1 else 0 for y in C]
x = 0
for b in C[::-1]:
x |= b
x <<= 1
x >>= 1
print(long_to_bytes(x))

據其他的解法還有一種構造方法是先取N>n2N>\frac{\sqrt{n}}{2},然後再使用下面的矩陣去 LLL,這個是成功率比較高的方法:

[100NP1010NP2001NPn121212NC]\begin{bmatrix} 1 & 0 & \cdots & 0 & NP_1 \\ 0 & 1 & \cdots & 0 & NP_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & \cdots & 1 & NP_n \\ \frac{1}{2} & \frac{1}{2} & \cdots & \frac{1}{2} & NC \end{bmatrix}

然後 LLL 之後的 rows 會有一列整個都是12-\frac{1}{2}12\frac{1}{2},分別代表 1 和 0。

來源: Cryptanalysis of two knapsack public-key
cryptosystems
Page 5

Jack’s Birthday Hash

給定一個固定的 hash,問你至少要有幾個其他的明文能使得其中任何一個的 hash 和那個固定的 hash 碰撞。

因為 hash 的可能值只有211=20482^{11}=2048,所以一個 hash 和它碰撞的機率是p=12048p=\frac{1}{2048},而至少一個碰撞的機率是 1 扣掉全部都沒碰撞的機率,所以要求的是1(1p)n>0.51-(1-p)^n>0.5 的 n,所以能得到n>log204720480.5n>\log_{\frac{2047}{2048}}{0.5}

Jack’s Birthday Confusion

這題是問至少要有幾個 hash 可以使任兩個產生碰撞,所以定義函數p(n)p(n) 代表nn 的 hash 都沒碰撞的機率:

p(n)=(20482048)(20472048)(2048n+12048)p(n)=(\frac{2048}{2048})(\frac{2047}{2048})\cdots(\frac{2048-n+1}{2048})

然後求1p(n)>0.751-p(n)>0.75,即p(n)<0.25p(n)<0.25,所以就寫個程式稍微算一下就好了。

Successive Powers

可以看出an1xan(modp)a_{n-1}x\equiv a_n\pmod{p} 的關係,然後如果用程式解的話可以用 z3 或是直接爆破符合三位數的 p。

數學的解法的話我是先找出這兩條:

492x819(modp)492x\equiv819\pmod{p}

4x836(modp)4x\equiv836\pmod{p}

然後得到

0102009(modp)0\equiv-102009\pmod{p}

因為102009=3×37×979102009=3\times37\times979,所以唯一的p=979p=979,而x=836/4=209x=836/4=209

Adrien’s Signs

這題我的初始解法是觀察到如果 bit 是 1 的話則 discrete_log(x, p) 會有解,否則就是 0,然後就用 sage 去算 200 多次的離散對數問題,反正pp 不大,3 分鐘內可以跑完。雖然我覺得這個解法可能是拿大炮打蚊子,不過我也沒想到更好的解法。

後來看別人的解答發現由於(ap)=1\left(\dfrac{a}{p}\right)=1,所以存在x2a(modp)x^2\equiv a\pmod{p},所以對於(aep)=1\left(\dfrac{a^e}{p}\right)=1 也是成立的。如果是ae-a^e 的情況,則有(aep)=(ae)p12=(ae)p12=(aep)=1(modp)\left(\dfrac{-a^e}{p}\right)=(-a^e)^\frac{p-1}{2}=-(a^e)^\frac{p-1}{2}=-\left(\dfrac{a^e}{p}\right)=-1\pmod{p}。 (p12\frac{p-1}{2} 是奇數)

所以就使用 Legendre Symbol 去算比較快,而它在 Sage 裡面是叫 kronecker(a, p)

Modular Binomials

原本的式子:

N=pqN=pq

c1(2p+3q)e1(modN)c_1\equiv(2p+3q)^{e_1}\pmod{N}

c2(5p+7q)e2(modN)c_2\equiv(5p+7q)^{e_2}\pmod{N}

首先我先尋找符合e1x=e2ye_1x=e_2y 的一組(x,y)(x,y),最簡單的方法就是取e1x=e2y=lcm(e1,e2)=ke_1x=e_2y=\mathrm{lcm}(e_1,e_2)=k

接下來得到新的兩個式子:

c1x(2p+3q)k(modN)c_1^x\equiv(2p+3q)^k\pmod{N}

c2y(5p+7q)k(modN)c_2^y\equiv(5p+7q)^k\pmod{N}

因為N=pqN=pq,所以(ap+bq)k(ap)k+(bq)k(modN)(ap+bq)^k\equiv(ap)^k+(bq)^k\pmod{N}。因此上面的式子就變成一組線性系統可以求解。

[2k3k5k7k][pkqk][c1xc2y](modN)\begin{bmatrix} 2^k & 3^k \\ 5^k & 7^k \end{bmatrix} \begin{bmatrix} p^k \\ q^k \end{bmatrix} \equiv \begin{bmatrix} c_1^x \\ c_2^y \end{bmatrix} \pmod{N}

反矩陣乘過去之後可以得到(pk,qk)(p^k,q^k),然後最後可以算出p=gcd(pk,N)p=\gcd(p^k,N)q=gcd(qk,N)q=\gcd(q^k,N)

Broken RSA

這題e=16e=16,不僅是偶數還是22 的次方。而NN 會發現到是個質數,在算de1(modN1)d\equiv e^{-1}\pmod{N-1} 的時候還會發現gcd(e,N)1\gcd(e, N)\neq1

所以既然沒辦法直接求dd,那就試著用開平方根的方法去做,在 Sage 裡面直接使用 sage.rings.finite_rings.integer_mod.square_root_mod_prime 就能算了。不過應該很快就能發現到直接開四次根所找到的答案並沒辦法得到 flag,這是因為當gcd(e,N)1\gcd(e, N)\neq1 的時候cme(modN)c\equiv m^e\pmod{N} 不保證只有唯一的解,所以這題應該有多個解。

square_root_mod_prime 看起來只能找到一個根,先暫時稱作aa,假設cm2(modN)c\equiv m^2\pmod{N} 除了aa 以外還有個bb 相異根,可以算出a2b2(a+b)(ab)0(modN)a^2-b^2\equiv(a+b)(a-b)\equiv0\pmod{N}。所以當aba\neq b 的時候另一個根就會是b=ab=-a

所以就讓它想辦法把每個分支都跑一遍就能找到全部的根了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from sage.rings.finite_rings.integer_mod import square_root_mod_prime
from Crypto.Util.number import long_to_bytes

n = # ...
e = # ...
ct = # ...

Z = Zmod(n)


def all_roots(k, deg):
if deg == 1:
yield k
return
if kronecker(k, n) != 1:
return
a = square_root_mod_prime(k)
yield from all_roots(a, deg // 2)
yield from all_roots(-a, deg // 2)


for r in all_roots(Z(ct), 16):
s = long_to_bytes(r)
if b"crypto" in s:
print(s)
break

Ellipse Curve Cryptography

這題雖然說是 Ellipse Curve,不過打開程式碼的時候會發現到它的相加和預想中的完全不同,然後看到後面的 assert 就會發現說這反而像是雙曲線一樣:x2Dy21(modp)x^2-Dy^2\equiv1\pmod{p}

經過測試之後看不太出來幾何上有什麼關係,不過可以發現到它的加法確實都有讓點保持在上面,所以這些點可以構成一個群。不過這題的解題目標就是求 private key,就需要想辦法算 discrete log,但是因為不是一般能看到的 group,所以沒辦法讓你直接算,所以只好自己實做看看然後算出來解密了:

註: 這題p1p-1 是 smooth 的,所以用 Polhig-Hellman 效果很好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
from sage.rings.finite_rings.integer_mod import square_root_mod_prime
from collections import namedtuple
from random import randint

Point = namedtuple("Point", "x y")

p = 173754216895752892448109692432341061254596347285717132408796456167143559
D = 529
Z = Zmod(p)
G = Point(
29394812077144852405795385333766317269085018265469771684226884125940148,
94108086667844986046802106544375316173742538919949485639896613738390948,
)
O = Point(1, 0)


def point_addition(P, Q, p=p):
Rx = (P.x * Q.x + D * P.y * Q.y) % p
Ry = (P.x * Q.y + P.y * Q.x) % p
return Point(Rx, Ry)


def scalar_multiplication(P, n, p=p):
Q = O
while n > 0:
if n % 2 == 1:
Q = point_addition(Q, P, p)
P = point_addition(P, P, p)
n = n // 2
return Q


def point_inverse(P, p=p):
return Point(P.x, p - P.y)


A = Point(
155781055760279718382374741001148850818103179141959728567110540865590463,
73794785561346677848810778233901832813072697504335306937799336126503714,
)
B = Point(
171226959585314864221294077932510094779925634276949970785138593200069419,
54353971839516652938533335476115503436865545966356461292708042305317630,
)
enc = {
"iv": "64bc75c8b38017e1397c46f85d4e332b",
"encrypted_flag": "13e4d200708b786d8f7c3bd2dc5de0201f0d7879192e6603d7c5d6b963e1df2943e3ff75f7fda9c30a92171bbbc5acbf",
}


def baby_step_giant_step(b, a, n, m=0):
if m == 0:
m = math.ceil(math.sqrt(n))
else:
m = math.ceil(math.sqrt(m))
tbl = []
for i in range(m):
P = scalar_multiplication(a, i, n)
tbl.append([P.x, i])
print("tbl ok")
aim = point_inverse(scalar_multiplication(a, m, n), n)
y = b
for i in range(m):
for j in range(m):
if y.x == tbl[j][0]:
return i * m + j
y = point_addition(y, aim, n)


GG = Point(2, 26)
PP = 541
AA = scalar_multiplication(GG, 47, PP)
k = baby_step_giant_step(AA, GG, PP)
print(k, AA, scalar_multiplication(GG, k, PP))
# exit()

# Not used in this problem, but I am not sure if this is implemented correctly
# def pollard_rho(kA, G, p):
# n = p - 1

# def xab(x, a, b):
# m = x.x % 3
# if m == 0:
# return point_addition(x, x), (a * 2) % n, (b * 2) % n
# elif m == 1:
# return point_addition(x, G), (a + 1) % n, b
# else:
# return point_addition(x, kA), a, (b + 1) % n

# a, b, x = 0, 0, O
# A, B, X = 0, 0, O
# for i in range(n):
# # print(x, a, b, X, A, B)
# x, a, b = xab(x, a, b)
# X, A, B = xab(X, A, B)
# X, A, B = xab(X, A, B)
# if x.x == X.x:
# r = b - B
# if b == 0:
# return None
# return ((A - a) * pow(r, -1, p)) % p


# print(pollard_rho(scalar_multiplication(G, 2), G, p))


def pohlig_hellman(h, g, n, P=p):
moduli = []
ms = []
for p, e in list(factor(n)):
print(p, e)
a = int(n // (p ** e))
gi = scalar_multiplication(g, a, P)
hi = scalar_multiplication(h, a, P)
xi = baby_step_giant_step(hi, gi, P, p ** e)
moduli.append(p ** e)
ms.append(xi)
print("partial result: ", xi, hi, gi)
print(moduli, ms)
return CRT_list(ms, moduli)


k = pohlig_hellman(AA, GG, PP, PP)
print(k, AA, scalar_multiplication(AA, k, PP))
print(p)
ka = pohlig_hellman(A, G, p - 1)
print("Found: ", ka)
print(G)
print(scalar_multiplication(G, ka))
print(A)

from hashlib import sha1

shared = scalar_multiplication(B, ka).x
key = sha1(str(shared).encode("ascii")).digest()[:16]
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

aes = AES.new(key, AES.MODE_CBC, bytes.fromhex(enc["iv"]))
print(unpad(aes.decrypt(bytes.fromhex(enc["encrypted_flag"])), 16))

後來看其他的做法才發現到x2Dy2(xDy)(x+Dy)1(modp)x^2-Dy^2\equiv(x-\sqrt{D}y)(x+\sqrt{D}y)\equiv1\pmod{p},且D=529=23\sqrt{D}=\sqrt{529}=23。這個情況下可以做u=xDyu=x-\sqrt{D}yv=x+Dyv=x+\sqrt{D}y 的變換把它轉成uv=1uv=1 的情況,且我們知道這個轉換是可逆的。

而這題在D=529=232D=529=23^2 的情況也讓這個轉換一樣保持在Fp×F_p^\times 上,沒有什麼其他問題。然後因為uv1(modp)uv\equiv1\pmod{p} 總共只有p1p-1 個點(模反元素),所以在雙射的情形我們知道原本的 group 也有p1p-1 的點,即 order 為p1p-1,正好和Fp×\mathbb{F}_p^\times 的 order 相同。

所以在這邊合理的猜測是這個 group 和Fp×\mathbb{F}_p^\times 同構,轉換為T:(x,y)u=xDyT: (x,y)\rightarrow u=x-\sqrt{D}y,然後這樣就能使用一般的 discrete log 去計算了。

註: 使用T:(x,y)v=x+DyT: (x,y)\rightarrow v=x+\sqrt{D}y 也可以

額外可以讀的相關文章: https://doi.org/10.1016/j.amc.2020.125537

Unencryptable

這題它給你了mem(modN)m^e\equiv m\pmod{N}mm,即這組 RSA 中的一個 fixed point,這可以改寫為m655361(modN)m^{65536}\equiv1\pmod{N}。這代表了NN 整除了m655361m^{65536}-1,所以m655361m^{65536}-1 裡面肯定有ppqq 存在,只是分解m655361m^{65536}-1 的難度並不比分解NN 簡單…。

第一個關鍵是發現說6553665536 並不是mk1(modN)m^k\equiv 1\pmod{N} 中最小的kk,實際上用用迴圈找一下可以知道它最小的k=512k=512,所以m5121m^{512}-1 裡面也是有ppqq 兩個因數在。

不過這樣還是簡化到分解的問題,因為m5121>Nm^{512}-1>N。所以這邊的第二個關鍵是要發現到x5121x^{512}-1 這個多項式是可以分解成很多項的,用 Sage 可以這樣做:

1
2
3
4
x = var('x')
f = x*512 - 1
print(f.factor())
# (x^256 + 1)*(x^128 + 1)*(x^64 + 1)*(x^32 + 1)*(x^16 + 1)*(x^8 + 1)*(x^4 + 1)*(x^2 + 1)*(x + 1)*(x - 1)

然後我們知道f(m)f(m) 裡面有ppqq 存在,所以分解過的項裡面代入x=mx=m 之後肯定有幾項符合gcd(fs(m),N)>1gcd(f_s(m),N)>1,而那個就是ppqq

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import long_to_bytes, bytes_to_long

N = # ...
e = 0x10001
c = # ...
m = # ...

x = var("x")
f = x ** 512 - 1
nfs = []
for fs, i in f.factor_list():
g = gcd(fs(x=m), N)
if g > 1:
nfs.append(g)
p, q = nfs
assert p * q == N
d = pow(e, -1, (p - 1) * (q - 1))
print(long_to_bytes(pow(c, d, N)))

Real Eisenstein

這題的目標是要找到一組aia_i 使得i=1n2256aipi=c\lfloor{\sum_{i=1}^{n}2^{256}a_i\sqrt{p_i}}\rfloor=c,且aia_i 都是在 ascii 範圍裡面的整數。

我的想法和前面某題和 Knapsack 有關的題目很像,就是想辦法構造一個 Lattice 出來:

L=[12256p112256p212256pn000c]L= \begin{bmatrix} 1 & & & & 2^{256}\sqrt{p_1} \\ & 1 & & & 2^{256}\sqrt{p_2} \\ & & \ddots & & \vdots \\ & & & 1 & 2^{256}\sqrt{p_n} \\ 0 & 0 &\cdots & 0 & -c \end{bmatrix}

存在a=(a1,a2an,1)a=(a_1, a_2\cdots a_n, 1) 使得aL=(a1,a2an,0)aL=(a_1, a_2\cdots a_n, 0),因為是線性組合所以aLaL 也在LL 裡面,是其中的一個比較短的向量,所以用 LLL 有機會得到答案的向量。

不過如果直接這樣算會發現找不到答案,所以可以透過調整些係數,例如我是在LL 的最後一列給它乘一個SS 作為個倍數去調整向量的大小,然後做 LLL 就有辦法找到了。

SS 的值我是很單純的暴力找…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from decimal import *

getcontext().prec = int(100)

PRIMES = primes_first_n(27)
n = len(PRIMES)
c = 1350995397927355657956786955603012410260017344805998076702828160316695004588429433


for scale in range(1500, 5000):
ps = [int((Decimal(int(p)).sqrt() * int(scale * (16 ** 64)))) for p in PRIMES][:n]
I = matrix.identity(n)
P = matrix(ps).T
C = matrix([-c * scale])
O = matrix([0] * n)
M = block_matrix([[I, P], [O, C]])
L = M.LLL()
for r in L:
if abs(r[-1]) == 0 and all(x >= 0 for x in r[:-1]):
print(scale, r)
r = bytes(r[:-1])
if b"crypto" in r:
print(r)
exit()

BLOCK CIPHERS

Passwords as Keys

它有給你字典檔,直接拿那些去爆破就好了。

ECB Oracle

這題和 ECB 的性質有個關係,因為 ECB 對於一樣的輸入都會產生出一樣的輸出,所以可以透過構造 plaintext 去爆破。AES 的 block size 是 128 bits,也就是 16 個 bytes,如果我們先輸入 15 個 bytes 的已知資料(例如塞滿 a),那前密文的前 16 bytes 就是 encrypt(b'a'*15 + FLAG[0]),然後只要靠比較密文相不相同就能爆破 FLAG[0] 出來。

如果要破解 FLAG[1] 的方法也是差不多,就先得到 encrypt(b'a'*14 + FLAT[0] + FLAG[1]),然後利用剛剛得到的 FLAG[0] 去爆破 encrypt(b'a'*14 + FLAT[0] + c) 中的 c,最後相同的話就找到 c 了。

不過這題的 flag 長度是超過 block size 的,所以對於 flag 的後半可能要稍微調整一下才能破解出來,整個整合起來就是下面的腳本了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import requests
import string


def encrypt(b):
resp = requests.get(f"http://aes.cryptohack.org/ecb_oracle/encrypt/" + b.hex())
return bytes.fromhex(resp.json()["ciphertext"])


chrs = [ord(c) for c in '{_}'+string.printable]


def bruteforce(i, prefix=b""):
assert len(prefix) == i
if 15 - i > 0:
expected = encrypt(b"a" * (15 - i))[:16]
else:
expected = encrypt(b"a" * (31 - i))[16:32]
for c in chrs:
if 15 - i > 0:
b = b"a" * (15 - i) + prefix + bytes([c])
if encrypt(b)[:16] == expected:
return bytes([c])
else:
b = b"a" * (31 - i) + prefix + bytes([c])
if encrypt(b)[16:32] == expected:
return bytes([c])


# print(bruteforce(0)) # c
# print(bruteforce(1, b'c')) # r
# print(bruteforce(2, b'cr')) # y

flag = b"crypto{"
for i in range(len(flag), 32):
c = bruteforce(i, flag)
flag = flag + c
print(flag)
if c == b"}":
break

ECB CBC WTF

去維基百科查一下 CBC 會發現它和 ECB 很像,只是初始有多個 iv 而已,所以解密方向很明顯了,就是先把密文拆成 iv 和真正的 ciphertext 兩塊,再來把 ciphertext 丟上去解密得到 xor 過的 plaintext。

之後它的 plaintext 可以分成兩塊,第一塊和 iv 做 xor 就能得到原文了,不過第二塊需要和 ciphertext 的第一塊做 xor 才行,因為 CBC 的第二塊的 iv 就是第一塊的 ciphertext。

在 CBC 裡面 iv 是在兩個地方使用的,一是在 encrypt 前,另一個是 decrypt 才用的,所以你隨便修改 iv 是不會讓解密失敗的,然後這也是這個題目的關鍵。在 CBC 解密之後和 iv xor 前所得到的是plaintextiv\mathrm{plaintext}\oplus\mathrm{iv},然後和原本的 iv xor 之後就得到了 plaintext。

這邊解密之後的iv\mathrm{iv} 是我們所能控制的,假設我們給他了一個ivpayload\mathrm{iv}\oplus\mathrm{payload},之後解密之後就會得到plaintextpayload\mathrm{plaintext}\oplus\mathrm{payload},所以只要我們能構造一個payload\mathrm{payload} 使得adminFalsepayload=adminTrue\mathrm{adminFalse}\oplus\mathrm{payload}=\mathrm{adminTrue} 就搞定了。

所以最終只需要送一個假的iv=adminFalseadminTrueiv\mathrm{iv}'=\mathrm{adminFalse}\oplus\mathrm{adminTrue}\oplus\mathrm{iv} 就能搞定了。

Lazy CBC

這題它會在特定情況下(不能 decode 成 ascii 時)把解密的 plaintext 輸出出來。

下面兩行是 CBC 前兩個 block 的解密公式:

P0=DK(C0)ivP_0=D_K(C_0)\oplus\mathrm{iv}

P1=DK(C1)C0P_1=D_K(C_1)\oplus C_0

考慮設定C0=C1=0C_0=C_1=0 的情況會發現當它回傳時我們可以計算P0P1=ivC0=iv=KP_0\oplus P_1=\mathrm{iv}\oplus C_0=\mathrm{iv}=\mathrm{K},所以就成功得到 key 了。

註: CBC 如果在 iv 和 key 都是相同且固定的情況一樣會有相同 plaintext 所產生的 ciphertext 都是一樣的問題,和 EBC 的狀況一樣

Symmetry

OFB 模式的一個很重要的特性是加密和解密是一樣的,即EK=DKE_K=D_K。觀察一下它是把 iv 加密之後拿去和 plaintext 做 xor,所以如果拿加密的流程去對 ciphertext 做一樣的事的話就會得到 plaintext。

Bean Counter

這題的 Counter 有個小 bug,就是它預設的模式是 Step down mode,而這個 mode 每次 increment 所減的是 self.stup,而這個的值是 False。所以我們知道它每次進去的 iv 都是一樣的,也就代表和 png 的每個 block 所 xor 的東西是完全不會改變的。

再來 png 的前 16 bytes 是固定為 b'\x89\x50\x4e\x47\x0d\x0a\x1a\x0a\x00\x00\x00\x0d\x49\x48\x44\x52' 的,所以拿它去和 png 的前 16 bytes 做 xor 可以得到 key,然後再用 key 去對整個 ciphertext xor 就能得到原本的 png 了。

CTRIME

題目名稱其實就已經提示了方法了,去查一下相關資訊很快就能找到 CRIME 這個利用 compression ratio 的 side channel attack。方法其實很簡單,就是利用壓縮算法在壓縮時會把相同的字元壓在一起的方法來判斷,例如 abc FLAGFLAG FLAG 兩個字串壓縮後會是後面的長度比較短,所以就能透過判斷長度的變化去一個一個字元爆破。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import requests
import string


def get_ciphertext_length(b: bytes):
resp = requests.get("http://aes.cryptohack.org/ctrime/encrypt/" + b.hex())
return len(bytes.fromhex(resp.json()["ciphertext"]))


flag = b"crypto{"
chrs = (
b"{_}" + (string.digits + string.ascii_uppercase + string.ascii_lowercase).encode()
)

while True:
l = get_ciphertext_length(flag + b"\x00") # null byte probably won't appear in flag
for i in chrs:
c = bytes([i])
b = flag + c
if get_ciphertext_length(b) < l:
break
flag = flag + c
print(flag)
if c == b"}":
break

有個和 https 有關的攻擊 BREACH 就是基於這種攻擊的

Stream of Consciousness

這題使用的是 CTR 模式,但是它每次都是重新創一個 Counter,所以經過 encryption 之後的東西都會是固定的,所以問題就被化為了這樣的 xor 問題:

c1=m1Kc_1=m_1\oplus K

c2=m2Kc_2=m_2\oplus K

c3=m3Kc_3=m_3\oplus K

c4=m4Kc_4=m_4\oplus K

\vdots

首先可以知道裡面有一個是 flag,所以先隨便選兩個取排列做 xor 得到mimjm_i\oplus m_j,然後把它和已知的部份 crypto{ 做 xor 有機會得到能看了懂的英文單字,然後就把看了懂的那組的cic_i 或是cjc_jcrypto{ 看看,猜哪個的結果是 key 然後去 xor 其他的東西就能確定猜測是否正確。

接下來剩下的部分就要人工解了,因為它的其他訊息都是英文句子,有辦法去推測合理的下個字母應該是什麼來反推 key,然後這個部分當然是寫個簡單的腳本來讓人工解密比較有效率:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import requests
from itertools import combinations


def get():
resp = requests.get("http://aes.cryptohack.org/stream_consciousness/encrypt")
return bytes.fromhex(resp.json()["ciphertext"])


ciphertexts = [] # List of ciphertexts, about 22 messages

# When ciphertexts is empty, run this and paste the content above:
# for i in range(60):
# ciphertexts.append(get())
# print(ciphertexts)
# exit()

def xor(A, B):
return bytes([a ^ b for a, b in zip(A, B)])


for a, b in combinations(ciphertexts, 2):
pl = xor(xor(a, b), b"crypto{")
if b"I shall" in pl:
key = xor(b, b"crypto{") # You may need to xor it with a if it doesn't work
break
print("Partial key:", key.hex())


def xor_ciphertext(key):
return [xor(key, ct) for ct in ciphertexts]

# When you choose the wrong one, stop it and paste the last key here to continue
# key = bytes.fromhex(
# "HEX STRING OF KEY"
# )

while True:
pts = xor_ciphertext(key)
for i, pt in enumerate(pts):
print(i, pt)
idx = int(input("Enter index: "))
if idx == -1:
break
c = input("Enter next char: ")[0]
key += bytes([ord(c) ^ ciphertexts[idx][len(key)]])
print("Current key:", key.hex())
print(xor_ciphertext(key))

Logon Zero

這個題目和 CVE-2020-1472 有關,是個關於 Windows Server 的 Active Directory 的登入漏洞有關,詳情可以見此 pdf

簡單來說是 Windows 使用了 AES-CFB8 的模式,但是iv\mathrm{iv} 每次都設成 0,如果Ek(iv)E_k(\mathrm{iv}) 的第一個 byte 正好為 0 的話,只要把 input 也都設為 0 就能得到全部為 0 的 output。看 pdf 中的第 8 頁的圖片比較容易理解。

對於夠隨機的 key 來說Ek(iv)E_k(\mathrm{iv}) 的第一個 byte 為 0 的機率是1256\frac{1}{256},所以當第一個 byte 為 0 且 input 也是 0 的話就會得到 0 的 output,並且讓iv\mathrm{iv} 繼續保持為 0,所以就暴力去試直到中那個機率為止就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from pwn import *

p = remote("socket.cryptohack.org", 13399)
p.recvline()

while True:
p.sendline(
'{"option":"reset_password","token":"0000000000000000000000000000000000000000000000000000000000000000"}'
)
p.recvline()
p.sendline('{"option":"authenticate","password":""}')
r = p.recvline()
if b"admin" in r:
print(r.decode())
break
p.sendline('{"option":"reset_connection"}')
p.recvline()

Paper Plane

我先利用了 padding 去找了第二個 block 的 text 長度,然後再利用它倒過來找完第二的 block 的資訊,之後再弄第一個 block 就完成了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import requests
import string

chrs = (
b"{_}" + (string.digits + string.ascii_lowercase + string.ascii_uppercase).encode()
)


def send_msg(data: bytes, m0: bytes, c0: bytes):
resp = requests.get(
f"http://aes.cryptohack.org/paper_plane/send_msg/{data.hex()}/{m0.hex()}/{c0.hex()}/"
)
return "received" in resp.text


def xor(a, b):
return bytes(x ^ y for x, y in zip(a, b))


c0 = bytes.fromhex("bd09f9b1e6d9383c7a10ebc1f79b5adb")
m0 = bytes.fromhex("20dea5241388bfb182ca1c730ba73e42")
ci = bytes.fromhex("a0490d4fade6162c25ae74d959ec5605202ce21ad3eefa0e86f891fb40a827be")


def get_last_block_text_length():
for i in range(1, 16):
cip = b"\x00" * i + ci[i:]
m0p = xor(xor(m0, ci[:16]), cip[:16]) # So m0'^c1'=m0^c1
if not send_msg(cip, m0p, c0):
return i - 1


lbtl = get_last_block_text_length()
print(lbtl)
flag_len = 16 + lbtl
padding = 16 - lbtl
known_last_blk_suffix = bytes([padding] * padding)


def get_last_blk_chr(idx):
ksl = len(known_last_blk_suffix)
x = xor(ci[16 - ksl : 16], known_last_blk_suffix)
new_padding = bytes([16 - idx] * (15 - idx))
# x^c1=new_padding
for c in chrs:
# c^c1[idx]=x[-1]
# x[-1]^c1'[idx]=16-idx
cip = (
ci[:idx] + bytes([c ^ ci[idx] ^ (16 - idx)]) + xor(new_padding, x) + ci[16:]
)
m0p = xor(xor(m0, ci[:16]), cip[:16]) # So m0'^c1'=m0^c1
if send_msg(cip, m0p, c0):
return bytes([c])


for i in range(lbtl - 1, -1, -1):
c = get_last_blk_chr(i)
known_last_blk_suffix = c + known_last_blk_suffix
print(known_last_blk_suffix)

known_first_blk_suffix = b""


def get_first_blk_chr(idx):
padding = 16 - idx
for c in chrs:
sfx = bytes([c]) + known_first_blk_suffix
c0p = c0[:idx] + xor(xor(sfx, c0[idx:]), [padding] * padding)
if send_msg(ci[:16], m0, c0p):
return bytes([c])


for i in range(15, -1, -1):
c = get_first_blk_chr(i)
known_first_blk_suffix = c + known_first_blk_suffix
print(known_first_blk_suffix + known_last_blk_suffix)
if c == b"{":
chrs = b"crypto"

Triple DES

3DES 是個把 DES 重複結合而產生的模式,可以用C=Ek3(Dk2(Ek1(M)))C=E_{k_3}(D_{k_2}(E_{k_1}(M))) 表示,所以它有三個 key,不過根據標準的話 3DES 是有個只需提供兩個 keyk1k_1k2k_2 的模式,而k3=k1k_3=k_1

所以有個方法可能是會想要設k1=k2k_1=k_2 讓兩個對消,這樣就只剩下一層 DES 了,不過由於 pycryptodome 裡面的 3DES 會檢查k1k2k_1\neq k_2 所以這個方法行不通。

繼續查的話可以查到 DES 有 Weak key 的問題,就是對於某些特定的kk,DES 的Ek=DkE_k=D_k,例如 0101010101010101FEFEFEFEFEFEFEFE 都是這樣的kk

所以如果把 3DES 的kk 設成 0101010101010101FEFEFEFEFEFEFEFE 的話狀況會變這樣 (k1=k3k_1=k_3):

C=Ek3(Dk2(Ek1(Miv)))ivC=E_{k_3}(D_{k_2}(E_{k_1}(M\oplus\mathrm{iv})))\oplus\mathrm{iv}

再來把CC 再加密一次:

C=Ek3(Dk2(Ek1(Ek3(Dk2(Ek1(Miv)))iviv)))iv=Ek1(Dk2(Ek1(Ek1(Dk2(Ek1(Miv))))))iv=Dk1(Ek2(Dk1(Ek1(Dk2(Ek1(Miv))))))iv=Miviv=MC'=E_{k_3}(D_{k_2}(E_{k_1}(E_{k_3}(D_{k_2}(E_{k_1}(M\oplus\mathrm{iv})))\oplus\mathrm{iv}\oplus\mathrm{iv})))\oplus\mathrm{iv}\\ =E_{k_1}(D_{k_2}(E_{k_1}(E_{k_1}(D_{k_2}(E_{k_1}(M\oplus\mathrm{iv}))))))\oplus\mathrm{iv}\\ =D_{k_1}(E_{k_2}(D_{k_1}(E_{k_1}(D_{k_2}(E_{k_1}(M\oplus\mathrm{iv}))))))\oplus\mathrm{iv}\\ =M\oplus\mathrm{iv}\oplus\mathrm{iv}\\ =M

所以就用上面的特殊 key 把 flag 加密之後再加密一次得到的就是 flag 了。

CRYPTO ON THE WEB

Token Appreciation

jwt.io 上解開就好了。

JWT Sessions

一般 jwt 是存在 Authorization 的 header 裡面的。

No Way JOSE

注意到它會接受 None 的 Algorithm,所以用 None 生成一個就好了,不過因為 jwt.io 不支援 None 所以我就自己用 js 簡單自己生成一下就好了。

JWT Secrets

它說 secret 是 PyJWT readme 預設的 secret,即 secret,然後就用那個去 sign 出一個改過的 payload 就解決了。

RSA or HMAC?

它雖然在 sign 的時候用的是 RSA,但 decode 的時候沒有填 Algorithm,而 PyJWT 在舊版預設是用 HS256 decode 的,所以用 public key + HS256 去 sign 一個新的 payload 就好了。

jwt.io 不支援 secret 裡面有換行符號 \n 的樣子,需要自己用其他方法去 sign

JSON IN JSON

簡單的 JSON injection: maple","admin":"True 就可以了。

MISC

Gotta Go Fast

這題的一個解法是把 flag 拿到之後送回去 encrypt,因為是用 XOR 加密的,只要時間差不超過一秒鐘的話就可以成功解密了,不過因為有網路的延遲問題所以其實這很看運氣的。

另解就是從 range(current_time - 1000, current_time + 1000) 直接全部試一次,看看解密之後是不是 flag 就好了。

No Leaks

這題只要 xor 之後的 flag 和 flag 本身有任何一個字元的相同就會回 error,所以代表回傳的字元代表在 flag 在那個位置絕對不會是那個字元,所以用刪去法就好了。

這題和 Hackme CTF 上的某題很像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from pwn import *
import json
import base64

p = remote("socket.cryptohack.org", 13370)
p.recvline()

tbl = [[True] * 256 for i in range(20)]

while True:
p.sendline(json.dumps({"msg": "request"}))
d = json.loads(p.recvline().decode())
if "error" in d:
continue
not_in_flag = base64.decodebytes(d["ciphertext"].encode())
for i, b in enumerate(not_in_flag):
tbl[i][b] = False
print([sum(row) for row in tbl])
if all([sum(row) == 1 for row in tbl]):
print("".join(chr(row.index(True)) for row in tbl))
break

這個要跑蠻久的,我大概 10 分鐘多才成功爆破出來

Collider

這題找個 md5 collision 就好了,我是在這個答案找到的: https://crypto.stackexchange.com/a/15889

MD0

注意一下它的 hashpad 的運作原理,可以觀察發現如果 hash(b'') 的時候會有下面的情況發生:

1
2
3
4
5
6
7
8
9
10
11
pad(b"a" * 16, 16) # b'aaaaaaaaaaaaaaaa\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10'

# f(b, k) = AES.new(b, AES.MODE_ECB).encrypt(k)

# So we have:
b0 = key
b1 = b'\x10' * 16
out0 = b'\x00' * 16
out1 = f(b0, out0) ^ out0
out2 = f(b1, out1) ^ out1
# hash(b'') = out2

所以我們可以透過它回傳的值去計算 message 接上 admin=True 的 signature,不過傳過去的 message 記得要在前面接上 b'\x10' * 16

1
2
3
b2 = b'admin=True'
out3 = f(pad(b2, 16), out2) ^ out2
# hash(b'admin=True') = out3

PriMeD5

這題需要找到一個質數和一個合數的 md5 碰撞,我的做法就是很簡單的暴力去試而已,利用 hashclash 裡面的 fastcoll 去隨機產生碰撞,直到找到有一組質數和合數出現為止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import sys
import os

from Crypto.Util.number import isPrime, bytes_to_long, long_to_bytes


def test():
os.system("./md5_fastcoll -o a.bin b.bin")
pr = None
cp = None
with open("a.bin", "rb") as f:
x = f.read()
n = bytes_to_long(x)
if isPrime(n):
pr = x
else:
cp = x
with open("b.bin", "rb") as f:
x = f.read()
n = bytes_to_long(x)
if isPrime(n):
pr = x
else:
cp = x
return pr, cp


while True:
pr, cp = test()
if pr != None and cp != None:
print(bytes_to_long(pr))
print(bytes_to_long(cp))
break

在我的電腦大概試了 15 分鐘才跑出來,不過如果運氣夠好可能可以在快很多的情況下找出來。不想慢慢算的可以試著解開下面這個 RSA,它的 N 就是那個合數,而 plaintext 則是那個質數

1
2
3
N = 13992183881284921123723844148582775836385391453600917013227516407165891465651049228623745695394463817732084468417321794108360107228584764853250593762139656509127513568428431981508504966136993467509993334100909951250590752016035645660797693730920894445398515493902636158667134896321281322447492657549733410899
e = 65537
c = 3760482145762810643177502725138408007525653836519833633048010811044331913260002262520215544901522348733495205958481964677829019700399426818987363077429392652517883204138516501011876275745391243634928096567463649360638421265841206866091161405192755418111843121688944699773205453048726682929329222761064831491

No Difference

這題的 hash function 的後半都是沒用的,因為和 data 毫無關係,所以只留前面有做 xor 的部份就好了。這個地方使用 z3 要去解很簡單,就像下方這樣:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
SBOX = [...] # Too big

# permute has the following properties:
# permute(permute(x)) = x
# permute(a) ^ permute(b) = permute(a ^ b)
def permute(block):
result = [0 for _ in range(8)]
for i in range(8):
x = block[i]
for j in range(8):
result[j] |= (x & 1) << i
x >>= 1
return result


def substitute(block):
return [SBOX[x] for x in block]


def hash(data, subfn=substitute):
if len(data) % 4 != 0:
return None

state = [16, 32, 48, 80, 80, 96, 112, 128]
for i in range(0, len(data), 4):
block = data[i : i + 4]
state[4] ^= block[0]
state[5] ^= block[1]
state[6] ^= block[2]
state[7] ^= block[3]
state = permute(state)
state = subfn(state)

# Some parts are removed as they aren't related with data, and removing them can simplify it

return state


from z3 import *

s = Solver()

SSBOX = Array("SSBOX", BitVecSort(8), BitVecSort(8))
for i in range(256):
s.add(SSBOX[i] == SBOX[i])


def z3sub(state):
return [SSBOX[x] for x in state]


data1 = [BitVec(f"d1_{i}", 8) for i in range(4)]
data2 = [BitVec(f"d2_{i}", 8) for i in range(4)]
for i in range(4):
s.add(data1[i] != data2[i])
state1 = hash(data1, subfn=z3sub)
state2 = hash(data2, subfn=z3sub)
for i in range(8):
s.add(state1[i] == state2[i])

assert s.check() == sat
m = s.model()
a = bytes([m[x].as_long() for x in data1])
b = bytes([m[x].as_long() for x in data2])
assert hash(a) == hash(b)
print(a.hex())
print(b.hex())

另一個解法是直接暴力算也可以,反正輸出種類不多。

Armory

可以發現說它多項式的係數都是由 sha256 去算的,所以既然我們知道了第一個 share 就能把除了 flag 以外的係數算出來。接下來有這個多項式:

y=a2x2+a1x+a0y=a_2x^2+a_1x+a_0

多項式裡面的a2,a1,y,xa_2, a_1, y, x 都是已知的,所以a0a_0 就能很容易的求出來,然後還原成 flag 就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from hashlib import sha256
from Crypto.Util.number import long_to_bytes

p = 77793805322526801978326005188088213205424384389488111175220421173086192558047


def hashn(n: int):
return int.from_bytes(
sha256(int(n).to_bytes(32, byteorder="big")).digest(), byteorder="big"
)


p1 = (
105622578433921694608307153620094961853014843078655463551374559727541051964080,
25953768581962402292961757951905849014581503184926092726593265745485300657424,
)

coefs = [0, p1[0]]
for i in range(2, 8):
coefs.append(hashn(coefs[-1]))

flag = (
p1[1] - (coefs[2] * p1[0] ** 2 + coefs[1] * p1[0]) % p
) # y=coefs[2]*x^2+coefs[1]*x+coefs[0]
print(long_to_bytes(flag).decode())

Toshi’s Treasure

我們能控制的是(6,y6)(6, y_6) 這個點,可以寫出下面的多項式:

y=(x6)q(x)+ay6y=(x-6)q(x)+ay_6

當我們把(6,0)(6, 0) 傳過去後會得到的 secret 是常數項y(0)=6q(0)y(0)=-6q(0)aa 的值可以透過再傳一次(6,1)(6, 1) 過去之後的值去觀察可以知道a=5a=5,或是直接用拉格朗日插值法的公式去推y6y_6 前面的係數:

a=(5)(4)(3)(2)(65)(64)(63)(62)=5a=\frac{(-5)(-4)(-3)(-2)}{(6-5)(6-4)(6-3)(6-2)}=5

之後要讓它到假的 private keyPP 就找符合y(0)=6q(0)+5y6=Py(0)=-6q(0)+5y_6=Py6y_6 就可以了,也就是y6=51(P(6q(0)))y_6=5^{-1}(P-(-6q(0)))

然後真的 private key 也很容易求,就是6q(0)+5y6-6q(0)+5y_6 而已。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from pwn import *
import json

my_1k_wallet_privkey = (
0x8B09CFC4696B91A1CC43372AC66CA36556A41499B495F28CC7AB193E32EADD30
)
PRIME = 2 ** 521 - 1

p = remote("socket.cryptohack.org", 13384)


def recvjson():
return json.loads(p.recvline().strip().decode())


def sendjson(d):
p.sendline(json.dumps(d))


my_share = recvjson()
my_y = int(my_share["y"], 16)
recvjson() # x=2
recvjson() # x=3
recvjson() # x=4
recvjson() # x=5
sendjson({"x": 6, "y": hex(0)})
combined = recvjson()
wrong_priv = int(combined["privkey"], 16)
print("wrong", hex(wrong_priv))
recvjson() # invalid
recvjson() # again
sendjson({"x": 6, "y": hex((my_1k_wallet_privkey - wrong_priv) * pow(5, -1, PRIME))})
recvjson() # my wallet
recvjson() # msg
recvjson() # ask real priv
real_priv = (wrong_priv + 5 * my_y) % PRIME
print("real", hex(real_priv))
sendjson({"privkey": hex(real_priv)})
print(recvjson())

Bruce Schneier’s Password

關鍵是它使用了 numpy 的陣列去做運算,所以它預設是會像是 C 一樣 overflow 的,所以多個字元的乘積也是有可能是質數的,然後就直接暴力找就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
import numpy as np
import string
from itertools import product
from Crypto.Util.number import isPrime

pwd = "1Aa" + "a" * 20
ch = string.ascii_lowercase + string.ascii_uppercase + string.digits
for a, b, c, d in product(ch, ch, ch, ch):
ar = np.array(list(map(ord, pwd + a + b + c + d)))
if isPrime(int(ar.sum())) and isPrime(int(ar.prod())):
print(pwd + a + b + c + d)
break

DIFFIE-HELLMAN

Parameter Injection

這題是可以完全 MITM 的狀況,從讀取到偽裝是對方發送的都很簡單,方法就自己為雙方生成假的 private key 給另一方就好了。例如最簡單就是把假的 private key 都設為 0,所以 public key 都是 1,然後 shared secret 就是 g^((alice private key)*(fake bob private key sent to alice))=1 就成功搞定了。

Export-grade

這題一開始 Alice 會先和 Bob 進行使用的 protocol 的交換,所以只要把它支援的 protocol 改成 DH64,就能取得一組很小的 p,然後算 discrete log 就交給 Sage 處裡就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
from dh_decrypt import decrypt_flag # Script provided in "Diffie-Hellman Starter 5"

p =
g =
A =
B =
iv = ""
encrypted_flag = ""

Z = Zmod(p)
na = discrete_log(Z(A), Z(g))
shared = Z(B) ** na
print(decrypt_flag(shared, iv, encrypted_flag))

Static Client

這題有兩個解法,我想的的第一個解法是透過操作pp 來破解。Discrete Log 的算法裡面有個 Pohlig Hellman 算法可以在p\sqrt{p^*} 的複雜度之下解決,所以只要p1p-1 是光滑的就能求出 bob 的 private key 了。(pp^* 是 group order 質因數中最大的那個)

至於生成p1p-1 是光滑數的質數pp 的方法也蠻直接的,就2p1p2+12*p_1*p_2*\cdots+1 檢查看看是不是質數就好了,不過網路上其實已經能找到別人寫過的生成工具了: backdoor_generator.sage。(這個工具可以直接用 2to3 -w 升級到 python 3 使用)

另一個解法是透過g=Ag'=Ap=pp'=p 去換就好了,因為gb=Ab=gab=shared secretg'^{b}=A^{b}=g^{ab}=\mathrm{shared\space secret}AA' 的話並不重要。

Additive

這題滿簡單的,在改用 Additive Group 的情況下狀況會變這樣:

Aag(modp)A\equiv ag\pmod{p}

Bbg(modp)B\equiv bg\pmod{p}

所以ag1A(modp)a\equiv g^{-1}A\pmod{p},然後承上 B 之後就拿到 shared secret 了。

Static Client 2

和前面的 Static Client 一樣的解法,兩個做法都行,只是AA' 不能那麼隨便,需要塞點像樣的東西進去就可以了。

Script Kiddie

這題關鍵在於它在算次方的時候使用了 ^,但在 Python 裡面是 xor,然後 % 的運算子優先權又比 ^,所以 g ^ a % p 實際上等於 g ^ a (當 ap 小的時候)。

註: Sage 裡面的 ^ 確實是次方,xor 需要改用 ^^

所以b=Bgb=B\oplus g,然後bAb\oplus A 就是 shared secret 了。