RSA加密算法代码实现

作业目标

C语言实现RSA加密算法，并将其优化到尽量快的速度。

算法描述

RSA加密算法是最常用的非对称加密算法，CFCA在证书服务中离不了它。RSA是第一个比较完善的公开密钥算法，它既能用于加密，也能用于数字签名。RSA以它的三个发明者Ron Rivest, Adi Shamir, Leonard Adleman的名字首字母命名，这个算法经受住了多年深入的密码分析，但是它的安全性还没有被证明，当然也没有被否定。

RSA流程

注意 p和q是保密的，n是公开的
上述可以看成是密钥的产生和加密解密两个模块

数学准备

• 互质关系
  如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。
  不是质数也可以是互质关系，在证明时需要用到$(M^k,n)$ 互质.
• 欧拉公式 与 欧拉定理
  • φ(n)为比n小但与n互素的正整数个数，称为n的欧拉函数。
  • 对任一素数p, 有φ(n)＝p-1，而对于两个不同的素数p和q，则对n=pq，可以证明φ(n)＝φ(p*q)=φ§*φ(q)=(p-1)(q-1) 。
  • 欧拉定理：设 n 是大于 1 的整数，如果 a 满足 gcd(a, n) = 1 的整数，则： $$a^{\varphi (n)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)$$
• 模反元素 d
  • 乘法逆元：如果x与y的积除以z所得的余数为1，即xy = 1 (mod z)，则称x和y对于模数z来说互为逆元。
  • 模反元素 d：如果e与φ(n)互质，则存在d使得e*d - 1 被 φ(n)整除。即 e*d (mod φ(n)) =1.
• Solovay-Strassen概率性素性检测法：
  • 判定n是素数的正确性概率至少为50%，出错的概率小于50%。通过随机均匀的从{1，2，···，n-1}中选取a，对n进行k次Solovay-Strassen素性检测，如果每次都通过了素性检测，即没有输出“n不是素数”，则n是合数的概率小于1/（2^{k）。当k足够大时，1/（2}k）是一个非常小的数。也即误判的可能性非常小。
• 雅可比符号：
  • 
• 二次剩余
  • 可用来判断二次同余式是否有解；
  • 当存在某个X，式子$X^2\equiv d\pmod p $ 成立时，称“d是模p的二次剩余”
  • 质数乘方：每个奇数的平方都模8余1，因此模4也余1。设a是一个奇数。m为8，16或2的更高次方，那么a是关于m的二次剩余当且仅当$a\equiv 1\pmod 8 $
  • 对于奇质数p以及与p互质的整数A，A是关于p的若干次乘方的剩余当且仅当它是关于p的剩余。
• 扩展欧几里得算法
  • "扩展"这意味着该算法不仅保留了欧几里得算法的核心——求最大公约数，还具备欧几里得算法没有的功能——求解贝祖等式。
  • 

算法正确行证明

实验设计

文件组成

• main.c : 控制流程如下：

  1. 素数p:Got first prime factor, p = 9949 …
  2. 素数q:Got second prime factor, q = 4931 …
  3. n = p*q: Got modulus, n = pq = 49058519 …
  4. φ(n)＝(p-1)(q-1):Got totient, phi = 49043640 …
  5. 选择与φ(n)互质的整数e:Chose public exponent, e = 161
  6. Public key is (161, 49058519) …
  7. 计算e对于φ(n)的模反元素d:Calculated private exponent, d = 5178521
  8. Private key is (5178521, 49058519) …
  9. Opening file “TestText.txt” for reading
     File “TestText.txt” read successfully, [length] bytes read. Encoding byte stream in chunks of [3\2\1] bytes
  10. 加密:Encoding finished successfully …
  11. 解密:Decoding encoded message …
  12. 加密速度:t_encode = 978 ms v_encode = 15.79755 Byte/ms
  13. 解密速度:t_decode = 423 ms v_decode = 36.52482 Byte/ms
      Finished RSA demonstration!

• RSA.c: 各个功能实现

• RSA.h: 头文件集合

函数介绍

获取素数

int randPrime(int n) {
	int prime = rand() % n;
	n += n % 2; 
	prime += 1 - prime % 2;
	while(1) {
		if(probablePrime(prime, ACCURACY)) return prime;
		prime = (prime + 2) % n;
	}
}

使用：p = randPrime(SINGLE_MAX);
描述：
该素数小于n，即SINGLE_MAX = 10000（RSA.h）;
n 需要是偶数，所以模包装保留了奇数;
prime是奇数
probablePrime(prime, ACCURACY)函数是用来检测这个奇数是不是素数。但是并非通过就一定是素数，ACCURACY = 5,即概率性的素数检验方法的安全系数为5.

//判断n是否为素数
int probablePrime(int n, int k) {
	if(n == 2) return 1;
	else if(n % 2 == 0 || n == 1) return 0;
	while(k-- > 0) {
		if(!solovayPrime(rand() % (n - 2) + 2, n)) return 0;
	}
	return 1;
}
//概率性的素数检验方法
int solovayPrime(int a, int n) {
	int x = jacobi(a, n);
	if(x == -1) x = n - 1;
	return x != 0 && modpow(a, (n - 1)/2, n) == x;
}
//返回雅各比符号(a, n)的值
int jacobi(int a, int n) {
	int twos, temp;
	int mult = 1;
	while(a > 1 && a != n) {
		a = a % n;
		if(a <= 1 || a == n) break;
		twos = 0;
		while(a % 2 == 0 && ++twos) a /= 2; /* Factor out multiples of 2 */
		if(twos > 0 && twos % 2 == 1) mult *= (n % 8 == 1 || n % 8 == 7) * 2 - 1;
		if(a <= 1 || a == n) break;
		if(n % 4 != 1 && a % 4 != 1) mult *= -1; /* Coefficient for flipping */
		temp = a;
		a = n;
		n = temp;
	}
	if(a == 0) return 0;
	else if(a == 1) return mult;
	else return 0; /* a == n => gcd(a, n) != 1 */
}

