RSA加密系统在 MATLAB 语言下的实验（0907401班夏雪梁桃牛艳宁）摘要： RSA 是较为成功的一种公钥加密算法，本实验用MATLAB 语言实现 RSA 的加 密和解密过程， 可以较好地了解加密工作的严谨性和大量数据工作的复杂性。在 试验中，发现大数运算在没有好的算法的情况下，耗时之长是让人难以接受的。 为了实现大数运算， 在程序中专门设置了进行大数运算的部分。这是本实验的一 个特点。 关键字：加密大数求模复杂性背景：密码系统中信息发送者通过加密将可正常阅读的信息转化为难以识别的信息，希望除理想接收者外其他人即使截获信息本身也不能理解其含义。而作为信息传递的手段， 加密后的信息又必须能被接收者正确理解，即信息接收者可通过对加密信息解密来得到发送者所要发送的原本信息。这要求：发送者知道加密方法和相关数据， 接收者知道解密方法和相关数据。事实上，发送者并不需要得知解密方法及数据。密钥给出的正是在一定方法下加密和解密必然会用到的数据。对称密码加密和解密所用的方法是对称的，密钥是相同的。 一套密码系统中， 方法是固定的， 可以有多种密钥。 对对称密码而言， 知道了加密密钥， 也就知道了解密密钥。通信双方必须事先约定密钥， 而在密钥的传输过程中又存在很大的不安全因素，有时约定密钥甚至是不可能的，如一个接收者想要接收许多人发送的信息，又不希望每个发送者看到别人发送的信息，如果使用对称密码， 接收者只能与每个发送者都约定一组密钥，既麻烦也不安全， 而对于公开招标的单位， 不同公司间的投标信一定要相互保密，单位又不可能与所有公司约定密钥。为解决这类问题，人类创造性地发明了公开密钥体制。在公钥密码体制中，加密密钥和解密密钥分离，这样，一个具体用户就可以 将自己设计的加密密钥和算法公诸于众，而只保密解密密钥。 任何人利用这个加 密密钥和算法向该用户发送的加密信息，该用户均可以将之还原。 因为一组加密 密钥和解密密钥对应的是同样的密文和明文，之间必然会有联系， 以加密密钥为 公钥，解密密钥为私钥， 则根据公钥理论上可以推出私钥。因此一套公钥密码体 制的安全性关键就在于设计合理的加密算法使由公钥推出私钥极其困难。许多公 钥密码算法都是根据一些数学难题给出的。综述：我们这里所用的 RSA 公钥体制的安全就是基于大数分解的困难性。RSA 公 钥体制现在被广泛使用， 其基本思想是： 从两个超百位的大素数得到乘积相对简 单，反之，给了这样一个乘积，将其分解为两个素因子则极端困难。设n为一个正整数，将小于n且与之互素的正整数的个数记为，称之为欧拉函数。若p与q为两相异素数，pqn， 则)1)(1()(qpn。 而整数e与)(n互素，另一整数d与e满足)(mod1ned，则映射)(mod:,nxxnEee是从1,2, 1,0nZn到自身的一一映射，其逆映射为)(mod:,nxxnEdd。在 RSA 体制下，使用者选择一对相异素数p、q，计算pqn，再选择与)1)(1()(qpn互素的e，然后选择一个整数d使)(mod1ned。使用者将),(ne公开作为公钥，将),(nd作为私钥。另一使用者向该使用者发送明文数字A，先加密得密文)(mod nABe，该使用者接收到B，解密得明文)(modnBCd，根据上述数学原理，C与A是相等的。 实际使用中， 发送者需要将信息转化为数 字，接收者需要将数字还原为数字，而信息与数字的对应表是公开的。而对于信息的攻击者，只知公钥),(ne，为破译密码，需要得知),(nd，即必须求出d，最终归结为将大数分解pqn。对于很大的n，分解工作量极大， 这就保证了密码的安全性。 在 RSA 体系的模拟设计中，主要分为两大部分，即体系建立和系统使用。 体系建立需要生成加密解密所用参数，系统使用包括加密过程和解密过程。 实际编程中，需要根据MATLAB 语言特点和机器状况来安排参数大小和操 作过程。大数基本运算：首先要生成的参数就是两个大素数。素数小了， 在当今计算机的高速度运算 面前密码体系将毫无安全性可言，而大数运算在电脑上并不能直接进行，因此首 先要编写大数运算的程序，这也正是本实验有所创新的部分。 大数由于位数太多， 选择用向量来存放， 大数要实现 5 种基本运算， 加、减、 乘、除、模。 MATLAB 中一个整数最多为11 位，乘法有时会使位数加倍，故向 量的一个元素所存的数最多可以是5 位数，为合理利用计算机空间， 在计算过程 中节省时间，向量一个元素存放一个4 位数，正常情况其中数字有09999共 10000 种可能，这样有一定冗余度，便于增加功能或进行修改，也容易翻译为C+或 Java 以进行别的应用。一个向量设有100 个元素，最多可以表示十进制 下的 400 位数。 计算机内部的运算是在二进制基础上进行的，其运算过程对大数运算程序的 设计很有启发性。 在大数运算程序中， 加法是从低位到高位进行的，大数采用的 是 10000 进制，减法求补再进行相加并不能使运算简单，因此采用从低到高相 减的方法。 乘法要利用嵌套循环， 每个循环均是从低位到高位，依次相乘， 都加 到结果向量的相应位置。 除法最复杂，计算机内部是从高到低，相减和移位，由于采用二进制，结果 根据被除数和除数所在位置数的大小轻易得到，采用10000 进制时，商难以确 定，如果如果从 1 开始取值依次与除数相乘与被除数相应位置的数比较，将耗时 巨大。 在实际编程中采用了将10000 进制转换为二进制的办法。 因 21610000 ， 设一个有 1600 个元素的向量就足以容纳100 个 10000 进制数了。正常情况下 这 1600 个元素都是 0 或 1。计算机内部移位是很快的操作，而在除法程序中移 位必须强力移动，比较耗时。最终商由二进制数还要转换为10000 进制数。同 时，多次调用函数也会增加运算时间。总的来看，除法运算是缓慢的。 求模运算与除法运算类似， 不同的是除法结果记录了商，而求模结果记录了 余数。同样，模运算也是缓慢的。 进行下面的运算用了近4 分钟。文件 add.m实现了加法运算， dec.m实现了减法运算， mul.m 实现了乘法运 算，div.m 实现了除法运算， moda.m实现了求模运算。 除此之外，还有一些函数实现了一些使运算和编程方便的功能。getn.m 中 y=getn(n)可得到一个最低位为n 的 10000 进制数， dibytwo.m 中 y=dibytwo(been) 可 求出 向量 been 的 1/2。 y=digit(been)得到 的是 10000 进 制数 的 位 数 ， y=digitbe(been)得到的则是二进制数的位数，它们可以通过记录无效的0 的个数 来避免无用的计算，尤其是在乘法、除法和求模运算中。Y=cpabe(been,divto,a,c) 可以比较二进制下被除数、除数对齐时从低位第a位到高位第 c 位的数的大小，为除法和求模服务， 结果 0 表示小于，1 表示大于，2 表示相等，y=cpa(been,divto) 则比较两个 10000 进制数的大小， 结果为 2 表示大于， 1 表示相等， 0 表示小于， 可广泛用于条件语句中。is0.m检验 10000 进制数是否为 0，is0be.m检验二进制 数是否为 0。 mod2.m得出的是大数模 2后的结果，即最低位模 2的结果。 MATLAB 语言中“/” 表示的是 double型的除法，y=idiv(a,b)可给出整型除法a除以 b 的商。 bits.m 把 10000进制数变成二进制数， bytes.m把二进制变成 10000 进制， divbe.m 计算二进制除法，modbe.m会给出二进制求模结果， bytesn.m、 divben.m、 modben.m 都是为除法和模提供基础函数的，用途不是很广。 Isprime(n)检测数 n是否为素数， 函数利用了 Robin-Miller 测试法，当一个数 比较大时，检测其是否为素数要用较长时间，10000进制数为 2 位时，大约要用 30 秒，这是由于多位大数计算过程复杂的缘故，也反映出程序代码还很不科学。 程序中，函数 y=getprime(n)求得一个大于等于n 的素数，当 n 增加时，运算 更加复杂，而素数逐渐稀疏， 寻找素数耗时较长。 实验中得到素数432125493617 竟用了 5 个小时，进一步反映了利用向量分段存储的大数给运算带来的复杂性和 程序的不成熟。 生成素数 p、q 后，可以计算 n=p*q，记欧拉函数值 E=(p-1)*(q-1)，则 e 与 E 互素，即 gcd(e,E)=1，确定 e后，d 须满足 mod(e*d,E)=1，由此可求 d。 由于运算速度慢，最终得到一个素数432125493617 ，另一个为 31721，相乘 得 n=13707452783024857 ，欧拉函数值为13707020657499520 ，与之互素， e=3, 求模逆得 d=9138013771666347 。模幂函数为 y=mol(x,a,n)，得 y=mod(xa,n)采用 了重复平方取模的算法，模逆函数为y=getk(x,n)，得 y=x(-1)mod(n)。 至此，参数设置完毕。因为公钥、私钥可以互换，要根据实际情况选择。e、 d 比较， e 很小，若以之作为私钥，解密相对容易，加密则比较困难，从安全角 度来看， 3 太小了，一旦攻击者采用暴力破译，3 首当其冲。所以以 (d,n)为私钥， (e,n)为公钥。 由于以大数作为密钥时，加密、解密都很慢，所以，在形成视图时，其下相 关函数使用的密钥都是较小的数，以便于演示加解密过程所用的算法：1 素性检测 给定一个正整数p , 判断 p 是否是素数 , 称为素性检测。 RSA 密码算法中 p、q 都是大素数(大于十进制100位)。因此,素性检测是一个重要工具。目前主 要 有概 率测 试 法 与确 定性 测 试 法, 这 里 选 用 了 广 泛使 用的 概 率 测试 法 : Robin-Miller 测试法。 首先选择一个待测的随机数p,计算 b, b 是 2 整除 p- 1 的次数 ,然后计算 m, 使 p= 1+ 2b*m。测试算法如下 : (1)选择随机数a 0 且 z= 1 ,那么 p 不是素数 ; (5)设 j= j+ 1，如果j b 且 z!=p-1，设 z=(z2)mod p，然后回到第 ( 4)步。 如果 z= p-1 , 那么 p 通过测试 ,可能是素数 ; ( 6)如果 j= b 且 z! p- 1 ,那么 p 不是素数。 数 a 被当成证据的概率为3 /4。 这意味着当迭代次数为n时, 它产生一个假 的素数所花费的时间不超过(1/4)n。对大多数的随机数 , 几乎 99 . 9 %肯定 a 是 证据。 2.RSA密码算法中的加密算法与解密算法都要进行大数的模幂运算(gx)mod n ,因为 g , x , n 都是大数 ,不能直接采用先高次幂再求剩余的方法来处理, 一般 采用重复平方取模的算法、 M ontgomery算法和预处理的窗口法来加快运算速度。 实验中主要采用重复平方取模的算法来实现大数的模幂运算。具体算法如下: (1) a=g,b=x,c=1,转(2) ; (2)若 b= 0 ,则输出 c ,结束; 否则,转( 3) ; (3)若 b(mod 2) = 0 , 转入(4);否则, 转(5) ; (4) b=b/2,a=(a*a)mod(n),转( 3); ( 5)b=b-1,c=(a*c)mod (n) ,转( 2)。 加密过程与解密过程是相似的，加密时，首先要把计划传递的信息转化为数 字，在这里即把 string 或 char型转化为 int 型或 double型使用方法：打开 MATLAB 系统， 寻找文件 jiami.fig ， 公钥和私钥在内部都已经设置好了。 在左侧栏中寻找：或者点击画图标志：新建或打开：加密：点击加密