rsaeuro是一款小巧的开源rsa算法库，它支持生成RSA Key，签名，校验，对称加密，哈希算法等多种功能，可以说是一款应对非对称加解密应用的利器，被广泛应用在多种嵌入式应用场合，比如前东家的高安机顶盒，下面简述一下它的开发步骤。

获取代码

代码从github获取

https://github.com/mort666/RSAEuro

修改编译错误

由于代码比较古老，有些规范和语法新平台下的编译器汇编器已经不在支持了，并且开源代码本身的构建系统也有一些问题，所以下载下来的代码不能直接编译，需要修改，总的修改文件有如下几个：

修改补丁如下：

diff --git a/install/unix/makefile b/install/unix/makefile
old mode 100644
new mode 100755
index 6aee6c3..4ca599c
--- a/install/unix/makefile
+++ b/install/unix/makefile
@@ -35,15 +35,15 @@ CPUT = 386
 ANSISTD = 
 
 # utility routines
-del = del
-COPY = copy
+del = rm -fr
+COPY = cp
 
 # name of main executable to build
 PROG = all
 
 # Normal C flags.
 ifdef CPUT
-CFLAGS = $(INCL) -O -c -DPROTOTYPES=0 -DUSEASM=1 -DDES386=1
+CFLAGS = $(INCL) -O -c -DPROTOTYPES=0 -DDES386=1
 else
 ifdef ANSISTD
 CFLAGS = $(INCL) -O -c -DPROTOTYPES=0 -DUSA_ANSI=1
@@ -56,13 +56,13 @@ ASMFL = $(INCL) -c -Wa,-L
 MFLAGS = -I. -I$(RSAEURODIR)
 
 # The location of the common source directory.
-RSAEURODIR = ../source/
+RSAEURODIR = ../../source/
 RSAEUROLIB = rsaeuro.a
 RSAREFLIB = rsaref.a
 
 # The location of the demo source directory.
 RDEMODIR = ../rdemo/
-DEMODIR = ../demo/
+DEMODIR = ../../demo/
 
 ifdef CPUT
 all : rstdasm.$(O) demo $(RSAREFLIB)
diff --git a/source/des386.s b/source/des386.s
index 4607040..d69c03a 100644
--- a/source/des386.s
+++ b/source/des386.s
@@ -27,6 +27,7 @@
 		0.91 Current revision some minor bug fixes to original
 		code.  Comments revised to reflect original C code.
 */
+    .code32
 
 	/* Crafty DES Function */
 #define	F(l,r,key) 	movl r,%eax ;\
@@ -35,34 +36,34 @@
 	andl $0xfcfcfcfc,%eax ;\
 \
 	movb %al,%bl ;\
-	xorl _Spbox+6*256(%ebx),l ;\
+	xorl Spbox+6*256(%ebx),l ;\
 	movb %ah,%bl ;\
 	rorl $16,%eax ;\
-	xorl _Spbox+4*256(%ebx),l ;\
+	xorl Spbox+4*256(%ebx),l ;\
 	movb %al,%bl ;\
-	xorl _Spbox+2*256(%ebx),l ;\
+	xorl Spbox+2*256(%ebx),l ;\
 	movb %ah,%bl ;\
-	xorl _Spbox(%ebx),l ;\
+	xorl Spbox(%ebx),l ;\
 \
 	movl 4+key(%esi),%eax ;\
 	xorl r,%eax ;\
 	andl $0xfcfcfcfc,%eax ;\
 \
 	movb %al,%bl ;\
-	xorl _Spbox+7*256(%ebx),l ;\
+	xorl Spbox+7*256(%ebx),l ;\
 	movb %ah,%bl ;\
 	rorl $16,%eax ;\
-	xorl _Spbox+5*256(%ebx),l ;\
+	xorl Spbox+5*256(%ebx),l ;\
 	movb %al,%bl ;\
-	xorl _Spbox+3*256(%ebx),l ;\
+	xorl Spbox+3*256(%ebx),l ;\
 	movb %ah,%bl ;\
-	xorl _Spbox+256(%ebx),l
+	xorl Spbox+256(%ebx),l
 
 
 	.align 2
-.globl _desfunc
+.globl desfunc
 
-_desfunc:
+desfunc:
 	pushl %ebp
 	movl %esp,%ebp
 	pushl %esi
diff --git a/source/rsa386.s b/source/rsa386.s
index 9ce6e6f..6817be1 100644
--- a/source/rsa386.s
+++ b/source/rsa386.s
@@ -37,6 +37,7 @@
 
 	.align 2
 	.globl _NN_Cmp
