信息计算2019级2班5号张欢

张欢

RSA加密及签名的实现

一、RSA加密及签名原理（来自网上）

RSA加密算法 RSA公钥加密体制包含如下3个算法：KeyGen（密钥生成算法），Encrypt（加密算法）以及Decrypt（解密算法）。

• 。密钥生成算法以安全常数作为输入，输出一个公钥PK，和一个私钥SK。安全常数用于确定这个加密算法的安全性有多高，一般以加密算法使用的质数p的大小有关。越大，质数p一般越大，保证体制有更高的安全性。在RSA中，密钥生成算法如下：算法首先随机产生两个不同大质数p和q，计算N=pq。随后，算法计算欧拉函数。接下来，算法随机选择一个小于的整数e，并计算e关于的模反元素d。最后，公钥为PK=(N, e)，私钥为SK=（N, d）。
• 。加密算法以公钥PK和待加密的消息M作为输入，输出密文CT。在RSA中，加密算法如下：算法直接输出密文为
• 。解密算法以私钥SK和密文CT作为输入，输出消息M。在RSA中，解密算法如下：算法直接输出明文为。由于e和d在下互逆，因此我们有：
  

所以，从算法描述中我们也可以看出：公钥用于对数据进行加密，私钥用于对数据进行解密。当然了，这个也可以很直观的理解：公钥就是公开的密钥，其公开了大家才能用它来加密数据。私钥是私有的密钥，谁有这个密钥才能够解密密文。否则大家都能看到私钥，就都能解密，那不就乱套了。

RSA签名算法 签名算法同样包含3个算法：KeyGen（密钥生成算法），Sign（签名算法），Verify（验证算法）。

• 。密钥生成算法同样以安全常数作为输入，输出一个公钥PK和一个私钥SK。在RSA签名中，密钥生成算法与加密算法完全相同。
• 。签名算法以私钥SK和待签名的消息M作为输入，输出签名。在RSA签名中，签名算法直接输出签名为。注意，签名算法和RSA加密体制中的解密算法非常像。
• 。验证算法以公钥PK，签名以及消息M作为输入，输出一个比特值b。b=1意味着验证通过。b=0意味着验证不通过。在RSA签名中，验证算法首先计算，随后对比M'与M，如果相等，则输出b=1，否则输出b=0。注意：验证算法和RSA加密体制中的加密算法非常像。
  

所以，在签名算法中，私钥用于对数据进行签名，公钥用于对签名进行验证。这也可以直观地进行理解：对一个文件签名，当然要用私钥，因为我们希望只有自己才能完成签字。验证过程当然希望所有人都能够执行，大家看到签名都能通过验证证明确实是我自己签的

二、运行结果

张欢

三、运行代码

1. package rsa;
   
2. 
   
3. import java.io.ByteArrayInputStream;
   
4. import java.io.ByteArrayOutputStream;
   
5. import java.io.InputStream;
   
6. import java.security.Key;
   
7. import java.security.KeyFactory;
   
8. import java.security.KeyPair;
   
9. import java.security.KeyPairGenerator;
   
10. import java.security.PrivateKey;
    
11. import java.security.PublicKey;
    
12. import java.security.interfaces.RSAPrivateKey;
    
13. import java.security.interfaces.RSAPublicKey;
    
14. import java.security.spec.PKCS8EncodedKeySpec;
    
15. import java.security.spec.X509EncodedKeySpec;
    
16. import java.util.Base64;
    
17. import javax.crypto.Cipher;
    
18. 
    
