RSA算法分析和实现.docVIP

《应用密码学》实验报告 实验序号：03 　　　　　　　　　实验项目名称：RSA密码技术 学　　号 姓　　名 专业、班 实验地点 指导教师 实验时间 一、实验目的及要求 实验目的： 深入理解RSA原理，特别是大数分解难题的原理 明确选择RSA的参数p、q、e、d的条件，以及明文分段的条件 掌握求逆元素和求高次幂的计算方法 了解寻找素数的方法 了解素数、同余类、欧拉函数、费马定理、欧拉定理 要求： 1. 要求实验前做好准备，熟悉实验相关的技术和原理，制定实验方案，编写相关的程序或文档；实验独立完成，认真观察与思考；实验后进行分析小结，写出实验报告。 2. 用C语言实现 3. 撰写实验报告 二、实验设备（环境）及要求 微机、C语言 环境：Microsoft Visual C++ 6.0 用C语言实现选定的加密算法和相应的解密算法 三、实验内容与步骤 RSA实验原理和数据模型 首先,?找出三个数,?p,?q,?r,?其中?p,?q?是两个相异的质数,?r?是与?(p-1)(q-1)?互质的数，p,?q,?r?这三个数便是?private?key?。?接著,?找出?m,?使得?rm?==?1?mod?(p-1)(q-1).....?这个?m?一定存在,?因为?r?与?(p-1)(q-1)?互质,?用辗转相除法就可以得到了。再来,?计算?n?=?pq?，m,?n?这两个数便是?public?key?。?编码过程是,?若资料为?a,?将其看成是一个大整数,?假设?a??n....?如果?a?=?n?的话,?就将?a?表成?s?进位?(s?=?n,?通常取?s?=?2^t),?则每一位数均小於?n,?然後分段编码......?接下来,?计算?b?==?a^m?mod?n,?(0?=?b??n),?b?就是编码後的资料??解码的过程是,?计算?c?==?b^r?mod?pq?(0?=?c??pq),?於是乎,?解码完毕......?等会会证明?c?和?a?其实是相等的:)??如果第三者进行窃听时,?他会得到几个数:?m,?n(=pq),?b他如果要解码的话,?必须想办法得到?r......?所以,?他必须先对?n?作质因数分解.........?要防止他分解,?最有效的方法是找两个非常的大质数?p,?q,?使第三者作因数分解时发生困难。?定理?若?p,?q?是相异质数,?rm?==?1?mod?(p-1)(q-1),?a?是任意一个正整数,?b?==?a^m?mod?pq,?c?==?b^r?mod?pq,?则?c?==?a?mod?pq? 证明的过程,?会用到费马小定理,?叙述如下:?m?是任一质数,?n?是任一整数,?则?n^m?==?n?mod?m?(换另一句话说,?如果?n?和?m?互质,?则?n^(m-1)?==?1?mod?m)?运用一些基本的群论的知识,?就可以很容易地证出费马小定理的。 证明?因为?rm?==?1?mod?(p-1)(q-1),?所以?rm?=?k(p-1)(q-1)?+?1,?其中?k?是整数?因为在?modulo?中是?preserve?乘法的?(x?==?y?mod?z??and??u?==?v?mod?z??=??xu?==?yv?mod?z),?所以,?c?==?b^r?==?(a^m)^r?==?a^(rm)?==?a^(k(p-1)(q-1)+1)?mod?pq? 1.?如果?a?不是?p?的倍数,?也不是?q?的倍数时则?a^(p-1)?==?1?mod?p?(费马小定理)??=??a^(k(p-1)(q-1))?==?1?mod?p? a^(q-1)?==?1?mod?q?(费马小定理)??=??a^(k(p-1)(q-1))?==?1?mod?q?， 所以p,?q?均能整除? a^(k(p-1)(q-1))?-?1??=??pq?|?a^(k(p-1)(q-1))?-?1 即a^(k(p-1)(q-1))?==?1?mod?pq??=?c==?a^(k(p-1)(q-1)+1)?==?a?mod?pq?2.?如果?a?是?p?的倍数,?但不是?q?的倍数时,????则?a^(q-1)?==?1?mod?q?(费马小定理)????=??a^(k(p-1)(q-1))?==?1?mod?q????=??c?==?a^(k(p-1)(q-1)+1)?==?a?mod?q????=??q?|?c?-?a????因?p?|?a????=??c?==?a^(k(p-1)(q-1)+1)?==?0?mod?p????=??p?|?c?-?a????所以,?pq?|?c?-?a??=??c?==?a?m