RSA算法简介

灌水乐园
4 1068

     RSA体制是PKI最出名的体制,其他两种著名的公钥体制是离散对数体制和椭圆曲线体制(后续会慢慢介绍这两种体制的本质)。在介绍RSA体制前,先做一些简单的数学知识介绍。

    众所周知,RSA算法的安全性基于将一个大数(非素数)分解为素数因子是及其困难的,可是大家可能并没有想过一个数(非素数)为什么一定可以因式分解,在很多人看来或许这是个无需证明的推论。此处我也不准备证明这个推论,不过我给出这个推论的严格定义,该推论名为算术基本定理(具体的证明,大家可以用数学归纳法证明),算术基本定理的定义如下:

  •     
  • 任意数字 n 都可以以某种方式分解成素数乘积
  •     
  • 仅有一种这样的因式分解(不考虑顺序)


  至于因式分解的复杂度具体多少,因为本人水平有限,无法给出具体的推论以及证明。接下来我简单介绍一下RSA算法。

  密钥生成:

    1. 生成两个长度相等的随机大素数 p, q


    2. 计算  n = pq, φ(n) = (p - 1)(q - 1),此处gcd(p, q) = 1,所以欧拉函数的值等于(p - 1) * (q - 1),具体欧拉函数的一些推论以及证明有机会和大家讨论


    3. 随机选择整数 e,e 满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1


    4.  计算整数 d, d 满足 1 < d < φ(n),ed ≡ 1 (mod φ(n)),≡为同余符号

   

    5. (n, e) 为公钥,d 为私钥


私钥签名:

    1. h = H(m),其中 H 是任意一个杂凑函数(比如sm3,md5),m为明文

    2. s = h ^ d mod n,s 即为签名结果


公钥签名验证:

    1. h = H(m), m 为明文

    2. h1 = s ^ e mod n, s 为签名结果

    3.  if h == h1 return true else return false


具体的实现还需要加入一些随机值来保证安全性,为了性能考虑还会引入蒙哥马利等算法提升性能,具体的细节有机会和大家讨论,接下来我简单证明一下签名和验签:

因为 ed ≡ 1 (mod φ(n)), 所以 ed = mφ(n) + 1

因为s = h ^ d mod n, 所以 h ^ d ≡ s (mod n)

因为 h ^ d ≡ s mod n, 所以 s = h ^ d - kn, k 为整数

因为 h1 = s ^ e mod n,所以 s ^ e ≡ h1 mod n

因此要证明签名验证算法的正确性只需证明 h ≡ s ^ e mod n

因为 s = h ^ d - kn,所以代入式中得 h ≡ (h ^ d − kn) ^ e mod n

因为 kn 是 n 的倍数,所以只需证明 h ≡ (h ^ d ) ^ e mod n 即可

因为 ed = mφ(n) + 1,所以只需证明 h ≡ h ^ (mφ(n)+1) mod n 即可

因为 h ≡ h ^ (mφ(n)+1) mod n,  所以只需证明 h ≡ h1 h ^ (φ(n) ^ m) mod n 即可

根据欧拉定理 a ^ φ(n) ≡ 1 mod n 可得 h ≡ h 1 mod n,至此,证明完毕


灌水贴,大致扯了一下RSA算法,有机会和大家好好讨论


  • Jacklli Jacklli
    2018-03-29

    赞赞赞!

    0 回复
  • yason.li yason.li
    2018-03-29

    密码学的经典算法啊,不管是搞安全还是玩区块链都应该看一看!!!

    0 回复
  • LMOS LMOS
    2018-03-29

    是的 很牛 很强 

    0 回复
  • yuan郭  yuan郭
    2018-03-29

    Good!

    0 回复