19. public class RSAUtil{
    
20.         
    
21.         public static final String  SIGN_ALGORITHMS = "SHA1WithRSA";
    
22.         
    
23.     /**加密算法RSA*/
    
24.     public static final String KEY_ALGORITHM = "RSA";
    
25.    
    
26.         /**RSA最大加密明文大小*/
    
27.     private static final int MAX_ENCRYPT_BLOCK = 117;
    
28.    
    
29.     /**RSA最大解密密文大小*/
    
30.     private static final int MAX_DECRYPT_BLOCK = 128;
    
31.         
    
32.         /**
    
33.         * RSA签名
    
34.         * @param content 待签名数据
    
35.         * @param privateKey 商户私钥
    
36.         * @param input_charset 编码格式
    
37.         */
    
38.         public static String sign(String content, String privateKey, String input_charset){
    
39.         try {
    
40.                 PKCS8EncodedKeySpec priPKCS8         = new PKCS8EncodedKeySpec(Base64_.decode(privateKey) );
    
41.                 KeyFactory keyf                                 = KeyFactory.getInstance(KEY_ALGORITHM);
    
42.                 PrivateKey priKey                                 = keyf.generatePrivate(priPKCS8);
    
43.             java.security.Signature signature = java.security.Signature.getInstance(SIGN_ALGORITHMS);
    
44.             signature.initSign(priKey);
    
45.             signature.update(content.getBytes(input_charset));
    
46.             byte[] signed = signature.sign();
    
47.             return Base64_.encode(signed);
    
48.         }catch (Exception e) {
    
49.                 e.printStackTrace();
    
50.         }
    
51.         return null;
    
52.     }
    
53.         
    
54.         /**
    
55.         * RSA验签名检查
    
56.         * @param content 待签名数据
    
57.         * @param sign 签名值
    
58.         * @param ali_public_key 支付宝公钥
    
59.         * @param input_charset 编码格式
    
60.         */
    
61.         public static boolean verify(String content, String sign, String ali_public_key, String input_charset){
    
62.                 try {
    
63.                         KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
    
64.                 byte[] encodedKey = Base64_.decode(ali_public_key);
    
65.                 PublicKey pubKey = keyFactory.generatePublic(new X509EncodedKeySpec(encodedKey));
    
66.                         java.security.Signature signature = java.security.Signature.getInstance(SIGN_ALGORITHMS);
    
67.                         signature.initVerify(pubKey);
    
68.                         signature.update(content.getBytes(input_charset) );
    
69.                         boolean bverify = signature.verify( Base64_.decode(sign) );
    
70.                         return bverify;
    
71.                 } catch (Exception e) {
    
72.                         e.printStackTrace();
    
73.                 }
    
74.                 return false;
    
75.         }
    
76.         
    
77.         /**
    
78.         * 私钥解密
    
79.         * @param content 密文
    
80.         * @param private_key 商户私钥
    
81.         * @param input_charset 编码格式
    
82.         */
    
83.         public static String decrypt(String content, String private_key, String input_charset) throws Exception {
    
84.         PrivateKey prikey = getPrivateKey(private_key);
    
85.         Cipher cipher = Cipher.getInstance(KEY_ALGORITHM);
    
86.         cipher.init(Cipher.DECRYPT_MODE, prikey);
    
87.         InputStream ins = new ByteArrayInputStream(Base64_.decode(content));
    
88.         ByteArrayOutputStream writer = new ByteArrayOutputStream();
    
89.         //rsa解密的字节大小最多是128，将需要解密的内容，按128位拆开解密
    
90.         byte[] buf = new byte[128];
    
91.         int bufl;
    
92.         while ((bufl = ins.read(buf)) != -1) {
    
93.             byte[] block = null;
    
94.             if (buf.length == bufl) {
    
95.                 block = buf;
    
96.             } else {
    
97.                 block = new byte[bufl];
    
98.                 for (int i = 0; i < bufl; i++) {
    
99.                     block[i] = buf[i];
    
100.                 }
     
101.             }
     
102.             writer.write(cipher.doFinal(block));
     
103.         }
     
104.         return new String(writer.toByteArray(), input_charset);
     
105.     }
     
106.         
     
107.         /**
     
108.      * 公钥加密
     
109.      * @param data 源数据
     
110.      * @param publicKey 公钥(BASE64编码)
     
111.      */
     
112.     public static byte[] encryptByPublicKey(byte[] data, String publicKey) throws Exception {
     
113.         byte[] keyBytes = Base64_.decode(publicKey);
     
114.         X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(keyBytes);
     
115.         KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
     
116.         Key publicK = keyFactory.generatePublic(x509KeySpec);
     
117.         // 对数据加密
     
118.         Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
     
119.         cipher.init(Cipher.ENCRYPT_MODE, publicK);
     
120.         int inputLen = data.length;
     
121.         ByteArrayOutputStream out = new ByteArrayOutputStream();
     
122.         int offSet = 0;
     
123.         byte[] cache;
     
124.         int i = 0;
     
125.         // 对数据分段加密
     
126.         while (inputLen - offSet > 0) {
     
127.             if (inputLen - offSet > MAX_ENCRYPT_BLOCK) {
     
128.                 cache = cipher.doFinal(data, offSet, MAX_ENCRYPT_BLOCK);
     
129.             } else {
     
130.                 cache = cipher.doFinal(data, offSet, inputLen - offSet);
     
131.             }
     
132.             out.write(cache, 0, cache.length);
     
133.             i++;
     
134.             offSet = i * MAX_ENCRYPT_BLOCK;
     
135.         }
     
136.         byte[] encryptedData = out.toByteArray();
     
137.         out.close();
     
138.         return encryptedData;
     
139.     }
     
140.    
     
141.     public static String encryptByPublicKeyToStr(byte[] data, String publicKey) throws Exception {
     
142.             byte[] bytes = encryptByPublicKey(data, publicKey);
     
143.             String result = Base64_.encode(bytes);
     
144.             return result;
     
145.     }
     
146.         
     
147.         /**
     
148.         * 得到私钥
     
149.         * @param key 密钥字符串（经过base64编码）
     
150.         * @throws Exception
     
151.         */
     
152.         public static PrivateKey getPrivateKey(String key) throws Exception {
     
153.                 byte[] keyBytes;
     
154.                 keyBytes = Base64_.decode(key);
     
155.                 PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(keyBytes);
     
156.                 KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
     
157.                 PrivateKey privateKey = keyFactory.generatePrivate(keySpec);
     
158.                 return privateKey;
     
159.         }
     
160.         
     
161.         public static class Base64_ {
     
162.                 private static final Base64.Decoder decoder = Base64.getDecoder();
     
163.                 private static final Base64.Encoder encoder = Base64.getEncoder();
     
164.                 public static byte[] decode(String key) {
     
165.                         if (key == null) { return null;}
     
166.                         byte[] decode = decoder.decode(key);
     
167.                         return decode;
     
168.                 }
     
169.                 public static String encode(byte[] content) {
     
170.                         if (content == null) {return null;}
     
171.                         String encode = encoder.encodeToString(content);
     
172.                         return encode;
     
173.                 }
     
174.         }
     
175.         
     
176.         /**
     
177.          * 测试
     
178.          */
     
179.         public static void main(String args[]) throws Exception{
     
180.         KeyPairGenerator keyPairGen = KeyPairGenerator.getInstance("RSA");
     
181.         keyPairGen.initialize(1024);
     
182.         KeyPair keyPair = keyPairGen.generateKeyPair();
     
183.         RSAPublicKey publicKey = (RSAPublicKey) keyPair.getPublic();
     
184.         RSAPrivateKey privateKey = (RSAPrivateKey) keyPair.getPrivate();
     
185.         String pubKey = Base64_.encode(publicKey.getEncoded()); //公钥
     
186.         String priKey = Base64_.encode(privateKey.getEncoded()); //私钥
     
187. //        System.out.println(pubKey);
     
188. //        System.out.println(priKey);
     
189.         
     
190. //......................................公钥加密，私钥解密！
     
191.         
     
192.         String sourceStr = "Wise men don't fall in love, but a few kings are rich all the way";
     
193.         //公钥加密
     
194.         byte[] ens = RSAUtil.encryptByPublicKey(sourceStr.getBytes(),pubKey);
     
195.         String encodes = Base64_.encode(ens);
     
196.         System.out.println("公钥加密后:"+encodes);
     
197.         //私钥解密
     
198.         String res2 = RSAUtil.decrypt(encodes, priKey, "UTF-8");
     
199.         System.out.println("私钥解密后:"+res2+"，翻译：智者不入爱河，寡王一路硕博");
     
200.         
     
201. //.......................................签名验证，私钥签名，公钥验证是否正确!
     
202.         
     
203.         String source = "id=shoig&name=shoer&age=23dnjlegj;reg"; //模拟请求参数,然后对此请求参数进行签名。
     
204.         
     
205.         String sign = RSAUtil.sign(source, priKey, "UTF-8");
     
206.         
     
207.         System.out.println("签名是："+sign);
     
208.         
     
209.         // 公钥验证签名是否正确.
     
210.         // 具体流程是，请求参数+sign发送给公钥方，然后公钥方过滤掉sign，用公钥验证其他参数是否通过。
     
211.         
     
212.         boolean result = RSAUtil.verify(source, sign, pubKey, "UTF-8");
     
213.         
     
214.         System.out.println("验签结果是："+result);
     
215.         
     
216.         }
     
217. }

复制代码

张欢

ECC椭圆曲线上公钥密码

一、ECC算法原理

ECC 是 Elliptic Curves Cryptography 的缩写，意为椭圆曲线密码编码学。和RSA算法一样，ECC算法也属于公开密钥算法。最初由 Koblitz 和 Miller 两人于1985年提出，其数学基础是利用椭圆曲线上的有理点构成Abel加法群上椭圆离散对数的计算困难性。

二、ECC 算法工作原理
ECC 算法加密过程

• A选定一条椭圆曲线Ep（a,b），并取曲线上一点作为基点G
  
• A选择一个私钥k，并生成公钥K=kG
• A将Ep（a,b）和k，G发送给B
• B收到后将明文编码到Ep（a,b）上一点M，并产生一个随机数r
• B计算点C1=M+rK，C2=rG
• B将C1，C2传给A
• A计算C1-kC2=M+rkG-krG=M
• A对M解码得到明文
  

攻击者只能得到Ep（a,b），G，K，C1，C2，没有k就无法得到M。
ECC 算法签名验签流程

• A选定一条椭圆曲线Ep（a，b），并取曲线上一点作为基点G
  
• A选择一个私钥k，并生成公钥K=kG
• A产生一个随机数r，计算R(x,y)=rG
• A计算Hash=SHA(M)，M‘=M(modp)
• A计算S=（Hash+M’k）/r(modp)
• B获得S和M’，Ep(a,b)，K，R(x,y)
• B计算Hash=SHA(M)，M’=M(modp)
• B计算R’=（Hash*G+M’K）/S=(HashG+M’*kG)*r/(Hash+M’k)=rG=R（x,y），若R’=R，则验签成功。
  

