两道题，赛后被问到，顺便水水博客。

ezrsa·

题目：ezrsa.rar

2019 Crypto CTF的Clever Girl原题，甚至n、X和Y都没改，只是换了个flag。。。

大概意思是，现在有

$\frac{p}{p+1} + \frac{q+1}{q} = \frac{2s - X}{s + Y}$

知道 $X$ 、 $Y$ 和 $n = pq$ ，分解 $n$ ，把左边分式合并一下得

$\frac{2n + p + q + 1}{n + q} = \frac{2s - x}{s + y}$

然后分子分母分别相等得

$2n + p + q + 1 = 2s - x \\ n + q = s + y$

PS：准确来说这里两边分子分母是存在一个倍数关系，但是因为

$\text{GCD}(2n + p + q + 1, n + q) = \text{GCD}(2s - x, s + y) = 1$

所以这个倍数为 $1$ ，才直接相等。

消去 $s$ 后得到

$q = p + 1 + x + 2y$

两边乘上 $p$ 再整理一下，得到关于 $p$ 的方程

$p^2 + (1 + x + 2y)\ p - n = 0$

解方程求出 $p$ ，然后RSA解密即可。

参考代码：

# Sage
x = 153801856029563198525204130558738800846256680799373350925981555360388985602786501362501554433635610131437376183630577217917787342621398264625389914280509
y = 8086061902465799210233863613232941060876437002894022994953293934963170056653232109405937694010696299303888742108631749969054117542816358078039478109426
n = 161010103536746712075112156042553283066813155993777943981946663919051986586388748662616958741697621238654724628406094469789970509959159343108847331259823125490271091357244742345403096394500947202321339572876147277506789731024810289354756781901338337411136794489136638411531539112369520980466458615878975406339
c = 15380535750650959213679345560658190067564859611922563753882617419201718847747207949211621591882732604480600745000879508274349808435529637573773711729853565120321608048340424321537282281161623712479117497156437792084977778826238039385697230676340978078264209760724043776058017336241110097549146883806481148999

R = PolynomialRing(ZZ, 'p')
p = R.gen()
f = R(p^2 + p * (1 + x + 2*y) - n)
#print(f.roots())
p = f.roots()[0][0]
assert n % p == 0

q = n // p
import libnum
phi = (p-1) * (q-1)
e = 0x10001
d = e.inverse_mod(phi)
m = pow(c, d, n)
flag = libnum.n2s(int(m))
print(flag)

Dual ECDSA·

题目：Dual ECDSA.zip

听说是零解，后来打听了一下只是上题太晚，而且要爆破（主办方又等着背锅了

这个题有点麻烦，所以还是分一下标题（反正TOC修好了

题目分析·

首先题目有两个曲线，规模分别是256和521，说是NIST的参数所以应该都安全，可以先暂时排除曲线的漏洞。

继续分析，256的曲线用于伪随机数生成（PRNG），521的曲线用于ECDSA签名。

然后直接看embed_secret，S是flag的编码， $K$ 是PRNG产生的随机数，就直接可以确定需要做PRNG的随机数预测。

翻一下PRNG的调用，PRNG在三个地方被调用：pri_key的生成，sign中k_bytes的生成和embed_secret。

embed_secret就不用管了，因为是我要求的东西，k_bytes由于后面k做了hashfunc，所以即使恢复了k也不能恢复k_bytes，所以也不用管，所以现在和PRNG有关的只剩私钥pri_key，问题转化为知道ECDSA的两个签名恢复私钥。

解ECDSA私钥·

看ECDSA的sign，有

$s \equiv (e + p_{ri\_key} \cdot r) \cdot k^{-1} \pmod {O_{rder}}$

未知数的逆元有点难处理，挪一下

$s k \equiv e + p_{ri\_key} \cdot r \pmod {O_{rder}}$

然后分析一下大小，除了 $k$ 因为用sha256生成所以是256 bits，其他都是521 bits，256对于521来说算是“小”的数，所以可以格一格。

只有这样一个关系是不能直接上格的，因为 $p_{ri\_key}$ 是“大”的未知数，但是现在有两个签名，所以可以利用两个签名的关系消去 $p_{ri\_key}$ ，先把 $p_{ri\_key}$ 整理到一边

