RSA专题——”误用“攻击

低加密指数攻击

低加密指数广播攻击

共模攻击

低解密指数攻击

wiener‘s attack

由于，那么存在一个  满足。所以，

，如果  足够小，则  是 的逼近，尽管我们不知道 ，但是我们可以用来近似。

因为 $kvarphi(N)=ed−1<ed$，并且 $e<varphi(n)$，所以有=”” $d=”” gt=”” k$<=”” p=””>

补充：连分数知识相关

定义一：连分数

定理 1 任何一个有理数与其连分数形式是一一对应的。

证明：对于任意一个有理数 ，且  （即  互素），我们可以写出如下等式

例 1：  的连分数形式：

所以 

 的连分数形式

所以 

def continued_fraction(dn,n):
 res = []
 while dn % n:
  res.append(dn//n)
  dn, n = n, dn % n
 res.append(dn//n)
 print(res)

print(continued_fraction(5,3))

定义二：收敛分数

例 3： 计算  的收敛分数

def Convergence_function(continued):
 res =[]
 for i in range(1,len(continued)+1):
  tmp = 1
  conver = continued[:i][::-1]
  tmp = conver[0]
  for j in conver[1:]:
   tmp = j + 1/tmp
  res.append(tmp)
 return res

print(Convergence_function(continued_fraction(1234,32)))

定理 2 （Legendre’s theorem）

小结