张欢

三、代码实现
EccUtil.java

1. package ecc1;
   
2. 
   
3. import java.math.BigInteger;
   
4. import java.util.Random;
   
5. 
   
6. public class EccUtil {
   
7.     static E e;// 椭圆曲线
   
8.     Pare pare;// 椭圆上的已知点
   
9.     long privatekey;// 7位速度变慢 私钥--随机
   
10.     Pare publickey;// 公钥
    
11. 
    
12.     public EccUtil() {
    
13.         super();
    
14.         Random rand = new Random();
    
15.         e = new E(BigInteger.probablePrime(30, rand).intValue(), rand.nextInt(1024), rand.nextInt(1024));
    
16.         this.privatekey = rand.nextInt(1024);// 7位速度变慢 私钥--随机
    
17.         this.pare = new Pare(rand.nextInt(10000000), rand.nextInt(10000000));
    
18.         this.publickey = this.pare.multiply(privatekey);// new Pare();
    
19.     }
    
20. 
    
21.     class E {// 表示椭圆曲线方程
    
22.         Long p;// 模p的椭圆群
    
23.         Long a;
    
24.         Long b;
    
25. 
    
26.         public E(long p, long a, long b) {
    
27.             super();
    
28.             this.p = p;
    
29.             this.a = a;
    
30.             this.b = b;
    
31.         }
    
32. 
    
33.     }
    
34. 
    
35.     class Message {// 传送消息的最小单元
    
36.         Pare pa;
    
37.         Pare pb;
    
38. 
    
39.         public Message(Pare pa, Pare pb) {
    
40.             super();
    
41.             this.pa = pa;
    
42.             this.pb = pb;
    
43.         }
    
44. 
    
45.         @Override
    
46.         public String toString() {
    
47.             return this.pa.toString() + " " + this.pb.toString();
    
48.         }
    
49.     }
    
50. 
    
51.     class Pare {// 椭圆曲线上的点(x,y)
    
52.         long x;
    
53.         long y;
    
54. 
    
55.         public Pare() {
    
56.             super();
    
57.         }
    
58. 
    
59.         public Pare(long x, long y) {
    
60.             super();
    
61. 
    
62.             this.x = x;
    
63.             this.y = y;
    
64.         }
    
65. 
    
66.         // 加法
    
67.         public Pare add(Pare pare) {
    
68.             if (this.x == Integer.MAX_VALUE) {// 为无穷大时O+P=P
    
69.                 return pare;
    
70.             }
    
71.             Pare res = new Pare();
    
72.             if (this.y == pare.y && this.x == pare.x) {// 相等时
    
73.                 long d = moddivision(3 * this.x * this.x + EccUtil.e.a, EccUtil.e.p, 2 * this.y);
    
74. 
    
75.                 res.x = d * d - 2 * this.x;
    
76.                 res.x = mod(res.x, EccUtil.e.p);
    
77. 
    
78.                 res.y = d * (this.x - res.x) - this.y;
    
79.                 res.y = mod(res.y, EccUtil.e.p);
    
80.             } else if (pare.x - this.x != 0) {
    
81.                 long d = moddivision(pare.y - this.y, EccUtil.e.p, pare.x - this.x);
    
82.                 res.x = d * d - this.x - pare.x;
    
83.                 res.x = mod(res.x, EccUtil.e.p);
    
84. 
    
85.                 res.y = d * (this.x - res.x) - this.y;
    
86.                 res.y = mod(res.y, EccUtil.e.p);
    
87.             } else {// P Q互逆,返回无穷大
    
88.                 res.x = Integer.MAX_VALUE;
    
89.                 res.y = Integer.MAX_VALUE;
    
90.             }
    
91. 
    
92.             return res;
    
93.         }
    
94. 
    
95.         // 减法
    
96.         public Pare less(Pare p) {
    
97.             p.y *= -1;
    
98.             return add(p);
    
99.         }
    
100. 
     
101.         // 乘法
     
102.         public Pare multiply(long num) {
     
103.             Pare p = new Pare(this.x, this.y);
     
104.             for (long i = 1; i < num; i++) {
     
105.                 p = p.add(this);
     
106.             }
     
107.             return p;
     
108.         }
     
109. 
     
110.         // 求余,解决负号问题
     
111.         public long mod(long a, long b) {
     
112.             a = a % b;
     
113.             while (a < 0) {
     
114.                 a += b;
     
115.             }
     
116.             return a;
     
117.         }
     
118. 
     
119.         public long moddivision(long a, long b, long c) {
     
120.             a = mod(a, b);
     
121.             c = mod(c, b);
     
122.             a = a * EccMath.exgcd(c, b);
     
123.             return mod(a, b);
     
124.         }
     
125. 
     
126.         @Override
     
127.         public String toString() {
     
128.             return EccTools.obox(EccTools.long2hexStr(this.x), 4) + " "
     
129.                     + EccTools.obox(EccTools.long2hexStr(this.y), 4);
     
130.         }
     
131.     }
     
132. 
     
133.     // 加密
     
134.     public Message encryption(Pare g, Pare pbk, Pare word) {
     
135.         pbk = g.multiply(privatekey);// 公钥
     
136.         int d = new Random().nextInt(1024);// 随机数
     
137.         Pare dg = g.multiply(d);
     
138.         Pare dp = pbk.multiply(d);
     
139.         Pare send = word.add(dp);
     
140.         return new Message(dg, send);
     
141.     }
     
142. 
     
143.     public String encryption(Pare g, Pare pbk, String word) {
     
144.         StringBuffer sb = new StringBuffer();
     
145.         Pare[] words = Str2Pares(word);
     
146.         for (int i = 0; i < words.length; i++) {
     
147.             sb.append(encryption(g, pbk, words[i]).toString());
     
148.             sb.append(" ");
     
149.         }
     
150.         return sb.toString();
     
151.     }
     
152. 
     
153.     public String encryption(String word) {
     
154.         StringBuffer sb = new StringBuffer();
     
155.         Pare[] words = Str2Pares(word);
     
156.         for (int i = 0; i < words.length; i++) {
     
157.             sb.append(encryption(this.pare, this.publickey, words[i]).toString());
     
158.             sb.append(" ");
     
159.         }
     
160.         return sb.toString();
     
161.     }
     
162. 
     
163.     // 解密
     
164.     public Pare decryption(Message m) {
     
165.         Pare pab = m.pa.multiply(this.privatekey);
     
166.         Pare result = m.pb.less(pab);
     
167.         return result;
     
168.     }
     
169. 
     
170.     public String decryption(String s) {
     
171.         StringBuffer sb = new StringBuffer();
     
172.         Message[] mes = hexStr2Messages(s);
     
173.         for (int i = 0; i < mes.length; i++) {
     
174.             sb.append(decryption(mes[i]).toString());
     
175.         }
     
176.         return EccTools.hexStr2Str(sb.toString().replace(" ", ""));
     
177.     }
     
178. 
     
179.     public static void print(Object o) {
     
180.         System.out.println(o);
     
181.     }
     
182. 
     
183.     // 将字符串转换为 值对
     
184.     public Pare[] Str2Pares(String string) {
     
185. 
     
186.         Pare[] pares;
     
187.         if (string.length() % 2 != 0) {
     
188.             pares = new Pare[string.length() / 2 + 1];
     
189.         } else {
     
190.             pares = new Pare[string.length() / 2];
     
191.         }
     
192.         char[] chars = string.toCharArray();
     
193.         int i = 0;
     
194.         for (i = 0; i < string.length() / 2; i++) {
     
195.             pares[i] = new Pare(chars[i * 2], chars[i * 2 + 1]);
     
196.         }
     
197.         if (string.length() % 2 != 0) {
     
198.             pares[i] = new Pare(chars[i * 2], 0);
     
199.         }
     
200.         return pares;
     
201.     }
     
202. 
     
203.     // 将值对转换成16进制字符串
     
204.     public String Pares2hexStr(Pare[] pares) {
     
205.         StringBuffer s = new StringBuffer();
     
206.         for (int i = 0; i < pares.length; i++) {
     
207.             s.append(pares[i].toString());
     
208.         }
     
209.         return s.toString();
     
210.     }
     
211. 
     
212.     // 将16进制字符串转为 消息串
     
213.     public Message[] hexStr2Messages(String s) {
     
214.         String[] ss = s.split(" ");
     
215.         Message[] mes = new Message[ss.length / 4];
     
216.         for (int i = 0; i < mes.length; i++) {
     
217.             long pax = EccTools.hexStr2long(ss[i * 4]);
     
218.             long pay = EccTools.hexStr2long(ss[i * 4 + 1]);
     
219.             long pbx = EccTools.hexStr2long(ss[i * 4 + 2]);
     
220.             long pby = EccTools.hexStr2long(ss[i * 4 + 3]);
     
221.             mes[i] = new Message(new Pare(pax, pay), new Pare(pbx, pby));
     
222.         }
     
223.         return mes;
     
224.     }
     
225. 
     
226.     // 将消息串转为16进制字符串
     
227.     public String Messages2hexStr(Message[] mes) {
     
228.         StringBuffer sb = new StringBuffer();
     
229.         for (int i = 0; i < mes.length; i++) {
     
230.             sb.append(mes[i].toString());
     
231.             sb.append(" ");
     
232.         }
     
233.         return sb.toString();
     
234.     }
     
235. 
     
236.     public static void main(String[] args) {
     
237.         EccUtil ecc = new EccUtil();
     
238.         print("私钥:" + ecc.privatekey);
     
239.         print("公钥:" + ecc.publickey);
     
240.         print("基点:" + ecc.pare);
     
241.         print("");
     
242.         String s = "智者不入爱河，寡王一路硕博";
     
243. 
     
244.         String jm = ecc.encryption(s);
     
245.         print("密文:   " + jm);
     
246.         String mw = ecc.decryption(jm);
     
247.         print("明文:   " + mw);
     
248. 
     
249.     }
     
250. }
     

