RAS加密算法

欢迎交流讨论:

twitter: RytterMohn

一、RAS简单介绍

RSA密码体制是根据PKC算法，并由美国麻省理工学院（MIT）的研究小组提出的，该体制的名称是用了3位作者Rivest,Shamir,Adleman英文名字的第一个字母拼合而成。该体制的理论基础是数论中的下述论断：要求得到两个大素数（如大到100位）的乘积在计算机上很容易实现，但要分解两个大素数的乘积在计算机上几乎不可能实现，即为单向函数

介绍来自度娘~

二、加密过程

  1. 选择一对不相等且足够大的质数，列如：选z1和z2为较大的两个质数
  2. 计算z1和z2的乘积，n=z1*z2
  3. 计算n的欧拉函数$\phi(n)=(z1-1)*(z2-1)$
  4. 选一个与$\phi(n)$互质的整数e,且$e<\phi(n)$
  5. 算出e对于$\phi(n)$的模反元素d
  6. 公钥：KU=（e,n），e和n是成对的，共同组成公钥
  7. 私钥：KR=（d,n)，同上

使用方法：

明文M 加密 $M^e\mod\ n =C$

密文C 解密 $C^d\mod\ n=M$

三、概念解释

欧拉函数：

$\phi(n)$是小于n的正整数中与n互质的数的数目，注意：是互质数的个数，不是质数的个数

如果z1、z2都是质数，则$\phi(n)=(z1-1)*(z2-1)$

互质

指公约数只有1的两个整数，叫做互质整数。

模反元素

如果两个正整数互质，如e和$\phi(n)$，那么一定可以找到一个整数d，使e*d-1被$\phi(n)$整除，d就叫e的模反元素。

可写作：ed-1=k\$\phi(n)$

或：e*d mod $\phi(n)=1$

四、举例

例题一

RAS算法中，若选取两奇数p=5,q=3,公钥e=7，则私钥d为多少？

解

  1. 由p与q计算n，可得n=15
  2. 计算欧拉函数，得$\phi(n)=\phi(15)=8$
  3. 由e*d-1=k*8,k为正整数，得d=7

例题二

已知：

p = 3487583947589437589237958723892346254777

q = 8767867843568934765983476584376578389

e = 65537

求：

d=?

解

1
2
3
4
5
6
import gmpy2 as gm
p = 3487583947589437589237958723892346254777
q = 8767867843568934765983476584376578389
e = 65537
d = gm.invert(e,(p-1)*(q-1)) #invert函数第一个参数为e，第二个为$\phi$
print(d)

验证

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2 as gm

p = 3487583947589437589237958723892346254777
q = 8767867843568934765983476584376578389
e = 65537
d = gm.invert(e, (p - 1) * (q - 1))
print("d:", d)
M = gm.mpz(114514)  # mpz将其压缩
C = pow(M, e, p * q)
print("C", C)
C = gm.mpz(C)
m = pow(C, d, p * q)
print("更改后", m)

成功输出加密文本：114514

验证成功！

结果

img