非对称加密算法RSA 学习

非对称加密算法RSA 学习

RSA加密算法是一种非对称加密算法。RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

1973年,在英国政府通讯总部工作的数学家克利福德·柯克斯(Clifford Cocks)在一个内部文件中提出了一个相同的算法,但他的发现被列入机密,一直到1997年才被发表。

对极大整数做因数分解的难度决定了RSA算法的可靠性。 换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。假如有人找到一种快速因数分解的算法的话,那么用RSA加密的信息的可靠性就肯定会极度下降。 但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到目前为止,世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长,用RSA加密的信息实际上是不能被解破的。

一、举一个通俗易懂的例子

看一个数学小魔术:

让A写下一个任意3位数,并将这个数和91相乘;然后将积的最后三位数告诉B,这样B就可以计算出A写下的是什么数字了。

  • 比如A写下的是123,并且A计算出123 * 91等于11193,并把结果的末三位193告诉B ;
  • B只需要把193再乘以11,193 * 11 = 2123 末三位就是A写下的数字了;

道理很简单,91乘以11等于1001,而任何一个三位数乘以1001后,末三位显然都不变(例如123乘以1001就等于123123)。

知道原理后,可以构造一个定义域和值域更大的加密解密系统。
例如:

  • 任意一个数乘以400000001后,末8位都不变,而400000001 = 19801 * 20201。于是A来乘以19801,B来乘以20201,又一个加密解密不对称的系统就构造好了;
  • 甚至可以构造得更大一些 4000000000000000000000000000001 = 1199481995446957 * 3334772856269093,这样我们就成功构造了一个30位的加密系统;

如果仅仅按照上面的思路,如果对方知道原理,非常容易穷举出400000001这个目标值;RSA算法使用的是指数和取模运算,本质上就是上面这套思想。

此段落转载自:
如何用通俗易懂的话来解释非对称加密?

二、一句话:

对极大整数做因数分解的难度决定了RSA算法的可靠性。

三、RSA加密算法

3.1、维基百科——RSA加密算法

先看一下维基百科的算法描述:

公钥与私钥的产生

  • 1、随意选择两个大的质数 p和 q,p不等于 q,计算 N=pq
  • 2、根据欧拉函数,求得 r
r = φ(N) = φ(p)φ(q) = (p-1)(q-1)
  • 3、选择一个小于r并与r互质的整数e,求得e关于r的模反元素,命名为d ( ed ≡ 1(mod r) 模反元素存在,当且仅当e与r互质 );
  • 4、销毁p和q,此时 (N , e)是公钥,(N, d)为私钥;

加密消息

假设Bob想给Alice发送一个消息 n,他知道Alice产生的 Ne ;用下面这个公式他可以将 n加密为 c

c ≡ n^e (mod N)

计算 c并不复杂。Bob算出 c后就可以将它传递给Alice。

解密消息

Alice得到Bob的消息 c后就可以利用她的密钥d来解码。可以用以下这个公式来将 c转换为 n

n ≡ c^d (mod N)

此段落转载自:
维基百科——RSA加密算法

3.2、依照算法公式举个例子

依照算法公式来举个例子

1、随意选择两个大的质数 p和 q,p不等于 q,计算 N=pq

质数 定义:

除了1和该数自身外,无法被其他自然数整除的数。

举例:

p = 3;  q = 5;  N = 3*5 = 15;

2、根据欧拉函数,求得 r

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

欧拉函数 定义:

欧拉函数 φ(n)是小于或等于n的正整数中与n互质的数的数目。    例如:φ(8) = 4,因为1,3,5,7均和8互质。

举例:

r = φ(N) = φ(p)φ(q) = (p-1)(q-1) ;    r = φ(15) = φ(3)φ(5) = (3-1)(5-1) ;  r = 8

3、选择一个小于r并与r互质的整数e,求得e关于r的模反元素,命名为d ( ed ≡ 1(mod r) 模反元素存在,当且仅当e与r互质 );

互质 定义:

如果两个或两个以上的整数的最大公约数是 1,则称它们为互质    例如:1,3,5,7均和8互质

模反元素 定义:

如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。    例如:比如3和5互质,3关于5的模反元素就可能是2,因为 (3*2)%5=1 。

举例:

// 选择一个小于r并与r互质的整数e (1,3,5,7均和8互质):  e = 7;  // 求得e关于r的模反元素,命名为d (    ed ≡ 1(mod r)     )    ed ≡ 1(mod r) ;    7*d ≡ 1(mod 8) ;  7*d%8 = 1;  // 这里取d = 15  d = 15;

4、销毁p和q,此时 (N , e)是公钥,(N, d)为私钥

// 公钥  (N , e)  ( 15,7 )  // 私钥 (N, d)  ( 15,15 )

5、加密

假设Bob想给Alice发送一个消息 n,他知道Alice产生的 Ne ;用下面这个公式他可以将 n加密为 c

举例:

// 假设  n = 2;  // 计算c  c ≡ n^e (mod N) ;    (c^-1 * n^e)%N = 1 ;  (c^-1 * 2^7)%15 = 1 ;  //  c = 8;

6、解密

Alice得到Bob的消息 c后就可以利用她的密钥d来解码。可以用以下这个公式来将 c转换为 n

举例:

// 计算n  n ≡ c^d (mod N)    n ≡ 8^15 (mod 15) ;  (n^-1 * 8^15)%15 = 1 ;  //  n = 2;

参考

如何用通俗易懂的话来解释非对称加密?
维基百科——RSA加密算法
RSA算法详解

========== THE END ==========

wx_gzh.jpg