RSA construct 函数漏洞

本文整理了国赛Ciscn两道利用RSA.construct函数漏洞的题目

Ciscn-badkey1

signal.alarm(10)
print("Give me a bad RSA keypair.")

try:
    p = int(input('p = '))
    q = int(input('q = '))
    assert p > 0
    assert q > 0
    assert p != q
    assert p.bit_length() == 512
    assert q.bit_length() == 512
    assert isPrime(p)
    assert isPrime(q)
    n = p * q
    e = 65537
    assert p % e != 1
    assert q % e != 1
    d = inverse(e, (p-1)*(q-1))
except:
    print("Invalid params")
    exit(2)

try:
    key = RSA.construct([n,e,d,p,q])
    print("This is not a bad RSA keypair.")
    exit(3)
except KeyboardInterrupt:
    print("Hacker detected.")
    exit(4)
except ValueError:
    print("How could this happen?")
    from secret import flag
    print(flag)

RSA.construct 中检测了$d$和$n$是否互素，而服务器的代码里缺少这一步，因此解题思路就是找到一对满足$d$和$n$有公因数的$p,q$。

不妨假设$p = gcd(d,n)$，那么$d=kp$。再根据$ed\equiv 1(mod\;(p-1)(q-1))$，可列出：

$e\cdot kp-1=k^′(p-1)(q-1)$

改写一下就是 $e\cdot kp-k^′(p-1)(q-1)=1$，注意到$k^′$的大小和$e$接近，因此可以先爆破$k^′$，把$k^′$当作已知量，对给定一个$p$，利用拓展欧几里得算法求出$k,(q-1)$和公因数$g$。如果公因数$g=1$而且$q$是质数，那就找到了一组解。

from Crypto.Util.number import *

while True:
    p = getPrime(512)
    e = 0x10001
    for k in range(2, e):
        g, x, y = xgcd(e*p, -k*(p-1))
        if g == 1:
            q = y + 1
            if len(bin(q)) == 514 and isPrime(q):
                print('p =', p)
                print('q =', q)

Ciscn-badkey2

e = 65537
p = getPrime(512)
while p % e == 1:
    p = getPrime(512)
    
signal.alarm(10)
print("Give me 10 bad RSA keypairs that have the same prime factor:", p)

used_n = []
for i in range(10):
    try:
        n = int(input('n = '))
        assert n % p == 0
        assert n not in used_n
        used_n.append(n)
        q = n // p
        assert q > 0
        assert q != p
        assert q.bit_length() == 512
        assert isPrime(q)
        assert q % e != 1
        d = inverse(e, (p-1)*(q-1))
    except:
        print("Invalid n")
        exit(2)

    try:
        key = RSA.construct([n,e,d])
        print("This is not a bad RSA keypair,")
        exit(3)
    except KeyboardInterrupt:
        print("Hacker detected.")
        exit(4)
    except ValueError:
        print("Good job!")

print("How could this happen?")
from secret import flag
print(flag)

这题里面的RSA.construct函数只传了$n,e,d$三个参数，RSA.construct函数需要从这三个参数里恢复出$p,q$，如果不能恢复就会报错ValueError。

下面是construct函数内部代码

ktot = d * e - 1
# The quantity d*e-1 is a multiple of phi(n), even,
# and can be represented as t*2^s.
t = ktot
while t % 2 == 0:
    t //= 2
    
# Cycle through all multiplicative inverses in Zn.
# The algorithm is non-deterministic, but there is a 50% chance
# any candidate a leads to successful factoring.
# See "Digitalized Signatures and Public Key Functions as Intractable
# as Factorization", M. Rabin, 1979
spotted = False
a = Integer(2)
while not spotted and a < 100:
    k = Integer(t)
    # Cycle through all values a^{t*2^i}=a^k
    while k < ktot:
        cand = pow(a, k, n)
        # Check if a^k is a non-trivial root of unity (mod n)
        if cand != 1 and cand != (n - 1) and pow(cand, 2, n) == 1:
            # We have found a number such that (cand-1)(cand+1)=0 (mod n).
            # Either of the terms divides n.
            p = Integer(n).gcd(cand + 1)
            spotted = True
            break
            k *= 2
            # This value was not any good... let's try another!
            a += 2
            if not spotted:
                raise ValueError("Unable to compute factors p and q from exponent d.")

