密码算法

Posted on

RSA公钥加密系统

  • 公钥$P_A$, 私钥$S_A$
  • 对于Bob给Alice的加密消息M:
    • 发送方式:
      • Bob取得Alice公钥$P_A$
      • Bob计算出相应于M的密文$C=P_A(M)$
    • 接收过程:
      • Alice收到密文C后, 她用自己的密钥$S_A$恢复原始信息: $S_A(C) = S_A(P_A(M)) = M$
      • $S_A()$和$P_A()$互为反函数
  • 数字签名:
    • Alice运用她的密钥$S_A$和等式$\sigma=S_A(M’)$计算出信息$M’$的数字签名$\sigma$
    • Alice把消息/签名对$(M’, \sigma)$发送给Bob
    • 当Bob收到$(M’, \sigma)$时, 他可以利用Alice的公钥, 通过验证等式$M’=P_A(\sigma)$来证实该消息的确来自Alice.
  • RSA加密系统中, 一个参与者按下列过程创建他的公钥和密钥:
    • 随机选取两个大素数$p$和$q$, 使得$p\ne q$, 例如各1024位.
    • 计算$n=pq$
    • 选取一个和$\phi(n)=(p-1)(q-1)$互素的小奇数e
    • 对模$\phi(n)$, 计算出e的乘法逆元d的值
    • 将对$P=(e, n)$公开, 并作为参与者的RSA公钥
    • 将$S=(d,n)$保密, 作为参与者的RSA密钥
  • 应用公钥$O(1)$次模乘法, $O(\beta^2)$次位操作
  • 应用密钥$O(\beta)$次模乘法, $O(\beta^3)$次位操作
  • RSA加密系统的安全性来源于对大整数进行因数分解的困难性

整数的因子分解

  • Pollard的rho启发式方法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    POLLARD-RHO(n)
    i = 1
    x_1 = RANDOM(0, n-1)
    y = x_1
    k = 2
    while True
    	i = i + 1
    	x_i = (x_{i-1}^2 - 1) mod n
    	d = gcd(y-x_i, n)
    	if d != 1 and d != n
    		print d
    	if i == k
    		y == x_i
    		k = 2k

  • 可以在期望的$\theta(\sqrt n)$次算数运算内找到n的一个小因子p.

  • 如果p是合数, 则在大约经过$n^{1/4}$ 次更新之后, 可以预计该过程已经找到了足够多的约数
  • 函数$f(x)=(x^2-1)\mod n$生成的序列在出现回路之前预计要执行的步数为$\theta (\sqrt n)$