信息计算2019级2班9号范承蝶

范承蝶

一、RSA加解密和签名：
1、RSA加密介绍：
RSA加密是一种非对称加密。可以在不直接传递密钥的情况下，完成解密。者能够确保信息的安全性，避免了直接传递密钥所造成的被破解的风险。是由一对密钥来进行加解密的过程，分别称之为公钥和私钥。如果用公钥进行加密，则只能通过对应的私钥去解密，如果用私钥进行加密，则只能通过对应的公钥去解密。两者之间有数字相关，该加密发酸的原理就是对一极大整数做因数分解的困难行来保证安全性。通常个人保存私钥，公钥是公开的（可能同时多人持有）。
2、RSA加密和签名的区别：
加密和签名都是为了安全性考虑，但略有不同。常有人问加密和签名使用私钥还是公钥？其实都是对加密和签名的作用有所混淆。简单的说，加密是为了防止信息被泄露，而签名是为了防止信息被篡改。
3、源代码：
（1）RSACode

1. package test;
   
2. 
   
3. import java.io.ByteArrayOutputStream;
   
4. import java.security.Key;
   
5. import java.security.KeyFactory;
   
6. import java.security.KeyPair;
   
7. import java.security.KeyPairGenerator;
   
8. import java.security.PrivateKey;
   
9. import java.security.PublicKey;
   
10. import java.security.Signature;
    
11. import java.security.interfaces.RSAPrivateKey;
    
12. import java.security.interfaces.RSAPublicKey;
    
13. import java.security.spec.PKCS8EncodedKeySpec;
    
14. import java.security.spec.X509EncodedKeySpec;
    
15. import java.util.HashMap;
    
16. import java.util.Map;
    
17. 
    
18. import javax.crypto.Cipher;
    
19. 
    