其实是传统的已知私钥分解模数$n$​的方法，任意取一个底数$a$​，如果存在

$t=\frac{ed-1}{2^k},\quad t,k\in \N$

使得

$a^t\not\equiv 1\;or -1(mod\; n)且a^{2t}\equiv 1(mod\; n)$

那么$gcd(a^t-1,n)$或$gcd(a^t+1,n)$就为$n$​的因数。

但是问题在于，construct函数里用来检验的数$a$只是2-100之间的偶数。因此可以构造一对$p,q$使得函数无法对$n$进行分解。

为了将问题进行简化，先假设$p\equiv q\equiv 3(mod\;4)$​，容易得到：$(p-1)//2$​和$(q-1)//2$​都为奇数。那么求解思路就是找到的$p,q$​使得

$a^{\frac{(p-1)(q-1)}4}\equiv1(mod\;n)$

也等价于：

$ord_n(a)\leq\frac{(p-1)(q-1)}4$

根据中国剩余定理，如果$ord_p(a)=\frac{p-1}2,ord_q(a)=\frac{q-1}2$，就有：

$ord_n(a)=\frac{(p-1)(q-1)}4$

主要利用中国剩余定理是一个环同构：

$\begin{aligned}\varphi:\quad \mathbb{Z}_{m_1\cdots m_n}&\to\mathbb{Z}_{m_1}\oplus\cdots\oplus\mathbb{Z}_{m_n}\\ \bar{r}&\mapsto(\bar{r},\cdots,\bar{r})\end{aligned}$

并且 $\varphi(\bar 1)=(\bar1, \bar1)$。

所以如果对于所有检验的$a$，如果$a^{\frac{p-1}2}(mod\;p)$和$a^{\frac{q-1}2}(mod\;q)$同为1，就有：

$a^{\frac{(p-1)(q-1)}4}\equiv1(mod\;n)$

而只利用这一个限制条件基本上是不能完成的，因为对任意的 $p$，在2-100之间几乎一定会有$p$的原根。但如果要求 $a$ 是 $p$ 和 $q$ 的原根，即：

$a^{\frac{p-1}2}\equiv-1(mod\;p),a^{\frac{q-1}2}\equiv-1(mod\;q)$

利用 $\varphi(\overline {-1})=(\overline {-1}, \overline {-1})$从而：

$a^{\frac{(p-1)(q-1)}4}\equiv-1(mod\;n)$

这种情况下，$a^{\frac{(p-1)(q-1)}2}\equiv1(mod\;n)$，依然无法对$n$进行分解。

根据欧拉判别条件，如果$a^{\frac{p-1}2}\equiv1(mod\;p)$，$a$就是模$p$的二次剩余；否则$a^{\frac{p-1}2}\equiv-1(mod\;p)$，$a$就是模$p$的非二次剩余，两种情况下的勒让德符号$\left(\frac ap\right)$分别等于1、-1.

综合上面的结果，只要让$\left(\frac ap\right)=\left(\frac aq\right)$​，因此考虑$p\equiv q(mod\;a)$​，又因为$p\equiv q\equiv 3(mod\;4)$​，根据二次互反律可以得到：

$\left(\frac ap\right)=\left(\frac aq\right),a>2$

$a=2$时，需要$p\equiv q(mod\;8)$才能满足$\left(\frac ap\right)=\left(\frac aq\right)$.

二次互反律如下：

from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Math.Primality import *
from gmpy2 import next_prime
from math import prod
from random import randint
while 1:
    p = getPrime(512)
    if p % 4 == 3:
        break

t = []
for i in range(2, 50):
    if isPrime(i):
        t.append(i)

pmod = p % 614889782588491410

while 1:
    while 1:
        q = pmod + randint((2 ** 511) // 614889782588491410, (2 ** 512) // 614889782588491410) * 614889782588491410
        # q = getPrime(512)
        if isPrime(q) and q % 4 == 3:
            break
    n = p * q
    e = 0x10001
    d = inverse(e, (p - 1) * (q - 1))

    try:
        key = RSA.construct([n, e, d])

        continue
    except ValueError:
        print(p)
        print(q)
        break