solovay判定算法步骤
输入：一个大于3的奇整数n和一个大于等于1的安全参数k（用于确定测试轮数）。
输出：返回n是否为素数。
算法步骤：
对i从1到k做循环做以下操作：
（1）选择一个小于n的随机数a；
（2）计算j=a^((n-1)/2) mod n;
（3）如果j != 1 或 -1，则返回n不是素数；
（4）计算Jacobi符号J（a，n）=（a/n）；
（5）如果j != （a/n），则返回n不是素数；

模运算

// 求 a^b mod c
int modpow(long long a, long long b, int c) {
	int res = 1;
	while(b > 0) {
		if(b & 1) {
			res = (res * a) % c;
		}
		b = b >> 1;
		a = (a * a) % c; 
	}
	return res;
}

注意每次乘完都要取模，可以算得更快，也避免数字过大引发溢出问题。

加密与解密

int encode(int m, int e, int n) {
	return modpow(m, e, n);
}
int decode(int c, int d, int n) {
	return modpow(c, d, n);
}

选⼀个与φ(n)互质的整数e

找到一个介于 3 和 n - 1 之间的随机指数 x，使得 gcd(x, phi) = 1，这种分布非均匀

int randExponent(int phi, int n) {
	int e = rand() % n;
	while(1) {
		if(gcd(e, phi) == 1) return e;
		e = (e + 1) % n;
		if(e <= 2) e = 3;
	}
}

调用：e = randExponent(phi, EXPONENT_MAX);

计算e对于φ(n)的模反元素d

使用欧几里得扩展算法计算

int inverse(int n, int modulus) {
	int a = n, b = modulus;
	int x = 0, y = 1, x0 = 1, y0 = 0, q, temp;
	while(b != 0) {
		q = a / b;
		temp = a % b;
		a = b;
		b = temp;
		temp = x; x = x0 - q * x; x0 = temp;
		temp = y; y = y0 - q * y; y0 = temp;
	}
	if(x0 < 0) x0 += modulus;
	return x0;
}

调用：d = inverse(e, phi);

读文件部分与加密速度计算略

优化技巧

分成小块字节

//main.c
n = p * q;
if(n >> 21) bytes = 3;
else if(n >> 14) bytes = 2;
else bytes = 1;	
//RSA.c
/**
 使用公钥（指数、模数）对给定长度的消息进行编码
 结果数组的大小为 len/bytes，每个索引都是“bytes”连续字符的加密，由 m = (m1 + m2*128 + m3*128^2 + ..) 给出，
 *encoded = m^exponent mod modulus
 */
int* encodeMessage(int len, int bytes, char* message, int exponent, int modulus) {
	int *encoded = malloc((len/bytes) * sizeof(int));
	int x, i, j;
	for(i = 0; i < len; i += bytes) {
		x = 0;
		for(j = 0; j < bytes; j++) x += message[i + j] * (1 << (7 * j));
		encoded[i/bytes] = encode(x, exponent, modulus);
#ifndef MEASURE
		printf("%d ", encoded[i/bytes]);
#endif
	}
	return encoded;
}

/**
  * 使用私钥（指数、模数）解码给定长度的密文
  * 每个加密的数据包都应该代表每个 encodeMessage 的“字节”字符。
  * 返回的消息大小为 len * 字节。
 */
int* decodeMessage(int len, int bytes, int* cryptogram, int exponent, int modulus) {
	int *decoded = malloc(len * bytes * sizeof(int));
	int x, i, j;
	for(i = 0; i < len; i++) {
		x = decode(cryptogram[i], exponent, modulus);
		for(j = 0; j < bytes; j++) {
			decoded[i*bytes + j] = (x >> (7 * j)) % 128;
#ifndef MEASURE
			if(decoded[i*bytes + j] != '\0') printf("%c", decoded[i*bytes + j]);
#endif
		}
	}
	return decoded;
}

实验结果与反思

• 某次随机结果
  p = 1693, q = 3433, n = pq = 5812069, phi = 5806944,
  e = 383 公钥 (383, 5812069) …
  d = 2789759 私钥 (2789759, 5812069) …
  File “TestText.txt” read successfully, 15450 bytes read. Encoding byte stream in chunks of 3 bytes …
  加密成功
  开始解密，解密成功
  速度：
  t_encode = 1020 ms v_encode = 15.14706 Byte/ms
  t_decode = 492 ms v_decode = 31.40244 Byte/ms
  Finished RSA demonstration!

• 还看到一种生成随机数的做法是把1-10000之间的随机数写入数组，然后每次随机选择两个。

参考文献

《密码学引论》
https://zhuanlan.zhihu.com/p/48994878
https://github.com/pantaloons/RSA
https://sandtower.blog.csdn.net/article/details/120931364