RSA算法

1977年,三位数学家Rivest、Shamir和Adleman设计了一种算法,可以实现非对称加密

这种算法用他们三个人的名字首字母命名,叫做RSA算法

RSA算法非常可靠,密钥越长,它就越难破解


下面,先介绍一些基本概念与数学定理

质数与互质数

质数

一个大于1的自然数,除了1和它本身外,不能被其他自然数整除(除0以外)的数称之为质数(素数);否则称为合数。

例如,15=3×5,所以15不是素数 13除了等于13×1以外,不能表示为其它任何两个整数的乘积,所以13是一个素数 1不是质数,也不是合数


互质数

公约数只有1的两个数,叫做互质数。

判断或选取互质数的方法/定理有很多,如下所示:

  1. 任意两个质数一定构成互质数(如3与11、53与61);
  2. 大数是质数的两个数一定是互质数(如97与88);
  3. 一个质数如果不能整除另一个合数,这两个数为互质数; 即一个数是质数,另一个数只要不是前者的倍数,两者就构成互质关系(如3与10、5与26);
  4. 1和任何一个自然数在一起都是互质数;
  5. 相邻的两个自然数是互质数(如15与16);
  6. 相邻的两个奇数是互质数(如49与51)。
在RSA算法中 我们选用第一条和第二条作为互质数,即选取两个本身都是质数的数作为互质数 而以上第2条定理对于计算欧拉函数值有着积极作用

模运算

模运算的定义如下
m去被n整除,只取所得的余数作为结果,就叫做模运算。

例如,10 mod 3 = 1 、26 mod 6 = 2 、28 mod 2 = 0


同余

”是数论中表示同余的符号 同余的定义如下:
给定一个正整数m,如果两个整数ab满足a-b能被m整除,即(a-b)modm=0, 那么就称整数ab对模m同余,记作a≡b(modm),同时可成立amodm=b


欧拉函数

欧拉函数本身需要一系列复杂推导,本部分仅介绍对认识RSA算法有帮助的部分

任意给定正整数n,计算在小于等于n的正整数之中,有多少个与n构成互质关系? 计算这个值的方法就叫做欧拉函数,以φ(n)表示.

φ(n)表示小于或等于n的正整数中与n互质的数的数目 例如,在1到8之中,与8形成互质关系的是1、3、5、7,所以φ(n)=4 在RSA算法中,我们需要明白欧拉函数对以下定理成立

  • 如果n可以分解成两个互质的整数之积,即n=p×q,则有:φ(n)=φ(pq)=φ(p)φ(q);
  • 根据“大数是质数的两个数一定是互质数”可以知道: 一个数如果是质数,则小于它的所有正整数与它都是互质数; 所以如果一个数p是质数,则有:φ(p)=p-1
由上易得,若我们知道一个数n可以分解为两个质数pq的乘积,则有 φ(n)=(p-1)(q-1)

欧拉定理与模反元素

欧拉函数的用处,在于欧拉定理 “欧拉定理”指的是
如果两个正整数an互质,则n的欧拉函数φ(n)可以让下面的等式成立: a^φ(n)≡1(modn)

也就是说,aφ(n)次方被n除的余数为1 模反元素的推导过程如下

根据欧拉定理,有: a^φ(n)=a×a^φ(n)−1≡1(modn) 令b=a**φ(n)-1,得: ab≡1(modn) b就是a的模反元素

计算密钥

步骤:

  1. 寻找两个质数pq (此处选择61和53)
  2. 计算pq的乘积 N=p×q= 3233
  3. 根据“欧拉函数”介绍过的公式φ(n)=(p-1)(q-1)代入计算n的欧拉函数值φ(3233)=(61-1)×(53-1)=60×52=3120
  4. 随机选择一个整数e,条件是1<e<φ(n),且eφ(n)互质
  5. 乙就在1到3120之间,随机选择了17
  6. 因为eφ(n)互质,根据求模反元素的公式计算e,对于e的模反元素d有:ed≡1(modφ(n))这个式子等价于(ed-1)/φ(n)=kk为任意正整数)即edkφ(n)=1,代入数据得:17d-3120k*=1实质上就是对以上这个二元一次方程求解(此处需要使用欧几里得扩展公式)得到一组解为:(d,k)=(2753,-15)
  7. ne封装成公钥,nd封装成私钥n=3233,e=17,d=2753所以公钥就是(3233,17),私钥就是(3233,2753)其中,n的长度就是密钥长度,3233写成二进制是1100 1010 0001一共有12位,所以这个密钥就是12位实际应用中,RSA密钥一般是1024位,重要场合则为2048位

密钥组成与加解密公式

公钥KUn:质数p和质数q的乘积(pq必须保密) e:与(p-1)×(q-1)互质
私钥KRn:同公钥n de-1(mod(p-1)(q-1))
加密c=m^emodn
解密m=c^dmodn

安全性

根据以上实例,也许会有疑问 公钥中已包含n=3233,我将其因式分解回n=3233=61×53 再根据乙计算密钥的流程,不就可以根据公钥得出私钥了 事实上,RSA的安全性就是源自你没办法轻易的对大整数“因式分解” 上面的例子,密钥长度是12位 因为这只是个示例,所以密钥长度实在是太短了 你可以将示例中的n作因式分解,但是你没法对下面这个整数进行因数分解 12301866845301177551304949 58384962720772853569595334 79219732245215172640050726 36575187452021997864693899 56474942774063845925192557 32630345373154826850791702 61221429134616704292143116 02221240479274737794080665 351419597459856902143413 它等于这样两个质数的乘积: 33478071698956898786044169 84821269081770479498371376 85689124313889828837938780 02287614711652531743087737 814467999489 × 36746043666799590428244633 79962795263227915816434308 76426760322838157396665112 79233373417143396810270092 798736308917 事实上,这大概是人类已经分解的最大整数(232个十进制位,768个二进制位) 对极大整数做因数分解的难度决定了RSA算法的可靠性 实际应用中,RSA密钥一般是1024位(安全),重要场合则为2048位(极其安全)

发表评论

电子邮件地址不会被公开。 必填项已用*标注