20. public class RSA {
    
21. 
    
22.     /*
    
23.      * 加密算法RSA
    
24.      */
    
25.     public static final String KEY_ALGORITHM = "RSA";
    
26. 
    
27.     /**
    
28.      * 签名算法
    
29.      */
    
30.     public static final String SIGNATURE_ALGORITHM = "MD5withRSA";
    
31. 
    
32.     /**
    
33.      * 获取公钥的key
    
34.      */
    
35.     private static final String PUBLIC_KEY = "RSAPublicKey";
    
36. 
    
37.     /**
    
38.      * 获取私钥的key
    
39.      */
    
40.     private static final String PRIVATE_KEY = "RSAPrivateKey";
    
41. 
    
42.     /**
    
43.      * RSA最大加密明文大小
    
44.      */
    
45.     private static final int MAX_ENCRYPT_BLOCK = 117;
    
46. 
    
47.     /**
    
48.      * RSA最大解密密文大小
    
49.      */
    
50.     private static final int MAX_DECRYPT_BLOCK = 128;
    
51. 
    
52.     //生成密钥对(公钥和私钥)
    
53.     public static Map<String, Object> genKeyPair() throws Exception {
    
54.         KeyPairGenerator keyPairGen = KeyPairGenerator.getInstance(KEY_ALGORITHM);
    
55.         keyPairGen.initialize(1024);
    
56.         KeyPair keyPair = keyPairGen.generateKeyPair();
    
57.         RSAPublicKey publicKey = (RSAPublicKey) keyPair.getPublic();
    
58.         RSAPrivateKey privateKey = (RSAPrivateKey) keyPair.getPrivate();
    
59.         Map<String, Object> keyMap = new HashMap<String, Object>(2);
    
60.         keyMap.put(PUBLIC_KEY, publicKey);
    
61.         keyMap.put(PRIVATE_KEY, privateKey);
    
62.         return keyMap;
    
63.     }
    
64. 
    
65.    
    
66.     //用私钥对信息生成数字签名
    
67.     public static String sign(byte[] data, String privateKey) throws Exception {
    
68.         byte[] keyBytes = Base64.decode(privateKey);
    
69.         PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(keyBytes);
    
70.         KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
    
71.         PrivateKey privateK = keyFactory.generatePrivate(pkcs8KeySpec);
    
72.         Signature signature = Signature.getInstance(SIGNATURE_ALGORITHM);
    
73.         signature.initSign(privateK);
    
74.         signature.update(data);
    
75.         return Base64.encode(signature.sign());
    
76.     }
    
77. 
    
78.    
    
79.     //校验数字签名
    
80.     public static boolean verify(byte[] data, String publicKey, String sign)
    
81.             throws Exception {
    
82.         byte[] keyBytes = Base64.decode(publicKey);
    
83.         X509EncodedKeySpec keySpec = new X509EncodedKeySpec(keyBytes);
    
84.         KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
    
85.         PublicKey publicK = keyFactory.generatePublic(keySpec);
    
86.         Signature signature = Signature.getInstance(SIGNATURE_ALGORITHM);
    
87.         signature.initVerify(publicK);
    
88.         signature.update(data);
    
89.         return signature.verify(Base64.decode(sign));
    
90.     }
    
91. 
    
92.     //私钥解密
    
93.     public static byte[] decryptByPrivateKey(byte[] encryptedData, String privateKey)
    
94.             throws Exception {
    
95.         byte[] keyBytes = Base64.decode(privateKey);
    
96.         PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(keyBytes);
    
97.         KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
    
98.         Key privateK = keyFactory.generatePrivate(pkcs8KeySpec);
    
99.         Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
    
100.         cipher.init(Cipher.DECRYPT_MODE, privateK);
     
101.         int inputLen = encryptedData.length;
     
102.         ByteArrayOutputStream out = new ByteArrayOutputStream();
     
103.         int offSet = 0;
     
104.         byte[] cache;
     
105.         int i = 0;
     
106.         // 对数据分段解密
     
107.         while (inputLen - offSet > 0) {
     
108.             if (inputLen - offSet > MAX_DECRYPT_BLOCK) {
     
109.                 cache = cipher.doFinal(encryptedData, offSet, MAX_DECRYPT_BLOCK);
     
110.             } else {
     
111.                 cache = cipher.doFinal(encryptedData, offSet, inputLen - offSet);
     
112.             }
     
113.             out.write(cache, 0, cache.length);
     
114.             i++;
     
115.             offSet = i * MAX_DECRYPT_BLOCK;
     
116.         }
     
117.         byte[] decryptedData = out.toByteArray();
     
118.         out.close();
     
119.         return decryptedData;
     
120.     }
     
121. 
     
122.   
     
123.     //公钥解密
     
124.     public static byte[] decryptByPublicKey(byte[] encryptedData, String publicKey)
     
125.             throws Exception {
     
126.         byte[] keyBytes = Base64.decode(publicKey);
     
127.         X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(keyBytes);
     
128.         KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
     
129.         Key publicK = keyFactory.generatePublic(x509KeySpec);
     
130.         Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
     
131.         cipher.init(Cipher.DECRYPT_MODE, publicK);
     
132.         int inputLen = encryptedData.length;
     
133.         ByteArrayOutputStream out = new ByteArrayOutputStream();
     
134.         int offSet = 0;
     
135.         byte[] cache;
     
136.         int i = 0;
     
137.         // 对数据分段解密
     
138.         while (inputLen - offSet > 0) {
     
139.             if (inputLen - offSet > MAX_DECRYPT_BLOCK) {
     
140.                 cache = cipher.doFinal(encryptedData, offSet, MAX_DECRYPT_BLOCK);
     
141.             } else {
     
142.                 cache = cipher.doFinal(encryptedData, offSet, inputLen - offSet);
     
143.             }
     
144.             out.write(cache, 0, cache.length);
     
145.             i++;
     
146.             offSet = i * MAX_DECRYPT_BLOCK;
     
147.         }
     
148.         byte[] decryptedData = out.toByteArray();
     
149.         out.close();
     
150.         return decryptedData;
     
151.     }
     
152. 
     
153.    
     
154.     //公钥加密
     
155.     public static byte[] encryptByPublicKey(byte[] data, String publicKey)
     
156.             throws Exception {
     
157.         byte[] keyBytes = Base64.decode(publicKey);
     
158.         X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(keyBytes);
     
159.         KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
     
160.         Key publicK = keyFactory.generatePublic(x509KeySpec);
     
161.         // 对数据加密
     
162.         Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
     
163.         cipher.init(Cipher.ENCRYPT_MODE, publicK);
     
164.         int inputLen = data.length;
     
165.         ByteArrayOutputStream out = new ByteArrayOutputStream();
     
166.         int offSet = 0;
     
167.         byte[] cache;
     
168.         int i = 0;
     
169.         // 对数据分段加密
     
170.         while (inputLen - offSet > 0) {
     
171.             if (inputLen - offSet > MAX_ENCRYPT_BLOCK) {
     
172.                 cache = cipher.doFinal(data, offSet, MAX_ENCRYPT_BLOCK);
     
173.             } else {
     
174.                 cache = cipher.doFinal(data, offSet, inputLen - offSet);
     
175.             }
     
176.             out.write(cache, 0, cache.length);
     
177.             i++;
     
178.             offSet = i * MAX_ENCRYPT_BLOCK;
     
179.         }
     
180.         byte[] encryptedData = out.toByteArray();
     
181.         out.close();
     
182.         return encryptedData;
     
183.     }
     
184. 
     
185.    
     
186.     //私钥加密
     
187.     public static byte[] encryptByPrivateKey(byte[] data, String privateKey)
     
188.             throws Exception {
     
189.         byte[] keyBytes = Base64.decode(privateKey);
     
190.         PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(keyBytes);
     
191.         KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
     
192.         Key privateK = keyFactory.generatePrivate(pkcs8KeySpec);
     
193.         Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
     
194.         cipher.init(Cipher.ENCRYPT_MODE, privateK);
     
195.         int inputLen = data.length;
     
196.         ByteArrayOutputStream out = new ByteArrayOutputStream();
     
197.         int offSet = 0;
     
198.         byte[] cache;
     
199.         int i = 0;
     
200.         // 对数据分段加密
     
201.         while (inputLen - offSet > 0) {
     
202.             if (inputLen - offSet > MAX_ENCRYPT_BLOCK) {
     
203.                 cache = cipher.doFinal(data, offSet, MAX_ENCRYPT_BLOCK);
     
204.             } else {
     
205.                 cache = cipher.doFinal(data, offSet, inputLen - offSet);
     
206.             }
     
207.             out.write(cache, 0, cache.length);
     
208.             i++;
     
209.             offSet = i * MAX_ENCRYPT_BLOCK;
     
210.         }
     
211.         byte[] encryptedData = out.toByteArray();
     
212.         out.close();
     
213.         return encryptedData;
     
214.     }
     
215. 
     
216.   
     
217.     //获取私钥
     
218.     public static String getPrivateKey(Map<String, Object> keyMap)
     
219.             throws Exception {
     
220.         Key key = (Key) keyMap.get(PRIVATE_KEY);
     
221.         return Base64.encode(key.getEncoded());
     
222.     }
     
223. 
     
224.    // 获取公钥
     
225.     public static String getPublicKey(Map<String, Object> keyMap)
     
226.             throws Exception {
     
227.         Key key = (Key) keyMap.get(PUBLIC_KEY);
     
228.         return Base64.encode(key.getEncoded());
     
229.     }
     
230. }