$p_{ri\_key} \equiv (s_i k_i - e_i) r_i^{-1} \pmod {O_{rder}}$

然后就有

$(s_1 k_1 - e_1) r_1^{-1} \equiv (s_2 k_2 - e_2) r_2^{-1} \pmod {O_{rder}} \\ r_2 (s_1 k_1 - e_1) \equiv r_1 (s_2 k_2 - e_2) \pmod {O_{rder}} \\ r_1 s_2 k_2 - r_q e_2 + r_2 e_1 \equiv r_2 s_1 k_1 \pmod {O_{rder}} \\ (r_2 s_1)^{-1} r_1 s_2 k_2 + (r_2 s_1)^{-1}(r_2 e_1 - r_q e_2) \equiv k_1 \pmod {O_{rder}}$

有点复杂，简化一下，令

$\begin{aligned} A &:= (r_2 s_1)^{-1} r_1 s_2 \\ B &:= (r_2 s_1)^{-1}(r_2 e_1 - r_q e_2) \end{aligned}$

就是

$A k_2 + B \equiv k_1 \pmod {O_{rder}} \\ A k_2 - k_{12} O_{rder} + B = k_1$

然后就可以构造格基（ $D = 2^{256}$ 为配平数）

$M := \begin{bmatrix} A & 0 & 0 \\ -O_{rder} & 1 & 0 \\ B & 0 & D \end{bmatrix}$

就有

$(k_2, k_{12}, 1) \cdot M = (k_1, k_{12}, D)$

大概估算一下（需要一点格攻击理论，略）

$\| (k_1, k_{12}, D) \| \approx 2^{256} < 2^{\frac{521+256}{3}} \approx \sigma(M)$

可以格。

然后规约解出 $k_1$ ，代入

$p_{ri\_key} \equiv (s_i k_i - e_i) r_i^{-1} \pmod {O_{rder}}$

求出私钥 $p_{ri\_key}$

分析PRNG·

有了私钥后再来分析PRNG的运作，首先无论是random_bytes还是random_bit_integer都是用round去运作，所以直接看round。

round的输出就是 $(S_{tate} \cdot Q).x$ ，然后抹去低16 bits，每次round后都会_update，对state进行更新

$S_{tate,\ i+1} = (S_{tate,\ i} \cdot P).x$

然后random_bytes或random_bit_integer中把round完抹去16 bits后剩下的240 bits拼接起来，再取高 $n$ bits/bytes作为输出。

私钥 $p_{ri\_key}$ 是PRNG生成的第一个伪随机数， $p_{ri\_key}$ 是521 bits，所以在random_bit_integer中有rounds=3，把 $p_{ri\_key}$ 切分成三段：

$p_{ri\_key} := ( \text{sk}_0\text{ (240 bits)}\ |\ \text{sk}_1\text{ (240 bits)}\ |\ \text{sk}_2\text{ (41 bits)})$

可得

$\begin{aligned} \text{sk}_0 &= (S_{tate,\ 0} \cdot Q).x\ \text{ (hide low 16 bits)} \\ S_{tate,\ 1} &= (S_{tate,\ 0} \cdot P).x \\ \text{sk}_1 &= (S_{tate,\ 1} \cdot Q).x\ \text{ (hide low 16 bits)} \\ & \cdots\ \cdots \end{aligned}$

Dual_EC_DRBG后门·

根据题目提示可以搜搜DUAL_EC的后门（DUAL_EC BACKDOOR），代入这题中，大概意思是，如果知道一个 $n$ ，使得 $P = n Q$ ，就有

$S_{tate,\ 1} = (S_{tate,\ 0} \cdot P).x = (S_{tate,\ 0} \cdot n \cdot Q).x = (n \cdot (S_{tate,\ 0} \cdot Q)).x$

其中 $S_{tate,\ 0} \cdot Q$ 就是曲线上以 $\text{sk}_0$ （补全低16 bits）为x坐标的点，爆破被隐藏的16 bits，即可恢复 $S_{tate,\ 1}$ ，然后用 $S_{tate,\ 1}$ 去做后面的随机数预测。

