RSA

华中科技大学密码学课程设计报告

[三、RSA的快速实现]

专业班级：[信息安全0903] 学生姓名：[曹晨业] 指导教师：[崔国华] 完成时间：2013年4月5日

RSA算法简介：

RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。

RSA公开密钥密码体制。所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。 在公开密钥密码体制中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然秘密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK。正是基于这种理论，1978年出现了著名的RSA算法，它通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要。 RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在的三十多年里，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。 RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。

RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要 600bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(Secure Electronic Transaction)协议中要求CA采用2048bits长的密钥，其他实体使用1024比特的密钥。C)RSA密钥长度随着保密级别提高，增加很快。

实验目的：

通过实际编程加深对RSA算法加密、脱密和密钥产生过程的理解。

实验原理：

1.大数存储和四则运算

根据RSA算法的要求，为了实现大数的各种复杂运算，需要首先实现大数存储和基本四则运算的功能。当今开源的大数运算C++类有很多，多用于数学分析、天文计算等，本文选用了一个流行的大数类型，并针对RSA算法和本项目的具体需要对其进行了扩充和改进。下面简单介绍大数存储和四则运算的实现原理。

最先完成的功能是大数的存储，存储功能由flex_unit类提供。和普通的类型一样，每一个大数对应一个flex_unit的实例。类flex_unit中，用一个无符号整数指针unsigned * a指向一块内存空间的首地址，这块内存空间用来存储一个大数，所以可以说，大数是被存储在一个以unsigned为单元的线性组中。在方法void reserve( unsigned x )中通过C++的new来给a开辟空间，当flex_unit的实例中被存入比当前存储的数更大的数时，就会调用

reserve来增加存储空间，但是当flex_unit的实例中被存入比当前存储的数更小的数时，存储空间并不会自动紧缩，这是为了在运算的时候提高执行效率。结合指针a，有两个重要的无符号整数来控制存储，unsigned z和unsigned n，z是被分配空间的单元数，随数字变大不断增大，不会自己紧缩，而n是当前存储的大数所占的单元数，组成一个大数的各unsigned单元的存入和读出由set、get方法完成，变量n是只读的。类型unsigned在32位机是32位的，所以对于flex_unit这个大数类来说，每个大数最大可以达到 个字节长，这已经超过了32位机通常的最大内存容量，所以是足够进行RSA所需要的各种运算的。图3-2形象的说明了大数存储类flex_unit对大数的管理。

开辟了z个单元大的内存 内存空间 大数占n个单元 *a unsigned类型的指针

图3-2 flex_unit对大数的管理

在flex_unit的存储功能基础上，将其派生，得到vlong_value，在vlong_value中实现四则运算函数，并实现强制转换运算符unsigned，以方便大数类型和普通整数的互相赋值。当大数被强制转换为unsigned时，将取其最低四字节的值。四则运算实现的原理十分简单，都是按最基本的算术原理实现的，四则运算过程的本质就是按一定数制对数字的计算，比如相加，就是低位单元对齐，逐单元相加并进位，减法同理。而乘除法和取余也都是按照竖式运算的原理实现，并进行了必要的优化。虽然实现了四则运算函数，但是若是程序里的运算都要调用函数，显得烦琐而且看起来不美观，所以我们另写一个类vlong，关联(Associate，即使用vlong_value类型的对象或其指针作为成员)vlong_value，在vlong重载运算符。这样，当我们操作vlong大数对象的时候，就可以像使用一个简单类型一样使用各种运算符号了。之所以将vlong_value的指针作为成员而不是直接构造的对象，也是为了提高执行效率，因为大型对象的拷贝要消耗不少机器时间。

2.大数幂模与乘模运算Montgomery幂模算法

在实现了vlong类型后，大数的存储和四则运算的功能都完成了。考虑到RSA算法需要进行幂模运算，需要准备实现这些运算的方法。所以写一个vlong的友元，完成幂模运算功能。幂模运算是RSA 算法中比重最大的计算，最直接地决定了RSA 算法的性能，针对快速幂模运算这一课题，西方现代数学家提出了很多的解决方案。经查阅相关数学著作，发现通常都是依据乘模的性质

(a?b)modn?((amodn)?(bmodn))modn，先将幂模运算化简为乘模运算。

通常的分解习惯是指数不断的对半分，如果指数是奇数，就先减去一变成偶数，然后再对半分，例如求D=CE算。

C1?C?Cmodn?C2modn，E=15，可分解为如下6个乘模运

modn6

C2?C1?Cmodn?Cmodn3

C3?C2?C2modn?CC5?C4?C4modn?CmodnmodnC4?C3?Cmodn?C7modnmodn

归纳分析以上方法，对于任意指数E，可采用如图3-3的算法流程计算 。

开始 D=1;P=C mod n 14C6?C5?Cmodn?C15No E>0? Yes E为奇数? No Yes D?(D?P)modn E=E-1 E为偶数? Yes No P?(P?P)modn E=E/2 Result=D 结束

图3-3 幂模运算分解为乘模运算的一种流程

按照上述流程，列举两个简单的幂模运算实例来形象的说明这种方法。 ① 求215开始 15

E奇数 (E-1)/2 =7

D = DP mod n = 2

P = PP mod n = 4

E =

mod17的值

P = 2 mod 17 = 2

E =

D = 1

E奇数 D = DP mod n = 8 (E-1)/2 =3

E奇数 D = DP mod n = 9 (E-1)/2 =1

E奇数 D = DP mod n = 9 (E-1)/2 =0

最终D = 9 即为所求。

② 求28开始 8

mod13P = PP mod n = 16 P = PP mod n = 1 P = PP mod n = 1

E = E = E =

的值

P = 2 mod 17 = 2

E =

D = 1

E偶数 D = 1 P = PP mod n = 4 E =

E/2 =4

E偶数 D = 1 P = PP mod n = 3 E = E/2 =2

E偶数 D = 1 P = PP mod n = 9 E = E/2 =1

E奇数 D = DP mod n = 9 P = 不需要计算 E = (E-1)/2 =0

最终D = 9 即为所求。 观察上述算法，发现E根据奇偶除以二或减一除以二实际就是二进制的移位操作，所以要知道需要如何乘模变量，并不需要反复对E 进行除以二或减一除以二的操作，只需要验证E 的二进制各位是0 还是1 就可以了。同样是计算D?CEmodn，下面给出从右到左扫描二进制位进行的幂模算法描述，设

中间变量D,P,E的二进制各位下标从左到右为u,u-1,u-2,?,0。

Powmod(C,E,n) {

D=1;

P=C mod n;

for i=0 to u do {

if(Ei=1)D=D*P(mod n); P=P*P(mod n); } return D; }

选择与模数n互素的基数R=2k，n满足2k－1≤n<2k， n应为奇数。并且选择R-1及n’，满足0< R-1

M(m) {

??(mmodR)n'modR;0???Rt?(m??n)/R

本文来源：https://www.bwwdw.com/article/qsq2.html