+	.code32
 
 _NN_Cmp:
 	pushl %ebp

编译

在RSAEuro-master/install/unix目录下，直接执行make命令，完成编译：

编译后生成redemo, mdemo,randemo几个可执行程序，可以进行RSA 密钥生成，签名和校验。

以redemo为例，执行后的输出列表如下，可以选择创建密钥，加载密钥，给文件签名等等功能。

默认rsaeuro支持的keylength为508-1024， 也就是支持最大的素数乘积为1024位，以当前的计算机处理速度而言，仅仅相当于128长度密码AES的加密强度，所以一般应用中使用的是2048位的RSA算法，rsaeuro也可以支持到，方法是做如下改动：

这样修改后的redemo，将可以产生2048位的RSA公钥和私钥.

密码中的映射

如果用数学上映射的视角观察加密算法，你会发现加密算法的本质是一个映射，更准确地说是一个单射。只要知道任何一方，都能够反求另一方。只是求解的难度可能会有差异。

两个质数相乘，就算得到的结果再大你也不会觉得困难，但是如果让你对一个较大的数进行质因数分解，求出原本的质数组合，就没那么容易了。单射关系成立，得出结果很简单，但分解回两个质数很难，即便根据素数定理，这种分解一定存在并且唯一，这是分解质因数的特性，许多密码的设置正是运用了这个特性（NP难问题）。

2010年发布的研究报告指出，300台电脑在3年时间内不停运转，通过分解质因数得到的数是232位数。

RSA密码系统加密举例

根据百度描述的算法步骤，我们生成一组RSA KEY，并实现加解密

RSA密钥的生成过程

step 1:

寻找两个大素数p和q. 实际生活中，每台性能一般的普通电脑都可以在几分钟之内通过对奇整数的随机选择获取到满足要求的素数。实际上这个概率可以根据素数定理得到，并不是很低，完全可以做到。

step 2:

计算出p*q的欧拉φ函数, 令N=p*q, r=φ(N)=φ(p*q). 欧拉φ函数是乘性函数，所以可以得到r的值：

       r=φ(n)=φ(p*q)=φ(p)*φ(q)=(p-1)(q-1)

step 3:

随即选择一个整数e,满足e < r，并且e,r互素，也就是(e,r)=1. 这样，得到了公钥(N,e).

step 4:

这一步，还需要在找一个数，它是e关于r的模逆元，记为d, 满足ed-1=kr, k为整数。也就是ed与1模r同余：

       

所以前面第三步才要求e,r互素，否则不可能存在模逆元d. (N,d)就是私钥。

step 5:

销毁p,q，发布公钥，自己保留私钥。

销毁p,q的原因是:d是根据e和r算出来的，而r=φ(n)=φ(p*q)=φ(p)*φ(q)=(p-1)(q-1)， 所以仅仅根据公钥(n,e)推算d的话，需要对n进行素数分解为pxq，根据素数定理，分解唯一，且大素数分解非常困难，实践中很难做到，所以需要销毁p,q.

一个例子

选择素数p=5,q=11，则n=55, r=φ(n)=φ(55)=φ(5*11)=φ(5)*φ(11)=4*10=40. 选择e=3,并且gcd(40,3)=1.

为了得到d,根据e*d≡1 mod φ(n)， 也就是3*d mod 40=1, 3d=k*40+1.编程获取：

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int i = 1; 
    while(i)
    {
	if((i * 40+1)%3==0) {
		printf("%s line %d, avail d is %d, k is %d.\n",
			__func__, __LINE__, (i * 40+1)/3, i);
	}
	i ++;
    }
    return 0;
}

满足要求的d有多个,这个很自然，如果d0满足要求，则d0+k*φ(n)（dn≡d0(mod φ(n)) 自然也满足要求,也就是说，如果一个模φ(n)的同余类的某个元素是解，则此同余类的所有元素都是解，但是因为(e,r)=1，所以虽然这样的同余类有φ(n)-1个，但是满足要求的同余类只有1个。

e*d0≡1 mod φ(n) , φ(n)≡0 mod φ(n) 

<=>

 e*d0≡1 mod φ(n) , ekφ(n)≡0 mod φ(n)

<=> 

e(d0 + kφ(n))≡1 mod φ(n), k为整数：

所以,d0可以看做是特解，而通解是d0关于模r的同余类, 从下面程序的输出也可以看到27,67,107...都可以表示成27 + k * 40的表示形式。

