今天给各位分享rsa加密怎么实现的知识,如果能碰巧解决你现在面临的问题,别忘了关注本站。
如果需要理解RSA的加密原理,需要理解以下理论:
等同于求一元二次方程 23 * d + 192 * y = 1
可以求得其中一解为(d=167,y=-20)
至此就完成了所有的计算
对于上述例子的到公钥(221,23)和私钥(221,167)
在上述的计算过程中一共用到了
上面用到的数中只有公钥部分是公开的,即(221,23)。那么我们是否可以通过公钥来推到出私钥部分,即已知n和e,推到出d?
(1)ed 1(mod (n)),只有知道 (n)才能解出d
(2) (n)= (p) (q)= (p-1) (q-1),只有知道p和q才能得到 (n)
(3)n=p q,就需要对n进行因式分解
那么如果可以对n因式分解就可以求出d,也就意味着私匙被破解
那么RSA加密的可靠性就在于对n因式分解的难度,而现在对一个整数n做因式分解并没有巧妙的算法,只有通过暴力破解计算。在实际应用中的n取值通常在1024位以上,而公开已知的可因式分解的最大数为768位。所以现阶段来说RSA加密是可靠的。
现在我们就可以进行加密和解密了
我们使用上面生成的公钥(221,23)来加密。如果我们需要加密的信息是m( m必须为整数并且m要小于n ),m取56,可以用以下公式求出加密串c:
c (mod n)
10 (mod 221)
可以求出加密后的结果c为10
密钥为(221,167),加密结果c=10,可以使用以下公式求出被加密的信息
m (mod n) 即加密结果的d次方除以n的余数为m
56 (mod 221)
RSA加密属于块加密算法,总是在一个固定长度的块上进行操作。如果被加密的字符串过长,则需要对字符串进行切割,如果字符串过短则需要进行填充。
以下主介绍一下RSA_PKCS1_PADDING填充模式以及RSA_NO_PADDING模式
此填充模式是最常用的填充模式,在此填充模式下输入的长度受加密钥的长度限制,输入的最大长度为加密钥的位数k-11。如果公钥的长度为1024位即128字节,那么输入的长度最多为128-11=117字节。如果长度小于117就需要填充。如果输入T的长度为55字节,填充后的块为EM,则EM格式如下:
EM= 0x00 || BT || PS || 0x00 || T
在此填充模式下,输入的长度最多和RSA公钥长度一样长,如果小于公钥长度则会在前面填充0x00。如果公钥长度是128字节,输入T的长度为55字节,填充后的块为EM,则EM格式如下:
EM=P || T
参考:
#include stdlib.h
#include stdio.h
#include string.h
#include math.h
#include time.h
#define PRIME_MAX 200 // 生成素数范围
#define EXPONENT_MAX 200 // 生成指数e范围
#define Element_Max 127 // 加密单元的最大值,这里为一个char, 即1Byte
char str_read[100]="hello world !"; // 待加密的原文
int str_encrypt[100]; // 加密后的内容
char str_decrypt[100]; // 解密出来的内容
int str_read_len; // str_read 的长度
int prime1, prime2; // 随机生成的两个质数
int mod, eular; // 模数和欧拉数
int pubKey, priKey; // 公钥指数和私钥指数
// 生成随机素数,实际应用中,这两个质数越大,就越难破解。
int randPrime()
{
int prime, prime2, i;
next:
prime = rand() % PRIME_MAX; // 随机产生数
if (prime = 1) goto next; // 不是质数,生成下一个随机数
if (prime == 2 || prime == 3) return prime;
prime2 = prime / 2; // prime=4, prime2 的平方必定大于 prime , 因此只检查小于等于prime2的数
for (i = 2; i = prime2; i++) // 判断是否为素数
{
if (i * i prime) return prime;
if (prime % i == 0) goto next; // 不是质数,生成下一个随机数
}
}
// 欧几里德算法,判断a,b互质
int gcd(int a, int b)
{
int temp;
while (b != 0) {
temp = b;
b = a % b;
a = temp;
}
return a;
}
//生成公钥指数,条件是 1 e 欧拉数,且与欧拉数互质。
int randExponent()
{
int e;
while (1)
{
e = rand() % eular; if (e EXPONENT_MAX) break;
}
while (1)
{
if (gcd(e, eular) == 1) return e; e = (e + 1) % eular; if (e == 0 || e EXPONENT_MAX) e = 2;
}
}
//生成私钥指数
int inverse()
{
int d, x;
while (1)
{
d = rand() % eular;
x = pubKey * d % eular;
if (x == 1)
{
return d;
}
}
}
//加密函数
void jiami()
{
str_read_len = strlen(str_read); //从参数表示的地址往后找,找到第一个'\0',即串尾。计算'\0'至首地址的“距离”,即隔了几个字符,从而得出长度。
printf("密文是:");
for (int i = 0; i str_read_len; i++)
{
int C = 1; int a = str_read[i], b = a % mod;
for (int j = 0; j pubKey; j++) //实现加密
{
C = (C*b) % mod;
}
str_encrypt[i] = C;
printf("%d ", str_encrypt[i]);
}
printf("\n");
}
//解密函数
void jiemi()
{
int i=0; for (i = 0; i str_read_len; i++)
{
int C = 1; int a = str_encrypt[i], b=a%mod;
for (int j = 0; j priKey; j++)
{
C = (C * b) % mod;
}
str_decrypt[i] = C;
}
str_decrypt[i] = '\0'; printf("解密文是:%s \n", str_decrypt);
}
int main()
{
srand(time(NULL));
while (1)
{
prime1 = randPrime(); prime2 = randPrime(); printf("随机产生两个素数:prime1 = %d , prime2 = %d ", prime1, prime2);
mod = prime1 * prime2; printf("模数:mod = prime1 * prime2 = %d \n", mod); if (mod Element_Max) break; // 模数要大于每个加密单元的值
}
eular = (prime1 - 1) * (prime2 - 1); printf("欧拉数:eular=(prime1-1)*(prime2-1) = %d \n", eular);
pubKey = randExponent(); printf("公钥指数:pubKey = %d\n", pubKey);
priKey = inverse(); printf("私钥指数:priKey = %d\n私钥为 (%d, %d)\n", priKey, priKey, mod);
jiami(); jiemi();
return 0;
}
前几天看到一句话,“我们中的很多人把一生中最灿烂的笑容大部分都献给了手机和电脑屏幕”。心中一惊,这说明了什么?手机和电脑已经成为了我们生活中的一部分,所以才会有最懂你的不是你,也不是你男朋友,而是大数据。
如此重要的个人数据,怎样才能保证其在互联网上的安全传输呢?当然要靠各种加密算法。说起加密算法,大家都知道有哈希、对称加密和非对称加密了。哈希是一个散列函数,具有不可逆操作;对称加密即加密和解密使用同一个密钥,而非对称加密加密和解密自然就是两个密钥了。稍微深入一些的,还要说出非对称加密算法有DES、3DES、RC4等,非对称加密算法自然就是RSA了。那么当我们聊起RSA时,我们又在聊些什么呢?今天笔者和大家一起探讨一下,有不足的地方,还望各位朋友多多提意见,共同进步。
RSA简介:1976年由麻省理工学院三位数学家共同提出的,为了纪念这一里程碑式的成就,就用他们三个人的名字首字母作为算法的命名。即 罗纳德·李维斯特 (Ron Rivest)、 阿迪·萨莫尔 (Adi Shamir)和 伦纳德·阿德曼 (Leonard Adleman)。
公钥:用于加密,验签。
私钥:解密,加签。
通常知道了公钥和私钥的用途以后,即可满足基本的聊天需求了。但是我们今天的主要任务是来探究一下RSA加解密的原理。
说起加密算法的原理部分,肯定与数学知识脱不了关系。
我们先来回忆几个数学知识:
φn = φ(A*B)=φ(A)*φ(B)=(A-1)*(B-1)。
这个公式主要是用来计算给定一个任意的正整数n,在小于等于n的正整数中,有多少个与n构成互质的关系。
其中n=A*B,A与B互为质数,但A与B本身并不要求为质数,可以继续展开,直至都为质数。
在最终分解完成后,即 φ(N) = φ(p1)*φ(p2)*φ(p3)... 之后,p1,p2,p3都是质数。又用到了欧拉函数的另一个特点,即当p是质数的时候,φp = p - 1。所以有了上面给出的欧拉定理公式。
举例看一下:
计算15的欧拉函数,因为15比较小,我们可以直接看一下,小于15的正整数有 1、2、3、4、5、6、7、8、9、10、11、12、13、14。和15互质的数有1、2、4、7、8、11、13、14一共四个。
对照我们刚才的欧拉定理: 。
其他感兴趣的,大家可以自己验证。
之所以要在这里介绍欧拉函数,我们在计算公钥和私钥时候,会用到。
如果两个正整数m 和 n 互质,那么m 的 φn 次方减1,可以被n整除。
其中 .
其中当n为质数时,那么 上面看到的公式就变成了
mod n 1.
这个公式也就是著名的 费马小定理 了。
如果两个正整数e和x互为质数,那么一定存在一个整数d,不止一个,使得 e*d - 1 可以被x整除,即 e * d mode x 1。则称 d 是 e 相对于 x的模反元素。
了解了上面所讲的欧拉函数、欧拉定理和模反元素后,就要来一些化学反应了,请看图:
上面这幅图的公式变化有没有没看明白的,没看明白的咱们评论区见哈。
最终我们得到了最重要的第5个公式的变形,即红色箭头后面的:
mod n m。
其中有几个关系,需要搞明白,m 与 n 互为质数,φn = x,d 是e相对于x的模反元素。
有没有看到一些加解密的雏形。
从 m 到 m。 这中间涵盖了从加密到解密的整个过程,但是缺少了我们想要的密文整个过程。
OK,下面引入本文的第四个数学公式:
我们来看一下整个交换流程:
1、客户端有一个数字13,服务端有一个数字15;
2、客户端通过计算 3的13次方 对 17 取余,得到数字12; 将12发送给服务端;同时服务端通过计算3的15次方,对17取余,得到数字6,将6发送给客户端。至此,整个交换过程完成。
3、服务端收到数字12以后,继续计算,12的15次方 对 17取余,得到 数字10。
4、客户端收到数字 6以后,继续计算,6的13次方 对 17 取余,得到数字 10。
有没有发现双方,最终得到了相同的内容10。但是这个数字10从来没有在网络过程中出现过。
好,讲到这里,可能有些人已经恍然大悟,这就是加密过程了,但是也有人会产生疑问,为什么要取数字3 和 17 呢,这里还牵涉到另一个数学知识,原根的问题。即3是17的原根。看图
有没有发现规律,3的1~16次方,对17取余,得到的整数是从1~16。这时我们称3为17的原根。也就是说上面的计算过程中有一组原根的关系。这是最早的迪菲赫尔曼秘钥交换算法。
解决了为什么取3和17的问题后,下面继续来看最终的RSA是如何产生的:
还记得我们上面提到的欧拉定理吗,其中 m 与 n 互为质数,n为质数,d 是 e 相对于 φn的模反元素。
当迪菲赫尔曼密钥交换算法碰上欧拉定理会产生什么呢?
我们得到下面的推论:
好,到这里我们是不是已经看到了整个的加密和解密过程了。
其中 m 是明文;c 是密文; n 和 e 为公钥;d 和 n 为私钥 。
其中几组数字的关系一定要明确:
1、d是e 相对于 φn 的模反元素,φn = n-1,即 e * d mod n = 1.
2、m 小于 n,上面在讲迪菲赫尔曼密钥交换算法时,提到原根的问题,在RSA加密算法中,对m和n并没有原根条件的约束。只要满足m与n互为质数,n为质数,且m n就可以了。
OK,上面就是RSA加密算法的原理了,经过上面几个数学公式的狂轰乱炸,是不是有点迷乱了,给大家一些时间理一下,后面会和大家一起来验证RSA算法以及RSA为什么安全。
随着社会的发展,产品的更新速度也是越来越快,算法是方案的核心,保护开发者和消费者的权益刻不容缓,那么加密芯片在其中就扮演了重要的角色,如何选择加密芯片呢?
1.市面上加密芯片种类繁多,算法多种,加密芯片强度参差不齐,加密性能与算法、秘钥密切相关。常见的加密算法有对称算法,非对称算法,国密算法,大部分都是基于I2C、SPI或1-wire协议进行通信。加密芯片还是需要项目实际需求选择,比如对称加密算法的特点是计算量小、加密速度快、加密效率高等。
2.因为单片机软加密性能较弱且非常容易被复制,所以有了加密芯片的产生,大大增加了破解难度和生产成本。目前加密芯片广泛应用于车载电子、消费电子、美容医疗、工业控制、AI智能等行业。
3.韩国KEROS加密芯片专注加密领域十多年,高安全性、低成本,在加密保护领域受到了众多客户的高度赞扬及认可。KEROS采用先进的内置aes256安全引擎和加密功能,通过真动态数据交互并为系统中敏感信息的存储提供了安全的场所,有了它的保护电路,即使受到攻击,这些信息也可以保持安全。其封装SOP8,SOT23-6,TDFN-6集成I2C与1-wire协议满足不同应用需求。CK02AT、CK22AT、CK02AP、CK22AP支持1.8V-3.6V,256bit位秘钥长度,5bytes SN序列号,支持定制化免烧录,加密行业首选。关于rsa加密怎么实现的介绍到此就结束了,感谢大家耐心阅读。
本文标签:rsa加密怎么实现