复制代码

范承蝶

RSA代码后续以及测试运行截图：
（2）Base64Code

1. package test;
   
2. 
   
3. public class Base64{
   
4.   private static char[] Base64Code = {
   
5.     'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
   
6.     'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
   
7.     'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd',
   
8.    'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
   
9.     'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
   
10.     'y', 'z', '0', '1', '2', '3', '4', '5', '6', '7',
    
11.     '8', '9', '+', '/' };
    
12. 
    
13.   private static byte[] Base64Decode = {
    
14.     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    
15.     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    
16.     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    
17.     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    
18.     -1, -1, -1, 62, -1, 63, -1, 63, 52, 53,
    
19.     54, 55, 56, 57, 58, 59, 60, 61, -1, -1,
    
20.     -1, 0, -1, -1, -1, 0, 1, 2, 3, 4,
    
21.     5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
    
22.     15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
    
23.     25, -1, -1, -1, -1, -1, -1, 26, 27, 28,
    
24.     29, 30, 31, 32, 33, 34, 35, 36, 37, 38,
    
25.     39, 40, 41, 42, 43, 44, 45, 46, 47, 48,
    
26.     49, 50, 51, -1, -1, -1, -1, -1 };
    
27. 
    
28.    public static String encode(byte[] b)
    
29.    {
    
30.     int code = 0;
    
31.     if (b == null)
    
32.       return null;
    
33.     StringBuffer sb = new StringBuffer((b.length - 1) / 3 << 6);
    
34.     for (int i = 0; i < b.length; i++)
    
35.      {
    
36.       code |= b[i] << 16 - i % 3 * 8 & 255 << 16 - i % 3 * 8;
    
37.       if ((i % 3 != 2) && (i != b.length - 1))
    
38.          continue;
    
39.       sb.append(Base64Code[((code & 0xFC0000) >>> 18)]);
    
40.       sb.append(Base64Code[((code & 0x3F000) >>> 12)]);
    
41.       sb.append(Base64Code[((code & 0xFC0) >>> 6)]);
    
42.       sb.append(Base64Code[(code & 0x3F)]);
    
43.       code = 0;
    
44.      }
    
45. 
    
46.     if (b.length % 3 > 0)
    
47.       sb.setCharAt(sb.length() - 1, '=');
    
48.     if (b.length % 3 == 1)
    
49.       sb.setCharAt(sb.length() - 2, '=');
    
50.     return sb.toString();
    
51.    }
    
52. 
    
53.    public static byte[] decode(String code)
    
54.    {
    
55.     if (code == null)
    
56.       return null;
    
57.     int len = code.length();
    
58.     if (len % 4 != 0)
    
59.       throw new IllegalArgumentException("Base64 string length must be 4*n");
    
60.     if (code.length() == 0)
    
61.       return new byte[0];
    
62.     int pad = 0;
    
63.     if (code.charAt(len - 1) == '=')
    
64.       pad++;
    
65.     if (code.charAt(len - 2) == '=')
    
66.       pad++;
    
67.     int retLen = len / 4 * 3 - pad;
    
68.     byte[] ret = new byte[retLen];
    
69.     for (int i = 0; i < len; i += 4)
    
70.      {
    
71.       int j = i / 4 * 3;
    
72.       char ch1 = code.charAt(i);
    
73.       char ch2 = code.charAt(i + 1);
    
74.       char ch3 = code.charAt(i + 2);
    
75.       char ch4 = code.charAt(i + 3);
    
76.        int tmp = Base64Decode[ch1] << 18 | Base64Decode[ch2] << 12 | Base64Decode[ch3] << 6 | Base64Decode[ch4];
    
77.       ret[j] = (byte)((tmp & 0xFF0000) >> 16);
    
78.       if (i < len - 4)
    
79.        {
    
80.         ret[(j + 1)] = (byte)((tmp & 0xFF00) >> 8);
    
81.         ret[(j + 2)] = (byte)(tmp & 0xFF);
    
82.        }
    
83.        else {
    
84.         if (j + 1 < retLen)
    
85.           ret[(j + 1)] = (byte)((tmp & 0xFF00) >> 8);
    
86.         if (j + 2 < retLen)
    
87.           ret[(j + 2)] = (byte)(tmp & 0xFF);
    
88.        }
    
89.      }
    
90.     return ret;
    
91.    }
    
92. }
    

复制代码

（3）RSATest

1. import java.util.Map;
   
2. 
   
3. import test.RSA;
   
4. 
   
5. public class RSATest {
   
6.     static String publicKey;
   
7.     static String privateKey;
   
8. 
   
9.     static {
   
10.         try {
    
11.             Map<String, Object> keyMap = RSA.genKeyPair();
    
12.             publicKey = RSA.getPublicKey(keyMap);
    
13.             privateKey = RSA.getPrivateKey(keyMap);
    
14.             System.err.println("公钥: " + publicKey);
    
15.             System.err.println("私钥: " + privateKey);
    
16.         } catch (Exception e) {
    
17.             e.printStackTrace();
    
18.         }
    
19.     }
    
20. 
    
21.     public static void main(String[] args) throws Exception {
    
22.         test();
    
23.         testSign();
    
24.     }
    
25. 
    
26.     static void test() throws Exception {
    
27.         System.err.println("公钥加密——私钥解密");
    
28.         String source = "一边清零，一边拥有";
    
29.         System.out.println("加密前文字：" + source);
    
30.         byte[] data = source.getBytes();
    
31.         //公钥加密
    
32.         byte[] encodedData = RSA.encryptByPublicKey(data, publicKey);
    
33.         System.out.println("加密后文字：" + new String(encodedData));
    
34.         //私钥解密
    
35.         byte[] decodedData = RSA.decryptByPrivateKey(encodedData, privateKey);
    
36.         String target = new String(decodedData);
    
37.         System.out.println("解密后文字: " + target);
    
38.     }
    
39. 
    
40.     static void testSign() throws Exception {
    
41.         System.err.println("私钥加密——公钥解密");
    
42.         String source = "一边清零，一边拥有";
    
43.         System.out.println("原文字：" + source);
    
44.         byte[] data = source.getBytes();
    
45.         //私钥加密
    
46.         byte[] encodedData = RSA.encryptByPrivateKey(data, privateKey);
    
47.         System.out.println("加密后：" + new String(encodedData));
    
48.         //公钥解密
    
49.         byte[] decodedData = RSA.decryptByPublicKey(encodedData, publicKey);
    
50.         String target = new String(decodedData);
    
51.         System.out.println("解密后: " + target);
    
52. 
    
53.         System.err.println("私钥签名——公钥验证签名");
    
54.         String sign = RSA.sign(encodedData, privateKey);
    
55.         System.err.println("签名:\r" + sign);
    
56.         boolean status = RSA.verify(encodedData, publicKey, sign);
    
57.         System.err.println("验证结果:\r" + status);
    
58.     }
    
59. }

复制代码

4、运行截图：

范承蝶

二、椭圆曲线上公钥密码
1、椭圆加密算法介绍：
椭圆加密算法（ECC）是一种公钥加密体制，最初由Koblitz和Miller两人于1985年提出，其数学基础是利用椭圆曲线上的有理点构成Abel加法群上椭圆离散对数的计算困难性。公钥密码体制根据其所依据的难题一般分为三类：大素数分解问题类、离散对数问题类、椭圆曲线类。有时也把椭圆曲线类归为离散对数类。
2、原理：
(1)计算该椭圆曲线上所有在有限域GF(89)上的点；
(2)实现椭圆曲线上任意一个点P(例如P=(12,5))的倍点运算的递归算法，即计算k*P( k=2,3,…)；
(3)利用此递归算法找出椭圆曲线上的所有生成元G以及它们的阶n，即满足n*G=O。
3、源代码：

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #include<string.h>
   
4. #include<math.h>
   
5. #include<time.h>
   
6. #define MAX 100
   
7. 
   
8. typedef struct point{
   
9.         int point_x;
   
10.         int point_y;
    
11. }Point;
    
12. typedef struct ecc{
    
13.         struct point p[MAX];
    
14.         int len;
    
15. }ECCPoint;
    
16. typedef struct generator{
    
17.         Point p;
    
18.         int p_class;
    
19. }GENE_SET;
    
20. 
    
21. void get_all_points();
    
22. int int_sqrt(int s);
    
23. Point timesPiont(int k,Point p);
    
24. Point add_two_points(Point p1,Point p2);
    
25. int inverse(int n,int b);
    
26. void get_generetor_class();
    
27. void encrypt_ecc();
    
28. void decrypt_ecc();
    
29. int mod_p(int s);
    
30. void print();
    
31. int isPrime(int n);
    
32. 
    
