公钥加密 RSA 算法 [概念 + 计算 + 代码实现
文章目录
文章目录
- 文章目录
- 前言????????????
- 背景????????????
- 一、RSA算法描述
- 1️⃣密钥计算方法????
- 2️⃣加密方法????
- 3️⃣解密方法????
- 二、算法举例
- 1️⃣密钥计算????
- 2️⃣加密运算????
- 3️⃣加密运算????
- 三、算法实现
- 1️⃣RSA算法流程图
- 2️⃣代码实现
- 总结????????????
????推荐阅读:http://t.****.cn/nQfIY????
前言????????????
安全算法:公开密钥加密之RSA算法
公开密钥加密(又称“非对称加密”)是加密和解密使用不同密钥的一种加密方法。包括公开密钥和私有密钥(成对生成的,网上有工具网站)。
公开密钥(public key,后面简称P):加密用的密钥
私有密钥(secret key,后面简称S):解密用的密钥
背景????????????
RSA公钥加密算法是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。1987年首次公布,当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
RSA是目前最有影响力的公钥加密算法,它能够抵抗到目前为止已知的绝大多数密码攻击,已被ISO推荐为公钥数据加密标准。
今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长,用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天,RSA加密安全性受到了挑战。
RSA算法基于一个十分简单的数论事实:将两个大质数相乘十分容易,但是想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥。
RSA算法是现今使用最广泛的公钥密码算法,也是号称地球上最安全的加密算法。在了解RSA算法之前,先熟悉下几个术语
根据密钥的使用方法,可以将密码分为对称密码和公钥密码
????对称密码:加密和解密使用同一种密钥的方式
????公钥密码:加密和解密使用不同的密码的方式,因此公钥密码通常也称为非对称密码。
一、RSA算法描述
1️⃣密钥计算方法????
1.选择两个大素数p和q(典型值为1024位)
2.计算n=p×q
和z=(p-1)×(q-1)
// n表示欧拉函数
3.选择一个与z互质的数,令其为d
4.找到一个 e 使满足exd= 1 (mod z)
5.公开密钥为(e,m)
,私有密钥为(d,m)
2️⃣加密方法????
1.将明文看成比特串,将明文划分成k位的块 P 即可,这里k是满足 2*k<n 的最大整数。
2.对每个数据块 P,计算 C= P^(mod n),C 即为P的密文。
加密
C
=
P
e
(
m
o
d
n
)
C = P^e (mod n)
C=Pe(modn)
3️⃣解密方法????
对每个密文块 C,计算 P=C^d(mod n),P即为明文
解密:
P
=
c
d
(
m
o
d
n
)
P = c^d (mod n)
P=cd(modn)
二、算法举例
1️⃣密钥计算????
代码如下(示例):1.假设需要加密的明文信息为m=85,选择:e=7,p=11,q=13,说明使用RSA算法的加密和解密(计算密文并还原)
n=p*q=11*13=143
z=(p-1)*(q-1)=10*12=120
e*d=1(mod z)
7 * d( mod 120)=1 -------d=103
2️⃣加密运算????
(示例):
公钥:(e,n)=(7,143)
密文c=p^e (mod n)=123
3️⃣加密运算????
代码如下(示例):
密钥:(d,n)=(103,143)
明文:P=c^d (mod n)=85
三、算法实现
1️⃣RSA算法流程图
2️⃣代码实现
代码如下(示例):上题中的数据
编译软件:dev c++
#include<stdio.h>
#include<stdlib.h>
/* 函数申明 */
int long_n(int n);
int shuru(char *arr, int k, char *wei, int is_first);
void jiami(char *arr, int k, int e, int n);
/* 输入函数,记录从键盘输入的明文*/
int shuru(char *arr, int k, char *wei, int is_first)
{
int i;
char ch;
/*判断是否为第一分组的输入,如果是则获取输入的字符,否则就将上一分组最后获取的字符作为这一分组的第一个字符*/
if (is_first == 1)
ch = getchar();
else
ch = *wei;
for (i = 0; (i < k) && (ch != '\n');i++) //获取字符直到获取到回车符为止
{
arr[i] = ch;
ch = getchar();
}
*wei = ch; //最后获取到的字符准备作为下一分组的第一个字符
for (i = i; i < k; i++)
arr[i] = 'a'; //输入不够一组个数的整数倍则补'a'(即为补零)
if (ch == '\n') //接收到回车符返回0,否则为1
return 0;
else
return 1;
}
/*加密函数*/
void jiami(char *arr, int k, int e, int n)
{
int m = 0,c=1, i, j,t=0, shu,temp,num=0;
int *array;
/*Mi赋值过程*/
for (i = 0; i < k; i++)
{
temp = 1;
for (j = 0; j < (k-i-1)*2; j++)
temp = temp * 10;
shu = (int)arr[i] - 97;
m = m + temp * shu;
}
temp = e;
/*获取e的二进制表达形式的位数*/
do{
temp = temp / 2;
num++;
} while (temp != 0);
array = (int *)malloc(sizeof(int)*k); //申请动态数组
temp = e;
/*动态数组存储e的二进制表达形式*/
for (i = 0; i < num; i++)
{
array[i] = temp % 2;
temp = temp / 2;
}
/*避免出现天文数字的算法,详情见上文文字说明*/
for (i = num - 1; i >= 0; i--)
{
t = t * 2;
temp = c*c;
if (temp > n)
{
for (j = 0; temp - n*j >= 0; j++);
j--;
c = temp - n*j;
}
else
c = temp;
if (array[i] == 1)
{
t = t + 1;
temp = c*m;
if (temp > n)
{
for (j = 0; temp - n*j >= 0; j++);
j--;
c = temp - n*j;
}
else
c = temp;
}
e = e / 2;
}
temp = c;
i = 0;
/*c的位数小于分组长度则在前补零*/
do{
temp = temp / 10;
i++;
} while (temp != 0);
for (i; i < num; i++)
printf("0");
printf("%d", c);
}
/*获取分组的长度*/
int long_n(int n)
{
int temp,i,j,k,shi,comp=0;
temp = n;
/*获取n的位数*/
for (i = 1; temp / 10 != 0; i++)
{
temp = temp / 10;
}
temp = i;
/*若n的位数为基数*/
if (i % 2 != 0)
{
i = i - 1;
return i;
}
/*若位数为偶数*/
else
{
for (j = 0; j < i/2; j++)
{
shi = 1;
for (k = 0; k < temp - 2; k++)
shi = shi * 10;
comp = comp + shi * 25;
temp = temp - 2;
}
if (comp <= n)
return i;
else
{
i = i - 2;
return i;
}
}
}
/*主函数*/
int main()
{
int p, q, e, d, n, fai_n, k, i,is_first=1;
char ch,*arr,wei='a';
printf("请输入p、q、e值,用空格间隔开\n");
scanf("%d%d%d", &p, &q, &e); //从键盘获取p、q、e值
n = p*q;
fai_n = (p-1)*(q-1); //Φ(n)
for (k = 0; (k*n + 1) % e != 0; k++);
if ((k*n + 1) % e == 0)
d = (k*n + 1) / e; //d * e ≡ 1 (mod Φ(n))
k = long_n(n);
k = k / 2; //分组的长度
ch = getchar(); //缓冲回车符
arr = (char *)malloc(sizeof(char)*k); //申请动态数组
printf("请输入明文\n");
while (1)
{
i=shuru(arr,k,&wei,is_first); //调用输入字符的函数,接收到回车符返回0,否则为1
is_first = 0; //第一分组录入结束设为0
jiami(arr,k,e,n); //调用加密函数
if (i == 0) //接收到返回值为0跳出循环
break;
}
printf("\n");
return 0;
}
运行结果如下(示例):
总结????????????
以上就是今天笔记,本文仅仅简单介绍了RSA 概念➕计算题➕代码实现
推荐阅读
-
基于 Java 语言的国密 SM2/SM3/SM4 算法库,包括加密/解密、签名/校验、摘要计算的实现代码和测试方法。
-
什么是 PKI、KDC、DH、RSA - 公钥加密算法
-
了解公钥和私钥 - 公钥加密算法又称非对称加密算法,使用不同的密码进行加密和解密,其中一个用于公钥,另一个用于私钥: 公钥和私钥成对使用 公钥称为公钥,私钥称为私钥。 用公钥加密的数据只能用相应的私钥解密 用私钥加密的数据只能用相应的公钥解密。 如果数据可以用公钥解密,则必须用相应的私钥加密。 如果数据可以用私钥解密,则必须用相应的公钥加密。 公钥和私钥是相对的,没有规定哪一个必须是公钥或私钥。 第二,实现数据的安全传输 要实现数据的安全传输,当然要对数据进行加密。 如果使用对称加密算法,加密和解密使用同一个密钥,除了自己要保存外,对方也必须知道密钥才能解密数据。如果把密钥传给对方,就有可能泄露密码。所以我们使用非对称算法,过程如下: 首先,接收方生成一对密钥,即私钥和公钥; 然后,接收方将公钥发送给发送方; 发送方用收到的公开密钥加密数据并发送给接收方; 接收方收到数据后使用自己的私钥解密。 由于在非对称算法中,用公钥加密的数据必须用相应的私钥解密,而私钥只有接收方知道,这就确保了数据传输的安全性。 第三,信息的数字签名 除了确保数据的安全传输,公钥系统的另一个用途是对数据进行签名。通常,"数字签名 "用于验证发送者的身份,帮助保护数据的完整性。 例如,发送者 A 想向所有人发送一些信息,他用自己的私人密钥对信息进行了加密,即签名。这样,每个收到数据的人都能用发送者的公开密钥验证数据,并确认数据是由 A 发送的(因为只有 A 用他的私人密钥签署了数据,所以无法验证发送者的身份)。(因为只有用 A 的私钥签名的信息才能用公钥解密)。使用数字签名可以确认两件事: 保证信息是由签名者本人签名发送的,签名者无法否认或难以否认。 保证信息从发出到收到都没有被以任何方式修改过。 之所以能确认这两点,是因为公钥的解密必然要有相应的私钥加密,而私钥只有签名者持有。 四、公钥算法的缺陷 在现实中,公钥机制也有其缺点,那就是效率很低,比常用的私钥算法(如 DES 和 AES)慢上一两个数量级都有可能。因此,它不适合对大量原始信息进行加密。为了兼顾安全性和效率,我们通常会将公钥算法和私钥算法结合起来使用: 首先,发送方使用对称算法加密原始信息。 接收方使用公钥机制生成一对密钥,一个是公钥,一个是私钥。 接收方将公钥发送给发送方。 发送方用公钥加密对称算法的密钥,然后发送给接收方。 接收方用私人密钥解密对称算法的密钥。 发送方将加密后的原始信息发送给接收方。 接收方使用对称算法的密钥解密信息。 摘要
-
RSA 算法计算公钥
-
公钥加密 RSA 算法 [概念 + 计算 + 代码实现
-
C 语言和加密算法的实现:RSA、AES、ECC 及其他公钥和对称加密算法详解 (II) - II、AES 对称加密算法详解和 C 语言实现
-
C 语言和加密算法的实现:详细介绍 RSA、AES、ECC 及其他公钥和对称加密算法 (III)
-
ssh工作流程及原理-SSH(Secure Shell Protocol,安全的壳程序协议),它可以通过数据包加密技术将等待传输的数据包加密后再传输到网络上。ssh协议本身提供两个服务器功能:一个是类似telnet的远程连接使用shell的服务器;另一个就是类似ftp服务的sftp-server,提供更安全的ftp服务。 连接加密技术简介 目前常见的网络数据包加密技术通常是通过“非对称密钥系统”来处理的。主要通过两把不一样的公钥与私钥来进行加密与解密的过程。 公钥(public key):提供给远程主机进行数据加密的行为,所有人都可获得你的公钥来将数据加密。 私钥(private key):远程主机使用你的公钥加密的数据,在本地端就能够使用私钥来进行解密。私钥只有自己拥有。 SSH工作过程:在整个通讯过程中,为实现SSH的安全连接,服务端与客户端要经历如下五个阶段: 版本号协商阶段 SSH目前包括SSH1和SSH2两个版本,双方通过版本协商确定使用的版本 密钥和算法协商阶段 SSH支持多种加密算法,双方根据本端和对端支持的算法,协商出最终使用的算法 认证阶段 SSH客户端向服务器端发起认证请求,服务器端对客户端进行认证 会话请求阶段 认证通过后,客户端向服务器端发送会话请求 交互会话阶段 会话请求通过后,服务器端和客户端进行信息的交互 一、版本协商阶段 服务器端打开端口22,等待客户端连接; 客户端向服务器端发起TCP初始连接请求,TCP连接建立后,服务器向客户端发送第一个报文,包括版本标志字符串,格式为“SSH-<主协议版本号>.<次协议版本号>.<软件版本号>”,协议版本号由主版本号和次版本号组成,软件版本号主要是为调试使用。 客户端收到报文后,解析该数据包,如果服务器的协议版本号比自己的低,且客户端能支持服务器端的低版本,就使用服务器端的低版本协议号,否则使用自己的协议版本号。 客户端回应服务器一个报文,包含了客户端决定使用的协议版本号。服务器比较客户端发来的版本号,决定是否能同客户端一起工作。如果协商成功,则进入密钥和算法协商阶段,否则服务器断开TCP连接。 说明:上述报文都是采用明文方式传输。 二、密钥和算法协商阶段 服务器端和客户端分别发送算法协商报文给对端,报文中包含自己支持的公钥算法列表、加密算法列表、MAC(Message Authentication Code,消息验证码)算法列表、压缩算法列表等等。 服务器端和客户端根据对端和本端支持的算法列表得出最终使用的算法。 服务器端和客户端利用DH交换(Diffie-Hellman Exchange)算法、主机密钥对等参数,生成会话密钥和会话ID。 由此,服务器端和客户端就取得了相同的会话密钥和会话ID。对于后续传输的数据,两端都会使用会话密钥进行加密和解密,保证了数据传送的安全。在认证阶段,两端会使用会话用于认证过程。 会话密钥的生成: 客户端需要使用适当的客户端程序来请求连接服务器,服务器将服务器的公钥发送给客户端。(服务器的公钥产生过程:服务器每次启动sshd服务时,该服务会主动去找/etc/ssh/ssh_host*文件,若系统刚装完,由于没有这些公钥文件,因此sshd会主动去计算出这些需要的公钥文件,同时也会计算出服务器自己所需要的私钥文件。) 服务器生成会话ID,并将会话ID发给客户端。 若客户端第一次连接到此服务器,则会将服务器的公钥数据记录到客户端的用户主目录内的~/.ssh/known_hosts。若是已经记录过该服务器的公钥数据,则客户端会去比对此次接收到的与之前的记录是否有差异。客户端生成会话密钥,并用服务器的公钥加密后,发送给服务器。 ****服务器用自己的私钥将收到的数据解密,获得会话密钥。 服务器和客户端都知道了会话密钥,以后的传输都将被会话密钥加密。 三、认证阶段 SSH提供两种认证方法: 基于口令的认证(password认证):客户端向服务器发出password认证请求,将用户名和密码加密后发送给服务器,服务器将该信息解密后得到用户名和密码的明文,与设备上保存的用户名和密码进行比较,并返回认证成功或失败消息。 基于密钥的认证(publickey认证):客户端产生一对公共密钥,将公钥保存到将要登录的服务器上的那个账号的家目录的.ssh/authorized_keys文件中。认证阶段:客户端首先将公钥传给服务器端。服务器端收到公钥后会与本地该账号家目录下的authorized_keys中的公钥进行对比,如果不相同,则认证失败;否则服务端生成一段随机字符串,并先后用客户端公钥和会话密钥对其加密,发送给客户端。客户端收到后将解密后的随机字符串用会话密钥发送给服务器。如果发回的字符串与服务器端之前生成的一样,则认证通过,否则,认证失败。 注:服务器端对客户端进行认证,如果认证失败,则向客户端发送认证失败消息,其中包含可以再次认证的方法列表。客户端从认证方法列表中选取一种认证方法再次进行认证,该过程反复进行。直到认证成功或者认证次数达到上限,服务器关闭连接为止。实例
-
在C#中实现RSA算法并讲解如何将XML格式的公钥转换成PEM格式以便于Objective-C应用使用
-
.NET中的MD5加密和解密代码 - MD5的简要介绍: MD5是一种将大量信息在使用数字签名软件签署私钥之前进行“压缩”的保密格式转换方法。无论是MD4还是MD5,它们都需要获取一段随机长度的信息,并生成一个128位的信息摘要。 尽管这些算法在结构上略有不同,但MD2的设计与MD4和MD5完全不同,这是因为MD2是为了8位机器进行优化设计的,而MD4和MD5则是面向32位计算机的。这三个算法的详细描述和C语言源代码可以在Internet RFCs 1321中找到,这是最权威的文档,由Ronald L. Rivest于1992年8月提交给IETF。 以下是相关的代码实现: