CryptoHack WriteUps

發表於 2020-12-12 分類於 CTF

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

RSA

Factoring

丟到 FactorDB 上去解決。

Inferius Prime

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

Monoprime

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

Square Eyes

一樣是一個質數，不過是 $N=p^2$ ，所以 $\phi(N)=p\times{(p-1)}$ ，然後一樣算出 $d$ 就搞定了。

Manyprime

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

Salty

$e=1$ ，所以 $d=1$ ，因此 $m\equiv c\pmod{N}$ 和 $c\equiv m\pmod{N}$ 。

Modulus Inutilis

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

Everything is Big

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

Crossed Wires

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

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

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

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

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

Endless Emails

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

m^e\equiv c_1\pmod{n_1} \\ m^e\equiv c_2\pmod{n_2} \\ m^e\equiv c_3\pmod{n_3}

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

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

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

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

Marin’s Secrets

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

用 Sage 的解法非常短:

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，在我的電腦上花三分多鐘才分解出 $p$ $q$ 。

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

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

Ron was Wrong, Whit is Right

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

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

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

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

這三篇討論 $4p-1=Ds^2$ 形式有關的質數 $p$ 的分解方法，第一篇的方法在 RsaCtfTool 裡面裡面被稱為 qicheng，不過它的 $D$ 不包含 $427$ ，所以無法處裡。

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

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

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

修正方法可以參考這個 commit

Bespoke Padding

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

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

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

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

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

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

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

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，所以可以寫成 $(m*\mathtt{0x100}^{100-l})^e\equiv c\pmod{N}$ ，其中的 l 是 flag 的長度。這個基本上可以透過 Coppersmith’s method 讓它去求比較小的根而找到 m，不過經過測試會發現單純這樣所產生的多項式沒辦法找到解，因為這題的 flag 似乎比較長，不符合 $x<N^{1/e}$ ，所以沒辦法單純的使用這個方法去找。

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

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 的函數能讓你計算 $x^d\mod{N}$ 了，所以把得到的 $m^e\mod{N}$ 放進去之後自然就得到 flag 了，不過是 16 進位的數字，所以稍微轉換一下就好了。

Let’s Decrypt

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

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

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

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

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

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

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)^d\mod{n}=((a^d\mod{n})\times(b^d\mod{n}))\mod{n}$ ，所以分開 sign 之後乘起來再 $\mod{n}$ 就能得到 signed 的 ADMIN_TOKEN 了。

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，因為 $(\mathtt{token}+n)^d\mod{n}=\mathtt{token}\mod{n}$ 。 (由 mod 可以移入次方中的性質或是直接展開多項式都能得到)

Vote for Pedro

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

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

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 的延伸，不過這次簡化後變成有三個方程式要處裡:

k_0=\mathtt{SIG}^{e_0}\mod{n}

k_1=\mathtt{SIG}^{e_1}\mod{n}

k_2=\mathtt{SIG}^{e_2}\mod{n}

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

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

所以固定好 $n$ ，確定它會大於 $k_i$ 後再去拿 suffix，之後算出 $k_i$ 的質後用求出 $e_i$ ，最後得到 $s_i$ 做 xor 後就能得到 flag 了。

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)$ 下的運算所以負的要加回正的。

Point Addition

實作一下就好了:

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 也可以:

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 函數繼續實作整數乘法而已，很簡單:

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

前一題的簡單延伸


from hashlib import sha1

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

Efficient Exchange

這題關於在 $GF(p)$ 從 $y^2$ 求 $y$ 的方法需要前面 Quadratic Residues 和 Legendre Symbol 兩題的知識。

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 Problem 和 Elliptic Curve Discrete Logarithm Problem

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

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

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 了:

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 是同構的這個性質，想辦法找個映射把曲線上的點轉換到 $\mathbf F_p$ 的加法群，這樣的話原本困難的 DLP 就能變成簡單的計算 mod inverse 的問題。

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

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

$a_0$ 是一個函數代表的是過 $P$ 和 $Q$ 兩點的直線斜率，如果 $P=Q$ 則給切線斜率，若 $P=-Q$ 或是有任一點是無窮遠點的時候就回傳 $0$ 。

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

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

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

這種情況下的 DLP $A=kB$ 就能用下面的方法解決了:

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

所以

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

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

Elliptic Nodes

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

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

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

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

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

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

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

解這題的 Sage code:

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)^a$ 和 $e(P,bQ)=e(P,Q)^b$ 。

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

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=P$ ， $P$ 是目標的 public key。至於生成方法也很簡單，利用 $nP=O$ 的性質就好了，其中的 $n$ 是 group order 而 $P$ 是曲線上一點。

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。

# 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 有關的題目，即形式為 $ax^2+y^2=1+dx^2y^2$ 的曲線，而它們和某類的橢圓曲線 birationally equivalent。 (這可視為幾乎是同構的，詳見此)

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

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

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，即是否存在一個 $x$ 使得 $x^2\equiv a\pmod{p}$ 。

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

1
2
3

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

Legendre Symbol

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

