Dual RSA——双生RSA，对偶RSA

发表于 更新于 本文字数： 6.4k 阅读时长 ≈ 6 分钟
有关Dual RSA的简要笔记

Dual RSA

定义

Dual RSA 是一种 RSA 变体，目的是减少公钥和私钥的存储空间要求，本质上是不同的模数共享同一个公钥和私钥指数。

比如说，对于两个模数 \(N_1,N_2\)，满足 \[ ed=1\pmod{\varphi(N_1)}\newline ed=1\pmod{\varphi(N_2)} \] 即满足 \[ ed=1+k_1\varphi(N_1)\newline ed=1+k_2\varphi(N_2) \] 为生成这样的公钥，可以采用以下方法生成模数。

输入 \((n_e,n)\)，其中 \(n_e\) 表示 \(e\) 的位数，\(n\) 表示 \(N\) 的位数，且要满足 \(n_e<n/2\)，为方便表示，令 \(n_t=n/2-n_e\)

  1. 随机选择 \(n_e\) 位的 \(x_1\) 和 \(n_t\) 位的 \(x_2\)，使得 \(p_1=x_1x_2+1\) 是素数
  2. 随机选择 \(n_t\) 位的 \(y_2\)，使得 \(p_2=x_1y_2+1\) 是素数
  3. 随机选择 \(n_e\) 位的 \(y_1\)，使得 \(q_1=y_1y_2+1\) 是素数
  4. 随机选择 \(n_e\) 位的 \(e\)，使得 \(\gcd(x_1x_2y_1u_2,e)=1\)；计算 \(d,k_1\) 满足 \(ed=1+k_1x_1x_2y_1y_2\)，使得 \(q_2=k_1x_2+1\) 是素数（其中 \(k_2=y_1\)）
  5. 返回 \(N_1=p_1q_1,N_2=p_2q_2\)

一个生成三模数的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from Crypto.Util.number import *

