[求助]RSA加盐，低加密指数-求助问答-看雪-安全社区|安全招聘|kanxue.com

[求助]RSA加盐，低加密指数

2024-4-14 17:14 1153

[求助]RSA加盐，低加密指数

点墨留白

2024-4-14 17:14

1153

在研究RSA的攻击，碰到一个加盐的RSA加密方案，但是缺陷在于，e=3，就在网上找了相关的攻击方案，利用格基归约的。思路大致是按这个来的：https://www.cnblogs.com/ZimaBlue/articles/16552896.html
我的代码如下：

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

from Crypto.Util.number import *
import numpy as np
import gmpy2 as gp
from scipy.special import comb
import sympy as sp
import hashlib as hs
 
def changeType(data, stype=None, ttype=None, dimension=0):
    if stype is None:
        stype = gp.mpfr
    if ttype is None:
        ttype = gp.mpz
    if dimension == 0:
        return ttype(stype(data))
    elif dimension == 1:
        return [ttype(stype(e)) for e in data]
    elif dimension == 2:
        return [[ttype(stype(e)) for e in r] for r in data]
     
 
 
def LLL(base: np.array, delta: float = 0.75):
    m = 1.0 * base
    m_star = 1.0 * base
    mu = 0.0 * base
    gamma = 0.0 * base[:, 0]
 
    num = m.shape[0]
    #正交化
    for k in range(num):
        for j in range(k):
            mu[k, j] = m_star[k] @ m_star[j] / gamma[j]
            m_star[k] -= mu[k, j] * m_star[j]
        gamma[k] = m_star[k] @ m_star[k]
    del m_star
 
    def reduce(k, index):
        if k <= index:
            print("k必须大于index")
            exit(1)
        if abs(mu[k, index]) > 0.5:
            r = gp.round_away(mu[k, index])
            m[k] -= r * m[index]
            for j in range(index):
                mu[k, j] -= r * mu[index, j]
            mu[k, index] -= r
         
    while k < num:
        print(f'k={k}, start')
        reduce(k, k - 1)
        if gamma[k] >= (delta - mu[k, k - 1] ** 2) * gamma[k - 1]:
            for index in range(k - 2, -1, -1):
                reduce(k, index)
            k += 1
        else:
            MU = mu[k, k-1]
            Gamma = gamma[k] + MU ** 2 * gamma[k - 1]
            mu[k, k - 1] = MU * gamma[k - 1] / Gamma
            gamma[k] *= gamma[k - 1] / Gamma
            gamma[k - 1] = Gamma
 
            m[[k, k - 1]] = m[[k - 1, k]]
            for index in range(k - 1):
                mu[k - 1, index], mu[k, index] = mu[k, index], mu[k - 1, index]
            for index in range(k + 1, num):
                mu[index, k - 1], mu[index, k] = np.array([[1, mu[k, k - 1]], [0, 1]]) @ np.array([[0, 1], [1, -MU]]) @ np.array([mu[index, k - 1], mu[index, k]])
            if  k > 1:
                k -= 1
    length = [m[:, i] @ m[:, i] for i in range(m.shape[1])]
    index = length.index(min(length))
    return m, m[:, index]
 
def LLLTest():
    # b = np.array([[1, np.zeros(11), -622720],
    #               [0, 1, np.zeros(10), -695695],
    #               [0, 0, 1, np.zeros(9), -359449],
    #               [np.zeros(3), 1, np.zeros(8), -777278],
    #               [np.zeros(4), 1, np.zeros(7), -731810],
    #               [np.zeros(5), 1, np.zeros(6), -572203],
    #               [np.zeros(6), 1, np.zeros(5), -342619],
    #               [np.zeros(7), 1, np.zeros(4), -517768],
    #               [np.zeros(8), 1, np.zeros(3), -81435],
    #               [np.zeros(8), 1, np.zeros(3), -141920],
    #               [np.zeros(9), 1, 0, 0, -677905],
    #               [np.zeros(10), 1, 0, -422731],
    #               [np.zeros(12), 2764551]
    #             ])
    b = np.array(changeType([[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -622720],
                  [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -695695],
                  [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -359449],
                  [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, -777278],
                  [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, -731810],
                  [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -572203],
                  [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, -342619],
                  [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, -517768],
                  [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, -81435],
                  [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, -141920],
                  [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, -677905],
                  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -422731],
                  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2764551]
                ], ttype=gp.mpfr, dimension=2))
    # c = np.array(changeType([[1,1], [2,3]], ttype=gp.mpfr, dimension=2))
    a, _ = LLL(b)
    a = np.array(changeType(a, ttype=int, dimension=2))
    print(a)
 
def Attack(c, pubKey, salt):
    e = pubKey[0]
    n = changeType(pubKey[1])
    c = changeType(c)
    B = pow(n, 2 / (e * (e + 1)))
 
    mat = changeType([[n, *[0 for _ in range(e - 1)], pow(salt, e) - c]] +
                     [[*[0 for _ in range(r)], pow(B, r) * n, *[0 for _ in range(e - 1 - r)], pow(B, r) * comb(e, r) * pow(salt, e - r)] for r in range(1, e)] +
                     [[*[0 for _ in range(e)], pow(B, e)]], ttype=gp.mpfr, dimension=2)
    mat = np.array(mat)
 
    # print(mat)
    # np.savetxt('mat.csv', mat, delimiter=',')
    mat, _ = LLL(mat)
    # length = [mat[:, i] @ mat[:, i] for i in range(mat.shape[1]) if]
    # index = length.index(min(length))
    print('归约完成')
    for i in range(mat.shape[1]):
        Vector = mat[:, i]
        CV = list(reversed([Vector[i] / pow(B, i) for i in range(e + 1)]))
        x = sp.Symbol('x')
        poly = sp.Poly(CV, x)
        solution = sp.solve(poly, x)
        print(solution)
     
 
     
 
 
if __name__ == '__main__':
    c = 120440199294949712392334113337541924034371176306546446428347114627162894108760435789068328282135879182130546564535108930827440004987170619301799710272329673259390065147556073101312748104743572369383346039000998822862286001416166288971531241789864076857299162050026949096919395896174243383291126202796610039053
    n = 143413213355903851638663645270518081058249439863120739973910994223793329606595495141951165221740599158773181585002460087410975579141155680671886930801733174300593785562287068287654547100320094291092508723488470015821072834947151827362715749438612812148855627557719115676595686347541785037035334177162406305243
    e = 3
    salt = bytes_to_long(hs.sha256(b'32').digest())
    Attack(c, (e, n), salt)