Crypto_Papers_Read_&_Recurrent

Posted on Edited on In Word count in article: 24k Reading time ≈ 22 mins.

本博客将不可避免的产生：

  • 致命笔误
  • 直接复制
  • 不懂装懂
  • 懒得排版
  • 证明显然
  • 逻辑混乱
  • 中式翻译

[TOC]

0x01 RSA私钥过大的漏洞

Link

使用过小的RSA私钥指数引发的危险在十多年前就已经为人所知。用户虽然已知这些威胁，但依然希望从实质上降低解密时间，可能会倾向于使用一个与很大的私钥相关的小负素数。这篇论文展示了Wiener, Boneh & Durfee, Blomer & May的针对小私钥指数的攻击，以及由上述攻击延申的对含多个素数的RSA的攻击，同样适用于私钥指数非常大的情况。

1.1 低加密指数攻击

考虑公钥指数 的RSA。如果明文大小在 区间内，解密仅需简单的对密文 开三次方即可，因为 。考虑处于 区间内的明文。相应的，在有限域的表示里，。令 ，解密仅需计算出 的三次方，即 ​ 。

1.2 连分数攻击( Wiener )

针对RSA小私钥指数的Wiener 攻击，可以轻而易举的扩展到针对大私钥指数的攻击。

定理1. 令RSA的模数为，私钥指数 满足 ，则公钥 已知的情况下，在多项式时间 内可以求得私钥。

由RSA公式： ，可化为 。令 ，等式也可以写成 为正，且 。根据连分数的性质可求得

image-20240129210633885

因此， 是 的一个连分数项。通过连分数算法我们可以计算所有 连分数的子项，验证正确的 。令 是 连分数的子项，我们可以计算 并尝试分解 。当 时，，就能实现分解 。 分解后，计算 ，自然地 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import getPrime, long_to_bytes as ltb, bytes_to_long as btl 
DEBUG = True 
flag = b'AL3XEI_FAKE_FLAG' 

p,q = [getPrime(512) for _ in "pq"] 
D = getPrime(250) 
phi = ( p - 1 ) * ( q - 1 ) 
n = p * q 
d = phi - D 
e = int(pow(d, -1, phi)) 
m = btl(flag) 
c = pow( m, e, n ) 

print(f"n = { n }") 
print(f"e = { e }") 
print(f"c = { c }") 




if DEBUG: 
    print(D < int(( 1 / 3 ) * ( n ** ( 1 / 4) ))) # True
    print(d > int(( 1 / 3 ) * ( n ** ( 1 / 4) ))) # True
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
from Crypto.Util.number import getPrime, long_to_bytes as ltb, bytes_to_long as btl 
from gmpy2 import invert, powmod

n = 
e = 
c = 


for kD in continued_fraction(e / n).convergents(): 
    k = kD.numer() 
    D = kD.denom() 
    try:
        if ( e * D + 1) % k == 0:
            phi =  ( e * D + 1) // k 
            d = phi - D 
            if (e * d) % phi == 1:
                m = powmod(c, d, n) 
                if ltb(m) == b'AL3XEI_FAKE_FLAG':
                    print(ltb(m))
                    break 

    except Exception:
        continue 
# b'AL3XEI_FAKE_FLAG'

1.3 小逆元攻击( Boneh & Durfee )

Boneh & Durfee 提出的小私钥指数攻击是建立在解决小逆元问题上的。也即，给定整数 ， ，求较小的 使得 成立。特别的，对于RSA，令 ，且 。我们希望能找到 满足 上述方程的一个解是 ， 是正整数，满足 。求得这个解就能恢复 ，就能通过 求得私钥指数。Boneh & Durfee 攻击能够成立的界是 。

定理2. 对针对RSA小私钥指数的，基于小逆元攻击的方法，如果在 情况下成立，则在 ​ 情况下也成立。

由RSA公式： ，可化为 。等式也可以写成 是正整数。令 ，通过模 化简上式得： 就可以回到与 Boneh & Durfee 相同的证明开端了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import getPrime, long_to_bytes as ltb, bytes_to_long as btl 
from gmpy2 import invert, powmod

DEBUG = True 
flag = b'flag{AL3XEI_FAKE_FLAG}' 

