信息计算2019级1班7号徐佳颖

徐佳颖

徐佳颖

徐佳颖

徐佳颖

RSA算法实现

1.RSATools.cs

1. using System;
   
2. using System.Collections.Generic;
   
3. using System.Linq;
   
4. using System.Text;
   
5. using System.Threading.Tasks;
   
6. 
   
7. namespace RSA
   
8. {
   
9.     class RSATools
   
10.     {
    
11.         public static bool isPrim(long num)
    
12.         //以6为步进单元判断其是否为素数
    
13.         {
    
14.             //两个较小数另外处理
    
15.             if (num == 2 || num == 3)
    
16.                 return true;
    
17.             //不在6的倍数两侧的一定不是质数
    
18.             if (num % 6 != 1 && num % 6 != 5)
    
19.                 return false;
    
20.             long tmp = (long)Math.Sqrt(num);
    
21.             //在6的倍数两侧的也可能不是质数
    
22.             for (long i = 5; i <= tmp; i += 6)
    
23.                 if (num % i == 0 || num % (i + 2) == 0)
    
24.                     return false;
    
25.             //排除所有，剩余的是质数
    
26.             return true;
    
27.         }
    
28.         public static long gcd(long x, long y) => y != 0 ? gcd(y, x % y) : x;
    
29.         //采用递归的形式，判断两个数是否互质
    
30.         public static long inverse(long number1, long number3)
    
31.         //利用欧几里得算法计算m，d的逆元
    
32.         {
    
33.             long x1 = 1, x2 = 0, x3 = number3, y1 = 0, y2 = 1, y3 = number1;
    
34.             long q;
    
35.             long number4 = 0;
    
36.             long t1, t2, t3;
    
37.             while (y3 != 0)
    
38.             {
    
39.                 if (y3 == 1)
    
40.                 {
    
41.                     number4 = y2;
    
42.                     break;
    
43.                 }
    
44.                 else
    
45.                 {
    
46.                     q = (x3 / y3);
    
47.                     t1 = x1 - q * y1;
    
48.                     t2 = x2 - q * y2;
    
49.                     t3 = x3 - q * y3;
    
50.                     x1 = y1; x2 = y2; x3 = y3;
    
51.                     y1 = t1; y2 = t2; y3 = t3;
    
52.                 }
    
53.             }
    
54.             if (number4 < 0)
    
55.                 number4 = number4 + number3;
    
56.             return number4;
    
57.         }
    
58.         public static long getMod(long a, long b, long c)
    
59.         //利用快速指数模运算，计算m^e mod n
    
60.         {
    
61.             //指数 e --> a  底数 m --> b   模数 n --> c
    
62.             long number3 = 1;
    
63.             while (a != 0)
    
64.             {
    
65.                 if (a % 2 == 1)
    
66.                 {
    
67.                     a = a - 1;
    
68.                     number3 = (number3 * b) % c;
    
69.                 }
    
70.                 else
    
71.                 {
    
72.                     a = (a / 2);
    
73.                     b = (b * b) % c;
    
74.                 }
    
75.             }
    
76.             return number3;
    
77. 
    
78.         }
    
79. 
    
80.         public static long getN(long p, long q) => p * q;
    
81.         public static long getEuler_N(long p, long q) => (p - 1) * (q - 1);
    
82.         //求N的欧拉函数
    
83.         public static void getP_Q(out long p, out long q)
    
84.         {
    
85.             Random random = new Random();
    
86.             while (true)
    
87.             {
    
88.                 p = random.Next(1000);
    
89.                 q = random.Next(2000);
    
90.                 if (isPrim(p) && isPrim(q)) return;
    
91.             }
    
92.         }
    
93. 
    
94.         public static byte[] longToBytes(long a)
    
95.         {
    
96.             byte[] b = new byte[8];
    
97.             b[0] = (byte)(a);
    
98.             b[1] = (byte)(a >> 8 & 0xFF);
    
99.             b[2] = (byte)(a >> 16 & 0xFF);
    
100.             b[3] = (byte)(a >> 24 & 0xFF);
     
101.             b[4] = (byte)(a >> 32 & 0xFF);
     
102.             b[5] = (byte)(a >> 40 & 0xFF);
     
103.             b[6] = (byte)(a >> 48 & 0xFF);
     
104.             b[7] = (byte)(a >> 56 & 0xFF);
     
105.             return b;
     
106.         }
     
107.         public static long BytesToLong(byte[] input)
     
108.         {
     
109.             uint num = (uint)(((input[0] | (input[1] << 8)) | (input[2] << 0x10)) | (input[3] << 0x18));
     
110.             uint num2 = (uint)(((input[4] | (input[5] << 8)) | (input[6] << 0x10)) | (input[7] << 0x18));
     
111.             return (long)((num2 << 0x20) | num);
     
112.         }
     
113. 
     
114.         public static long[] UTF8ToLong(string input)
     
115.         {
     
116.             string input_64 = Convert.ToBase64String(Encoding.UTF8.GetBytes(input));
     
117.             byte[] inputByte = Convert.FromBase64String(input_64);
     
118.             long[] inputLong = new long[inputByte.Length];
     
119.             for (int i = 0; i < inputByte.Length; i++)
     
120.             {
     
121.                 inputLong[i] = (long)inputByte[i];
     
122.             }
     
123.             return inputLong;
     
124.         }
     
125.         public static string longToUTF8(long[] input)
     
126.         {
     
127.             byte[] inputByte = new byte[input.Length];
     
128.             for (int i = 0; i < inputByte.Length; i++)
     
129.             {
     
130.                 inputByte[i] = (byte)input[i];
     
131.             }
     
132.             string inputBase64 = Convert.ToBase64String(inputByte);
     
133.             byte[] outputb = Convert.FromBase64String(inputBase64);
     
134.             string output = Encoding.UTF8.GetString(outputb);
     
135.             return output;
     
136.         }
     
137.         public static long[] Base64ToLong(string input)
     
138.         {
     
139.             List<long> output_l = new List<long>();
     
140.             string t = "";
     
141.             for (int i = 0; i < input.Length; i++)
     
142.             {
     
143.                 t += input[i];
     
144.                 if (input[i] == '=')
     
145.                 {
     
146.                     byte[] tByte = Convert.FromBase64String(t);
     
147.                     output_l.Add(BytesToLong(tByte));
     
148.                     t = "";
     
149.                 }
     
150.             }
     
151.             return output_l.ToArray(); ;
     
152.         }
     
153.         public static string longToBase64(long[] input)
     
154.         {
     
155.             byte[][] inputByte = new byte[input.Length][];
     
156.             string output = "";
     
157.             for (int i = 0; i < input.Length; i++)
     
158.             {
     
159.                 inputByte[i] = longToBytes(input[i]);
     
160.                 output += Convert.ToBase64String(inputByte[i]);
     
161.             }
     
162.             return output;
     
163.         }
     
164. 
     
165.     }
     
166. }
     

