rsa密码体制的设计及matlab语言下的实现毕业论文(编辑修改稿)

rsa密码体制的设计及matlab语言下的实现毕业论文(编辑修改稿)内容摘要：

)(n 具有如下性质： （ 1）当 n 是素数时， 1)( nn ； （ 2）若 kn 2 ， k 为正整数，则 12)(  kn ； 四川理工学院毕业论文 5 （ 3）若 pqn ，且 1),( qp ，则 )1)(1()(  qpn ； （ 4） 若 ttpppn  21 21 ， )1( tipi  为素数，则： )1()1)(1()( 2111211 21   tt ppppppn t   . 定理 ：（欧拉定理）对于任意 整数 na, ，当 1),( na 时，有 na n mod1)(  . 证明 ： 设小于 n 且与 n 互素的正整数集合为 },{ )(21 nxxx  ， 由于 1),(,1),(  nxna i ，故对 )(1 ni  ， iax 仍与 n 互素。 因此 )(21 , naxaxax  构成 )(n 个与 n 互素的数，且两两不同余。 这是因为，若有 ji xx, ，使得,modnaxax ji  则由于 1),( na ，可以消去 a ，从而 nxx ji mod 所以 },{ )(21 naxaxax  与 },{ )(21 nxxx  在 nmod 的意义上是两个相同的集合， 分别计算两个集合中各元素的乘积，有 nxxxaxaxax nn m o d)(21)(21    由于 )(21 , nxxx  与 n 互素，故 )(mod1)( na n   . 推论 naa n mod1)(  中国剩余定理 中国剩余 定理是解一次同余方程组最有效的算法。 首先，我们写出一次同余方程组的一般形式： kk maxmaxmaxmodmodmod2211 如果对任 意 jikji  ,1 ，有 1),( ji mm ，即 kmmm , 21  两两互素，则有以下固定算法： （ 1） 计算 kmmmM 21 ，及ii mMM ； （ 2） 求出各 iM 模 im 的逆，即求 1iM ，满足 iii mMM m od11  ； （ 3） 计算 MaMMaMMx kkk m o d11111   ， x 即为方程组的一个解 . 例 ：求相邻的四个整数，依次可被 2222 7,5,3,2 整除 . 解 ： 设四个整数为 2,1,1  xxxx ，则有 第 2 章 相关数论知识 6 49mod225mod19mod04mod1xxxx 计算 492594 M 492591 M ， 2594,4994,49254 432  MMM 30,9, 14131211   MMMM 最终求得 44100m o d29349x四川理工学院毕业论文 7 第 3 章 RSA 的数学原理及其算法实现 RSA 的数学原理 RSA 算法 基于下面的两个事实，保证 RSA 算法的安全有效性： 1）已有确定一个数是不是素数的快速算法； 2）尚未找到确定一个合数的质因子的快速算法： RSA 算法的工作原理 （ 1） 任意选取两个不同的大质数 p 和 q ，计算乘积 qpn  ， )1()1()(  qpn ； （ 2） 任意选取一个大整数 e ， e 与 )1()1(  qp 互素，整数 e 用做加密密钥，（注意：e 的选取是很容易的，例如，所有大于 p 和 q 的质数都可用） （ 3） 确定解密密钥 d ： )1)(1m od(1  qped ，根据 e ， p ， q ，可以容易的计算出 d ； （ 4） 公开整数 n 和 e ，将 d 保密； （ 5） 将明文 p （假设 p 是一个小于 n 的整数）加密为密文 c ，计算方法为： npc e mod （ 6） 将密文 c 解密为明文 p，计算方法为： ncp d mod 然而，只根据 n 和 e （不是 p 和 q ），要计算出 d 是不可能的，因此，任何人都可以对明文进行加密，但只有授权用户（知道 d ）才可以对密文进行解密。 例如： 向用户 A 发送加密信息时， 利用 A 的公开密钥 An ， Ae ,计算 Ae nmmEc A m o d)(  求出的整数 c 即为密文， 当 A 受 到 c 后，利用自己 的解密密钥 Ad ，计算 Ad nccDm A m o d)(  由欧拉定理，这里计算出的 )(cD 恰好等于加密前的明文 m . 事实上，由于 )(mo d1 AAA nde   1|)( AAA den . 设 1)(  AAA ntde  ， Zt ，当 1))(,( Anm  时，有： Am nm mod1)(  第 3 章 RSA 的数学原理及其算法设计 8 于是： AtnnTde nmmmmmcD AAAA m o d)()( )(1)(    这时，对于每一个明文分组 m ，要求其与模数 n 互素 . RSA 的算法设计 RSA 加密算法和解密算法的具体步骤： （ 1） RSA 算法的初始化，系统 产生 2 个大素数 p 和 q （保密） .计算 qpn  ，（ n 公开）， )1()1()(  qpn ，令随机选取整数 e 作为公钥（加密密钥），满足 e （公开）和 )(n互质，计算私钥 d （解密密钥），满足 )(m od1 nde  .销毁 p ， q 及 )(n . （ 2） RSA 加密解密变换，首先将明文分块并数字化，然后将明文分成若干段，使每个数字化的明文段的值小于 n ，长度不大于 n2log ， 然后 对每个明文块 m 依次进行加密，解密变换 . 加密变换 ：分别使用公钥 e 和明文 m ，得密文 nmmEc e m o d)(  解密变换：分别使用私钥 d 和密文 c ，得明文 nccDm d m o d)(  例 ： RSA 公钥密码加密解密算法实例 选 53p ， 41q ， 2173 qpn ， 2080)( n ，选择 31e ，计算出 671d . 将 n ， e 公开， d 保密， 设明文 m 为 374，对其加密，得到密文： 2173m od44631  mc . 解密时，计算 21 73m od3746 7 1 c ，恢复出明文 374 . RSA 的加密解密过程是一个模 n 的指数运算，计算 nme mod 这个运算有一个快速实现的算法如下： 首先，将 e 表示为二进制形式： 11210 242  rr aaaae ， ][log2 er ， }1,0{ia 然后计算出： nmm mod21  nmnmm m o dm o d 4212  … nmnmm rrr m o dm o d 12221   其中， 10  nmi ， 11  ri ， 由于： 11101110 )()( 2222    rrrr aaaaaae mmmmm  . 四川理工学院毕业论文。