p,q = [getPrime(1024) for _ in "pq"] 
D = getPrime(540) 
phi = ( p - 1 ) * ( q - 1 ) 
n = p * q 
d = phi - D 
e = invert( d , phi ) 
m = btl(flag) 
c = powmod( m, e, n ) 

print(f"n = { n }") 
print(f"e = { e }") 
print(f"c = { c }") 

if DEBUG: 
    print(D > int(( 1 / 3 ) * ( n ** ( 1 / 4) ))) # True
    print(D < int(n ** 0.292)) # True 
    print(d > int(( 1 / 3 ) * ( n ** ( 1 / 4) ))) # True
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
57
58
59
60
61
62
63
64
65
66
from Crypto.Util.number import long_to_bytes
import itertools


def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficients_monomials()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []


n = 
e = 
c = 


P = Zmod(ZZ(e))["k,s"]
k, s = P.gens()
f = 1 + k * (n - s)
rs = small_roots(f, (2**540, 2**1025), m=4, d=5)
print(rs)
k, s = map(int, rs[0])
phi = n - s
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m)))
# b'flag{AL3XEI_FAKE_FLAG}'

1.4 含多个素数的 RSA

接下来的攻击将上述RSA攻击扩展到了含多个素数的形式。

定理3. 令 是含 个素数（大小相近）的RSA， 为私钥指数，且满足 。则公钥 已知的情况下，在多项式时间 内可以求得私钥。

证明过程与 Wiener 攻击近乎一致，不再阐述。

定理4. 对针对含多个素数的RSA小私钥指数的，基于小逆元攻击的方法，如果在 情况下成立，则在 情况下也成立。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import getPrime, bytes_to_long

DEBUG = True 
p,q,r = [getPrime(1024) for _ in "pqr"] 
n = p*q*r 
l = getPrime(490)
phi = (p - 1) * (q - 1) * (r - 1)
d = phi - l 
e = int(pow(d, -1, phi)) 

flag = b'flag{AL3XEI_FAKE_FLAG}'
m = bytes_to_long(flag)
c = pow(m, e, n)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")

if DEBUG:
    print("down: ", int((1/3)*(n**(1/6))).bit_length())  
    print("up: ", int(pow(n, 0.292)).bit_length())
    print("k:", int((e*l+1)//phi).bit_length()) 
    print("s:", int(-(- p*q-p*r-q*r+p+q+r-1)).bit_length(), (e*l+1)%phi)

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
57
58
59
60
61
62
63
64
65
from Crypto.Util.number import long_to_bytes
import itertools


def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []


n = 
e = 
c = 

P = Zmod(ZZ(e))["k,s"]
k, s = P.gens()
f = 1 + k * (n - s)
rs = small_roots(f, (2**490, 2**2050), m=4, d=5)
print(rs)
k, s = map(int, rs[0])
phi = n - s
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m)))

1.5 总结

RSA私钥指数过大会导致与私钥指数过小一样不安全。特别的，对于RSA，私钥指数 与 都会带来不安全性。

0x02 二次生成器的密码分析

Link

令 为素数， 为模 有限域内的整数。二次生成器 (QCG) 是一个由等式关系 构成的伪随机数序列 。这篇论文展示了如果任意多个连续的 的高位已知，就可以在多项式时间内还原初始变量 (即使在参数 未知的情况下)，前提是初始变量 不在某些特殊值的小的子集里。

2.1 二次生成器

令 为素数， 为模 有限域内的整数。二次生成器 (QCG) 是一个由等式关系 构成的伪随机数序列 。等式中的 ​ 分别被称为乘子和偏移量。

在密码设置中，初始量 以及常量 应该被设为私钥，利用生成器生成流密码。显然，如果多个连续的 已知，求得 是很容易的。所以在这个设置中，我们只输出 的最高有效位 (msb) ，希望能让输出的序列更难预测。这篇论文展示的就是在这种情况下如何预测 。

假设序列 未知，但对于给定的 ，一些近似值 已知。以下分别讨论 公开和 公开， 不公开的两种情况下，如果 条件足够好， 和 就能在多项式内还原。

在开始前，还要定义一个参数 ，用来衡量 近似 的程度。这个参数通常假设为 。更确切地， 是 的 - 近似，等价于 。

