RSA加密算法

密码学

Created At : 2022-03-24 18:20

Count:1.4k Views 👀 :

简介
数学基础
密钥生成的步骤
加密解密
c语言实现

简介

密码学由两种算法一个是对称加密算法，一个是非对称加密算法，那什么是对称加密算法呢？

既甲方选择一种加密，乙方使用同种规则解密，这被称为对称加密算法。

我们今天要说的RSA，是一种非对称加密，就是说乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。甲方获取乙方的公钥，然后用它对信息加密。乙方得到加密后的信息，用私钥解密。如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。

数学基础

我们讲RSA的内容之前先了解一点前置数学知识，

互质关系

如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。

任意两个质数构成互质关系，比如13和61。
一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。
如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。
1和任意一个自然数是都是互质关系，比如1和99。
p是大于1的整数，则p和p-1构成互质关系，比如57和56。
p是大于1的奇数，则p和p-2构成互质关系，比如17和15。

欧拉函数

任意给定正整数n，计算在小于等于n的正整数之中，有多少个与n构成互质关系？

计算这个值的方法就叫做欧拉函数，以φ(n)表示.

例如，在1到8之中，与8形成互质关系的是1、3、5、7，所以φ(8)=4

再比如，φ(7）=6，因为7本来是一个质数，所以互质的数有1、2、3、4、5、6

在RSA算法中，欧拉函数对以下定理成立

如果n可以分解成两个互质的整数之积，即n=p×q，则有：φ(n)=φ(pq)=φ( p )φ( q )
当p为质数，φ( p )=p-1，所以有φ(n)=(p-1)(q-1)

同余定理

“≡”是数论中表示同余的符号

同余的定义如下：

给定一个正整数m，如果两个整数a和b满足a - b能被m整除，即(a - b )mod m=0，

那么就称整数a与b对模m同余，记作a ≡ b ( mod m)，同时可成立a mod m = b

注意，同余与模运算是不同的

显然,有如下事实

（1）若a≡0(mod m)，则m|a；

（2）a≡b(mod m)等价于a与b分别用m去除，余数相同。

密钥生成的步骤

选取两个大素数p和q 为了获得最高的安全性，设两数的长度一样
计算n=pq， n称为模
计算欧拉函数F（n）=(p-1)(q-1)
选取加密密钥e 其与f（n）互素，如果选择的e值合适 rsa加解密将会加快，e的常用值为 3 ，17 ，2^16+1=65537
计算模反元素d，如果两个正整数e和F（n）互质，那么一定可以找到一个整数d，使得ed-1被F（n）整除

或者说ed除以F（n）所得余数为1，此时d就叫做e的模反元素，所以求私钥d的公式：d*e≡1mod[(p-1)(q-1)]
将n和e封装成公钥，n和d封装成私钥。

举个例子 p=3，q=11

质数相乘 N=PXQ=3X11=33

欧拉函数 F(n)=（p-1)X(q-1)=2X10=20

选公钥 e 这里选3

（DXE）%F（n）=1

这里求d是3XD%20=1 D等于7 ，

私钥的两个数就是（n，d）也就是（33，7），公钥（e,n)也就是（33，3）

加密解密

（1）加密要用公钥 (n,e), 所谓”加密”，就是算出下式的密文c：

如果M=此时为20，依据上面的例子可以得到c=14

（2）解密要用私钥(n,d)，

推导一下

“加密–解密”的整个过程全部完成。如果不知道d，就没有办法从c求出m,要知道d就必须分解n，这是极难做到的，所以RSA算法保证了通信安全。

公钥(n,e) 只能加密小于n的整数m，那么如果要加密大于n的整数，该怎么办？

有两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；

c语言实现

#include<stdio.h>
int main()
{
	long int p, q, n, e, xn, d, M, i, C = 1, K = 1;
	printf("请输入两个素数p和q:\np = ");
	scanf("%d", &p);
	printf("q = ");
	scanf("%d", &q);
	n = p*q;
	xn = (p - 1)*(q - 1);
	printf("请输入e = ");
	scanf("%d", &e);
	d = xn / e + 1;
	while (e*d % xn != 1)
		d++;
	printf("待加密的消息M = ");
	scanf("%d", &M);
	for (i = 1; i <= e; i++)
	{
		C = M;
		C %= n;
	}
	printf("---------------------------\n");
	printf("公钥KU = (% ld, % ld)\n", n, e);
	printf("私钥KR = (% ld, % ld)\n\n", n, d);
	printf("密文C = % ld ^ %ld mod % ld = % ld\n", M, e, n, C);
	for (i = 1; i <= d; i++)
	{
		K*= C;    
		K %= n;  
	}
	printf("解密M = % ld ^ %ld mod % ld = % ld\n\n", C, d, n, K);
	return 0;
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1204342476@qq.com