抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

公钥加密系统

在一个公钥加密系统中,任何人参与者都拥有独自的公钥和密钥,通常用P表示公钥,用S表示密钥,公钥用于加密,密钥用于解密。并且公钥可以公开,任何人都可以使用这个公钥发送一段密文,而只有私钥的持有者才可以用私钥解密

公钥和私钥对应的函数互为反函数

DearXuan

RSA公钥加密体系基于一个数论事实:把两个大质数相乘很容易,但是分解大数为两个质数的乘积很难

RSA加密

在RSA公钥加密系统中,可以通过以下过程创建一对公钥和私钥

  1. 任意选取远大于信息 M 的大质数 p 和 q,且 p != q
  2. 令 n = pq
  3. 计算 φ = (p-1)(q-1)
  4. 选取一个与 φ 互质的小奇数 e
  5. 计算对模 φ 意义下的 e 的乘法逆元 d,即 ed ≡ 1 (mod φ)
  6. 公开 P=(e, n),此即为RSA公钥
  7. 隐藏 S=(d, n),此即为RSA私钥

对于明文 M,使用以下函数进行加密

DearXuan

对于密文 C,使用以下函数进行解密

DearXuan

反函数关系

根据反函数关系,可得

DearXuan

由于 e 和 d 是关于模 φ 的乘法逆元,所以

DearXuan

由于 p 和 q 远大于 M,所以 M ≢ 0(mod p),M ≢ 0(mod q),则

DearXuan

同理,可以得到以下结论

DearXuan

因此

DearXuan

由于 n 远大于 M,所以只需要对前者求余,就能得到 M 的值

评论