2.2 乘子与偏移量已知，预测二次生成器

定理1. 令 为素数， 为 整数且 。对任意 ，存在一个算法，当 与二次生成器产生的两个连续的值 -近似的 已知时，在多项式时间内返回 的值。

令 。由 ，可得 令 可得 因此由同余式 构成的格 含有解 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from random import randint 
from Crypto.Util.number import * 

Bits = 512
UnKnownBits = 146 
flag = b'flag{AL3XEI_FAKE_FLAG}' 

p = getPrime(Bits) 
a, c = [randint(0, p) for _ in "ac"] 

v_0 = bytes_to_long(flag) 
v_1 = (a*v_0**2+c)%p 
v_2 = (a*v_1**2+c)%p  

print(f"a = {a}") 
print(f"c = {c}") 
print(f"p = {p}") 
print(f"high_v1 = {v_1>>UnKnownBits}")
print(f"high_v2 = {v_2>>UnKnownBits}")
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
57
58
59
60
from Crypto.Util.number import long_to_bytes
import itertools


def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []
a = 
c = 
p = 
high_v1 = 
high_v2 = 
PR = Zmod(ZZ(p))["l1, l2"] 
l1, l2 = PR.gens() 
f = a*(high_v1*(2^146)+l1)^2+c-(high_v2*(2^146)+l2)
low_v1 = ZZ(small_roots(f, (2^146, 2^146), m=3, d=4)[0][0]) 

v_0 = mod(((high_v1*(2^146)+low_v1)-c)*inverse_mod(a, p)%p, p).sqrt() 
print(long_to_bytes(ZZ(v_0)))

2.3 乘子已知，偏移量未知，预测二次生成器

定理2. 令 为素数， 为 整数且 。对任意 ，存在一个算法，当 与二次生成器产生的三个连续的值 -近似的 已知时，在多项式时间内返回 ​ 的值。

令 ，且 ，可得含已知量 和未知量 的方程： 向量 满足已知的一致性系数。为了使量标更平衡，将上式写作： 因此由同余式 构成的格 含有解 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from random import randint 
from Crypto.Util.number import * 

Bits = 256
UnKnownBits = 48
flag = b'flag{AL3XEI_FAKE_FLAG}' 

p = getPrime(Bits) 
a, c = [randint(0, p) for _ in "ac"] 
v_0 = bytes_to_long(flag) 
assert v_0<p
v_1 = (a*v_0**2+c)%p 
v_2 = (a*v_1**2+c)%p  
v_3 = (a*v_2**2+c)%p  

print(f"a = {a}") 
print(f"p = {p}") 
print(f"high_v0 = {v_1>>UnKnownBits}")
print(f"high_v1 = {v_2>>UnKnownBits}")
print(f"high_v2 = {v_3>>UnKnownBits}")
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
from Crypto.Util.number import long_to_bytes
import itertools


def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []

UnKnownBits = 48
a = 
p = 
high_v0 = 
high_v1 = 
high_v2 = 

high_v0 = high_v0<<UnKnownBits
high_v1 = high_v1<<UnKnownBits
high_v2 = high_v2<<UnKnownBits

PR = Zmod(ZZ(p))["l0, l1, l2"] 
l0, l1, l2 = PR.gens() 
f =( a*high_v0^2-high_v1-a*high_v1^2+high_v2 ) + 2*a*high_v0*l0 - (1+2*a*high_v1)*l1 + l2 + a*(l0^2-l1^2) 

ls = small_roots(f, (2^UnKnownBits, 2^UnKnownBits, 2^UnKnownBits), m=3, d=4)
v_0, v_1, v_2 = high_v0+ZZ(ls[0][0]), high_v1+ZZ(ls[0][1]), high_v2+ZZ(ls[0][2]) 
c = (v_1 - a*v_0^2) 

sd = mod((v_0-c)*inverse_mod(a, p)%p, p).sqrt() 

print(long_to_bytes(ZZ(sd)))

2.4 总结 & 尚未解决的问题

显然定理1的界 ，定理2的界 。因此是否能提高 ​ 的界值得讨论。

在 给出但乘子 未知的条件下也能用类似的过程预测二次生成器。

