AlpacaHack Round 3 に参加して、時間が余ったので WriteUp を書きました。

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=}")

いつもの RSA だが、 $p = q \cdot \rm{nextPrime}(r) + \rm{nextPrime}(q) \cdot r$ という形で p が生成されていて、 $r$ が既知。

最初にやった解法

$\rm{nextPrime}(r) - r = d_1, \rm{nextPrime}(q) - q = d_2$ とおくと、 $p = q \cdot \rm{nextPrime}(r) + \rm{nextPrime}(q) \cdot r$ より、 $p = q(r + d_1) + (q + d_2)r = 2qr + qd_1 + rd_2$ となる。

$d1,d2$ は非常に小さいので、 $p \fallingdotseq 2qr$ と近似できる。ここで、 $2pqr = 2nr$ にフェルマー法を使えば、 $p, 2qr$ に分解できそう…だが残念ながらこのままではうまくいかなかった。(ハマりポイント)

フェルマー法で素因数分解できるのは $(a + b)(a - b) \; (a, b \in \mathbb{N})$ の形の数だけなので、2つの分解後の値の偶奇が同じにならないといけない。上の方法だと、 $p$ は奇数、 $2qr$ は偶数なので、失敗してしまう。

代わりに $8pqr = 8nr$ を $2p, 4qr$ に分解すればよい。

from Crypto.Util.number import *
from gmpy2 import isqrt

n = 200697881793620389197751143658858424075492240536004468937396825699483210280999214674828938407830171522000573896259413231953182108686782019862906633259090814783111593304404356927145683840948437835426703183742322171552269964159917779
e = 65537
c = 77163248552037496974551155836778067107086838375316358094323022740486805320709021643760063197513767812819672431278113945221579920669369599456818771428377647053211504958874209832487794913919451387978942636428157218259130156026601708
r = 30736331670163278077316573297195977299089049174626053101058657011068283335270


def fermat_method(N):
    a = isqrt(N) + 1
    while True:
        b2 = a * a - N
        if isqrt(b2) ** 2 == b2:
            return (a - isqrt(b2), a + isqrt(b2))
        a += 1


x, y = fermat_method(n * r * 8)

p = GCD(n, x)
q = n // p

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

flag: Alpaca{q_and_r_have_nothing_to_do_with_QR_code}

後から思いついた解法

上の解法が想定解な問題にしては多く解かれすぎている気がする。

よく考えると、 $n = pq = 2q^{2}r + q^{2}d_1 + qrd_2$ で、 $r, d_1$ は既知で $d_2$ は全探索可能。二次方程式 $(2r + d_1)q^{2} + rd_{2}q - n = 0$ を解けば $q$ が求まる。

from Crypto.Util.number import *

n = 200697881793620389197751143658858424075492240536004468937396825699483210280999214674828938407830171522000573896259413231953182108686782019862906633259090814783111593304404356927145683840948437835426703183742322171552269964159917779
e = 65537
c = 77163248552037496974551155836778067107086838375316358094323022740486805320709021643760063197513767812819672431278113945221579920669369599456818771428377647053211504958874209832487794913919451387978942636428157218259130156026601708
r = 30736331670163278077316573297195977299089049174626053101058657011068283335270


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

d_1 = nextPrime(r) - r
for d_2 in range(2000):
    PR.<x> = PolynomialRing(ZZ)
    f = (2 * r + d_1) * x^2 + r * d_2 * x - n
    q = f.roots()
    if q:
        q = q[0][0]
        p = n // q
        break

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