33. char alphabet[30]="abcdefghijklmnopqrstuvwxyz";
    
34. int a=-1,b=0,p=89;//椭圆曲线为E89(-1,0)： y2=x3-x (mod 89)
    
35. ECCPoint eccPoint;
    
36. GENE_SET geneSet[MAX];
    
37. int geneLen;
    
38. char plain[]="yes";
    
39. int m[MAX];
    
40. int cipher[MAX];
    
41. int nB;//私钥
    
42. Point P1,P2,Pt,G,PB;
    
43. Point Pm;
    
44. int C[MAX];
    
45. 
    
46. int main()
    
47. {       
    
48.         get_generetor_class();
    
49.         encrypt_ecc();
    
50.         decrypt_ecc();
    
51.         return 0;
    
52. }
    
53. //task4:加密
    
54. void encrypt_ecc()
    
55. {
    
56.         int num,i,j;
    
57.         int gene_class;
    
58.         int num_t;
    
59.         int k;
    
60.         srand(time(NULL));
    
61.         //明文转换过程
    
62.         for(i=0;i<strlen(plain);i++)
    
63.         {
    
64.                 for(j=0;j<26;j++) //for(j=0;j<26;j++)
    
65.                 {
    
66.                         if(plain[i]==alphabet[j])
    
67.                         {
    
68.                                 m[i]=j;//将字符串明文换成数字，并存到整型数组m里面
    
69.                         }
    
70.                 }         
    
71.         }
    
72.         //选择生成元
    
73.         num=rand()%geneLen;
    
74.         gene_class=geneSet[num].p_class;
    
75.         while(isPrime(gene_class)==-1)//不是素数
    
76.         {
    
77.                  num=rand()%(geneLen-3)+3;
    
78.                  gene_class=geneSet[num].p_class;
    
79.         }       
    
80.         G=geneSet[num].p;
    
81.         nB=rand()%(gene_class-1)+1;//选择私钥
    
82.         PB=timesPiont(nB,G);
    
83.         printf("\n公钥：\n");
    
84.         printf("一边清零，一边拥有");
    
85.         printf("\n私钥：\n");
    
86.         printf("nB=%d\n",nB);
    
87.         //加密
    
88.         //
    
89.         k=rand()%(gene_class-2)+1;
    
90.         P1=timesPiont(k,G);
    
91.         //
    
92.         num_t=rand()%eccPoint.len; //选择映射点
    
93.         Pt=eccPoint.p[num_t];
    
94.         P2=timesPiont(k,PB);
    
95.         Pm=add_two_points(Pt,P2);
    
96.         printf("加密数据：\n");
    
97.         printf("kG=(%d,%d),Pt+kPB=(%d,%d),C={",P1.point_x,P1.point_y,Pm.point_x,Pm.point_y);
    
98.         for(i=0;i<strlen(plain);i++)
    
99.         {
    
100.                 C[i]=m[i]*Pt.point_x+Pt.point_y;
     
101.                 printf("{%d}",C[i]);
     
102.         }       
     
103.         printf("}\n");
     
104. }
     
105. //task5:解密
     
106. void decrypt_ecc()
     
107. {
     
108.         Point temp,temp1;
     
109.         int m,i;
     
110.         temp=timesPiont(nB,P1);
     
111.         temp.point_y=0-temp.point_y;
     
112.         temp1=add_two_points(Pm,temp);//求解Pt
     
113.         printf("\n解密结果：\n");
     
114.         for(i=0;i<strlen(plain);i++)
     
115.         {
     
116.                 m=(C[i]-temp1.point_y)/temp1.point_x;
     
117.                 printf("%c",alphabet[m]);//输出密文
     
118.         }
     
119.         printf("\n");
     
120. }
     
121. //判断是否为素数
     
122. int isPrime(int n)
     
123. {
     
124.         int i,k;
     
125.     k = sqrt(n);
     
126.     for (i = 2; i <= k;i++)
     
127.     {
     
128.             if (n%i == 0)
     
129.                         break;
     
130.         }      
     
131.     if (i <=k){
     
132.             return -1;
     
133.         }
     
134.     else {
     
135.              return 0;
     
136.         }
     
137. }
     
