《武汉大学应用密码学rsa加密解密大作业》由会员分享，可在线阅读，更多相关《武汉大学应用密码学rsa加密解密大作业（7页珍藏版）》请在金锄头文库上搜索。
1、1 对 RSA 算法的理解RSA 加密算法是一种非对称加密算法，它基于一个非常简单的数论思想：“将两个素数乘起来 是很容易的，但是分解该乘积是非常困难的” 。1.1 加解密步骤(1)生成公钥和私钥a) 随机生成两个不相等的大素数 p 和 q，计算 N=p*q;b) 根据欧拉函数，求出 =(p-1)*(q-1);c) 选择一个小于 r 的整数 e，求 e 关于 r 的模反元素 d 使得 e*d mod =1得到公钥，私钥(2)加密给定明文 m，公钥，计算密文 c = me(N)。(3)解密给定密文 c，私钥 ，计算明文 m = cd(N)。1.2 素性检验RSA 算法的实现难点之一是生成大素数，
2、这就需要生成一个大数并对其进行素性检验。素性检验有很多种方法。其中包括确定性方法和随机方法。确定性方法有试除法( 埃拉托斯特尼筛法)，卢卡斯-莱默检验法和 AKS 素数测试。常见的随机方法有费马素性检验，米勒-拉宾检验和欧拉-雅科比测试。本次作业采用 就是米勒- 拉宾检验方法。米勒-拉宾 (Miller Rabin) 算法原理：要测试 N 是否为素数，首先将 N-1 分解为 2s d。在每次测试开始时，先随机选一个介于 1, N-1的整数 a，之后如果对所有的 r0, s-1，若 ad mod N 1 且 a2rd mod N 1，则 N 是合数。否则，N 有 3/4 的概率为素数。1.3 安
3、全问题（1）公共模数攻击。每个人具有相同的 r，但有不同的指数 e 和 d，这是不安全的。（2）低加密指数攻击。如果选择了较低的 e 值，虽然可以加快计算速度，但存在不安全性。（3）低解密指数攻击。如果选择了较低的 d 值，也是不安全的。（4）选择密文攻击。如 A 想让 T 对一个 T 不愿意签名的消息 m签名，A首先选择一个任意值 x，计算 y=xe（mod r） ，然后要求 T 对 m=ym签名，A 最后计算(m d mod r)x-1 mod r =( ym) d x-1mod r= md mod r。还有一些不是直接对 RSA 的算法本身进行的攻击，如中间人攻击、 时间攻击、边信道攻击
4、等。2.具体实现2.1 函数说明void ProducePrime(JTextField prime)：使用 JAVA 的 Biginteger 生成 512 位的大数，再用 Miller Robin 算法检验是否是素数。参数 prime 即为生成的大素数。boolean MillerRobin(BigInteger n)：用 Miller Robin 检验判断大数 n 是否是素数。BigInteger modex(BigInteger a, BigInteger b, BigInteger n)：模幂运算，计算ab mod nBigInteger inverse(BigInteger a,
5、BigInteger b)：求逆运算，计算 a-1 ( b )String Encode(String Plaintext, BigInteger n, int nLen, int m, JTextField e)：加密，用公钥（n，e ）对明文 Plaintext 加密。String Decode(String Ciphertext, BigInteger n, int m, JTextField d)：解密，用私钥 d 对密文 Ciphertext 解密。2.2 JAVA 代码import java.math.BigInteger;import java.util.Random;impor
6、t java.util.Scanner;import javax.swing.JTextField;public class RSA public static void main(String args) String s;JTextField p = new JTextField(35);JTextField q = new JTextField(35);JTextField e = new JTextField(35);JTextField d = new JTextField(35);ProducePrime(p);ProducePrime(q);BigInteger pp = new
7、 BigInteger(p.getText();BigInteger qq = new BigInteger(q.getText();BigInteger oo = (pp.subtract(new BigInteger(1).multiply(qq.subtract(new BigInteger(1);BigInteger ee;do ee = new BigInteger(100, new Random().mod(oo); while (MillerRobin(ee) = false);e.setText(ee.toString();d.setText(inverse(ee, oo).t
8、oString();BigInteger n = pp.multiply(qq);int nLen = n.bitLength();int m = (int) (Math.ceil(double) (nLen) / 16.0);nLen = (nLen - 1) / 16;String Ciphertext = new String();String Plaintext = new String();System.out.println(P： + p.getText();System.out.println(Q： + q.getText();System.out.println(公钥： + e
9、.getText();System.out.println(私钥： + d.getText();Scanner scanner = new Scanner(System.in);System.out.println(输入要加密字符串：);s = scanner.nextLine();Ciphertext = Encode(s, n, nLen, m, e);System.out.println(加密结果： + Ciphertext);Plaintext = Decode(Ciphertext, n, m, d);System.out.println(解密结果： + Plaintext);/产生
10、大素数public static void ProducePrime(JTextField prime) BigInteger n = new BigInteger(0);Random r = new Random();do n = new BigInteger(512, 5, r);prime.setText(n.toString(); while (MillerRobin(n) = false);/Miller Robin 素性检验public static boolean MillerRobin(BigInteger n) int time = 1000;BigInteger m = n
11、.mod(new BigInteger(2);if (m.equals(new BigInteger(0) return false;int s = 0;int k = 0;BigInteger t = n.subtract(new BigInteger(1);while (t.mod(new BigInteger(2).equals(0) t.divide(new BigInteger(2);+s;for (int i = 0; i 0) long num = (r.and(BigInteger.valueOf(65535).longValue();buf = (char) (num) +
12、buf;r = r.shiftRight(16);outBuf = outBuf.append(buf);return outBuf.toString();2.3 测试结果：P：12903680547085151737561439790003288859653719849848961393625486116955728079417775547658393616190353194898778491498344834046298085040266668913843973354103033Q：965485259575386626661798155084845386764376902206479716
13、9642065983699715060744588949225361203288815589569670663094430366487834097518093790530180407555360339公钥：1133142713903219484415537969751私钥：28922989776768963419549165514164324954490370928168575931605576028829732928678530850327875656825227710658919943707800730592452562367934147890879752396622139030804163699256451593568559485448537342459783771485514401379019549226274342735681574190165140500336299924656362866091812534177904849175286307833237971415输入要加密字符串：密码学算法 RSA加密结果：偮钘? 兄埅?烄証箕?霑痘? 啛猝市 ?鎈?釤?筕?酪? ?霧? 羳? 鑮解密结果：密码学算法 RSA
