杂题闲记-2

GACTF2020

Elgamal-RSA

一开始直接把key给了。。。不过本身Elgamal部分本身就很简单，其实并无所谓

先求解Elgamal，计算出secret:

已知：

$c_1 = g^r $

$ c_2 = m * g^{dr} $

$ c_{11} = g^{B*r + A} $

$ c_{12} = m * g^{B*r + A} $

$ h = g ^ d$

推导：

\[ c_2 ^{-B} = m^{-B} * (g^d)^{-Br} \]

\[ c_{12} * c_2^{-B} = m^{1-B} * (g^d)^A \]

\[ (c_{12} * c_2^{-B})^{\frac{1}{1-B}} = m * (g^d)^{\frac{A}{1-B}} \]

\[ (c_{12} * c_2^{-B})^{\frac{1}{1-B}} * h^{\frac{1-B}{A}} = m\]

从而得到secret，之后计算$\phi(n)$，发现有 $e|\phi(n)$，但$n$有6个素因子，都不大，故对每个素因数$p_i$，先在$ p_i^{l_i}$下decrypt，即把e当作

\[ \frac{e}{gcd(e, \phi(p_i^{l_i}))} \]

得到$m_i$，之后求模$ p_i^{l_i}$下$m_i$的 $gcd(e, \phi(p_i^{l_i}))$ 次根，然后CRT即可，完整exp如下：

from Crypto_tools import *

g, h, A, B, p, q = 
c1, c2 = 
c11, c12 = 

# calculate the secret
g_br = (inverse(pow(g, A, p), p) * c11) % p
tmp = pow(c12 * inverse(pow(c2, B, p), p), inverse(1-B, q), p)
m = tmp * inverse(pow(h, A * inverse(1-B, q), p), p)

c = 
n = m % p
e = 0x1296
primes = [232087313537, 104280142799213, 28079229001363, 653551912583, 42044128297, 802576647765917]
index = [5, 6, 14, 15, 6, 7]

# check the primes
base = 1
for i in range(len(primes)):
    base = base * (primes[i]**index[i])
print(base == n)

phi = []
for i in range(len(primes)):
    phi.append(primes[i] ** (index[i]-1) * (primes[i]-1))

low_e = []
for i in phi:
    low_e.append(int(gcd(i, e)))

low_n = []
for i in range(len(primes)):
    low_n.append(primes[i] ** index[i])