并且，由于(d,r)=1,这说明，满足要求的小于r的数字中，d只有一个.

我们选择最小的一个，当k取2时，d=27，得到私钥(n,d)=(55,27).

所以：公钥(n,e)=(55,3)，私钥(n,d)=(55,27).

假设需要加密的明文信息为m=14:

加密过程：得到密文c=m^e mod 55=14^3 mod 55=49

解密过程：得到明文m=c^d mod 55=49^27 mod 55=14

NOTE：每次加密的消息m需要满足m<N,如果消息太长，就截成几段。

验证

用普通的计算器很难验证计算结果，原因是没有任何一个计算器能够处理49^27这么大的数字，即便p,q我们已经选择的足够小了。

GNU提供了一个开源工具BC，能够处理任意精度的数值计算，它支持以任意精度给出结果，很多的胶水语言，比如perl, html,python等做计算器应用的时候实际上是调用了bc的算法, man bc如下图所示：

比如我想得到根号2的2000位，那就在控制台输入如下指令即可得到结果：

$ echo "scale=2000;sqrt(2)"|bc

计算49^27也不在话下，校验过程如下，通过BC，我们验证了利用上面产生的RSA密钥对14进行加密和解密的正确性，如下图所示：

前面提到，私钥的d有多个，如果d可以取27，那么d也就可以取27 + k * 40的任意值，我们取67验证一下：

公钥(n,e)=(55,3)，私钥(n,d)=(55,67).

假设需要加密的明文信息为m=14:

加密过程：得到密文c=m^e mod 55=14^3 mod 55=49

解密过程：得到明文m=c^d mod 55=49^67 mod 55=14

同样是对的.

这个结论可以证明：

如果：

则

证明过程：

由于 r=φ(n), n是素数，所以n必定和c互素，根据费马-欧拉定理：

所以：

所以

所以：

得证

关于中间证明用到的费马-欧拉定理和费马小定理，详见吗咪叔的证明：

另一个例子

假定加密模数是素数43和59的乘积，这样可以得到n=43*59=2537为模，取e=13.并且满足(e, φ(n)) = (13, 42*58) = 1.

下一步必须找到私钥，就必须找到e=13关于模φ(2537)=φ(43*59)=42*58=2436的逆。利用欧拉算法进行计算，可得d=937是13模2436的逆。

e*d≡1 mod φ(n) = 1 mod 2436,也可以用程序得到d:

#include <stdio.h>
#include <stdlib.h>
using namespace std;

typedef long long LL;
void ex_gcd(LL a, LL b, LL &x, LL &y, LL &d)
{
	if (!b)
		d = a, x = 1, y = 0;
	else
		ex_gcd(b, a % b, y, x, d), y -= x * (a / b);
}

LL gcd(LL a, LL b)
{
	return !b ? a : gcd(b, a % b);
}

void remainder_equation(int a, int b, int n)
{
	long long X, Y, d, r;
	long long res;
	long long min_res;

	d = gcd(a, n);
	ex_gcd(a, n, X, Y, d);
	if (b % d == 0) {
		r = n / d;
		X = X * (b / d) % n;//特解
		for (int i = 0 ; i < d; i++) {
			res = (X + (i * r)) % n;//通解
			printf("%lld\n", res);            //输出所有解
		}
		min_res = (X % (n / d) + (n / d)) % (n / d);
		printf("min_res %lld.\n", min_res); //输出最小解
	} else {
		printf("No Sulutions!\n");
	}
}

int main(void)
{
	int a = 13;
	int b = 1;
	int n = 2436;

	remainder_equation(13, 1, 2436);
	return 0;
}

待加密数字为："i love you"，按照在26个字母表中的下标表示：09 12 15 22 05 25 15 21。

由于需要满足待加密数字m<n.所以，将加密信息拆分为：0912  1522 0525 1521 四组。

分别加密：

c1=m^e mod n = （0912)^13 mod 2537 = 875.

c2=m^e mod n = （1522)^13 mod 2537 = 99.

c3=m^e mod n = （0525)^13 mod 2537 = 402.

c4=m^e mod n = （1521)^13 mod 2537 = 1325.

所以，密文为：0875 0099 0404 1325

解密：

m1=m^d mod n = （875)^937 mod 2537 = 912.

m2=m^d mod n = （99)^937 mod 2537 = 1522.

m3=m^d mod n = （402)^937 mod 2537 = 525.

m4=m^d mod n = （1325)^937 mod 2537 = 1521.

