1. 大数的运算原理
rsa算法依赖于大数的运算,目前主流rsa算法都建立在512位到1024位的大数运算之上,所以我们首先需要掌握大数(比如1024位)的运算原理。
大多数的编译器只能支持到32位(或64位)的整数运算,即我们在运算中所使用的整数必须小于等于32位,即0xffffffff,这远远达不到rsa的需要,于是需要专门建立大数运算库,来解决这一问题。
最简单的办法是将大数当作字符串进行处理,也就是将大数用10进制字符数组进行表示,然后模拟人们手工进行"竖式计算"的过程编写其加减乘除函数。但是这样做效率很低。当然其优点是算法符合人们的日常习惯,易于理解。
另一种思路是将大数当作一个二进制流进行处理,使用各种移位和逻辑操作来进行加减乘除运算,但是这样做代码设计非常复杂,可读性很低,难以理解也难以调试。
这里我们采用了一种介于两者之间的思路:将大数看作一个n进制数组,对于目前的32位而言,n可以取2的32次方,即 0x100000000,假如将一个1024位的大数转化成0x10000000进制,它就变成了32位,而每一位的取值范围是0- 0xffffffff.我们正好可以用一个无符号长整数来表示这一数值。所以1024位的大数就是一个有32个元素的unsigned long数组。而且0x100000000进制的数组排列与2进制流对于计算机来说,实际上是一回事,但是我们完全可以针对unsigned long数组进行"竖式计算",而循环规模被降低到了32次之内,并且算法很容易理解。
但考虑到乘法和除法,都要进行扩展才能进行快速的计算(如果把除法变减法而不扩展,速度将慢的无法忍受)。所以我们将n取2的16次方的,即 0xffff.每一位用unsigned short来表示,当进行乘除运算时,将short扩展成long,这是编译器所支持的,所以运算起来,比较快。
2. 大数的各种运算
这些运算都是常见的,同时也是常用的。要实现rsa算法,就必须先实现大数的这些运算。
1) 大数的比较。两个无符号或有符号的大数进行大小比较。大数和一般整数进行比较。大于,等于,小于,返回值各异,以区别比较结果。
2) 大数的赋值。将一个大数的值,符号等,逐位赋给另一个大数。将一般整数的值,符号等赋给一个大数。
3) 大数的加法。两个大数从低位到高位逐位相加,要考虑到进位的问题。或大数与一般整数的相加。
4) 大数的减法。两个大数从低位到高位逐位相减,要考虑到借位的问题。或大数与一般整数的相减。
5) 大数的乘法。两个大数的乘法,从一个大数的低位到高位,逐位与另一个大数相乘,然后将结果低位对齐相加,要考虑进位,类似于普通的竖式乘法。或大数与一般整数的乘法。
6) 大数的除法。两个大数的除法,从一个大数的高位到低位,逐步与另一个大数相除,要考虑借位,类似于普通的竖式除法。或大数与一般整数的乘法。
7) 大数的取余。两个大数的取余,类似于大数的除法,只是当除到底时,返回的是余数而已,也存在借位的问题。或大数于一般整数的取余。
8) 大数的欧氏算法。它是已知大数a、b,求满足ax≡1 mod b的x,是最大公约数算法的扩展,同样用辗转相除法。再递归的过程中,两个参数都要用到,到要变化的。具体算法请参考源代码。
9) 大数的蒙氏算法。它是已知大数a、b和c,求x=a^b mod c的值。要对指数进行逐渐降阶,直到变成2次方,也就是转换成乘法和取余运算。降阶的方法和算法的具体过程,请参考相关书籍和源代码。
10) 大数的最大公约数。求两个大数的最大公约数,用辗转相除法。
rsa算法的实现
a. 生成密钥函数
gchar ggeneratekey(gbigint *n,gbigint *e,gbigint *d);
功能:该函数实现了产生密钥的功能。先产生两个随机的大素数p和q,然后计算n=p×q,随机产生(或固定)一个大数e,计算d,使得ed≡1 mod (p-1)(q-1)。
参数:
n:两个大数的乘积,和e或d联合构成密钥或解密密钥。
e:一个大数,作为加密密钥。
d:一个和e互异的大数,作为解密密钥。
返回值:1-成功,0-失败。
b. 数据加密函数
char gencrsa(unsigned char* indata, unsigned long inlen, gbigint* e, gbigint* n,
unsigned char *outdata, unsigned long* outlen, int flg);
功能:把待加密的明文数据indata,用加密密钥e和n进行分段加密。
加密后的数据放到提前开辟好的内存outdata中,其长度outlen不得小于((inlen+k-12)/(k-11))*k,这里k为n的位数。
参数:
indata:指向明文数据的指针。
inlen:传入数据的长度,即明文数据的长度。
e和n:两个大数,作为加密密钥。
outdata:存放加密后密文数据的指针。
outlen:传入outdata的长度,传出数据的长度,即密文数据的长度。
flg:公钥加密或私钥加密的标志,g_public-公钥,g_private-私钥。
返回值:1-成功,0-失败。
c. 数据解密函数
char gdecrsa(unsigned char* indata, unsigned long inlen, gbigint* d, gbigint* n,
unsigned char *outdata, unsigned long* outlen, int flg);
功能:把待解密的密文数据indata,用解密密钥e和n进行分段解密。
解密后的数据放到提前开辟好的内存outdata中,其长度outlen不得小于(inlen)*k/(k-11),
这里k为n的位数。
参数:
indata:指向密文数据的指针。
inlen:传入数据的长度,即密文数据的长度。
d和n:两个大数,作为加密密钥。
outdata:存放解密后明文数据的指针。
outlen:传入outdata的长度,传出数据的长度,即明文数据的长度。
flg:公钥加密或私钥加密的标志,g_public-公钥,g_private-私钥。
返回值:1-成功,0-失败。
d. 用小素数检测
gchar gisnotprime(gbigint *p);
功能:检测随机大数p能否被小素数整除。
参数:
p:待检测的随机大数。
返回值:0-可能是素数,其它-为能整除p的小素数或1.
e. rabin-miller检测
gchar grabinmillertest(gbigint *p,int tnum);
功能:用rabin-miller算法,对大数p进行tnum次检测,判断p是否可能为素数。
参数:
p:待检测的随机大数。
tnum:检测的次数,它可以决定该检测的可信度。
返回值:0-失败或通不过,1-成功并通过,说明p可能是素数。
f. 随机产生大素数
gchar ggenerateprime(gbigint *p);
功能:随机生成一个大素数。
参数:
p:随机生成的大素数。
返回值:0-失败,1-成功。
g. 顺序搜索大素数
gchar ggenerateprimeex(gbigint *p, int flg);
功能:根据标志flg,递增或递减地搜索p附近的大素数。
参数:
p:搜索到的大素数。
flg:方向标志,g_increase-递增,g_decrease-递减。
返回值:0-失败,1-成功。
h. 字符串与大数的转换
gchar gstr2bigint(gbigint *gbi,char *str,int flg);
功能:根据标志flg,将表示成10进制或16进制形式的字符串str转换成大数gbi.
参数:
gbi:转换成的大数。
str:待转换的字符串。
flg:标志,oct_flg-8进制,dec_flg-10进制,hex_flg-16进制。
返回值:0-失败,1-成功。
gchar gbigint2str(char *str,gbigint *gbi,int flg);
功能:根据标志flg,将大数gbi转换成10进制或16进制形式表示的字符串str.
参数:
str:转换成的字符串。
gbi:待转换的大数。
flg:标志,oct_flg-8进制,dec_flg-10进制,hex_flg-16进制。
返回值:0-失败,1-成功。
i. 一般整数的乘除
guint gintmul(guint *a, guint b);
功能:一般整数的乘法。在函数内部,对整数a和b进行扩展,然后与b相乘,把结果放在a中返回,进位作为返回值。
参数:
a:传入一个整数,传出相乘的结果。
b:传入一个整数,作乘数。
返回值:两个整数相乘的进位。失败时,返回0.
guint gintdiv(guint *ah, guint *al, guint b);
功能:一般整数的除法。在函数内部,将整数ah和al合并成一个扩展了的整数,然后除以整数b,把结果的高位放到ah中,低位放到al中返回,余数作为返回值。
参数:
ah:传入一个整数,作为被除数的高位;传出相除后的结果的高位。
al:传入一个整数,作为被除数的低位;传出相除后的结果的低位。
b:传入一个整数,作除数。
返回值:相除的余数。失败时,返回0.
j. 大数的比较
gchar gcmp(gbigint *a, gbigint *b);
功能:对大数a和大数b进行比较,不考虑它们的符号,只比较数值。
参数:
a:传入一个大数。
b:传入另一个大数。
返回值:-1-大数a小于大数b,0-大数a等于大数b,+1-大数a大于大数b.
gchar gcmpex(gbigint *a, gbigint *b);
功能:对大数a和大数b进行比较,考虑它们的符号,整数大于负数。
参数:
a:传入一个大数。
b:传入另一个大数。
返回值:-1-大数a小于大数b,0-大数a等于大数b,+1-大数a大于大数b.
gchar gcmpint(gbigint *a, guint b);
功能:大数与整数的比较。对大数a和一般整数b进行比较,不考虑它们的符号。
参数:
a:传入一个大数。
b:传入一个一般整数。
返回值:-1-大数a小于b,0-大数a等于b,+1-大数a大于b.
k. 大数的赋值
gchar gmov(gbigint *a, gbigint *b);
功能:将大数b的值,赋给大数a,考虑它们的符号。
参数:
a:传出赋值的结果。
b:传入另一个大数。
返回值:0-失败,1-成功。
gchar gmovint(gbigint *a, guint b);
功能:将整数b的值,赋给大数a,考虑它们的符号。
参数:
a:传出赋值的结果。
b:传入一个一般整数。
返回值:0-失败,1-成功。
l. 大数的加法
gchar gadd(gbigint *a, gbigint *b);//加
功能:对大数a和大数b进行加法运算,考虑它们的符号。
参数:
a:传入一个大数,传出相加的结果。
b:传入另一个大数。
返回值:0-失败,1-成功。
gchar gaddint(gbigint *a, gsint b);
功能:对大数a和整数b进行加法运算,考虑它们的符号。
参数:
a:传入一个大数,传出相加的结果。
b:传入一个一般整数。
返回值:0-失败,1-成功。
m. 大数的减法
gchar gsub(gbigint *a, gbigint *b);//减
功能:对大数a和大数b进行减法运算,考虑它们的符号。
参数:
a:传入一个大数,传出相减的结果。
b:传入另一个大数。
返回值:0-失败,1-成功。
gchar gsubint(gbigint *a, gsint b);
功能:对大数a和整数b进行减法运算,考虑它们的符号。
参数:
a:传入一个大数,传出相减的结果。
b:传入一个一般整数。
返回值:0-失败,1-成功。
n. 大数的乘法
gchar gmul(gbigint *a, gbigint *b);//乘
功能:对大数a和大数b进行乘法运算,考虑它们的符号。
参数:
a:传入一个大数,传出相乘的结果。
b:传入另一个大数。
返回值:0-失败,1-成功。
gchar gmulint(gbigint *a, gsint b);
功能:对大数a和整数b进行乘法运算,考虑它们的符号。
参数:
a:传入一个大数,传出相乘的结果。
b:传入一个一般整数。
返回值:0-失败,1-成功。
o. 大数的除法
gchar gdiv(gbigint *a, gbigint *b);//除
功能:对大数a和大数b进行除法运算,考虑它们的符号。
参数:
a:传入一个大数,传出相除的结果。
b:传入另一个大数。
返回值:0-失败,1-成功。
gchar gdivint(gbigint *a, gsint b);
功能:对大数a和整数b进行除法运算,考虑它们的符号。
参数:
a:传入一个大数,传出相除的结果。
b:传入一个一般整数。
返回值:0-失败,1-成功。
p. 大数的取余
gchar gmod(gbigint *a, gbigint *b);//取余
功能:对大数a和大数b进行取余运算,考虑它们的符号。
参数:
a:传入一个大数,传出取余的结果。
b:传入另一个大数。
返回值:0-失败,1-成功。
gchar gmodint(gbigint *a, gsint b);
功能:对大数a和整数b进行取余运算,考虑它们的符号。
参数:
a:传入一个大数,传出取余的结果。
b:传入一个一般整数。
返回值:0-失败,1-成功。
q. 欧几里德算法
gchar geuc(gbigint *a,gbigint *b);//欧几里德算法
功能:对大数a和大数b执行欧几里德算法,结果放到a中。即用辗转相除的思想,求满足ax≡1 mod b的x的值,也即求满足ax-by=1的较小的大数x和y的值。
其中用到了递归的思想,运算后,大数a和大数b,都改变了。
参数:
a:传入一个大数,传出满足ax-by=1的x的值。
b:传入另一个大数,传出满足ax-by=1的y的值
返回值:0-失败,1-成功。
r. 蒙格马利算法
gchar gmon(gbigint *a, gbigint *b, gbigint *c);//蒙格马利算法
功能:对大数a,大数b和大数c执行蒙格马利算法,结果放到a中。
即用指数降阶的思想,求算式a^b mod c的值。至于降阶的原理,请参考相关书籍。
参数:
a:传入一个大数,传出运算的结果。
b:传入另一个大数。
c:传入第三个大数。
返回值:0-失败,1-成功。
s. 最大公约数
gchar ggcd(gbigint *a, gbigint *b);//最大公约数
功能:用辗转相除法,求大数a和大数b的最大公约数。
参数:
a:传入一个大数,传出a和b的最大公约数
b:传入另一个大数。
返回值:0-失败,1-成功。
摘自 脉凌网络
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/603872.html