rsa公钥加密算法的设计与实现本科毕业论文(编辑修改稿)

rsa公钥加密算法的设计与实现本科毕业论文(编辑修改稿)内容摘要：

RSA 密码体制 公钥密码体制的一个想法就是：也许能找到一个密码体制，使得由给定的ek 来求 dk 是计算上不可行的。 如果这样的话，加密规则 ek 是一个公钥，可以在一个目录中公布（这也就是公钥体制名称的由来）。 (7) RSA 公钥密码体制的具体描述如下。 (4) 中山大学本科生毕业论文 7 （ 1）密钥生成 选择两个随机大素数 p 和 q，并计算 n pq 和 ( ) ( 1)( 1)n p q   。 选择一个随机数 e ， 1 ( )en ，满足 gcd( , ( )) 1en  ，并计算 1 m od( ( ))d e n。 公钥为 (, )en ，私钥为 d。 （ 2）加密 对明文 mn ，其对应密文为 moded m n。 （ 3）解密 对密文 c ，其对应明文为 moddm c n。 （ 4）证明 由于 1mod( ( ))de n ，故存在整数 k 满足 ( ) 1de k n。 故有 ( ) 1 1 ( 1 )( ) m ode d k n p k qm m m m m q     。 而此式在 gcd( , )m p p 时显然也成立。 同样可以推出 ( ) 1 m oded k nm m m q  故有 中山大学本科生毕业论文 8 ( ) 1 m o dd ed k nc m m m n    二、实验部分 （一） 实验 目的 通过对 RSA 的研究和实现，学习 RSA 的数学基础、掌握 RSA 加密的原理和方法、巩固计算机编程能力。 （二）实验环境 Microsoft Windows 7 Microsoft Visual Studio 2020 Microsoft .Net Framework 使用 C 编程语言 （三）实验步骤 在引论中写了要实现 RSA，必须先解决 大整数类的实现 、模幂运算 的快速计算 以及 快速产生大素数 这三个问题。 此外，计算 1 m od( ( ))d e n 需要用到 扩展的欧几里德算法 （ Extended Euclid）。 1. 大整数类 大整数一般指数位超过计算机整数类型值集范围的整数。 如 C 中的 Unsigned long 型整数能处理整数值 4294967295（ 2321），占据 32bits 存储空间，此时，大整数就是指大于 4294967295 的十位以上的整数。 若取 109为“基”，即以 109为一个存储单元。 109=（ 1000） 3102410=230，占 30 位，以 4Bytes 的整型长度存储的话，空间利用率可达 %。 (8)同时，同时有表达直观、容易理解、录入输出方便和数据处理能力较高的优点。 中山大学本科生毕业论文 9 然而，为了模幂运算的效率，最终决定以 2 为基，用 bool 型数组而不是 int型，并重载加、减、乘、除、求余、相等、不等、大于、小于等运算符。 2. 快速 模幂运算 计算模幂运算 modbac。 快速模幂运算又称快速幂取模，其原理是 m o d ( m o d ) ( m o d ) m o da b c a c b c c。 故，令 k 为整数，若 2bk ， 2m od m od ( m od ) ( m od ) m odb k k ka c a c a c a c c； 若 21bk， 2 1 2m o d m o d ( m o d ) ( m o d ) m o db k ka c a c a c a c c。 因此可以分解计算，有快速算法： int exp_mod(int a, int b, int n) { int r = 1。 while (b) { if (b amp。 1) r = (r * a) % n。 a = (a * a) % n。 b = 1。 } return r。 } 3. 快速产生随机素数 如引论所说，没有方法直接产生一个素数，通常的做法是产生一个随机奇数，判断是 否为素数，产生一个随机数恰好是素数的概率是。 于是分为两部分，一是随机数产生，二是素性判断。 由计算机函数产生的随机数称伪随机数，有许多文章对伪随机数的构造原理、实现方法和效果（生产效率和随机性）进行了分析和研究，但由于 中有伪随机数生成器 random()，所以不再重写而是直接阅读 MSDN (9)使用之。 素数测试算法主要分两种：概率素数测试算法和真素数测试算法。 概率素数测试算法的特点是：算法速度较快、原理简单、易于编程实现、有一定的误判概率。 真素数测试算法速度很慢，比如最基础的从 3 开始测试每一个中山大学本科生毕业论文 10 整数是否被待测试数 n 整除直到 n。 目前最好的基于椭圆曲线的算法的时间复杂度是 6logn  ，基于割圆环的测试算法的时间复杂度是 loglogloglog n。 且真素数测试算法背后的理论比较艰深，在计算机中的实现十分复杂，实现复杂带来的不正确实现的安全隐患要比概率算法误判带来的安全隐患大得多。 概率算法的误判完全可以被控制在一个极低的可接受的概率范围内，误判概率在 80(1/2) 以下足以满足绝大部分的安全需求。 综合上述原因，在实际应用中，大多使用基于概率的素数测试算法。 通过对比，选择 MillerRabin 算法作为素数测试算法。 MillerRabin 算法是Fermat 算法的一个变形改进，它的理论基础是从 Fermat 定理引申而 来的。 Fermat 定理： n 是一个奇素数， a 是任何整数 (1 1)an   ，则 1 1(mod )nan 。 事实： n 是一个奇素数，则方程 2 1modxn 只有 1 两个解。 MillerRabin 算法的理论基础：如果 n 是一个奇素数，将 1n 表示为 2*s r 的形式（ r 是奇数）， a 是和 n 互素的任何整数，那么 1(mod )ran 或者对某个j (0 1, )j s j Z   ，等式 2 1(mod )jran 成立。 这个理论由 Fermat 定理以及一个事实推导而来。 MillerRabin 算法的误判概率为 (1/4)t ，时间复杂度为 32(log ( ))On，其中 t 为测试次数。 (10) 4. 扩展的欧几里德算法 欧几里德算法是辗转相除法，用于计算两整数的公约数，其依赖原理如下： g c d ( , ) g c d ( , m o d )a b b a b （ ab 且 modab不为 0） 扩展欧几里德定理：对于不完全为 0 的非负整数 a ， b ，以及其最大公约数gcd( , )ab ，必存在整数对 x ， y ，使得 gcd( , )a b ax by。 其实现方法是在进行辗转相除法时，因为 中山大学本科生毕业论文 11 g c d ( , )g c d ( , m o d ) 39。 ( m o d ) 39。 a b a x b yb a b b x a b y  恒等变换得 39。 39。 ( / ) 39。 xyy x a b y （其中 /ab是取商） 故能设计出一个递归函数，求出 x， y，满足 gcd( , )a b ax by。 （四）代码设计 1. 大整数类 在前文中已经说明了我的大整数类的数据结构定为布尔型数组。 实际上，在开始写这个类的时候，我用的是 int 数组与 bool 数组并存或者可以随时切换的形式。 这样的类可以灵活处理数据，比如录入一个十进制数，和另外一个十进制数相加再输出时，可以直接调用两个十进制数相加的函数，并直接输出，节约了三次进制转换。 然而，这样的类变得很复杂和臃肿，且在这个程序里不会有这样的要求，故最后把十进制模式移出并构建新类。 类的数据结构与字段如下： 图 十进制整数类 图 二进制整数类 字段 ，类名 Bigint 类中，用数组储存大整数的绝对值，符号放在 sign 中，并用 length 表示长度。 这里的 length 不是数组的长度，而是数组的有用长度；用 length 表示长度可中山大学本科生毕业论文 12 以在比较大小，四则运算时节约计算。 大整数绝对值在 bool 数组中的储存方式是，把大整数二进制化，低位放在数组低位，高位在数组高位。 如把 2 放入，则把 2 二进制化为 102，则 _body[0]=0,_body[1]=1。 并赋值 length 为 2。 接着进行运算符重载。 图 大整数类运算符重载 其中包括一个从 int 型到 Bigint 型的隐式转换函数，可以在进行 Bigint 型与int 型值进行运算时节约代码。 公开的函数中，对 5 种二元计算， 6 种比较运算以及 1 种一元计算进行了重载，并完成了哈希函数和相等函数的重写。 下面的私有函数用以辅助上面的函数实现，如 BinaryCheckZero 用于确定 body 的有效数位；BinaryDividestep 用于做除法运算中的一步，即被除数顶位减除数。 下面是进制转换与输入输出。 图 进制转换 中山大学本科生毕业论文 13 十进制到二进制的转换是通过一般的“除 2 取余，逆序排列” (11)方式，但二进制转十进制却不是用通常的“按权相加”法，而是“乘 2 加 1”的方法。