复制代码

张欢

续：
EccMath.java

1. package ecc1;
   
2. 
   
3. import java.math.BigInteger;
   
4. 
   
5. public class EccMath {
   
6.     // 此方法求余数。prime:素数，primitive：本原元，random：随机数。
   
7.     public static long reaminder(long prime, long primitive, long random) {
   
8.         long reamin = primitive % prime;
   
9.         long currentreamin = reamin;
   
10.         String binary = Long.toBinaryString(random);
    
11.         System.out.println(binary);
    
12.         for (int i = 0; i < binary.length() - 1; i++) {
    
13.             if (binary.charAt(i + 1) == '0') {
    
14.                 currentreamin = (currentreamin * currentreamin) % prime;
    
15.             } else {
    
16.                 currentreamin = (currentreamin * currentreamin * reamin) % prime;
    
17.             }
    
18. 
    
19.         }
    
20. 
    
21.         return currentreamin;
    
22.     }
    
23. 
    
24.     public static BigInteger reaminder(BigInteger prime, BigInteger primitive, long random) {
    
25.         BigInteger reamin = primitive.mod(prime);
    
26.         BigInteger currentreamin = reamin;
    
27.         String binary = Long.toBinaryString(random);
    
28.         for (int i = 0; i < binary.length() - 1; i++) {
    
29.             if (binary.charAt(i + 1) == '0') {
    
30.                 currentreamin = currentreamin.multiply(currentreamin).mod(prime);
    
31.             } else {
    
32.                 currentreamin = currentreamin.multiply(currentreamin).multiply(reamin).mod(prime);
    
33.             }
    
34. 
    
35.         }
    
36.         return currentreamin;
    
37.     }
    
38. 
    
39.     public static BigInteger reaminder(String prim, String primitiv, String rand) {
    
40.         BigInteger prime = new BigInteger(prim);
    
41.         BigInteger primitive = new BigInteger(primitiv);
    
42.         Long random = new Long(rand);
    
43.         BigInteger reamin = primitive.mod(prime);
    
44.         BigInteger currentreamin = reamin;
    
45.         String binary = Long.toBinaryString(random);
    
46.         for (int i = 0; i < binary.length() - 1; i++) {
    
47.             if (binary.charAt(i + 1) == '0') {
    
48.                 currentreamin = currentreamin.multiply(currentreamin).mod(prime);
    
49.             } else {
    
50.                 currentreamin = currentreamin.multiply(currentreamin).multiply(reamin).mod(prime);
    
51.             }
    
52. 
    
53.         }
    
54.         return currentreamin;
    
55.     }
    
56. 
    
57.     // 此方法判断素数
    
58.     public static boolean isPrime(long num) {
    
59.         boolean flag = true;
    
60.         for (long i = 2; i < num / 2; i++) {
    
61.             if (num == 2) {
    
62.                 break;
    
63.             }
    
64.             if (num % i == 0) {
    
65.                 flag = false;
    
66.                 break;
    
67.             }
    
68.         }
    
69.         return flag;
    
70.     }
    
71. 
    
72.     // 求最大公约数:欧几里得算法，辗转相除法
    
73.     public static long gcd(long a, long b) {
    
74.         long reamin = a % b;
    
75.         if (reamin == 0) {
    
76.             return b;
    
77.         } else {
    
78.             return gcd(b, reamin);
    
79.         }
    
80.     }
    
81. 
    
82.     // 扩展的欧几里得算法求逆元，如果有返回值，没有返回-1
    
83.     public static long exgcd(long a, long b) {
    
84.         long x1 = 1, x2 = 0, x3 = b, y1 = 0, y2 = 1, y3 = a;
    
85.         while (true) {
    
86.             if (y3 == 0) {
    
87.                 return -1;
    
88.             }
    
89.             if (y3 == 1) {
    
90.                 return y2 > 0 ? y2 : y2 + b;
    
91.             }
    
92.             long t1, t2, t3;
    
93.             long q = x3 / y3;
    
94.             t1 = x1 - q * y1;
    
95.             t2 = x2 - q * y2;
    
96.             t3 = x3 - q * y3;
    
97.             x1 = y1;
    
98.             x2 = y2;
    
99.             x3 = y3;
    
100.             y1 = t1;
     
101.             y2 = t2;
     
102.             y3 = t3;
     
103.         }
     
104.     }
     
105. 
     
106.     public static BigInteger exgcd(BigInteger a, BigInteger b) {
     
107.         BigInteger x1 = BigInteger.ONE, x2 = BigInteger.ZERO, x3 = b, y1 = BigInteger.ZERO, y2 = BigInteger.ONE, y3 = a;
     
108.         while (true) {
     
109.             if (y3.equals(BigInteger.ZERO)) {
     
110.                 return BigInteger.ZERO.subtract(BigInteger.ONE);
     
111.             }
     
112.             if (y3.equals(BigInteger.ONE)) {
     
113.                 return y2;
     
114.             }
     
115.             BigInteger t1, t2, t3;
     
116.             BigInteger q = x3.divide(y3);// x3/y3;
     
117.             t1 = x1.subtract(q.multiply(y1));// x1-q*y1;
     
118.             t2 = x2.subtract(q.multiply(y2));// x2 - q*y2;
     
119.             t3 = x3.subtract(q.multiply(y3));// x3 - q*y3;
     
120.             x1 = y1;
     
121.             x2 = y2;
     
122.             x3 = y3;
     
123.             y1 = t1;
     
124.             y2 = t2;
     
125.             y3 = t3;
     
126.         }
     
127.     }
     
128. 
     
129. }
     