目前还不清楚当模数 未知时如何预测二次生成器。

0x03 在攻击变体 RSA 中找到具有新应用的多元多项式根的策略

Link

这篇论文展示了利用格基 Coppersmith 技术计算多元模多项式小整数根的策略。应用该策略，该论文得出在多项式时间内攻击两种 RSA 变体的方法。首先是 Qiao-Lam scheme, 其利用中国剩余定理在解密过程发挥作用。然后是共素数 RSA ，其素数生成的方法能抵抗 Wiener 攻击。

1.1 jochemsz_may 方法

论文开篇回顾了了 Coppersmith 以及 boneh Durfee 基于 Coppersmith 设计的针对 RSA 的攻击，并指出：找到一个小根的多项式 的分析严重依赖于 中出现的单项式，因此每个新的多项式都必须重新进行分析。这个工作无疑是十分繁杂的。2005年，Blomer 和 May 展示了如何寻找二元多项式小整数根的最佳界限。在本文中，我们提出了一种启发式策略，适用于所有多元多项式；无论是具有模数根还是整数根。

1.2 参数的设定

令多项式 有小根 ， 的上界分别为 。根据论文提出的新策略，所有小根都能有效的在多项式时间 内恢复出来，前提是满足 同时，论文明确给出 ，而 的意思就是多项式的最大系数，所以 就是多项式对各 进行 代入后的最大系数。举个例子，如 ， ，则 ，显然最大系数在 ，即 。

1.3 对 共素 RSA 的攻击

定理1. 对任意 , 存在 使以下成立：令 为 比特 的 RSA 模数， 为 比特的素数，且 , 位数为 ， 。令 , , 其中 , 则 可以在 的前提下，在多项式时间 时间内求出。

由上式可得： 联立两个式子： 。这个方程也可以写成 , 它的小根为 , 上界为 。同时也可以算出 。

论文给出了几个实现攻击需要的参数列表。

image-20240303165643981 
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
from Crypto.Util.number import *

n = 4092 
gamma = 0.4
delta = 0.1604
flag = b'AL3XEI_FAKE_FLAG' 