PS：这里是这道题最恶心的地方，因为椭圆曲线乘法的效率并不高，还好这里 $\text{sk}_0$ 被隐藏的值并不大，测试了一下完整爆破大概要半小时，由于值不大所以爆了大概五分钟。

最后问题就剩下，如何找 $n$ 。

Meet in Middle爆n·

观察一下 $P$ 和 $Q$ 的生成，都是在 $S_{tate,\ 0} \cdot G$ 上乘了一个规模 $2^{20}$ 的随机数，姑且可以令

$\begin{aligned} P = p \cdot S_{tate,\ 0} \cdot G \\ Q = q \cdot S_{tate,\ 0} \cdot G \end{aligned}$

可以轻易地得到

$q P = p Q$

如果想同时爆破 $p$ 和 $q$ 的话，复杂度是 $2^{20+20}$ ，不大可行，但如果用中间相遇的话，复杂度是 $2 \cdot2^{20}$ ，可行。

然后就是Meet in Middle的套路了，首先爆破 $2^{20}$ 个 $q_i P$ ，用set存起来（因为set的搜索复杂度是log），然后爆破 $2^{20}$ 的 $p_j Q$ ，如果发现有 $p_j Q$ 落在set中，即这个 $p_j$ （大概率）就是 $p$ ，最后再爆一次 $q_i P \overset{?}{=} p Q$ 把 $q$ 也爆出来即可。

然后计算 $n \equiv q^{-1} p \pmod {O_{rder}}$ 就得到 $n$ 。

随机数预测·

最后计算一下round了多少次，把state更新到对应位置即可。

参考代码：

# Sage
from hashlib import sha256
from tqdm import tqdm
import libnum

# safe curve parameters
# NIST P-256
NIST_256 = (
    NIST_256_P := 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff,
    NIST_256_K := GF(NIST_256_P),
    NIST_256_A := NIST_256_K(0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc),
    NIST_256_B := NIST_256_K(0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b),
    NIST_256_CURVE := EllipticCurve(NIST_256_K, (NIST_256_A, NIST_256_B)),
    NIST_256_GEN := NIST_256_CURVE(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5),
    NIST_256_ORDER := 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 * 0x1
)
NIST_256_CURVE.set_order(NIST_256_ORDER)

# NIST P-521
NIST_521 = (
    NIST_521_P := 0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff,
    NIST_521_K := GF(NIST_521_P),
    NIST_521_A := NIST_521_K(0x01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc),
    NIST_521_B := NIST_521_K(0x0051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00),
    NIST_521_CURVE := EllipticCurve(NIST_521_K, (NIST_521_A, NIST_521_B)),
    NIST_521_GEN := NIST_521_CURVE(0x00c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66, 0x011839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650),
    NIST_521_ORDER := 0x01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409 * 0x1
)
NIST_521_CURVE.set_order(NIST_521_ORDER)

pub_key = NIST_521_CURVE(1284057549640164959065310299974715949780883842543987295579845101714329490371866414620403984059688256268916840753322634228189993387677187086805910608913877240, 2871828286437266324077547225563521746454811466060839307814808187038977339931268294634407454097422974392263009902452840007777204947601588882408605940896033213)
P = NIST_256_CURVE(44709432769601533647164055172337077577197388971405441067408648552120273899439, 5146142757398992761089276624845497246953677849813524410717292563307277646248)
Q = NIST_256_CURVE(79560279623532866071675257110279687192436171302512534366260446974055296569775, 26859165885861631636190724510665269671005299628857498631278393159264950495322)
sig1 = (5089140070991418866765317340224488883853896999535207637664248575094162436344850602488004304731596114325990969313189073305315747359692187240695087335320008392, 2992276069467527712690275343211346442634209004250088074729707123246604474164141954635893526085370984681060737605953014207436859072640690696867665537702633916)
sig2 = (2872033002190388322518484598506887434919678523735730644910370844671443735688758643453429779989693237887466003372385925789250465970691404896872113423303038969, 6723990832715616500336095376073676701350917549865164961917998759715703447465536431516566237824694270482046698060410301496792150963281602144685882679390639901)
emb_flag = NIST_521_CURVE(3956409056364638168400543181298452742239103965766830338476029710731353557119679043260892196298159250455141959488613009091004454622819349680688797299967002549, 2951776604917486290836695572957027106817487586162444507028471362837490084205243361576174502575216282250806141358680269076670568688622463255476309019517775311)
r1, s1 = sig1
r2, s2 = sig2

