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

张黎曦

RSA加密解密、签名算法

一、RSA加密解密、签名算法介绍

RSA加密是一种非对称加密。可以在不直接传递密钥的情况下，完成解密。这能够确保信息的安全性，避免了直接传递密钥所造成的被破解的风险。是由一对密钥来进行加解密的过程，分别称为公钥和私钥。两者之间有数学相关，该加密算法的原理就是对一极大整数做因数分解的困难性来保证安全性。通常个人保存私钥，公钥是公开的（可能同时多人持有）。

签名就是在这份资料后面增加一段强而有力的证明，以此证明这段信息的发布者和这段信息的有效性完整性。RSA签名常用的就是将这份信息进行hash，得到一个hash值，再将hash值加密作为签名，后缀在信息的末尾。哈希的好处：更安全，签名更快，解除了签名长度的限制。

二、算法分析

加密解密算法分析：

1、选取两个大素数p和q，p和q保密。

   利用Java语言的中的java.math.BigInteger类的方法中随机产生大数，并使用probablePrime()方法,获取两个BigInteger，其值为给定长度的正可能质数。

2、计算n=pq,f(n)=(p-1)(q-1)。n公开，f(n)保密。

   BigInteger类对象的加减乘除等运算均使用该类自带的方法。

3、随机选取正整数1<e<f(n),满足gcd(e,f(n))=1。e是公开的加密密钥。

   对e从2到f(n)进行循环，找到一个e满足gcd(e,f(n))=1。其中调用判断两数是否为素数的方法public static int getgcd(BigInteger n1,BigInteger n2)。

4、计算d，满足de(1modf(n))。d是保密的解密密钥。

   其中d为e mod f(n)的逆元，调用求逆元的方法public static BigInteger getInverse(BigInteger u,BigInteger n)，返回逆元。

5、加密变换：对明文m,密文为c = 。

   调用方法public static BigInteger getgaomimou(BigInteger a,BigInteger b,BigInteger n)，参数a=m,b=e,n=n,返回密文。

6、解密变换：对密文c，明文为m = 。

   同样是调用方法public static BigInteger getgaomimou(BigInteger a,BigInteger b,BigInteger n)，参数a=c,b=d,n=n,返回明文。

签名算法分析：

A生成一对密钥（公钥和私钥），私钥不公开，A自己保留。公钥为公开的，任何人可以获取。

A用自己的私钥对消息加签，形成签名，并将加签的消息和消息本身一起传递给B。

B收到消息后，在获取A的公钥进行验签，如果验签出来的内容与消息本身一致，证明消息是A回复的。

三、源代码

1. import java.math.BigInteger;
   
2. import java.util.*;
   
3. 
   