g = getPrime(int(n*gamma)) 
while True:
    p = getPrime(n//2) 
    if (p-1)%(2*g) == 0 :
        break 

while True:
    q = getPrime(n//2) 
    if (q-1)%(2*g) == 0 :
        break 

a, b = (p-1)//(2*g), (q-1)//(2*g) 
N = p*q 
d = getPrime(int(n*delta)) 
e = inverse_mod(d, 2*g*a*b) 

m = bytes_to_long(flag) 
c = pow(m,e,n) 
print(f'n = {n}') 
print(f'e = {e}') 
print(f'c = {c}') 

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
from sage.all import *
import itertools
from time import time
from Crypto.Util.number import long_to_bytes


# display matrix picture with 0 and X
# references: https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage
def matrix_overview(BB):
    for ii in range(BB.dimensions()[0]):
        a = ('%03d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        print (a)

def sort_monomials(monomials):
    x, y, z = monomials[0].parent().gens()
    Mx = []
    My = []
    Mz = []
    degx = max([monomial.degree(x) for monomial in monomials])
    degy = max([monomial.degree(y) for monomial in monomials])
    degz = max([monomial.degree(z) for monomial in monomials])
    for i in range(degx + 1):
        for j in range(degy + 1):
            for k in range(degz + 1):
                if k+j > i:
                    break
                mono = x^i * y^j * z^k
                if mono in monomials:
                    Mx += [mono]
    for j in range(degy + 1):
        for k in range(degz + 1):
            for i in range(degx + 1):
                if k > j:
                    break
                mono = x^i * y^j * z^k
                if mono in monomials and mono not in Mx:
                    My += [mono]
    for k in range(degz + 1):
        for j in range(degy + 1):
            for i in range(degx + 1):
                mono = x^i * y^j * z^k
                if mono in monomials and mono not in (Mx+My):
                    Mz += [mono]
    return Mx + My + Mz


def jochemsz_may_trivariate(pol, XX, YY, ZZ, WW, tau, mm):
    '''
    Implementation of Finding roots of trivariate polynomial [1].
    Thanks @Bono_iPad
    References: 
        [1] Ellen Jochemsz and Alexander May. "A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants"
    '''
    tt = floor(mm * tau)
    cond = XX^(7 + 9*tau + 3*tau^2) * (YY*ZZ)^(5+9/2*tau) < WW^(3 + 3*tau)
    print ('[+] Bound check: X^{7+9tau+3tau^2} * (YZ)^{5+9/2tau} < W^{3+3tau}:', )
    if cond:
        print( 'OK')
    else:
        print ('NG')

    # Polynomial constant coefficient (a_0) must be 1
    # XXX: can a_0 be zero?
    f_ = pol
    a0 = f_.constant_coefficient()

    while gcd(a0, XX) != 1:
        XX += 1
    while gcd(a0, YY) != 1:
        YY += 1
    while gcd(a0, ZZ) != 1:
        ZZ += 1
    while gcd(a0, WW) != 1:
        WW += 1

    RR = WW * XX^(2*(mm-1)+tt) * (YY*ZZ)^(mm-1)

    if a0 != 0:
        F = Zmod(RR)
        PK = PolynomialRing(F, 'xs, ys, zs')
        f_ = PR(PK(f_) * F(a0)^-1)

    # Construct set `S` (cf.[1] p.8)
    S = set()
    for i2, i3 in itertools.product(range(0, mm), repeat=2):
        for i1 in range(0, 2*(mm-1) - (i2 + i3) + tt + 1):
            S.add(x^i1 * y^i2 * z^i3)
    m_S = []
    for k in range(mm):
        for j in range(mm):
            for i in range(2*(mm-1) - (i2 + i3) + tt + 1):
                m_S += [x^i*y^j*z^k]
    S = m_S

    # Construct set `M` (cf.[1] p.8)
    M = set()
    for i2, i3 in itertools.product(range(0, mm + 1), repeat=2):
        for i1 in range(0, 2*mm - (i2 + i3) + tt + 1):
            M.add(x^i1 * y^i2 * z^i3)
    M_S = list(M - set(S))

    m_M_S = []
    deg_x = max([mono.degree(x) for mono in M_S])
    deg_y = max([mono.degree(y) for mono in M_S])
    deg_z = max([mono.degree(z) for mono in M_S])
    for k in range(deg_z + 1):
        for j in range(deg_y + 1):
            for i in range(deg_x + 1):
                mono = x^i*y^j*z^k
                if mono in M_S:
                    m_M_S += [mono]
    M_S = m_M_S

    # Construct polynomial `g`, `g'` for basis of lattice
    g = []
    g_ = []
    M_S = sort_monomials(M_S)
    S = sort_monomials(S)
    for monomial in S:
        i1 = monomial.degree(x)
        i2 = monomial.degree(y)
        i3 = monomial.degree(z)
        g += [monomial * f_ * XX^(2*(mm-1)+tt-i1) * YY^(mm-1-i2) * ZZ^(mm-1-i3)]

    for monomial in M_S:
        g_ += [monomial * RR]

    # Construct Lattice from `g`, `g'`
    monomials_G = []
    monomials = []
    G = g + g_
    deg_x = deg_y = deg_z = 0
    for g_poly in G:
        monomials_G += g_poly.monomials()
        deg_x = max(deg_x, g_poly.degree(x))
        deg_y = max(deg_y, g_poly.degree(y))
        deg_z = max(deg_z, g_poly.degree(z))
    monomials_G = sorted(set(monomials_G))

    for k in range(deg_z + 1):
        for j in range(deg_y + 1):
            for i in range(deg_x + 1):
                mono = x^i*y^j*z^k
                if mono in monomials_G:
                    monomials += [x^i*y^j*z^k]
    assert len(monomials) == len(G)
    monomials = sort_monomials(monomials)
    dims = len(monomials)
    M = Matrix(IntegerRing(), dims)
    for i in range(dims):
        M[i, 0] = G[i](0, 0, 0)
        for j in range(dims):
            if monomials[j] in G[i].monomials():
                M[i, j] = G[i].monomial_coefficient(monomials[j]) * monomials[j](XX, YY, ZZ)
    matrix_overview(M)
    print ()
    print ('=' * 128)
    print ()

    # LLL

    start = time()
    B = M.LLL()
    matrix_overview(B)
    print('[+] LLL cost %d sec' % (time() - start))

    # Re-construct polynomial `H_i` from Reduced-lattice
    H = [(i, 0) for i in range(dims)]
    H = dict(H)
    for i in range(dims):
        for j in range(dims):
            H[i] += PR((monomials[j] * B[i, j]) / monomials[j](XX, YY, ZZ))

    PX = PolynomialRing(IntegerRing(), 'xn')
    xn = PX.gen()
    PY = PolynomialRing(IntegerRing(), 'yn')
    yn = PX.gen()
    PZ = PolynomialRing(IntegerRing(), 'zn')
    zn = PX.gen()

    # Solve for `x`
    r1 = H[2].resultant(pol, y)
    r2 = H[3].resultant(pol, y)
    r3 = r1.resultant(r2, z)
    x_roots = map(lambda t: t[0], r3.subs(x=xn).roots())
    x_roots = list(x_roots)
    assert len(x_roots) > 0
    if len(x_roots) == 1 and x_roots[0] == 0:
        print ('[-] Can\'t find non-trivial solution for `x`')
        return 0, 0, 0
    x_root = x_roots[0]
    print ('[+] Found x0 = %d' % x_root)

    # Solve for `z`
    r1_ = r1.subs(x=x_root)
    r2_ = r2.subs(x=x_root)
    z_roots = map(lambda t: t[0], gcd(r1_, r2_).subs(z=zn).roots())
    z_roots = list(z_roots)
    assert len(z_roots) > 0
    if len(z_roots) == 1 and z_roots[0] == 0:
        print ('[-] Can\'t find non-trivial solution for `z`')
        return 0, 0, 0
    z_root = z_roots[0]
    print ('[+] Found z0 = %d' % z_root)

    # Solve for `y`
    y_roots = map(lambda t: t[0], H[2].subs(x=x_root, z=z_root).subs(y=yn).roots())
    y_roots = list(y_roots)
    assert len(y_roots) > 0
    if len(y_roots) == 1 and y_roots[0] == 0:
        print ('[-] Can\'t find non-trivial solution for `y`')
        return 0, 0, 0
    y_root = y_roots[0]
    print ('[+] Found y0 = %d' % y_root)
    assert pol(x_root, y_root, z_root) == 0
    return (x_root, y_root, z_root)

n = 
e = 
c = 

gamma = 0.4
delta = 0.1604

PR.<x, y, z> = PolynomialRing(ZZ)

# Maximal value of solution `x0`, `y0`, `z0`
XX = floor(n^delta)
YY = floor(n^(delta + 0.5 - gamma))
ZZ = YY

# Norm of polynomial as vector representation
WW = floor(n^(2 + 2*delta - 2*gamma))

# Some Non-negative real ([SAN10] 3.1 (11))
tau = (1/2 + gamma - 4*delta) / (2*delta)

# Powering degree
mm = 1

# Target polynomial
pol = e^2 * x^2 + e*x*(y+z-2)-(y+z-1)-(n-1)*y*z
x0, y0, z0 = jochemsz_may_trivariate(pol, XX, YY, ZZ, WW, tau, mm)

d = x0 
m = pow(c,d,n) 
print(long_to_bytes(int(m)))

0X04 带有小的未知乘子的隐藏数问题：MEGA 的六次查询密码分析以及其他应用

Link

安全研究员最近提出了针对云存储提供商 MEGA 的一种攻击。该攻击通过伪装恶意服务器，在与客户端进行 512 次登录交互后会得到 RSA 私钥。这篇论文展示了由 MEGA 协议漏洞获取更多隐私的攻击攻击，只需与客户端进行 6 次登录交互即可恢复私钥。该联合攻击涉及多种密码分析技术。特别的，这篇论文还提出了一种隐藏数问题变体的解法，该变体涉及小的未知乘子。

4.1 HNP-SUM 简介

论文的一项创新工作是解决了带有小的未知乘子的隐藏数问题 (以下简称为 HNP-SUM) 。

定义1. (HNP-SUM) 对于给定的整数 ，存在整数 满足

如何恢复 签名的值 (ti 互素)。

定理1. 对 HNP-SUM 出现的 以及随机生成的 ，当 时，存在算法使HNP-SUM 可在多项式内求解。

4.2 求解 HNP-SUM

对于 的情况，给定 满足 经过变换得到 由于 的界固定，对于 存在个小的解 。通过构造格 定理2. 对于 HNP-SUM 问题的 情况下，若 ​ 成立，可在多项式时间内求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
from lbc_toolkit import hnp

m = b'AL3XEI_FAKE_FLAG'
N, E, T = random_prime(2^722),  2^180, 2^180  
print(T^3*E<N)

x = bytes_to_long(m)  
_T = [randrange(1, T) for _ in "01"] 
_E = [randrange(0, E) for _ in "01"]  
A = [(t * x + e) % N for t, e in zip(_T, _E)] 

print(f'N = {N}') 
print(f'_T = {_T}') 
print(f'A = {A}') 
print(f'E = {E}') 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from lbc_toolkit import hnp
from Crypto.Util.number import *

N = 
_T = 
A = 
E = 
sol = hnp(N, _T, A, E, verbose=True)
print(long_to_bytes(sol))
    
# [hnp] Lattice dimensions: (4, 4)
# [hnp] Lattice reduction took 0.005s
# b'AL3XEI_FAKE_FLAG'

对于 的情况也可以做拓展。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
from lbc_toolkit import hnp

m = b'AL3XEI_FAKE_FLAG'
N, E, T = random_prime(2^360),  2^50, 2^50  
print(T^6*E<N)

x = bytes_to_long(m)  
_T = [randrange(1, T) for _ in range(5)] 
_E = [randrange(0, E) for _ in range(5)]  
A = [(t * x + e) % N for t, e in zip(_T, _E)] 

print(f'N = {N}') 
print(f'_T = {_T}') 
print(f'A = {A}') 
print(f'E = {E}') 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from lbc_toolkit import hnp
from Crypto.Util.number import *

N = 
_T = 
A = 
E = 
sol = hnp(N, _T, A, E, verbose=True)
print(long_to_bytes(sol))
    
# [hnp] Lattice dimensions: (7, 7)
# [hnp] Lattice reduction took 0.013s
# b'AL3XEI_FAKE_FLAG'

4.3 应用：对 MEGA 的攻击

MEGA 工作 (以及实施对 MEGA 攻击) 的环境中，服务器持有客户端 RSA 私钥的密文副本，加密方式是 AES-ECB mode，密钥由用户密码派生生成。

在 MEGA 的登录协议中，服务器向客户端发送了一个使用 AES-ECB mode 加密的 RSA 私钥。 客户端解密 RSA 私钥，使用此 RSA 私钥解密 session ID 得到 RSA 公钥 ，并发送给服务器一个应答值。RSA 私钥包含 。

客户端返回服务器的值是 。

令 RSA 的公钥为 ， 的因数为 。公钥指数与私钥指数分别为 。公钥由客户端定义，在网络客户端上 , 而在 SDK 上 。私钥的编码为

1
l(q) ∥ q ∥ l(p) ∥ p ∥ l(d) ∥ d ∥ l(u) ∥ u ∥ P
  • l(x) 将值 x 的比特长度编码为一个 2 字节的整数
  • 所有整数以大端格式存储
  • P长8字节，作为填充，具体值攻击者未知
  • q 是 1024 位，故 l(q) = 0x400，且由于明文大小已知，它在明文中的偏移量也可预测
  • d 包含了 d, dp, dq
  • 1024 位的 u 值跨越了 9 个 AES 明文块，其中第一个和最后一个包含长度和填充字段

私钥加密后 656 字节/ 41 个 AES 块，使用 AES-ECB 加密后

1
ct1 ∥ ct2 ∥...∥ ct41 = EAES(pt1) ∥ EAES(pt2) ∥...∥ EAES(pt41)。

实质上，客户端返回服务器的值是对 进行了一次 RSA-CRT 的解密。

1
2
3
4
5
6
m_p = c^(d_p) mod p
m_q = c^(d_q) mod q
t = (m_p - m_q) mod p
h = (t * u) mod p
m' = h * q + m_q 
SID = m'[2:44]  # 去掉 padding 校验位