灰度矩阵
MATLAB-RSA加密算法及其MATLAB实现版权声明：本⽂为博主原创⽂章，未经博主允许不得转载。 blog.csdn/baidu_35692628/article/details/77679381
序⾔
之前对RSA加密算法做过⼀些调研，并⽤MATLAB实现，这⾥做⼀个总结。
1. 对称加密和⾮对称加密
根据密钥的使⽤⽅法，可以将加密⽅法分为对称加密和⾮对称加密
对称加密：加密和解密使⽤同⼀种密钥的⽅法（使⽤⽤户名和密码）。密码称为对称密码。
⾮对称加密：加密和解密使⽤不同的密码。密码称为公钥密码。 RSA（三个创始⼈姓⽒开头字母）是⽬前使⽤最⼴泛的⾮对称加密算法。
2. 公钥和私钥
公钥与私钥：两者的关系如下
两者彼此配对，分别唯⼀。
公钥与密⽂⼀起公开，私钥则由个⼈保管。
公钥加密的密⽂只能⽤与其唯⼀配对的私钥才能解开，反之亦然。
加解密时的密钥使⽤：
⾸先记住，每个通信⽅都有⾃⼰的⼀对唯⼀配对的公钥和私钥，⽐如甲有甲⾃⼰的公钥和私钥，⼄有⼄⾃⼰的公钥和私钥。除了⾃⼰，别⼈只能获得“公钥 + 加密后的密⽂”。
我们将通信过程分为两种应⽤场景：⽂件加解密和签名加解密，如下图所⽰
发送加解密（⽐如邮件通信）：
⼄使⽤甲的公钥对邮件进⾏加密，甲接收到之后使⽤⾃⼰的私钥进⾏解密。
甲使⽤⼄的公钥对邮件进⾏加密，⼄接收到之后使⽤⾃⼰的私钥进⾏解密。
签名加解密（⽐如⽂件发送）：ktv点歌台
⼄使⽤⾃⼰的私钥进⾏签名，甲接收到⽂件后使⽤⼄提供的公钥进⾏验证。
甲使⽤⾃⼰的私钥进⾏签名，⼄接受到⽂件后使⽤甲提供的公钥进⾏验证。
整个通信过程，除了⾃⼰，对⽅并不知道⾃⼰的私钥。
3. RSA加密算法的基本原理
模数N的获取：1024bit⼤数。选取两个不同的⼤素数p，q
欧拉函数值φ(n)的获取：
选择⼩质数e作为公钥指数：
16bit⼩数
满⾜下式即可，⼀般取e = 65537
gcd(e , φ(n)) = 1 即 e与φ(n)互质耳机防尘塞
计算私钥指数d：
1024bit⼤数
通过同余⽅程计算私钥指数d（e的模反元素）
同余⽅程中e与φ(n)互质则有且只有⼀个解
密⽂的计算：假设A（A < N）为明⽂，B为密⽂
明⽂的获取：
4. RSA加密算法分析
安全性：
由上述过程我们可以看出，e和d形成⾮对称密钥关系，加密者使⽤e加密，解密者使⽤d解密，第三者拦截了密⽂B、公钥e和⼤素数N，在不知道p和q的前提下，⽆法推算出d，也就⽆法获得明⽂A。
⽽且获取最困难的在于⼤数N分解，当N取⾮常⼤的值时，将其分解成p*q是异常困难的，⽬前所能分解的最⾼⼆进制位数是 768bit，当选取N为1024bit甚⾄2048bit时已经⾜够安全。
RSA加密算法的缺陷
虽然RSA的安全性依赖于⼤数的因⼦分解，但并没有从理论上证明破译RSA的难度与⼤数分解难度等价。即RSA的重⼤缺陷是⽆法从理论上把握它的保密性能如何。
产⽣密钥很⿇烦，受到素数产⽣技术的限制，因⽽难以做到⼀次⼀密。
分组长度太⼤，为保证安全性，N⾄少也要600bits以上，使运算代价很⾼，尤其是速度较慢，较对称密码算法慢⼏个数量级；且随着⼤数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。因此，使⽤RSA只能加密少量数据，⼤量的数据加密还要靠对称密码算法。 算法要解决的主要问题：RSA密钥的选取和加解密过程都⾮常简洁，在算法上需要实现四个问题
[1] 如何处理⼤数运算，包括加减乘和求模运算。其中最复杂的是求模运算。
[2] 如何求解同余⽅程。
[3] 如何快速进⾏模乘运算。
[4] 如何获取⼤素数计算N。
这些问题往往不是相互独⽴的，⽽是相互关联相互嵌套的。
5. RSA加密算法实现的核⼼问题
[1] ⼤数表⽰和存储
各个参数的⼤⼩：
⼀般情况公钥指数e是固定的为65537(3字节)，32进制表⽰时长度为1
私钥指数d和模数N均为1024bit(128字节)，32进制的长度为32（1024 = 32 × 32）
为何采⽤R(2^32进制)：
⽬前主流的RSA算法都建⽴在1024位的⼤数运算之上，⽽⼤多数的编译器都只能单次⽀持到64位的整数运算，也就是说在
运算中所使⽤的整数必须不⼤于64位。
⼤数不论是⽤⼗进制数组进⾏处理还是⼆进制进⾏处理效率都⽐较低，因为需要多次循环还需要额外的空间存放计算的进退位
标志及中间结果。
所以采⽤R进制(R=2^32)进⾏改进，此时1024位⼤数就变成了⼀个含有32个元素的R进制数组，针对数组进⾏各种运算所
需的循环规模⾄多32次。
[2] 模幂/模乘运算
RSA的核⼼算法：
RSA的核⼼算法是模幂运算，然⽽模幂运算⼜是多次模乘运算的循环，模乘运算中由于求模运算的复
杂性，即单次求模运算实际上包含了多次加法、减法和乘法运算，所以算法的效率提升主要关注如何简化求模运算过程。
模幂运算转换为模乘运算：以⼆进制为例
1. 求模运算转换为模乘运算
B = A ^ e % N，如果先计算出幂的结果再对最后的结果求模，这样的幂值很⼤，占⽤⼤量的存储空间，实现起来有些困难。
所以在硬件实现中，普遍使⽤改变e的表⽰形式，变成⼆进制机器码，并进⾏逐位扫描，实质上是将⼤数e变成0、1⽐特串，将模幂转换成 A^0 % N ，A^1 % N的操作。
例：求 D = C^15 % N 的模幂运算根据求模运算法分解为 6 个模乘运算，归纳分析发现都可以采⽤算法计算⼀般情况 D=C^E % N
D = 1
While E >= 0
if E%2 = 0
C = C*C % N
E = E/2
else
D = D*C % N
E = E – 1
return D
继续分析发现，要知道 E 何时能整除 2 ，并不需要反复进⾏减⼀或者除⼆操作，只需要验证 E 的⼆进制各位是 0 还是 1 就可以了，从左⾄右或从右⾄左都可以，从左⾄右更简洁，那么对于
2. 模幂运算转换为模乘运算
根据上式，则有
D = 1
for i = n to 0 //(⾼位到低位L-R的扫描，也可采⽤低位到⾼位R-L的扫描⽅式)
D = D*D % N
if E(i) = 1
D = D*C % N
800导航return D
这样就将模幂运算[幂次再求模]转换成了⼀系列的模乘运算[相乘再求模]。
[3] Montgomery约减表达式简化求模运算
蒙哥马利约减表达式：Montgomery约减表达式如下
其中S表⽰被约数，M表⽰模数，分别对应为明⽂A和模数N，S + q*M实际表⽰模M的S所在的剩余类的所有数。
所以想求 S*R^(-1) % M 的值可以⽤ Mon % M 来计算。
到 q 使得 S + q*M 是 R 的倍数，被除数就是整数了，这就是Montgomery约减表达式简化求模运算的原理。
蒙哥马利算法的核⼼思想：
道闸广告机在于将求A*B % N转化为不需要反复求模的A*B*R’% N，其中R’= R^(-n)，即只需要移动n位即可。
1. 进制转换
将求 A*B % N 转化为不需要反复求模的 A*B*R’% N，其中 R 表⽰进制。
如果利⽤⼆进制算法求 1024 位的 A*B*R’ % N，需要循环 1024 次之多。
考虑将 A 表⽰为任意的 R 进制如下，R = 0x100000000 = 2^32，此时每次移 32 位。
2. 求近似值：
我们需要得到的蒙哥马利乘积为 C’ = A*B*R’ % N，则以下求模算法只能得出C’的近似值
C’ = 0
for i = from 0 to k
C’ = C’ + A*B
C’ = C’/r
if C’ >= N
C’ = C’ – N
return C’
3. 利⽤蒙哥马利约减表达式修正算法：
因为在循环中每次C’ = C’/r时都可能有余数被舍弃，因此利⽤Montgomery约减表达式引⼊系数 q 使得 (C’ + A*B + q*N) % r = 0 将算法修改为
C’ = 0
for i = from 0 to k
C’ = C’ + A*B + q*N
C’ = C’/r
if C’ >= N
电动车电池制作C’ = C’ – N
return C’
这样的话最终的返回值就是 A*B*R’ % N 的精确值，求系数q的过程在这⾥省略。若令 R = 2^32，这样得出的Montgomery算法，循环次数将不⼤于32，整个运算过程中最⼤的中间变量C’ = (C’ + A*B + q*N) < 2*r*N < 1057位，算法效率就相当⾼了。
6. RSA加密算法主要模块的MATLAB代码实现
[1] RSA⼤数运算模块
⼤数运算的加减乘运算和⼆进制的加减乘运算有直接的相似，设置中间变量存储中间结果，设置进位或借位参与运算。
⽐较⼤数除法，由于⽆法将两个数试商，只能将被除数和除数划分为R进制元素计算近似值，通过Montgomery模乘修正算法实现。
⼤数乘法的硬件实现：将两个1024bit的乘数扩展为1026bit分成38组，每组27bit进⾏38个并⾏DSP流⽔复⽤。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议