130. 
     

复制代码

EccTools.java

1. package ecc1;
   
2. 
   
3. public class EccTools {
   
4.     // 字符串左边补0直到长度为i
   
5.     public static String obox(String s, int i) {
   
6.         String ss = s;
   
7.         while (ss.length() < i) {
   
8.             ss = "0" + ss;
   
9.         }
   
10.         return ss;
    
11.     }
    
12. 
    
13.     // 字符串右边补0直到长度为i
    
14.     public static String boxo(String s, int i) {
    
15.         String ss = s;
    
16.         while (ss.length() < i) {
    
17.             ss += "0";
    
18.         }
    
19.         return ss;
    
20.     }
    
21. 
    
22.     // 将字符串变成16进制字符串
    
23.     public static String Str2hexStr(String s) {
    
24.         StringBuffer sb = new StringBuffer();
    
25.         for (int i = 0; i < s.length(); i++) {
    
26.             sb.append(obox(Integer.toHexString(s.charAt(i)), 4));
    
27.         }
    
28.         return sb.toString();
    
29.     }
    
30. 
    
31.     // 将16进制字符串变成字符串
    
32.     public static String hexStr2Str(String s) {
    
33.         StringBuffer sb = new StringBuffer();
    
34.         int index = 0;
    
35.         int length = s.length();
    
36.         while (index + 4 <= length) {
    
37.             String sh = s.substring(index, index + 4);
    
38.             sb.append((char) Integer.parseInt(sh, 16));
    
39.             index += 4;
    
40.         }
    
41.         if (sb.charAt(sb.length() - 1) == 0) {
    
42.             sb.deleteCharAt(sb.length() - 1);
    
43.         }
    
44.         return sb.toString();
    
45.     }
    
46. 
    
47.     // String数组转换为char数组
    
48.     public static char[] Ss2Cs(String[] s) {
    
49.         char[] result = new char[s.length];
    
50.         for (int i = 0; i < s.length; i++) {
    
51.             result[i] = (char) Integer.parseInt(s[i], 16);
    
52.         }
    
53.         return result;
    
54.     }
    
55. 
    
56.     // String转换为char数组
    
57.     public static char[] Str2Cs(String s) {
    
58.         char[] result = new char[s.length() / 2];
    
59.         for (int i = 0; i < s.length() / 2; i++) {
    
60.             StringBuffer sb = new StringBuffer();
    
61.             sb.append(s.charAt(i * 2));
    
62.             sb.append(s.charAt(i * 2 + 1));
    
63.             result[i] = (char) Integer.parseInt(sb.toString(), 16);
    
64.         }
    
65.         return result;
    
66.     }
    
67. 
    
68.     // hexString转换为数组
    
69.     public static char[] hexStr2Cs(String s) {
    
70. 
    
71.         char[] result = new char[s.length() / 2];
    
72.         for (int i = 0; i < s.length() / 2; i++) {
    
73.             StringBuffer sb = new StringBuffer();
    
74.             sb.append(s.charAt(i * 2));
    
75.             sb.append(s.charAt(i * 2 + 1));
    
76.             result[i] = (char) Integer.parseInt(sb.toString(), 16);
    
77.         }
    
78.         return result;
    
79.     }
    
80. 
    
81.     // char数组转换为String数组
    
82.     public static String[] Cs2Ss(char[] s) {
    
83.         String[] result = new String[s.length];
    
84.         for (int i = 0; i < s.length; i++) {
    
85.             result[i] = Integer.toHexString(s[i]);
    
86.         }
    
87.         return result;
    
88.     }
    
89. 
    
90.     // char数组转换为hexString
    
91.     public static String Cs2hexStr(char[] s) {
    
92.         StringBuffer sb = new StringBuffer();
    
93.         for (int i = 0; i < s.length; i++) {
    
94.             sb.append(obox(Integer.toHexString(s[i]), 2));
    
95.         }
    
96.         return sb.toString();
    
97.     }
    
98. 
    
99.     // long转换为hexString
    
100.     public static String long2hexStr(long lo) {
     
101. 
     
102.         return Long.toHexString(lo);
     
103.     }
     
104. 
     
105.     // longs数组转换为hexString
     
106.     public static String longs2hexStr(long[] lo) {
     
107.         StringBuffer sb = new StringBuffer();
     
108.         for (int i = 0; i < lo.length; i++) {
     
109.             sb.append(Long.toHexString(lo[0]));
     
110.             sb.append(" ");
     
111.         }
     
112.         return sb.toString();
     
113.     }
     
114. 
     
115.     // hexString转换为long
     
116.     public static long hexStr2long(String s) {
     
117.         return Long.parseLong(s, 16);
     
118.     }
     
119. 
     
120.     // hexString转换为long数组
     
121.     public static long[] hexStr2longs(String s) {
     
122.         String[] ss = s.split(" ");
     
123.         long[] ls = new long[ss.length];
     
124.         for (int i = 0; i < ls.length; i++) {
     
125.             ls[i] = Long.parseLong(ss[i], 16);
     
126.         }
     
127.         return ls;
     
128.     }
     
129. 
     
130. }
     
131. 
     

复制代码

四、运行结果