m1 = b"AN INFAMOUS PRNG NAMED DUAL_EC BACKDOORED BY NSA, FINALLY CONFIRMED BY SNOWDEN IN 2013."
m2 = b"NO ONE CAN EXTRACT THE BACKDOOR! UNLESS YOU CAN BREAK THE ECDSA SIGNATURE SCHEME / ECDLP!"
e1 = Integer(sha256(m1).hexdigest(), 16)
e2 = Integer(sha256(m2).hexdigest(), 16)

A = (r2 * s1).inverse_mod(NIST_521_ORDER) * r1 * s2 % NIST_521_ORDER
B = (r2 * s1).inverse_mod(NIST_521_ORDER) * (r2 * e1 - r1 * e2) % NIST_521_ORDER
D = 2^256
M = matrix(ZZ, [
  [A, 0, 0],
  [-NIST_521_ORDER, 1, 0],
  [B, 0, D]
])
L = M.LLL()
k1 = L[0][0]
pri_key = (s1 * k1 - e1) * r1.inverse_mod(NIST_521_ORDER) % NIST_521_ORDER
assert pri_key * NIST_521_GEN == pub_key
print('pri_key = %d' % pri_key)
#pri_key = 3485610893951725241527993343531545160643467731154038572265284511034638641341028810868621014490583010060929949171052960921516880852738013166910870634224098439

# P = p g = p s G
# Q = q g = q s G
# q P == p Q
qP = set()
PP = P
for qi in tqdm(range(1, 2^20)):
  qP.add(PP)
  PP += P
res_p = []
QQ = Q
for pi in tqdm(range(1, 2^20)):
  if QQ in qP:
    res_p += [Integer(pi)]
    print('p = %d' % pi)
  QQ += Q
assert len(res_p) == 1
p = res_p[0]
# 02:46 + 02:35
#p = 593765
sG = p * Q

PP = P
for qi in tqdm(range(1, 2^20)):
  if PP == sG:
    q = Integer(qi)
    print('q = %d' % q)
    break
  PP += P
#q = 357549
n = q.inverse_mod(NIST_256_ORDER) * p % NIST_256_ORDER

assert pri_key.nbits() == 521
sk0 = pri_key >> (521 - 240)
sk1 = (pri_key >> (521 - 240*2)) & ((1 << 240) - 1)
sk2 = pri_key & ((1 << (521 - 240*2)) - 1)
sk0h = sk0 << 16
for sk0l in tqdm(range(2^16)):
  try:
    SK0 = NIST_256_CURVE.lift_x(sk0h + sk0l)
  except ValueError:
    continue
  state1 = Integer((n * SK0).xy()[0])
  test_sk1 = Integer((state1 * Q).xy()[0]) >> 16
  if test_sk1 == sk1:
    print('state1 = %d' % state1)
    break
# 04:36<25:47
#state1 = 26326889805989780770448309515391194094516636869818202210707443829278309569816

def getState(sn):
  staten = state1
  for i in range(sn - 1):
    staten = Integer((staten * P).xy()[0])
  return staten
sk2 = pri_key & ((1 << (521 - 240*2)) - 1)
state2 = getState(2)
assert bin(Integer((state2 * Q).xy()[0]) >> (256 - sk2.nbits())) == bin(sk2)

state = getState(3*3)
K = 0
for _ in range(3):
  out = Integer((state * Q).xy()[0]) >> 16
  K = (K << 240) + out
  state = Integer((state * P).xy()[0])
K = K >> (3*240 - 521)
print('K = %d' % K)

S = K.inverse_mod(NIST_521_ORDER) * emb_flag
flag = libnum.n2s(int(S.xy()[0]))
print(flag)
# 10m36s