判斷出是不是 Quadratic Residues 之後它還要你把 $x$ 算出來，然後給了個提示 $p\equiv 3\pmod{4}$ ，去查了一下會發現說在這個情況下 $x\equiv a^{\frac{p+1}{4}}\pmod{p}$ 的。因為 $x^2\equiv a^{\frac{p+1}{2}}\equiv a^{\frac{p-1}{2}}\times{a}\equiv a\pmod{p}$ 。

Modular Square Root

上一題的延伸，只是這次是 $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 的解法:

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 結合。

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、加密與解密流程大致可以表示如下:

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\equiv(fe)\equiv(f(rh+m))\equiv(gr+fm)\pmod{q}

m\equiv\frac{gr+fm}{f}\equiv\frac{gr}{f}+m\equiv m\pmod{g}

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

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

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

\begin{bmatrix} 1 & h \\ 0 & q \end{bmatrix}

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

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

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

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

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

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

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

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

Backpack Cryptography

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

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

\begin{bmatrix} I_{n\times n} & P_{n\times1} \\ O_{1\times n} & -C_{1\times1} \end{bmatrix}

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

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

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>\frac{\sqrt{n}}{2}$ ，然後再使用下面的矩陣去 LLL，這個是成功率比較高的方法:

\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 會有一列整個都是 $-\frac{1}{2}$ 或 $\frac{1}{2}$ ，分別代表 1 和 0。

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

Jack’s Birthday Hash

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

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

Jack’s Birthday Confusion

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

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

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

Successive Powers

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

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

492x\equiv819\pmod{p}

4x\equiv836\pmod{p}

然後得到

0\equiv-102009\pmod{p}

因為 $102009=3\times37\times979$ ，所以唯一的 $p=979$ ，而 $x=836/4=209$ 。

Adrien’s Signs

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

後來看別人的解答發現由於 $\left(\dfrac{a}{p}\right)=1$ ，所以存在 $x^2\equiv a\pmod{p}$ ，所以對於 $\left(\dfrac{a^e}{p}\right)=1$ 也是成立的。如果是 $-a^e$ 的情況，則有 $\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}$ 。 ( $\frac{p-1}{2}$ 是奇數)

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

Modular Binomials

原本的式子:

N=pq

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

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

首先我先尋找符合 $e_1x=e_2y$ 的一組 $(x,y)$ ，最簡單的方法就是取 $e_1x=e_2y=\mathrm{lcm}(e_1,e_2)=k$ 。

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

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

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

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

\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}

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

Broken RSA

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

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

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

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

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 就會發現說這反而像是雙曲線一樣: $x^2-Dy^2\equiv1\pmod{p}$

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

註: 這題 $p-1$ 是 smooth 的，所以用 Polhig-Hellman 效果很好

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))

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

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

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

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

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

Unencryptable

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

第一個關鍵是發現說 $65536$ 並不是 $m^k\equiv 1\pmod{N}$ 中最小的 $k$ ，實際上用用迴圈找一下可以知道它最小的 $k=512$ ，所以 $m^{512}-1$ 裡面也是有 $p$ $q$ 兩個因數在。

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

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)$ 裡面有 $p$ $q$ 存在，所以分解過的項裡面代入 $x=m$ 之後肯定有幾項符合 $gcd(f_s(m),N)>1$ ，而那個就是 $p$ 或 $q$ 。

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)))

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 的後半可能要稍微調整一下才能破解出來，整個整合起來就是下面的腳本了:

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 前所得到的是 $\mathrm{plaintext}\oplus\mathrm{iv}$ ，然後和原本的 iv xor 之後就得到了 plaintext。

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

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

Lazy CBC

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

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

P_0=D_K(C_0)\oplus\mathrm{iv}

P_1=D_K(C_1)\oplus C_0

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

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

Symmetry

OFB 模式的一個很重要的特性是加密和解密是一樣的，即 $E_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 FLAG 和 FLAG FLAG 兩個字串壓縮後會是後面的長度比較短，所以就能透過判斷長度的變化去一個一個字元爆破。

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 問題:

c_1=m_1\oplus K

c_2=m_2\oplus K

c_3=m_3\oplus K

c_4=m_4\oplus K

\vdots

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

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

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))

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

MISC

Gotta Go Fast

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

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

No Leaks

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

這題和 Hackme CTF 上的某題很像

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

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

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 去隨機產生碰撞，直到找到有一組質數和合數出現為止。

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 要去解很簡單，就像下方這樣:

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())

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

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 處裡就好。

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

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

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

另一個解法是透過 $g'=A$ 和 $p'=p$ 去換就好了，因為 $g'^{b}=A^{b}=g^{ab}=\mathrm{shared\space secret}$ 。 $A'$ 的話並不重要。

Additive

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

A\equiv ag\pmod{p}

B\equiv bg\pmod{p}

所以 $a\equiv g^{-1}A\pmod{p}$ ，然後承上 B 之後就拿到 shared secret 了。

Static Client 2

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

Script Kiddie

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

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

所以 $b=B\oplus g$ ，然後 $b\oplus A$ 就是 shared secret 了。

RSA