复制代码

2.RSA.cs

1. using System;
   
2. using System.Collections.Generic;
   
3. using System.Text;
   
4. 
   
5. namespace RSA
   
6. {
   
7.     class RSA
   
8.     {
   
9.         private long p, q;
   
10.         private long n;
    
11.         private long euler_N;
    
12.         private long[] publicKey;//0-e 1-n
    
13.         private long[] privateKey;//0-d 1-n
    
14. 
    
15.         public long P { get => p; set => p = value; }
    
16.         public long Q { get => q; set => q = value; }
    
17.         public long[] PublicKey { get => publicKey; set => publicKey = value; }
    
18.         public long[] PrivateKey { get => privateKey; set => privateKey = value; }
    
19.         public long N { get => n; set => n = value; }
    
20.         public long Euler_N { get => euler_N; set => euler_N = value; }
    
21. 
    
22.         public void InitPublicKey()
    
23.         //初始化公钥
    
24.         {
    
25.             RSATools.getP_Q(out p, out q);
    
26.             euler_N = RSATools.getEuler_N(p, q);
    
27.             long e;
    
28.             n = RSATools.getN(p, q);
    
29. 
    
30.             Random radom = new Random();
    
31.             while (true)
    
32.             {
    
33.                 e = radom.Next(655300);
    
34.                 if (e > 1 && e < euler_N && RSATools.gcd(e, euler_N) == 1 && RSATools.isPrim(e)) break;
    
35.             }
    
36. 
    
37.             publicKey = new long[2];
    
38.             publicKey[0] = e;
    
39.             publicKey[1] = n;
    
40.         }
    
41.         public void InitPrivateKey()
    
42.         //初始化私钥
    
43.         {
    
44.             long d = RSATools.inverse(publicKey[0], euler_N);
    
45.             privateKey = new long[2];
    
46.             privateKey[0] = d;
    
47.             privateKey[1] = n;
    
48.         }
    
49. 
    
50.         //加密操作
    
51.         public long encrypt(long plaintext, long[] p_k) => RSATools.getMod(p_k[0], plaintext, p_k[1]);
    
52.         //解密操作
    
53.         public long decrypt(long ciphertext) => RSATools.getMod(privateKey[0], ciphertext, privateKey[1]);
    
54. 
    
55.         public string getCiphertext(string plaintext, long[] p_k)
    
56.         //加密明文得到密文
    
57.         {
    
58.             long[] p_long = RSATools.UTF8ToLong(plaintext);
    
59.             long[] c_long = new long[p_long.Length];
    
60.             for (int i = 0; i < p_long.Length; i++)
    
61.             {
    
62.                 c_long[i] = encrypt(p_long[i], p_k);
    
63.             }
    
64.             string c_text = RSATools.longToBase64(c_long);
    
65.             return c_text;
    
66.         }
    
67.         public string getPlaintext(string ciphertext)
    
68.         //解密密文得到明文
    
69.         {
    
70.             long[] c_long = RSATools.Base64ToLong(ciphertext);
    
71.             long[] p_long = new long[c_long.Length];
    
72.             for (int i = 0; i < c_long.Length; i++)
    
73.             {
    
74.                 p_long[i] = decrypt(c_long[i]);
    
75.             }
    
76.             string p_text = RSATools.longToUTF8(p_long);
    
77.             return p_text;
    
78.         }
    
79.     }
    
80. }
    