4. public class rsa {
   
5.         //判断两数是否互素
   
6.     public static int getgcd(BigInteger n1,BigInteger n2)
   
7.     {
   
8.             BigInteger q,r;
   
9.             do
   
10.             {
    
11.                     q = n1.divide(n2);
    
12.                     r = n1.subtract(q.multiply(n2));
    
13.                     if(r.compareTo(BigInteger.ZERO)==0)
    
14.                     {
    
15.                             break;
    
16.                     }
    
17.                     else
    
18.                     {
    
19.                             n1 = n2;
    
20.                             n2 = r;
    
21.                     }
    
22.             }while(r.compareTo(BigInteger.ZERO)!=0);
    
23.             
    
24.             if(n2.compareTo(BigInteger.ONE) == 0)
    
25.                     return 1;
    
26.             else
    
27.                     return 0;
    
28.     }
    
29.     //求逆元
    
30.     public static BigInteger getInverse(BigInteger u,BigInteger n)
    
31.     {
    
32.             BigInteger q,r,n1 = n,n2 = u,t,b1=BigInteger.ZERO,b2=BigInteger.ONE;
    
33.             do
    
34.             {
    
35.                     q = n1.divide(n2);
    
36.                     r = n1.subtract(q.multiply(n2));
    
37.                     if(r.compareTo(BigInteger.ZERO)!=0)
    
38.                     {
    
39.                             n1 = n2;
    
40.                         n2 = r;
    
41.                         t = b2;
    
42.                         b2 = b1.subtract(q.multiply(b2));
    
43.                         b1 = t;
    
44.                     }
    
45.             }while(r.compareTo(BigInteger.ZERO)!=0);
    
46.             if(n2.compareTo(BigInteger.ONE)==0)
    
47.                 return (b2.add(n)).mod(n);
    
48.             else
    
49.                     return BigInteger.ZERO;
    
50.     }
    
51.     //求高幂模
    
52.     public static BigInteger getgaomimou(BigInteger a,BigInteger b,BigInteger n)
    
53.     {
    
54.             BigInteger c = BigInteger.ONE;
    
55.             while(b.compareTo(BigInteger.ZERO)!=0)
    
56.             {
    
57.                     while((b.mod(new BigInteger("2"))).compareTo(BigInteger.ZERO)==0)
    
58.                     {
    
59.                             b = b.divide(new BigInteger("2"));
    
60.                             a = a.multiply(a).mod(n);
    
61.                     }
    
62.                     if((b.mod(new BigInteger("2"))).compareTo(BigInteger.ZERO)!=0)
    
63.                     {
    
64.                             b = b.subtract(BigInteger.ONE);
    
65.                             c= c.multiply(a).mod(n);
    
66.                     }
    
67.             }
    
68.             return c;
    
69.     }
    
70.     //加解密
    
71.         public static void main(String[] args) {
    
72.                 BigInteger e,d;
    
73.                 //生成两个大素数
    
74.                 BigInteger p = BigInteger.probablePrime(30, new Random());
    
75.                 BigInteger q = BigInteger.probablePrime(30, new Random());
    
76.                 BigInteger n = p.multiply(q);
    
77.                 System.out.println("n="+n);
    
78.                 BigInteger mn = (p.subtract(BigInteger.ONE))
    
79.                                 .multiply(q.subtract(BigInteger.ONE));
    
80.                 //选取正整数e，作为公开的加密密钥
    
81.                 for(e = new BigInteger("2");e.compareTo(mn)<0;e = e.add(BigInteger.ONE))
    
82.                 {
    
83.                         int t = getgcd(e,mn);
    
84.                         if(t == 1)
    
85.                                 break;
    
86.                 }
    
87.                 System.out.println("加密密钥e="+e);
    
88.                 //解密密钥
    
89.                 d = getInverse(e,mn);
    
90.                 System.out.print("请输入明文：");
    
91.                 Scanner in=new Scanner(System.in);
    
92.                 BigInteger ptext=in.nextBigInteger();
    
93.                 BigInteger ctext = getgaomimou(ptext,e,n);
    
94.                 System.out.println("加密结果为："+ctext);
    
95.                 ptext = getgaomimou(ctext,d,n);
    
96.                 System.out.println("解密结果为："+ptext);
    
97.         }               
    
98. }

复制代码

张黎曦

ECC椭圆曲线上公钥密码算法

一、ECC椭圆曲线上公钥密码介绍

椭圆曲线加密算法，简称ECC，是基于椭圆曲线数学理论实现的一种非对称加密算法。相比RSA，ECC优势是可以使用更短的密钥，来实现与RSA相当或更高的安全，RSA加密算法也是一种非对称加密算法，在公开密钥加密和电子商业中RSA被广泛使用。据研究，160位ECC加密安全性相当于1024位RSA加密，210位ECC加密安全性相当于2048位RSA加密（有待考证）。

二、椭圆曲线上简单的加密/解密

公开密钥算法总是要基于一个数学上的难题。比如RSA 依据的是：给定两个素数p、q 很容易相乘得到n，而对n进行因式分解却相对困难。那椭圆曲线上有什么难题呢？

