AlpacaHack Round 3 (Crypto) writeup - チョコラスクのブログ

AlpacaHack初めてのCrypto回 (AlpacaHack Round 3 (Crypto)) に参加しました！

3問目までは順調でしたが、4問目で実装をバグらせてしまい、結果は3位でした。優勝したかった...

qrime
Rainbow Sweet Alchemist
A Dance of Add and Mul
Hat Trick

qrime

次のようなスクリプトとその出力が与えられます。

import os
from Crypto.Util.number import bytes_to_long, getRandomNBitInteger, isPrime

def nextPrime(n):
    while not isPrime(n := n + 1):
        continue
    return n

def gen():
    while True:
        q = getRandomNBitInteger(256)
        r = getRandomNBitInteger(256)
        p = q * nextPrime(r) + nextPrime(q) * r
        if isPrime(p) and isPrime(q):
            return p, q, r

flag = os.environ.get("FLAG", "fakeflag").encode()
m = bytes_to_long(flag)

p, q, r = gen()
n = p * q

phi = (p - 1) * (q - 1)
e = 0x10001
d = pow(e, -1, phi)
c = pow(m, e, n)

print(f"{n=}")
print(f"{e=}")
print(f"{c=}")
print(f"{r=}")

素数 $p,q$ の間に関係性があるという典型的なRSA暗号の問題です。今回は、p = q * nextPrime(r) + nextPrime(q) * rという関係式があり、 $r$ の値は与えられています。