low_c = []
for i in range(len(primes)):
    low_c.append(pow(c, inverse(e//low_e[i], phi[i]), low_n[i]))

for i in range(len(low_n)):
    print('\n%d primes'%(i+1))
    print('n = ' + str(low_n[i]))
    print('root = ' + str(low_e[i]))
    print('c = ' + str(low_c[i]))

# use sage's 'Mod(c,n).nth_root(root)'
candidate = [353407247512303965045365245273514113979254413155723038594, 118406996121335867872417220406950412663021908207429086460086709649567668592818842789, 40838194187011975196269228876765908865444944296745005849695833986972327289154552784299932702051642970620861282724383667531261441125357573017325620944049102688903343462724551047586535304480, 1695123516800295425246681257666516560158663239197207672350847711896311171077931594423061655507605147792730816972030575396344034948137641207075718430653779535756721008018915068547, 4723044149650256515091565811539899787013565528592340044059397238, 214489300896472271161382790695870756301586580281999239401045130054091244899629639375835223662794331991713]

# check
for i in range(len(candidate)):
    assert pow(candidate[i], e, low_n[i]) == c % low_n[i]

# find all roots
roots = []
for i in range(len(candidate)):
    roots.append(all_roots_mod(low_n[i], candidate[i], low_e[i], phi[i]))

# check again
for i in range(len(candidate)):
    for j in roots[i]:
        assert pow(j, e, low_n[i]) == c % low_n[i]

# solve
for i_1 in range(6):
    for i_2 in range(6):
        if i_1 == i_2:
            continue
        for i in roots[i_1]:
            for j in roots[i_2]:
                possible = long_to_bytes(GCRT([low_n[i_1], low_n[i_2]], [i, j])[0])
                if all_ascii(possible):
                    print(possible)
                    sys.exit()

Square

这题本质是要求出二元二次方程的整数通解，即求出解之间的递推式。使用这个工具可以轻松解决，此处探讨一种特殊情况的原理（太久不看分析，感觉完全不会构造了orz），一般性情况的原理可见这里。

二元二次方程可定义通式：$Ax^2 + Bxy+Cy^2+Dx+Ey+F = 0 \quad (1)$

且 $\exists k \in Z_+, \ let \ B^2 -4AC = k^2$ （此处即为特殊条件）

之后进行构造求解，根本思想是降低次数，即通过构造简化为二元一次方程求解

一般需要降次时，容易想到需要构造平方来，于是先使用一个系数产生可配项

$(1) * 4A $

\[ \Rightarrow 4A^2x^2 + 4ABxy + 4ACy^2 +4ADx +4AEy + 4AF = 0 \quad (2)\]

之后2式加减$(B^2y^2 + 2BDy +D^2)$ （通过这个构造trick来化简)

\[ \Rightarrow 4 A^2 x^2 + 4 A B+x y + B^2 y^2 + 4 A D x + 2 B D y + D^2 + \]

\[ 4 A C y^2 - B^2 y^2 + 4 A E y - 2 B D y + 4 A F - D^2 = 0 \]

由此构造平方和，化简得$(2Ax+By+D)^2 - (ky)^2 +(4AE-2BD)*y = D^2 - 4AF \quad (3)$

再将左边构造成两个平方差

$(3) * k^2 + (2AE-BD)^2 $

\[ \Rightarrow (2Akx + Bky +Dk)^2 - (k^2y + (2AE-BD))^2 = D^2k^2 - 4AFk^2 + (2AE-BD)^2 \]

由此利用平方差公式，得到：

\[ \Rightarrow [(2Akx + Bky +Dk) + (k^2y + 2AE-BD)][(2Akx + Bky +Dk) - (k^2y + 2AE-BD)] \]

\[ = D^2k^2 - 4AFk^2 + (2AE-BD)^2\]

此时分两种情况讨论：

设$C = D^2k^2 - 4AFk^2 + (2AE-BD)^2$

C为0：

即有$D^2k^2 - 4AFk^2 + (2AE-BD)^2 = 0$，则左边的积的两个因子（简称为$f_1, f_2$）必然有一个因子为0，这就转换成了两个二元一次方程，之后只需判断有无解，选择相适的解集即可。
C不为0：

此时对C进行因子分解，得到所有因子（包含所有负数）$divisor_i, i = 1, 2, \dots, s$

对$f_1, f_2$，逐个判断$f_1 = divisor_i$ 解的正确性，遍历$divisor$ 数列，必然可以得到原方程的解集。

本题具体解法比较麻烦，属于较为一般的情况，了解构造思想即可。

RCTF2020

infantECC | working

使用定理：

GF(p)上形为$y^2 = x^3 + b$ 的椭圆曲线在$p\equiv 2 \mod 3$时，阶数为p+1（这种曲线即为所谓的超奇异曲线）

emmmm准备复现的时候发现ROIS把博客删了???，只找到了Hellman的wp，但我主要是想看看多元Copper Smith的使用方法。。。所以就只能面向exp复现了。。。

猜测$E_p, E_q$ 均为超奇异曲线（否则无法做题）

则已知s，r的低256位，且 $s*r \equiv \mod ((p+1)*(q+1))$

$(p+1)*(q+1) = n + (p+q) + 1$，n未知，但已知$E_n$两个点，故通过ECC可以很容易复原出来：

$k*n = gcd((x_1^3+b-y_1^2), (x_2^3+b-y_2^2))$

k较小，得到结果分解即可得到n：

1
2
3

N = gcd(int(Cy)^2-int(Cx)^3-int(b), int(Ty)^2-int(Tx)^3-int(b))
# 下面代码为消除k
N = factor_trial_division(N, 1000)[-1][0]

将s，r看作e，d，由此问题转化为了类似于Copper Smtih中Partial d的情况

可知有 $k*(p+1)*(q+1) = e*d - 1$ ，且$d < 2^{412}$

$\Rightarrow k *(n + p + q + 1) = e*d -1$

设$s = p+q$，且已知d的低256位$d_{low}$，则 $\Rightarrow k * (n+s+1) = e * (d_{high}* 2 ^{256}+ d_{low})-1$

存在三个变量：$k, s, d_{high}$

此处使用三元Copper Smith 求解，先考虑三个变量的上界：

$k = \frac{e*d - 1}{(p+1)*(q-1)} \leq 2 ^{1024 + 412 - 1024} = 2 ^ {412}$

$s = (p+1)*(q+1) \leq 2 ^ {1024}$

$d_{high} = \frac{d - d_{low}}{2^{256}} \leq 2^{412-256} = 2^{156}$

这里考虑类似于Boneh and Durfee attack，具体原理可以先看这篇论文

尝试使用二元Cooper去解

设$s = p+q$

则 $k'*(n + s + 1) \equiv e * d_{low} -1 \mod 2^{256}$

还有 $p^2 - sp +n \equiv 0 \mod 2^{256}$

上式乘$p$，下式乘$k'$，相加得到$k'np + k'p + p +k'p^2 + k'n \equiv ed_{low}p \mod 2^{256}$

$\Rightarrow k'p^2 + (k'n + k' + 1 - ed_{low}) p + k'n \equiv 0 \mod 2^{256}$

此时只剩下两个未知量$k', p$，通常$k'$是采用在$(0, e-1)$ 下爆破来获取，而这里e为1024位，显然并不现实。。

De1CTF2020

easy_RSA

Ver学长tql，比赛的时候还没入门，于是只能复现的时候看了，本题貌似不小心和D3CTF的撞了，学长后来也很懵233

本题利用的是Howgrave-Graham and Seifert’s Attack是基于Wiener's Attack（$d < N^{\frac{1}{4}}$）和Guo's Common Modulus Attack（$d < N^{\frac{1}{3}}$）的一种攻击，通过这篇paper，可以比较清晰的了解原理，也可以看官方wp

可行性分析：

相较于其借鉴的两种攻击，此种攻击对d的范围限制更小，根据所有公钥数量r，有约束$d < N^{\frac{3+r}{7r}}$，原题中给了两个e，故r = 2，即需$d< N^{\frac{5}{14}}$，而所给d范围限定在$[N^{\frac{1}{3}}, 2^{49} *N^{\frac{1}{3}} ]$，约为$[N^{\frac{1}{3}}, N^{\frac{1}{3}+0.023} ]$，即d在680bit到730bit之间。

而又有 $\frac{1}{3} + 0.023 \approx 0.357 \approx \frac{5}{14}$

可以看到d基本是在范围内的，故攻击可行

已知：n组$e_i$，满足$e_i * d_i = 1 + ki * \phi(N), d < N^{\delta}$

本题使用了$lcm(N)$，相当于$e_i * d_i = 1 + ki * \frac{\phi(N)}{g}$，并无无太大影响

依据四个等式可以列出矩阵：

之后为了能够正确格基约化，需要将各分量放缩到数量级相近，通过简单计算使用如下放缩矩阵即可：

之后直接求解方程组，得到向量$x_2$，然后利用如下推导，即可求出$\phi(N)$ \[ e_i * d_i = 1 + k_i * \frac{\phi(N)}{g}\\ \Rightarrow \phi(N) = \frac{e_id_ig-g}{k_i}\\ \Rightarrow \phi(N) = \frac{e_id_ig}{k_i} + \frac{g}{k_i}\\ \Rightarrow e_i * \frac{k_2d_1g}{k_1k_2}-1 \leq \phi(N) \leq e_i * \frac{k_2d_1g}{k_1k_2} + 1 \]

最后等式中未知的分母，分子即为$x_2$向量中的分量，exp如下：

from sage.all import *
from sage.all_cmdline import *


N = 
e1 = 
e2 = 
c = 
E = [e1, e2]

for i in range(2048//3,  2048//3 + 50):
    x = Integer(i) / Integer(2048)
    print(i)
    N_1 = round(N**(Integer(1)/Integer(2)))
    N_2 = round(N**(1+x))

    N_3 = round(N**(Integer(i) / Integer(100)))
    A = Matrix(ZZ, [[N,   -N_1 * N,   0,            N**2],
                    [0,   N_1 * e2,  -N_2 * e2,     -e2*N],
                    [0,    0,         N_2 * e1,     -e1*N],
                    [0,    0,         0,            e1*e2]])

    AL = A.LLL()
    C = Matrix(ZZ, AL[0])
    B = A.solve_left(C)[0]

    phi_base = floor(e2 * (B[1] // B[0]))
    for j in range(-1, 2):
        phi = phi_base + j
        for e in E:
            d = int(Zmod(phi)(65537).inverse_of_unit())
            m = int(Zmod(N)(c)**d)
            if m.bit_length() < 1024:
                print(m.to_bytes(64, byteorder='big'))
                sys.exit(1)

~~奇怪的想法~~

emmm我在复现的时候看paper，就觉得很奇怪，为什么构造的等式一定是这四个呢：

从理论上来说，将$G_{1,2}$ 替换成$k_1W_2$，似乎也无伤大雅，但我尝试这样构造之后，并没有成功，即便爆破了放缩的系数，仍然无法求解，而且误差相当的大，后来算了一波bound，发现确实不符合2333，大概作者写的时候可能也经历了这种尝试吧。

不过这题也帮我梳理了一种构造Latiice时的步骤：

寻找n组等式，其中具有n个未知量
通过这n组等式，提取出n个未知量作为初始向量x，构造秩为n的矩阵A，并有$xA = y$
计算向量y的范数，分析各分量的数量级，通过一个放缩矩阵D，将y向量各分量尽量放缩到一个数量级上
对矩阵$A' = AD$使用格基约化，利用约简出的向量和$A'$ 矩阵求出向量x，得到欲求量

Pwnhub2020 Crypto theme

CoinFlip

知识点：

Elgamal加密时所选p（即模）的安全准则：DDH假设（Decisional Diffie–Hellman）

对于随机选取的$a, b \in Z_p$，已知$g^a, g^b$，产生的 $g^{ab}$ 接近于$Z_p$ 上的随机数

可以形式化为：

若p存在k次剩余$r_k$，$\frac{p-1}{k}$ 也应为一大素数
对于p上的任意椭圆曲线E，E的阶很大
对于p上的超椭圆曲线，其Jacobian的阶很大

如上所述，GF上的乘法群并不符合DDH假设，因为其可以通过计算Lengendre符号区分$g^ab$和一般随机序列。故直接根据所给公钥，区分两组明文，但存在一定概率性（两组明文的Lengendre符号可能相同）。

测试exp如下：

from Crypto.PublicKey import ElGamal
from Crypto.Util.number import bytes_to_long
import os
from random import SystemRandom
from Crypto_tools import *


p = 
g = 
y = 
pubkey = ElGamal.construct((p, g, y))
base = jacobi(y, p)
for i in tqdm(range(2**10)):
    rnd = SystemRandom()
    msg1 = bytes_to_long(b"Head" + os.urandom(124))
    msg2 = bytes_to_long(b"Tail" + os.urandom(124))

    count = 0
    while True:
        coin = rnd.randrange(2)
        gift = pubkey._encrypt([msg1, msg2][coin], rnd.randrange(1, p - 1))
        check_1 = jacobi(gift[0], p)
        check_2 = jacobi(gift[1], p)
        ans = 0
        if check_1 == 1:
            if check_2 == 1:
                ans = 0
            else:
                ans = 1
        elif check_1 == -1 and base == -1:
            if check_2 == 1:
                ans = 1
            else:
                ans = 0
        if ans == coin:
            count += 1
            if count == 50:
                print('try %d times' % i)
                print('flag{LordRiot\'s test flag}')
                exit()
        else:
            break

注意pycrypto中的Elgamal由于继承关系，encrypt函数为空，应调用_encrypt函数。

Oblivious transfer

核心漏洞是在于始终使用一组RSA公私钥，从而可以构造两个连接，利用不变量来爆破，wp郑佬写的很详细了，这里就不详述了，我这里把大小写区分了一下，大概跑一百多次就可以跑出结果，exp如下：

from pwn import *
from Crypto.Util.number import *
from itertools import product

# main-decrypt
main_connection = remote('127.0.0.1', 10001)
n = int(main_connection.recvline())
e = int(main_connection.recvline())
init_x0 = int(main_connection.recvline())
init_x1 = int(main_connection.recvline())
main_connection.sendline(str(init_x0))
msg0 = int(main_connection.recvline())
init_enc1 = int(main_connection.recvline())

# sub-attack
attack_connection = remote('127.0.0.1', 10001)
attack_connection.recvline()
attack_connection.recvline()
possible = [set(range(256)) for _ in range(256)]
cnt = 1
little_min = 97
little_max = 122
big_min = 65
big_max = 90

while True:
    x0 = int(attack_connection.recvline())
    x1 = int(attack_connection.recvline())
    attack_connection.sendline(str(init_x0 - init_x1 + x0))
    enc0 = int(attack_connection.recvline())
    enc1 = int(attack_connection.recvline())
    attack_connection.sendline('0')
    attack_connection.sendline('0')

    bytes_enc = long_to_bytes(enc0, 256)[::-1]

    for i in range(256):
        if i == 0:
            carrymin = 0
            carrymax = 0
        else:
            if min(possible[i - 1]) + big_min >= 256:
                carrymin = 1
            else:
                carrymin = 0
            if max(possible[i - 1]) + little_max < 256:
                carrymax = 0
            else:
                carrymax = 1

        if i == 256 - 1:
            little_start = bytes_enc[i] - carrymax
            little_end = bytes_enc[i] - carrymin
            big_start = bytes_enc[i] - carrymax
            big_end = bytes_enc[i] - carrymin
        else:
            little_start = bytes_enc[i] - little_max - carrymax
            little_end = bytes_enc[i] - little_min - carrymin
            big_start = bytes_enc[i] - big_max - carrymax
            big_end = bytes_enc[i] - big_min - carrymin
        tmp = set(x % 256 for x in range(little_start, little_end + 1)) | set(x % 256 for x in range(big_start, big_end + 1))
        possible[i] &= tmp

    limit = 1
    for i in range(256):
        limit *= len(possible[i])
    cnt += 1
    print(cnt, limit.bit_length())

    if limit < 50000:
        print("Trying all possibilities")
        for b in product(*possible):
            m = bytes_to_long(bytes(b[::-1])) % n
            if pow(m, e, n) == init_x0 - init_x1:
                main_connection.sendline(str(msg0))
                main_connection.sendline(str((init_enc1 - m) % n))
                print('Got')
                print(main_connection.recvline())
                main_connection.interactive()
        print("Failed")
        attack_connection.close()
        main_connection.close()
        exit()