考虑如下等式：K=kG  [其中 K,G为Ep(a,b)上的点，k为小于n（n是点G的阶）的整数。不难发现，给定k和G，根据加法法则，计算K很容易；但给定K和G，求k就相对困难了。这就是椭圆曲线加密算法采用的难题。我们把点G称为基点（base point），k（k< p style=”word-wrap: break-word;” >现在我们描述一个利用椭圆曲线进行加密通信的过程：

　　1、用户A选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G。

　　2、用户A选择一个私有密钥k，并生成公开密钥K=kG。

　　3、用户A将Ep(a,b)和点K，G传给用户B。

　　4、用户B接到信息后 ，将待传输的明文编码到Ep(a,b)上一点M（编码方法很多，这里不作讨论），并产生一个随机整数r（r

　　5、用户B计算点C1=M+rK；C2=rG。

　　6、用户B将C1、C2传给用户A。

　　7、用户A接到信息后，计算C1-kC2，结果就是点M。 因为C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M 再对点M进行解码就可以得到明文。

在这个加密通信中，如果有一个偷窥者H ，他只能看到Ep(a,b)、K、G、C1、C2 而通过K、G 求k 或通过C2、G求r 都是相对困难的。因此，H无法得到A、B间传送的明文信息。

张黎曦

源代码：

1. 
   
2.     /**
   
3.      * 生成密钥对(公钥和私钥)
   
4.      *
   
5.      * @return
   
6.      * @throws Exception
   
7.      */
   
8.     public static KeyPair initKey(int keySize,String KEY_ALGORITHM) throws Exception {
   
9.         KeyPairGenerator keyPairGen = KeyPairGenerator.getInstance(KEY_ALGORITHM);
   
10.         keyPairGen.initialize(keySize);
    
11.         KeyPair keyPair = keyPairGen.generateKeyPair();
    
12.         return keyPair;
    
13.     }
    
14. 
    
15.     /**
    
16.      * 公钥加密
    
17.      * @param data      源数据
    
18.      * @param publicKey 公钥(BASE64编码)
    
19.      * @return
    
20.      * @throws Exception
    
21.      */
    
22.     public static String encryptByPublicKey(String data, String publicKey)
    
23.             throws Exception {
    
24.         Security.addProvider(new BouncyCastleProvider());
    
25.         X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(keyBytes);
    
26.         KeyFactory keyFactory = KeyFactory.getInstance("EC");      
    
27.         Cipher cipher = Cipher.getInstance("ECIES","BC");
    
28.         cipher.init(Cipher.ENCRYPT_MODE, keyFactory.generatePublic(x509KeySpec));
    
29.         return Base64.getEncoder().encodeToString(cipher.doFinal(Base64.getDecoder().decode(data)));
    
30.       
    
31.     }
    
32.     /**
    
33.      * 私钥解密
    
34.      *
    
35.      * @param encryptedData 已加密数据
    
36.      * @param privateKey    私钥(BASE64编码)
    
37.      * @return
    
38.      * @throws Exception
    
39.      */
    
40.     public static String decryptByPrivateKey(String encryptedData, String privateKey)
    
41.             throws Exception {
    
42.         byte[] keyBytes = Base64.getDecoder().decode(privateKey);
    
43.         PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(keyBytes);
    
44.         KeyFactory keyFactory = KeyFactory.getInstance("EC");
    
45.         Security.addProvider(new BouncyCastleProvider());
    
46.         Cipher cipher = Cipher.getInstance("ECIES","BC");
    
47.         cipher.init(Cipher.DECRYPT_MODE, keyFactory.generatePrivate(pkcs8KeySpec));
    
48.         return Base64.getEncoder().encodeToString(cipher.doFinal(Base64.getDecoder().decode(encryptedData)));
    
49.     }
    
50. 
    
51.          /**
    
52.      * 用私钥对信息生成数字签名
    
53.      *
    
54.      * @param content       已加密数据 base64
    
55.      * @param priKey 私钥(BASE64编码)
    
56.      * @param signatureAl 签名算法
    
57.      * @return
    
58.      * @throws Exception
    
59.      */
    
60.     public static String sign(String content, String priKey,String signatureAl) throws Exception {
    
61.         PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(Base64.getDecoder().decode(priKey));
    
62.         KeyFactory keyFactory = KeyFactory.getInstance("EC");
    
63.         ECPrivateKey privateK = (ECPrivateKey)keyFactory.generatePrivate(pkcs8KeySpec);
    
64.         Signature sign = Signature.getInstance(signatureAl);//"SHA256withECDSA"
    
65.         sign.initSign(privateK);
    
66.         sign.update(Base64.getDecoder().decode(content));
    
67.         return Base64.getEncoder().encodeToString(sign.sign());
    
68.     }
    
69. 
    
70. /**
    
71.      * 用私钥对信息生成数字签名
    
72.      *
    
73.      * @param content       已加密数据 base64
    
74.      * @param priKey 私钥(BASE64编码)
    
75.      * @param signatureAl 签名算法
    
76.      * @return
    
77.      * @throws Exception
    
78.      */
    
79.     public static String sign(String content, String priKey,String signatureAl) throws Exception {
    
80.         PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(Base64.getDecoder().decode(priKey));
    
81.         KeyFactory keyFactory = KeyFactory.getInstance("EC");
    
82.         ECPrivateKey privateK = (ECPrivateKey)keyFactory.generatePrivate(pkcs8KeySpec);
    
83.         Signature sign = Signature.getInstance(signatureAl);//"SHA256withECDSA/"
    
84.         sign.initSign(privateK);
    
85.         sign.update(Base64.getDecoder().decode(content));
    
86.         return Base64.getEncoder().encodeToString(sign.sign());
    
87.     }
    
88. 
    
89. 
    

复制代码