Java教程

RSA加密算法

本文主要是介绍RSA加密算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

RSA加密算法详解

1、寻找两个不相同的质数

  • 随意选择两个大的质数pqp不等于q,计算N=p*q;

  • 什么是质数?我想可能会有一部分人已经忘记了,定义如下:

    除了1和该数自身外,无法被其他自然数整除的数(也可定义为只有1该数本身两个正因数)的数)。
    

2、根据欧拉函数获取r

  • r = φ(N) = φ(p)φ(q) = (p-1)(q-1)

  • 欧拉函数的定义:

欧拉函数 φ(n)是小于或等于n的正整数中与n互质的数的数目。
  • 互质的定义:
如果两个或两个以上的整数的最大公约数是 1,则称它们为互质

例如:φ(8) = 4,因为1,3,5,7均和8互质。

3、选择一个小于r并与r互质的整数e

  • 选择一个小于r并与r互质的整数e,求得e关于r的模反元素,命名为d(***ed = 1(mod r)***模反元素存在,当且仅当e与r互质),e我们通常取65537。

  • 模反元素:

如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。

比如35互质,3关于5的模反元素就可能是2,因为3*2-1=5可以被5整除。所以很明显模反元素不止一个,2加减5的整数倍都是3关于5的模反元素*{…-3, 2,7,12…}* 放在公式里就是3*2 = 1 (mod 5)

4、销毁p和q

  • 此时我们的*(N , e)是公钥,(N, d)为私钥,爱丽丝会把公钥(N, e)传给鲍勃,然后将(N, d)*自己藏起来。一对公钥和私钥就产生了

备注

  • p,q:我们随机挑选的两个大质数
  • N:是由两个大质数pq相乘得到的。N = p * q
  • r:由欧拉函数得到的N的值,r = φ(N) = φ§φ(q) = (p-1)(q-1)
  • e:随机选择和和r互质的数字,实际中通常选择65537
  • d: d是以欧拉定理为基础求得的e关于r的模反元素,ed = 1 (mod r)

Ne我们都会公开使用,最为重要的就是私钥中的dd一旦泄露,加密也就失去了意义。那么得到d的过程是如何的呢?如下:

  1. 比如知道e和r,因为d是e关于r的模反元素;r是φ(N) 的值
  2. φ(N)=(p-1)(q-1),所以知道p和q我们就能得到d
这篇关于RSA加密算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!