138. //task3:求生成元以及阶
     
139. void get_generetor_class()
     
140. {       
     
141.         int i,j=0;
     
142.         int count=1;
     
143.         Point p1,p2;
     
144.         get_all_points();       
     
145.         printf("\n**********************************输出生成元以及阶：*************************************\n");
     
146.         for(i=0;i<eccPoint.len;i++)
     
147.         {
     
148.                 count=1;
     
149.                 p1.point_x=p2.point_x=eccPoint.p[i].point_x;
     
150.                 p1.point_y=p2.point_y=eccPoint.p[i].point_y;               
     
151.                 while(1)
     
152.                 {       
     
153.                         p2=add_two_points(p1,p2);                                       
     
154.                         if(p2.point_x==-1 && p2.point_y==-1)
     
155.                         {
     
156.                                 break;
     
157.                         }
     
158.                         count++;
     
159.                         if(p2.point_x==p1.point_x)
     
160.                         {
     
161.                                 break;
     
162.                         }                                               
     
163.                 }
     
164.                 count++;
     
165.                 if(count<=eccPoint.len+1)
     
166.                 {
     
167.                         geneSet[j].p.point_x=p1.point_x;
     
168.                         geneSet[j].p.point_y=p1.point_y;
     
169.                         geneSet[j].p_class=count;
     
170.                         printf("(%d,%d)--->>%d\t",geneSet[j].p.point_x,geneSet[j].p.point_y,geneSet[j].p_class);
     
171.                         j++;
     
172.                         if(j % 6 ==0){
     
173.                                 printf("\n");
     
174.                         }
     
175.                 }
     
176.                 geneLen=j;       
     
177.         }
     
178. }
     
179. 
     
180. //task2:倍点运算的递归算法
     
181. Point timesPiont(int k,Point p0)
     
182. {
     
183.         if(k==1){
     
184.                 return p0;
     
185.         }                
     
186.         else if(k==2){
     
187.                 return add_two_points(p0,p0);
     
188.         }else{
     
189.                 return add_two_points(p0,timesPiont(k-1,p0));
     
190.         }
     
191. }
     
192. 
     
193. //两点的加法运算
     
194. Point add_two_points(Point p1,Point p2)
     
195. {
     
196.         long t;
     
197.         int x1=p1.point_x;
     
198.         int y1=p1.point_y;
     
199.         int x2=p2.point_x;
     
200.         int y2=p2.point_y;
     
201.         int tx,ty;
     
202.         int x3,y3;
     
203.         int flag=0;
     
204.         //求
     
205.         if((x2==x1)&& (y2==y1) )
     
206.         {
     
207.                 //相同点相加
     
208.                 if(y1==0)
     
209.                 {
     
210.                         flag=1;
     
211.                 }else{
     
212.                         t=(3*x1*x1+a)*inverse(p,2*y1) % p;
     
213.                 }
     
214.         }else{
     
215.                 //不同点相加
     
216.                 ty=y2-y1;
     
217.                 tx=x2-x1;
     
218.                 while(ty<0){
     
219.                         ty+=p;}
     
220.                 while(tx<0)
     
221.                 {tx+=p;}
     
222.                 if(tx==0 && ty !=0)
     
223.                 {flag=1;}
     
224.                 else{t=ty*inverse(p,tx) % p;}
     
225.         }
     
226.         if(flag==1)
     
227.         {p2.point_x=-1;p2.point_y=-1;}
     
228.         else{
     
229.                 x3=(t*t-x1-x2) % p;
     
230.                 y3=(t*(x1-x3)-y1) % p;
     
231.         //使结果在有限域GF(P)上
     
232.                 while(x3<0)
     
233.                 {x3+=p;}
     
234.                 while(y3<0)
     
235.                 {y3+=p;}
     
236.                 p2.point_x=x3;
     
237.                 p2.point_y=y3;}       
     
238.         return p2;
     
239. }
     
240. //求b关于n的逆元
     
241. int inverse(int n,int b)
     