$r$ が与えられているので、nextPrime(r)の値は計算できます ( $r'$ とおきます)。また、 $q$ の次の素数 nextPrime(q)の値を $q+d$ と表すことにします。このとき、

$\displaystyle{ p=qr'+(q+d)r }$

なので、

$\displaystyle{ q(qr'+(q+d)r)=n }$

が成り立ちます。未知数は $q$ と $d$ であり、 $d$ を固定すると $q$ に関する2次方程式になっています。

ここで、 $d$ はかなり小さいです。具体的には、 $q$ 付近には平均すると $\frac{1}{\log q}$ の割合で素数が存在することが知られている (素数定理) ので、 $d$ は $\log q$ くらいの値になります。よって、 $d=1,2,3,\ldots$ と順に、先ほどの $q$ に関する2次方程式を解いていけば、 $q$ の値が見つかります。

2次方程式を解くのはSageMathで殴ると楽です。

from Crypto.Util.number import *

def nextPrime(n):
    while not isPrime(n := n + 1):
        continue
    return n

R.<x> = PolynomialRing(ZZ)
r1 = nextPrime(r)
for i in range(1,10000):
    f = x*(x*r1+(x+i)*r)-n
    res = f.roots()
    if len(res)!=0:
        q = res[0][0]
        break

p = n//q
d = pow(int(e),int(-1),int((p-1)*(q-1)))
m = pow(int(c),int(d),int(n))
print(long_to_bytes(int(m)))

Rainbow Sweet Alchemist

次のようなスクリプトとその出力が与えられます。

import os
import random
from math import prod
from Crypto.Util.number import isPrime, bytes_to_long

r = random.Random(0)
def deterministicGetPrime():
  while True:
    if isPrime(p := r.getrandbits(64)):
      return p

# This is not likely to fail
assert deterministicGetPrime() == 2710959347947821323, "Your Python's random module is not compatible with this challenge."

def getPrime(bit):
  factors = [deterministicGetPrime() for _ in range(bit // 64)]
  while True:
    p = 2 * prod(factors) + 1
    if isPrime(p):
      return p
    factors.remove(random.choice(factors))
    factors.append(deterministicGetPrime())

flag = os.environ.get("FLAG", "fakeflag").encode()
m = bytes_to_long(flag)

p, q = getPrime(1024), getPrime(1024)
n = p * q
e = 0x10001
c = pow(m, e, n)

print(f"{n=}")
print(f"{e=}")
print(f"{c=}")

素数が特殊な方法で生成されているRSA暗号の問題です。

$p-1$ の素因数が全て小さいことがわかっている場合、p-1法とよばれる方法で $n=pq$ を素因数分解することができます。具体的には、 $M$ を素数を小さい順にたくさん掛け合わせた値とし、 $p-1$ が $M$ の約数となるようにします。すると、フェルマーの小定理より、整数 $a$ ( $a\not\equiv 0\bmod{p}$ ) に対し $a^{M}\equiv 1\bmod{p}$ となります。一方、 $q-1$ が $M$ の約数でなければ、 $a$ を適当に取ると $a^{M}\not\equiv 1\bmod{q}$ となるので、

$\displaystyle{ p=\mathrm{gcd}(a^{M}-1, n) }$

で $p$ が求まる、というものです。

この問題では、 $p-1$ の素因数は64bitなので、64bitの素数を全て掛け合わせることはできず、p-1法をそのまま適用はできませんが、 $p-1$ の素因数の候補がわかっているので同様の方法が使えます。実際、r = random.Random(0)の箇所で乱数のseedが0になっているので、deterministicGetPrimeで生成される素数の列は計算することができ、これが $p-1$ の素因数の候補です。この素因数の候補をいくつか掛け合わせたものを $M$ とすることで、p-1法と同様にして $p$ を求められます。

なお、 $q$ もdeterministicGetPrimeを使って生成されているので、 $M$ を大きくしすぎると $p-1$ も $q-1$ も $M$ の約数となってしまい、 $\mathrm{gcd}(a^{M}-1, n)=n$ となってしまいます。 $p-1$ のみが $M$ の約数となるよう、掛ける素因数の候補の個数を調節します。

from Crypto.Util.number import *
import random
from math import prod

r = random.Random(0)
def deterministicGetPrime():
  while True:
    if isPrime(p := r.getrandbits(64)):
      return p

fs = [deterministicGetPrime() for _ in range(300)] # 300の部分は、p-1の素因数を全て含むが、q-1の素因数を全ては含まないくらいに調節する
M = 2*prod(fs)

a = 2
while True:
  g = GCD(pow(a, M, n)-1, n)
  if g>1 and g<n:
    q = g
    break
  a += 1

p = n//q
d = pow(int(e),int(-1),int((p-1)*(q-1)))
m = pow(int(c),int(d),int(n))
print(long_to_bytes(int(m)))

有名アルゴリズムの中身の理解をいい感じに問えていてとても良い問題だと思いました。

A Dance of Add and Mul

次のようなスクリプトとその出力が与えられます。

import os
import random
from Crypto.Util.number import bytes_to_long

flag = os.environ.get("FLAG", "fakeflag").encode()
bit_length = len(flag) * 8

# BLS12-381 curve
p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
K = GF(p)
E = EllipticCurve(K, (0, 4))

G1, G2 = E.gens()
o1, o2 = G1.order(), G2.order()

xs = [random.randrange(0, o1) for _ in range(bit_length + 1)]
m = bytes_to_long(flag)

cs = []
for c, (x1, x2) in zip(bin(m)[2:].zfill(bit_length), zip(xs[:-1], xs[1:])):
  if c == "1":
    x1, x2 = x2, x1
  cs.append(x1 * G1 + x2 * G2)

print([P.xy() for P in cs])

SECCON Beginners CTF 2024でも出題されたBLS12-381という曲線が使われています。 $G_{1}, G_{2}$ はランダムではなく決定的アルゴリズムで生成されているようで、 $o_{1}, o_{2}$ の値は次のようになっています。

sage: G1                                                                                                          
(547267894408768087084154039555760353521479753946258632875036726158932984746527535614714820052060149146314557270019 : 1835063209175869974242139117441761755355391001264886580587881843166918857183334906933623397100805888438647438806516 : 1)
sage: G2                                                                                                          
(3969264096345269692399260831745939410953236272103079138813879945504403168173217859890302962785334991213756532919067 : 3379460874886854849045122318333716330044841999681175165157995677955191656134039472761779256971819501741022142910487 : 1)
sage: factor(o1)                                                                                                  
3 * 11 * 10177 * 859267 * 52437899 * 52435875175126190479447740508185965837690552500527637822603658699938581184513
sage: factor(o2)                                                                                                  
3 * 11 * 10177 * 859267 * 52437899 * 52435875175126190479447740508185965837690552500527637822603658699938581184513

また、 $E$ の位数は次のようになっていることから、 $E$ の群構造は $E(\mathbb{F}_{p})\simeq \mathbb{Z}/3\mathbb{Z} \oplus (\mathbb{Z}/11\mathbb{Z})^{2} \oplus (\mathbb{Z}/10177\mathbb{Z})^{2} \oplus \cdots$ となっているようです。

sage: factor(E.order())                                                                                           
3 * 11^2 * 10177^2 * 859267^2 * 52437899^2 * 52435875175126190479447740508185965837690552500527637822603658699938581184513

位数が小さい素因数を持つことから、Pohlig-Hellman法が使えそうです。 $(x_{1}, x_{2})$ と $(x_{2}, x_{1})$ の識別しか問われていないので、 $x_{i}\bmod{10177}$ がわかれば十分です。

$r=10177$ とし、 $P=x_{1}G_{1}+x_{2}G_{2}$ を満たす $(x_{1}, x_{2})$ について、 $x_{i}\bmod{r}$ を求めます。Pohlig-Hellman法の要領で $H_{i}=(o_{1}/r)G_{i}$ , $Q=(o_{1}/r)P$ とすると、 $H_{i}$ の位数は $r$ で、 $Q=(x_{1}\bmod{r})H_{1}+(x_{2}\bmod{r})H_{2}$ です。

$r=10177$ なので $x_{i}\bmod{r}$ の組を全探索すると時間がかかりそうですが、 $x_{2}=0, 1, \ldots , r-1$ に対し $x_{2}H_{2}$ から $x_{2}$ への対応を事前計算してhashmapで持っておき、 $x_{1}\bmod{r}$ を全探索して $Q-x_{1}H_{1}$ がある $x_{2}H_{2}$ に一致するものを探せばよいです。

from Crypto.Util.number import *

p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
K = GF(p)
E = EllipticCurve(K, (0, 4))

G1, G2 = E.gens()
r = 10177
o = 793479390729215512516507951283169066088130679960393952059283337873017453583023682367384822284289
H1 = (o//r)*G1
H2 = (o//r)*G2

H2s = dict()
H = E(0)
for i in range(r):
    H2s[str(H)] = i
    H += H2

flag = ""
xs = []
for P in cs:
    P = E(P)
    Q = P*(o//r)
    x = None
    Q1 = Q
    for i in range(r):
        if str(Q1) in H2s:
            j = H2s[str(Q1)]
            x = (i,j)
            break
        Q1 -= H1
    print(x)
    if flag == "":
        flag += "0"
    else:
        if flag[-1] == "0":
            if xs[-1][1] == x[0]:
                flag += "0"
            else:
                flag += "1"
        else:
            if xs[-1][0] == x[0]:
                flag += "0"
            else:
                flag += "1"
    xs.append(x)

flag = long_to_bytes(int(flag, 2))
print(flag)

first bloodでした。普通の楕円曲線暗号では位数が素数の楕円曲線を使うことが多そうですが、pairing-friendly curveは位数が小さい素因数を持つので注意が必要、という話があり (BLS12-381 For The Rest Of Us)、いつか作問のネタにしようと思っていたところだったので、小さい素因数に着目することはすぐ思いつけました。

この問題はペアリングを使って解くこともできたようで、そちらも思いつくべきだった感じでした。

Hat Trick

次のようなスクリプトが与えられます。

import json
import os
import random
import signal
import string
from Crypto.Util.number import getPrime, getRandomInteger

class RollingHash:
  def __init__(self, p=None, base=None) -> None:
    self.p = getPrime(64) if p is None else p
    self.base = (getRandomInteger(64) if base is None else base) % self.p
  def hash(self, s: str):
    res = 0
    for i, c in enumerate(s):
      res += ord(c) * (self.base ** i)
      res %= self.p
    return res

def check_str(s: str, max_len: int):
  assert len(s) <= max_len, "too long!"
  for i, c in enumerate(s):
    assert c in string.ascii_lowercase, f"found invalid char {c} at {i}"

signal.alarm(3 * 60)

flag = os.environ.get("FLAG", "fakeflag")
MAX_LEN = 54

rhs = [RollingHash() for _ in range(3)]
print("params:",json.dumps([{ "base": rh.base, "p": rh.p } for rh in rhs]))

for _ in range(3):
  target_hash = [random.randrange(0, rh.p) for rh in rhs]
  print('target:', target_hash)
  s = input("> ")
  check_str(s, MAX_LEN)

  actual_hash = [rh.hash(s) for rh in rhs]
  if target_hash != actual_hash:
    print("Oops! You missed the target hash. Better luck next time!")
    exit(1)

print("Congratulations! Here is your flag:", flag)

競プロerおなじみのローリングハッシュで、与えられたハッシュ値の文字列を構築する問題です。

ローリングハッシュの衝突を構築する問題はLLLアルゴリズムで解けることが知られており (yukicoder)、この問題も同様にLLLアルゴリズムで解くことができそうです。

baseを $b$ 、targetを $t$ と書くことにします。まず、3種類のmodでハッシュを取っていますが、中国剰余定理を用いて $b\equiv b_{i}\bmod{p_{i}}$ , $t\equiv t_{i}\bmod{p_{i}}$ を満たす $b, t$ を取ることで、1つのmod $p=p_{1}p_{2}p_{3}$ で考えることができます。

$L=54$ (文字列の長さの最大値) として、

$\displaystyle{ \sum_{i=0}^{L-1} c_{i}b^{i}\equiv t\bmod{p} }$

を満たす $c_{i}$ を求めたいです。文字は全て英小文字でなければならないので、 $97\leq c_{i}\leq 122$ である必要があります。 $c_{i}'=c_{i}-109$ , $t'=t-109\sum_{i=0}^{L-1}b^{i}$ と置き換えると、

$\displaystyle{ \sum_{i=0}^{L-1} c_{i}'b^{i}\equiv t'\bmod{p} }$

を満たす小さい $c_{i}'$ ( $|c_{i}'|\leq 12$ ) を求めることが目標です。

線形不定方程式の小さい整数解を求めたいときは、LLLアルゴリズムが有用です。LLLアルゴリズムは、入力の行列の行ベクトルが張る格子の基底であって、小さいベクトルからなるもの (簡約基底) を出力します。

今回は、次のような行列

$\displaystyle{ \begin{pmatrix} b^{0} & 1 & 0 & 0 & \dots & 0 & 0 \\ b^{1} & 0 & 1 & 0 & \dots & 0 & 0 \\ b^{2} & 0 & 0 & 1 & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ b^{L-1} & 0 & 0 & 0 & \dots & 1 & 0 \\ -t' & 0 & 0 & 0 & \dots & 0 & 1 \\ p & 0 & 0 & 0 & \dots & 0 & 0 \\ \end{pmatrix} }$

に対してLLLアルゴリズムを適用します。すると、この行列の行ベクトルの線形結合で表される小さいベクトルとして

$\displaystyle{ (0, c_{0}', c_{1}', c_{2}', \ldots , c_{L-1}', 1) }$

が得られることが期待できます。実際は、 $1$ 列目が $0$ になることを期待して $1$ 列目全体に $2^{200}$ 倍の大きい重みをつけ、 $L+2$ 列目が $1$ になる ( $t'$ の係数が $1$ になる) ことを期待して $L+2$ 列目に $2^{10}$ 倍の重みを適当につけてみると、ある程度の確率で欲しいベクトルが得られました。

from Crypto.Util.number import *
from ptrlib import *

sock = Socket("nc xxx.xxx.xxx.xxx xxxxx")

params = eval(sock.recvlineafter("params: "))

ps = []
bs = []
for v in params:
    ps.append(v['p'])
    bs.append(v['base'])
p = prod(ps)
b = CRT_list(bs,ps)

L = 54
mid = 109
for _ in range(3):
    ts = eval(sock.recvlineafter("target: "))
    t = CRT_list(ts,ps)
    
    for i in range(L):
        t -= mid*pow(int(b),int(i),int(p))
        t%=p

    w1 = 2**10
    w2 = 2**200
    mat = [[0]*(L+2) for _ in range(L+2)]
    for i in range(L):
        mat[i][0] = pow(int(b),int(i),int(p))*w2
        mat[i][i+1] = 1
    mat[L][0] = -t*w2
    mat[L][L+1] = w1
    mat[L+1][0] = p*w2

    res = matrix(ZZ,mat).LLL()

    for l in res:
        if l[-1]<0:
            l = [-x for x in l]
        if l[0]==0 and l[-1]==w1 and all(abs(x)<13 for x in l[1:-1]):
            l = l[1:-1]
            ans = ""
            for x in l:
                ans += chr(int(mid+x))
            sock.sendlineafter("> ",ans)
            break

sock.interactive()

カスなので行列の $-t'$ のところを $t'$ にしていて10分ほど溶かしました...