文章目录文章目录文章目录前言💞💞💞背景💖💖💖一、RSA算法描述1️⃣密钥计算方法🌺2️⃣加密方法🚤3️⃣解密方法🌸二、算法举例1️⃣密钥计算🚩2️⃣加密运算🍁3️⃣加密运算🧐三、算法实现1️⃣RSA算法流程图2️⃣代码实现总结🌺🌺🌺前言💞💞💞安全算法：公开密钥加密之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 2.对每个数据块 P，计算 C= P^(mod n),C 即为P的密文。 加密 C = P^e (mod n)3️⃣解密方法🌸对每个密文块 C，计算 P=C^d(mod n),P即为明文 解密： P = c^d (mod n)二、算法举例1️⃣密钥计算🚩 代码如下（示例）：1.假设需要加密的明文信息为m=85，选择：e=7，p=11，q=13，说明使用RSA算法的加密和解密(计算密文并还原) 代码语言：javascript复制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=1032️⃣加密运算🍁 （示例）： 代码语言：javascript复制公钥:(e,n)=(7,143) 密文c=p^e (mod n)=1233️⃣加密运算🧐 代码如下（示例）： 代码语言：javascript复制密钥:(d,n)=(103,143) 明文：P=c^d (mod n)=85三、算法实现1️⃣RSA算法流程图2️⃣代码实现 代码如下（示例）：上题中的数据 编译软件：dev c++ 代码语言：javascript复制#include #include /* 函数申明 */ 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 概念➕计算题➕代码实现