复制代码

徐佳颖

3.Program.cs

1. using System;
   
2. using System.Collections.Generic;
   
3. using System.Linq;
   
4. using System.Text;
   
5. using System.Threading.Tasks;
   
6. 
   
7. namespace RSA
   
8. {
   
9.     class Program
   
10.     {
    
11.         static void Main(string[] args)
    
12.         {
    
13.             RSA a = new RSA();
    
14.             a.InitPublicKey();
    
15.             a.InitPrivateKey();
    
16.             string p = a.P.ToString();
    
17.             string q = a.Q.ToString();
    
18.             string publickey = a.PublicKey[0].ToString() + "-" + a.PublicKey[1].ToString();
    
19. 
    
20. 
    
21.             Console.Write("原文：");
    
22.             string plaintext = "19561654894513215674894153210324168789413210685749845613216574894156321321564897415631321654896";
    
23.             Console.WriteLine(plaintext);
    
24. 
    
25.             Console.Write("密文：");
    
26.             string ciphertext = a.getCiphertext(plaintext, a.PublicKey);
    
27.             Console.WriteLine(ciphertext);
    
28. 
    
29.             Console.Write("译文：");
    
30.             string decryptedtext = a.getPlaintext(ciphertext);
    
31.             Console.WriteLine(decryptedtext);
    
32.         }
    
33.     }
    
34. }
    

复制代码

徐佳颖