def genKey(nbits, dbits):
    bbits = (nbits // 2 - dbits) // 2

    while True:
        a = getRandomNBitInteger(dbits)
        b = getRandomNBitInteger(bbits)
        c = getRandomNBitInteger(bbits)
        p1 = a * b * c + 1
        if isPrime(p1):
            # print("p1 =", p1)
            break

    while True:
        d = getRandomNBitInteger(dbits)
        p2 = b * c * d + 1
        if isPrime(p2):
            # print("p2 =", p2)
            break

    while True:
        e = getRandomNBitInteger(bbits)
        f = getRandomNBitInteger(bbits)
        q1 = e * d * f + 1
        p3 = a * e * f + 1
        if isPrime(q1) and isPrime(p3):
            # print("p3 =", p3)
            # print("q1 =", q1)
            break

    while True:
        d_ = getRandomNBitInteger(dbits)
        if GCD(a * b * c * d * e * f, d_) != 1:
            continue
        e_ = inverse(d_, a * b * c * d * e * f)
        k1 = (e_ * d_ - 1) // (a * b * c * d * e * f)
        assert e_ * d_ == (a * b * c * d * e * f) * k1 + 1
        q2 = k1 * e * f + 1
        q3 = k1 * b * c + 1
        if isPrime(q2) and isPrime(q3):
            # print("q2 =", q2)
            # print("q3 =", q3)
            # print("e =", e_)
            # print("d =", d_)
            break

    n1 = p1 * q1
    n2 = p2 * q2
    n3 = p3 * q3
    
    assert pow(pow(0xdeadbeef, e_, n1), d_, n1) == 0xdeadbeef
    assert pow(pow(0xdeadbeef, e_, n2), d_, n2) == 0xdeadbeef
    assert pow(pow(0xdeadbeef, e_, n3), d_, n3) == 0xdeadbeef

    return(e_, n1, n2, n3)

攻击

基本

对于模数对 \((N_1,N_2)\)，满足 \[ ed=1+k_1\varphi(N_1)\newline ed=1+k_2\varphi(N_2) \] 可以写成 \[ ed=1+k_1N_1-k_1s_1\newline ed=1+k_1N_2-k_2s_2 \] 其中，\(s_1=p_1+q_1-1,s_2=p_2+q_2-1\)。

那么可以建立方程 \[ \mathcal{B}=\begin{bmatrix} A&e&e\\ 0&-N_1&0\\ 0&0&-N_2 \end{bmatrix}\newline (d,k_1,k_2)\mathcal{B}=(Ad,1-k_1s_1,1-k_2s_2) \] 其中，\(A=eN^{-1/2}\)（\(\|A\|=n_e-n/2\)）。

对于更多模数，同理 \[ \mathcal{B}=\begin{bmatrix} A&e&\cdots&e\\ &-N_1\\ &&\ddots\\ &&&-N_l \end{bmatrix} \] 那么，对于三模数的攻击代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
e = 272785315258275494478303901715994595013215169713087273945370833673873860340153367010424559026764907254821416435761617347240970711252213646287464416524071944646705551816941437389777294159359383356817408302841561284559712640940354294840597133394851851877857751302209309529938795265777557840238332937938235024502686737802184255165075195042860413556866222562167425361146312096189555572705076252573222261842045286782816083933952875990572937346408235562417656218440227
n1 = 473173031410877037287927970398347001343136400938581274026578368211539730987889738033351265663756061524526288423355193643110804217683860550767181983527932872361546531994961481442866335447011683462904976896894011884907968495626837219900141842587071512040734664898328709989285205714628355052565784162841441867556282849760230635164284802614010844226671736675222842060257156860013384955769045790763119616939897544697150710631300004180868397245728064351907334273953201
n2 = 327163771871802208683424470007561712270872666244394076667663345333853591836596054597471607916850284565474732679392694515656845653581599800514388800663813830528483334021178531162556250468743461443904645773493383915711571062775922446922917130005772040139744330987272549252540089872170217864935146429898458644025927741607569303966038195226388964722300472005107075179204987774627759625183739199425329481632596633992804636690274844290983438078815836605603147141262181
n3 = 442893163857502334109676162774199722362644200933618691728267162172376730137502879609506615568680508257973678725536472848428042122350184530077765734033425406055810373669798840851851090476687785235612051747082232947418290952863499263547598032467577778461061567081620676910480684540883879257518083587862219344609851852177109722186714811329766477552794034774928983660538381764930765795290189612024799300768559485810526074992569676241537503405494203262336327709010421

A = e / ZZ(isqrt(n1))
print(f'{A = }')
B = matrix.diagonal([A, -n1, -n2, -n3], sparse=False)
B[0, 1:] = e
L = B.LLL()

d = L[0, 0]
d = d // A
print(f'{d = }')

但该种攻击方式要求 \(n_d<n/3\)，即 \(d\) 的位数要小于 \(N\) 的位数的三分之一左右。

这是一种估算，不一定精确。

连分数

对于两个大整数 \(n_1,n_2\)，有 \[ \begin{cases} p=uv+1\\ q=uy+1\\ r=xy+1\\ s=kv+1\\ n_1=pr\\ n_2=qs \end{cases} \] 这样使得 \(ed=1\pmod{uvxy}=1\pmod{uykv}=1+k\cdot uvxy=1+x\cdot uykv\)，那么 \[ \frac{n_2}{n_1}=\frac{(xy+1)(kv+1)}{(uv+1)(vy+1)}\approx \frac{k}{x} \] 其中可以计算得到 \[ \left| \frac{n_2}{n_1}-\frac{k}{x} \right|=\frac{(vy+1)(kv+1)x-(uv+1)(xy+1)k}{x(uv+1)(xy+1)} \] 其中 \(\delta\) 为生成时 \(d,u,v,x,y\) 的位数，那么 \[ \left| \frac{n_2}{n_1}-\frac{k}{x} \right|\approx\frac{2^{3\delta}}{2^{5\delta}} \] 那么在一定范围内可以认为其满足连分数定理，故 \(\frac{k}{x}\) 很可能是 \(\frac{n_2}{n_1}\) 的一个有理近似。

而已知 \(k,x\)，可以考虑同余式 \[ \begin{cases} k\varphi+1\equiv 0\pmod{e}\\ \varphi\equiv 0\pmod{x} \end{cases} \] 那么可以通过 CRT 求解 \[ \varphi\equiv 0\pmod{ex} \] 而 \(|n_1-\varphi|=p+r-1\leq 2^{2\delta+1}\)，故可以简单爆破得到 \(\varphi\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
e = 98467641690093871695975267875795181585857989477939466388009417059131670850127
n1 = 64521998900946151035183250161361578590562898382852517840849876271081392030031478373013958266147661124818863160595707167944931647973532540982401464973584021447422475868642097572419813003671216480805967701734701439164191640156357221192923526468945493032975925992013636078779749848731628561181164769185524770589
n2 = 36054324863568917511130648763027165052886430166527588098384118258948926960785865728094271975577562345932247144759061359056537900829252352901512813929996631705102975455228713114838828313022933493627416617967097921738345054995913178996631066725890217631952233116357709092349310952226981239074912741833028864549

cf = continued_fraction(n2 / n1)
convers = cf.convergents()
for pkx in convers:
    pk, px = pkx.as_integer_ratio()
    if pk == 0:
        continue
    phi_mod_ex = crt([inverse_mod(-pk, e), 0], [e, px])
    lcm_ex = lcm(e, px)
    phi = (n1 - phi_mod_ex - 2^512) // lcm_ex * lcm_ex + phi_mod_ex
    while phi < n1:
        phi += lcm_ex
        if gcd(phi, e) != 1:
            continue
        d = (phi + 1) // e
        print(d)

临近边界

如果对于上面的格无法格规约出解，但是参数比较接近边界，可以考虑小范围爆破 \[ \mathcal{B}=\begin{bmatrix} A_0&0&e&\cdots&e\\ &A_1&ed_h&\cdots&ed_h\\ &&-N_1\\ &&&\ddots\\ &&&&-N_l \end{bmatrix}\newline (d_s,1,k_1,\cdots,k_l)\mathcal{B}=(A_0d_s,A_1,1-k_1s_1,\cdots,1-k_ls_l) \]