信息计算2019级2班8号张黎曦

张黎曦

mooc截图

张黎曦

mooc截图

张黎曦

import java.math.BigInteger;
import java.util.*;

public class rsa {
​//判断两数是否互素
   public static int getgcd(BigInteger n1,BigInteger n2)
   {
​    BigInteger q,r;
​    do
​    {
​​    q = n1.divide(n2);
​​    r = n1.subtract(q.multiply(n2));
​​    if(r.compareTo(BigInteger.ZERO)==0)
​​    {
​​    ​break;
​​    }
​​    else
​​    {
​​​    n1 = n2;
​​​    n2 = r;
​​    }
​    }while(r.compareTo(BigInteger.ZERO)!=0);
​   
​    if(n2.compareTo(BigInteger.ONE) == 0)
​​    return 1;
​    else
​​    return 0;
   }
   //求逆元
   public static BigInteger getInverse(BigInteger u,BigInteger n)
   {
   ​BigInteger q,r,n1 = n,n2 = u,t,b1=BigInteger.ZERO,b2=BigInteger.ONE;
   ​do
   ​{
   ​​q = n1.divide(n2);
   ​​r = n1.subtract(q.multiply(n2));
   ​​if(r.compareTo(BigInteger.ZERO)!=0)
   ​​{
   ​​​n1 = n2;
   ​​    n2 = r;
   ​​    t = b2;
   ​​    b2 = b1.subtract(q.multiply(b2));
   ​​    b1 = t;
   ​​}
   ​}while(r.compareTo(BigInteger.ZERO)!=0);
   ​if(n2.compareTo(BigInteger.ONE)==0)
   ​    return (b2.add(n)).mod(n);
   ​else
   ​​return BigInteger.ZERO;
   }
   //求高幂模
   public static BigInteger getgaomimou(BigInteger a,BigInteger b,BigInteger n)
   {
   ​BigInteger c = BigInteger.ONE;
   ​while(b.compareTo(BigInteger.ZERO)!=0)
   ​{
   ​​while((b.mod(new BigInteger("2"))).compareTo(BigInteger.ZERO)==0)
   ​​{
   ​​​b = b.divide(new BigInteger("2"));
   ​​​a = a.multiply(a).mod(n);
   ​​}
   ​​if((b.mod(new BigInteger("2"))).compareTo(BigInteger.ZERO)!=0)
   ​​{
   ​​​b = b.subtract(BigInteger.ONE);
   ​​​c= c.multiply(a).mod(n);
   ​​}
   ​}
   ​return c;
   }
   //加解密
​public static void main(String[] args) {
​​BigInteger e,d;
​​//生成两个大素数
​​BigInteger p = BigInteger.probablePrime(30, new Random());
​​BigInteger q = BigInteger.probablePrime(30, new Random());
​​BigInteger n = p.multiply(q);
​​System.out.println("n="+n);
​​BigInteger mn = (p.subtract(BigInteger.ONE))
​​​​.multiply(q.subtract(BigInteger.ONE));
​​//选取正整数e，作为公开的加密密钥
​​for(e = new BigInteger("2");e.compareTo(mn)<0;e = e.add(BigInteger.ONE))
​​{
​​​int t = getgcd(e,mn);
​​​if(t == 1)
​​​​break;
​​}
​​System.out.println("加密密钥e="+e);
​​//解密密钥
​​d = getInverse(e,mn);
​​System.out.print("请输入明文：");
​​Scanner in=new Scanner(System.in);
​​BigInteger ptext=in.nextBigInteger();
​​BigInteger ctext = getgaomimou(ptext,e,n);
​​System.out.println("加密结果为："+ctext);
​​ptext = getgaomimou(ctext,d,n);
​​System.out.println("解密结果为："+ptext);
​}​​
}