242. {
     
243.         int q,r,r1=n,r2=b,t,t1=0,t2=1,i=1;
     
244.         while(r2>0)
     
245.         {
     
246.                 q=r1/r2; r=r1%r2;
     
247.                 r1=r2; r2=r;
     
248.                 t=t1-q*t2; t1=t2; t2=t;
     
249.         }
     
250.         if(t1>=0)
     
251.                 return t1%n;
     
252.         else{  
     
253.                 while((t1+i*n)<0)
     
254.                         i++;
     
255.                 return t1+i*n;
     
256.         }
     
257. }
     
258. //task1:求出椭圆曲线上所有点
     
259. void get_all_points()
     
260. {
     
261.         int i=0;int j=0;
     
262.         int s,y=0;int n=0,q=0;
     
263.         int modsqrt=0; int flag=0;
     
264.         if (4 * a * a * a + 27 * b * b != 0)
     
265.         {
     
266.                 for(i=0;i<=p-1;i++)
     
267.                 {
     
268.                         flag=0;
     
269.                         n=1;
     
270.                         y=0;
     
271.                         s= i * i * i + a * i + b;
     
272.                         while(s<0)
     
273.                         {
     
274.                                 s+=p;
     
275.                         }
     
276.                         s=mod_p(s);
     
277.                         modsqrt=int_sqrt(s);
     
278.                         if(modsqrt!=-1)
     
279.                         {
     
280.                                 flag=1;
     
281.                                 y=modsqrt;
     
282.                         }else{
     
283.                                 while(n<=p-1)
     
284.                                 {
     
285.                                         q=s+n*p;
     
286.                                         modsqrt=int_sqrt(q);
     
287.                                         if(modsqrt!=-1)
     
288.                                         {
     
289.                                                 y=modsqrt;
     
290.                                                 flag=1;
     
291.                                                 break;
     
292.                                         }
     
293.                                                 flag=0;
     
294.                                                 n++;
     
295.                                 }
     
296.                         }
     
297.                         if(flag==1)
     
298.                         {
     
299.                                 eccPoint.p[j].point_x=i;
     
300.                                 eccPoint.p[j].point_y=y;
     
301.                                 j++;
     
302.                                 if(y!=0)
     
303.                                 {
     
304.                                         eccPoint.p[j].point_x=i;
     
305.                                         eccPoint.p[j].point_y=(p-y) % p;
     
306.                                         j++;
     
307.                                 }                               
     
308.                         }
     
309.                 }
     
310.                 eccPoint.len=j;//点集个数
     
311.                 print(); //打印点集
     
312.         }       
     
313. }
     
314. 
     
315. //取模函数
     
316. int mod_p(int s)
     
317. {
     
318.         int i;        //保存s/p的倍数
     
319.         int result;        //模运算的结果
     
320.         i = s / p;
     
321.         result = s - i * p;
     
322.         if (result >= 0)
     
323.         {
     
324.                 return result;
     
325.         }
     
326.         else
     
327.         {
     
328.                 return result + p;
     
329.         }
     
330. }
     
331. 
     
332. //判断平方根是否为整数
     
333. int int_sqrt(int s)
     
334. {
     
335.         int temp;
     
336.         temp=(int)sqrt(s);//转为整型
     
337.         if(temp*temp==s)
     
338.         {
     
339.                 return temp;
     
340.         }else{
     
341.                 return -1;
     
342.         }
     
343. }
     
344. //打印点集
     
345. void print()
     
346. {
     
347.         int i;
     
348.         int len=eccPoint.len;
     
349.         printf("\n该椭圆曲线上共有%d个点(包含无穷远点)\n",len+1);
     
350.         for(i=0;i<len;i++)
     
351.         {
     
352.                 if(i % 8==0)
     
353.                 {
     
354.                         printf("\n");
     
355.                 }
     
356.                 printf("(%2d,%2d)\t",eccPoint.p[i].point_x,eccPoint.p[i].point_y);
     
357.         }
     
358.         printf("\n");
     
359. }

复制代码

4、运行截图：