所以，机密后的明文为:

0912 1522 0525 1521.

完全吻合，证明利用公钥进行加密和解密的过程是完全正确的。

bc验算：

模同余类的图形化表示,geogebra floor/ceil函数：

国密公钥算法

国钥公钥密码算法SM2也是一种非对称加密算法，应用场景和领域和RSA相当，但是存储密度和安全性更强一些，由于是国密算法，主要部署在内销电子产品芯片中。

对于高次的同余方程，如果x0是方程的一个解，则x≡ x0(mod m)剩余类也是方程的解，如下程序所示：

#include <stdio.h>

// x^5+x+1 ≡ 0(mod 7)
int main(void)
{
	int i;

	for(i = 0 ; i < 7; i ++)
	{
		if((i*i*i*i*i + i + 1)%7 == 0){
			printf("%s line %d, %d is result.\n", __func__, __LINE__, i);
		}
	}
	/*
	*main line 11, 2 is result. x≡ 2(mod 7)
	*main line 11, 4 is result. x≡ 4(mod 7)
	*/
	return 0;
}

素性判断的多项式算法

2002年，素数判定问题的多项式时间算法被找到，此前人们一直不知道该问题的确切难度，这一伟大发现改变了2000多年来人们对素数判定方法难度的认知，这个伟大发现是3位印度数学家完成的，现在这个高效的素数判定方法被称为AKS算法，由3位作者姓氏的首字母组成，实现代码如下：

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
//AKS algorithm for testing if a number is prime
typedef unsigned long long uint64;
 
uint64 gcd(uint64 n, uint64 r) 
{
	return r == 0 ? n : gcd(r, n % r);
}
 
bool check_power(uint64 n)
{
	for (double i = 2; i <= ceil(log(n) / log(2)); i++)
	{
		double p = pow(n, 1.0 / i);
		if (p - floor(p) == 0)
			return true;
	}
	return false;
}
bool test(uint64 r)
{
	uint64 i = 2;
	while (i <= sqrt(r)) {
		if (i % r == 0)
			return false;
		i++;
	}
	return true;
}
 
uint64 syz(uint64 r) {
	uint64 i = 2;
	while (i <= sqrt(r)) {
		if (i % r != 0)
			i++;
		else 
			r /= i;
		return r;
	}
}
uint64 pf(uint64 a, uint64 b, uint64 r) {
	uint64 z = 1;
	while (b != 0)
	{
		if (b % 2 == 0)
		{
			b >>= 1;
			a = (a * a) % r;
		}
		else
		{
			b --;
			z = (z * a) % r;
		}
	}
	return z;
}
 
uint64 mods(uint64 n, uint64 r, uint64 a)
{
	int x = 5;//
	uint64 f = 1, g = x * a, y = n, h; 
	while (y != 0)
	{
		if (y % 2 == 0)
		{
			y >>= 1;
			h = g * g;
			g = h % (uint64)(pow(x, r) - 1);
		}
		else
		{
			y --;
			h = f * g;
			f = h % (uint64)(pow(x, r) - 1);
		}
	}
	return f;
}

int main(void)
{
	uint64 a = 1;
	int x = 5;
	uint64 n; 
	printf("please input integer n:"); 
	scanf("%llu", &n);
	if (n < 2)
	{
		printf("n should be greater or equals to 2\n");
		return 0;
	}
	if (check_power(n))
	{
		printf("%llu is a composite number!\n", n);
		return 0;
	}
	else
	{
		uint64 r = 2;
		while (r < n)
		{
			if (gcd(n, r) != 1)
			{
				printf("%llu is a composite number\n", n);
				return 0;
			}
			else if (test(r))
			{
				uint64 q = syz(r - 1);
				if (q >= 4 * sqrt(r) * (uint64)(log(n) / log(2)) && pf(n, (r - 1) / q, r) != 1)
					break;
			}
			r ++;
		}
		for (a = 1; a <= 2 * sqrt(r) * ((uint64)(log(n) / log(2))); a++)
		{
			if (mods(n, r, a) != (((uint64)pow(x, n) - a) % ((uint64)pow(x, r) - 1)))
			{
				printf("%llu is a prime number\n", n);
				return 0;
			}
		}
		printf("%llu is a composite number\n", n);
	}
	return 0;
}

---

参考文档

每日一课：奥数知识点 —— 同余法

bc 命令，Linux bc 命令详解：算术操作精密运算工具 - Linux 命令搜索引擎

---

结束