flag: Alpaca{q_and_r_have_nothing_to_do_with_QR_code}

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):
  x=0
  factors = [deterministicGetPrime() for _ in range(bit // 64)]
  while True:
    p = 2 * prod(factors) + 1
    if isPrime(p):
      print(x,p)
      return p
    factors.remove(random.choice(factors))
    factors.append(deterministicGetPrime())
    x+=1

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 = 2 \cdot \prod_{i=1}^{16} p_i + 1$ という形で $p$ が生成されている。 $p_i$ は高々 3000 個ぐらいの既知の素数からランダムに選ばれている。

$p - 1$ の素因数の候補がかなり絞れているので、p-1 法を使えばよい。

$M = 2 \cdot \prod_{i=1}^N \rm{deterministicGetPrime}()$ とおく。このとき $M$ は $p-1$ の倍数なので、 $M = k(p-1) \; (k \in \mathbb{N})$ と書ける。

そして適当に取った値 $a$ (ただし $\gcd(a,n) = 1$ )に対して $a^{M} \pmod{n}$ を求めてみると、フェルマーの小定理により $a^{p-1} \equiv 1 \pmod{p}$ なので、 $a^{M} \equiv a^{k(p-1)} \equiv 1 \pmod{p}$ となる。

すると、 $a^{M} - 1 \equiv 0 \pmod{p}$ となるので、 $a^{M} - 1$ は $p$ の倍数。最後に $\gcd(a^{M} - 1, n)$ を取れば $p$ が求まる。

注意するべきこととして、 $M$ の素因数を増やしすぎると $a^{M} - 1$ が $p$ の倍数かつ $q$ の倍数になって $n$ の倍数になり、gcd をとっても $n$ が返ってきてしまうので、適当に素因数の数を調整する必要がある。

import random
from Crypto.Util.number import *

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."


n = 2350478429681099659482802009772446082018100644248516135321613920512468478639125995627622723613436514363575959981129347545346377683616601997652559989194209421585293503204692287227768734043407645110784759572198774750930099526115866644410725881688186477790001107094553659510391748347376557636648685171853839010603373478663706118665850493342775539671166315233110564897483927720435690486237018231160348429442602322737086330061842505643074752650924036094256703773247700173034557490511259257339056944624783261440335003074769966389878838392473674878449536592166047002406250295311924149998650337286245273761909
e = 65537
c = 945455686374900611982512983855180418093086799652768743864445887891673833536194784436479986018226808021869459762652060495495939514186099959619150594580806928854502608487090614914226527710432592362185466014910082946747720345943963459584430804168801787831721882743415735573097846726969566369857274720210999142004037914646773788750511310948953348263288281876918925575402242949315439533982980005949680451780931608479641161670505447003036276496409290185385863265908516453044673078999800497412772426465138742141279302235558029258772175141248590241406152365769987248447302410223052788101550323890531305166459


M = 2
for i in range(300):
    M *= deterministicGetPrime()

a = 2
s = pow(a, M, n)
p = GCD(pow(a, M, n) - 1, n)
assert 1 < p < n

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

flag: Alpaca{n0t_s0_sm00th_y3t_n0t_s0_s4f3}

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

BLS12-381 上の生成元 $G_1, G_2$ について、

$C_i = \begin{cases} x_{i}G_1 + x_{i+1}G_2 & (\rm{flag}\lbrack i\rbrack = 0)\\ x_{i+1}G_1 + x_{i}G_2 & (\rm{flag}\lbrack i\rbrack = 1) \end{cases}$

が与えられるので $\rm{flag}$ を復元する問題。

ここで $C_{i+1} - C_i$ を考えてみる。

$C_{i+1} - C_i = \begin{cases} (x_{i + 1} - x_{i})G_1 + (x_{i + 2} - x_{i + 1})G_2 & (\rm{flag}\lbrack i\rbrack = 0, \rm{flag}\lbrack i+1\rbrack = 0)\\ (x_{i + 2} - x_{i})G_1 & (\rm{flag}\lbrack i\rbrack = 0, \rm{flag}\lbrack i+1\rbrack = 1)\\ (x_{i + 1} - x_{i})G_2 & (\rm{flag}\lbrack i\rbrack = 1, \rm{flag}\lbrack i+1\rbrack = 0)\\ (x_{i + 2} - x_{i + 1})G_1 + (x_{i + 1} - x_{i})G_2 & (\rm{flag}\lbrack i\rbrack = 1, \rm{flag}\lbrack i+1\rbrack = 1) \end{cases}$

なので、 $\rm{flag}\lbrack i\rbrack$ がわかっている状況で $C_{i+1} - C_i$ が $G_1, G_2$ と線形従属か調べれば、 $\rm{flag}\lbrack i+1\rbrack$ が求まる。

2つの点 $P_1, P_2$ が線形従属かどうかは、Weil Pairing を用いて $e(P_1, P_2) = 1$ かどうかで判定できる。

$\rm{flag}\lbrack 0\rbrack$ だけ全探索 (といっても 0 か 1) すれば、あとは $\rm{flag}$ を復元できる。

from Crypto.Util.number import *

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

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

points = (省略)

ps = []
for x,y in points:
    p = E.point((x,y))
    ps.append(p)

flag = [0]
for i in range(len(ps) - 1):
    p = ps[i + 1] - ps[i]
    if p.weil_pairing(G1,o1) == 1 or p.weil_pairing(G2,o2) == 1:
        flag.append(1 - flag[-1])
    else:
        flag.append(flag[-1])

flag = int("".join(map(str, flag)),2)

print(long_to_bytes(flag))

flag: Alpaca{this_title_is_inpired_by_a_rhythm_game}

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)

3 種類の RollingHash でのハッシュ値が指定されるので、それを再現する文字列を 3 回求める問題。

$\sum_{j=0}^{n-1} s \lbrack j \rbrack \cdot (\mathrm{base}_{i})^{j} \equiv \mathrm{target}_{i} \pmod{p_{i}}$ を満たす $s$ (ただし、 $s$ は小文字アルファベットのみなので、文字コードに直すと $97 \leq s\lbrack i \rbrack \leq 122$ が必要) を求めればよい。

これは LLL で求めてあげればよい。

具体的には、次のような行列に対して、LLL を適用する。( $C$ は大きな定数, $109$ は a と z の中間の文字コード)

$\begin{pmatrix} 1 & 0 & \cdots & 0 & C (\rm{base}_{1})^{0} & C (\rm{base}_{2})^{0} & C (\rm{base}_{3})^{0} & 0 \\ 0 & 1 & \cdots & 0 & C (\rm{base}_{1})^{1} & C (\rm{base}_{2})^{1} & C (\rm{base}_{3})^{1} & 0 \\ \vdots & & \ddots & & & & & \vdots \\ 0 & 0 & \cdots & 1 & C (\rm{base}_{1})^{n-1} & C (\rm{base}_{2})^{n-1} & C (\rm{base}_{3})^{n-1} & 0 \\ 0 & 0 & \cdots & 0 & C \cdot p_1 & 0 & 0 & 0 \\ 0 & 0 & \cdots & 0 & 0 & C \cdot p_2 & 0 & 0 \\ 0 & 0 & \cdots & 0 & 0 & 0 & C \cdot p_3 & 0 \\ 0 & 0 & \cdots & 0 & C \cdot (\rm{target}_{1} - \sum_{i=0}^{n-1} 109 \cdot (\rm{base}_{1})^{i}) & C \cdot (\rm{target}_{2} - \sum_{i=0}^{n-1} 109 \cdot (\rm{base}_{2})^{i}) & C \cdot (\rm{target}_{3} - \sum_{i=0}^{n-1} 109 \cdot (\rm{base}_{3})^{i}) & 1 \\ \end{pmatrix}$

あとはいい感じに復元する。

# server からもらった値
params = [{"base": 7495669337736576833, "p": 15515047977171867379}, {"base": 281842360924091419, "p": 11836558304313656867}, {"base": 13737796388031820979, "p": 14218652448201901093}]
target = [13337056006799405152, 10654476647390251828, 143192050234617175]
t1,t2,t3 = target

mi = ord("a")
ma = ord("z")
mm = (mi + ma) // 2
C = 1000
N = 54 # MAX_LEN

x = [[0 for _ in range(58)] for _ in range(58)]

for i in range(N):
    x[i][i] = 1
    x[i][N] = pow(params[0]["base"], i, params[0]["p"]) * C
    x[i][N + 1] = pow(params[1]["base"], i, params[1]["p"]) * C
    x[i][N + 2] = pow(params[2]["base"], i, params[2]["p"]) * C
    t1 = (t1 - pow(params[0]["base"], i, params[0]["p"]) * mm) % params[0]["p"]
    t2 = (t2 - pow(params[1]["base"], i, params[1]["p"]) * mm) % params[1]["p"]
    t3 = (t3 - pow(params[2]["base"], i, params[2]["p"]) * mm) % params[2]["p"]

x[N][N] = params[0]["p"] * C
x[N + 1][N + 1] = params[1]["p"] * C
x[N + 2][N + 2] = params[2]["p"] * C
x[N + 3][N] = -t1 * C
x[N + 3][N + 1] = -t2 * C
x[N + 3][N + 2] = -t3 * C
x[N + 3][N + 3] = 1

M = Matrix(ZZ, x)
M = M.LLL()

for l in M:
    if l[-4] == 0 and l[-3] == 0 and l[-2] == 0 and l[-1] == 1:
        s = b""
        for i in range(N):
            s += bytes([mm + l[i]])
        s = s.decode()
        print(s)

flag: Alpaca{i_st1ll_h4v3_n0_id3a_why_r0ll1ng_h4sh_is_c4ll3d_th4t}