一个RSA加密算法。

andalousie

这个算法参考了多个资源。还有自己的改变。RSA.cpp

1. #include <iostream>
   
2. #include <ctime>
   
3. #include "HugeInt.h"
   
4. #include "Random.h"
   
5. 
   
6. // Compute x^n ( mod p ).
   
7. // HugeInt: must have copy constructor, operator=,
   
8. //     conversion from int, *, /, %, ==, and !=
   
9. //     Assumes that p is not zero and power( 0, 0, p ) is 1
   
10. HugeInt power( const HugeInt & x, const HugeInt & n , const HugeInt & p )
    
11. {
    
12. 
    
13.     if( n == 0 )
    
14.         return 1;
    
15. 
    
16.     HugeInt tmp = power( ( x * x ) % p, n / 2, p );
    
17.    
    
18.     if( n % 2 != 0 )
    
19.         tmp = ( tmp * x ) % p;
    
20. 
    
21.     return tmp;
    
22. }
    
23. 
    
24. // Probabilistic primality testing routine.
    
25. // If witness does not return 1, n is definitely composite.
    
26. // Do this by computing a^i ( mod n ) and looking for
    
27. // non-trivial square roots of 1 along the way.
    
28. // HugeInt: must have copy constructor, operator=,
    
29. //     conversion from int, *, /, -, %, ==, and !=
    
30. HugeInt witness( const HugeInt & a, const HugeInt & i, const HugeInt & n )
    
31. {
    
32.     if( i == 0 )
    
33.         return 1;
    
34. 
    
35.     HugeInt x = witness( a, i / 2, n );
    
36.     if( x == 0 )    // If n is recursively composite, stop
    
37.         return 0;
    
38. 
    
39.       // n is not prime if we find a nontrivial square root of 1
    
40.     HugeInt y = ( x * x ) % n;
    
41.     if( y == 1 && x != 1 && x != n - 1 )
    
42.         return 0;
    
43. 
    
44.     if( i % 2 == 1 )
    
45.         y = ( a * y ) % n;
    
46. 
    
47.     return y;
    
48. }
    
49. 
    
50. // Make NUM_TRIALS calls to witness to check if n is prime.
    
51. bool isPrime( const HugeInt & n )
    
52. {
    
53.     const int NUM_TRIALS = 5;
    
54.         Random rnd;
    
55. 
    
56.     for( int counter = 0; counter < NUM_TRIALS; counter++ )
    
57.         if( witness( rnd.randomInt( 2, n ) , n - 1, n ) != 1 )
    
58.             return false;
    
59. 
    
60.     return true;
    
61. }
    
62. 
    
63. // Returns the greatest common divisor of a and b.
    
64. HugeInt gcd( const HugeInt & a, const HugeInt & b )
    
65. {
    
66.     if( b == 0 )
    
67.         return a;
    
68.     else
    
69.         return gcd( b, a % b );
    
70. }
    
71. 
    
72. // Given a and b, assume gcd( a, b ) = 1.
    
73. // Find x and y such that  a x + b y = 1.
    
74. // HugeInt: must have copy constructor,
    
75. //     zero-parameter constructor, operator=,
    
76. //     conversion from int, *, /, +, -, %, ==, and >
    
77. void fullGcd( const HugeInt & a, const HugeInt & b,
    
78.               HugeInt & x, HugeInt & y )
    
79. {
    
80.     HugeInt x1, y1;
    
81. 
    
82.     if( b == 0 )
    
83.     {
    
84.         x = 1;       // If a != 1, there is no inverse
    
85.         y = 0;       // We omit this check
    
86.     }
    
87.     else
    
88.     {
    
89.         fullGcd( b, a % b, x1, y1 );
    
90.         x = y1;
    
91.         y = x1 - ( a / b ) * y1;
    
92.     }
    
93. }
    
94. 
    
95. // GetPrime randomly picks a large, odd number until it gets
    
96. // one that is prime. It uses is_prime to check for primality.
    
97. // The more failed primes that occur, the larger the N becomes.
    
98. 
    
99. HugeInt GetPrime( )
    
100. {
     
101.         Random rnd(time(0));
     
102.         HugeInt N = rnd.randomInt( 1000000000, INT_MAX );
     
103.         HugeInt NN = rnd.randomInt( 1000000000, INT_MAX );
     
104.         HugeInt multiplier(1314521);
     
105.         N = N * NN * N * multiplier;
     
106.         HugeInt Odd = 2;
     
107. 
     
108.         if ( N % 2 == 0 )
     
109.                 N = N+1;
     
110. 
     
111.         while ( !isPrime( N )){
     
112.                 N = N + Odd;
     
113.         }
     
114.         return N;
     
115. }
     
116. 
     
117. // Solve a x == 1 ( mod n ).
     
118. // Assume that gcd( a, n ) = 1.
     
119. HugeInt inverse( const HugeInt & a, const HugeInt & n )
     
120. {
     
121.     HugeInt x, y;
     
122. 
     
123.     fullGcd( a, n, x, y );
     
124.     return x > 0 ? x : x + n;
     
125. }
     
126. 
     
127. // Illustrate an RSA computation
     
128. int main( )
     
129. {
     
130.       // Sample of how RSA works.
     
131.     HugeInt p = GetPrime();
     
132.     HugeInt q = GetPrime();
     
133.     HugeInt message, code, decode;
     
134.     HugeInt n, nPrime, e, d;
     
135.         std::string myletter = "For my friends!";
     
136.         message.rsa(myletter);
     
137. 
     
138.     std::cout <<  "p: " << p << std::endl;
     
139.     std::cout <<  "q: " << q << std::endl;
     
140. 
     
141.     n = p * q;
     
142.     std::cout <<  "n: " << n << std::endl;
     
143. 
     
144.     nPrime = ( p - 1 ) * ( q - 1 );
     
145.     std::cout <<  "nprime: " << nPrime << std::endl;
     
146. 
     
147.     for( e = nPrime/521; gcd( e, nPrime ) != 1; e++ );
     
148.     std::cout <<  "e: " << e << std::endl;
     
149. 
     
150.     d = inverse( e, nPrime );
     
151.     std::cout <<  "d: " << d << std::endl;
     
152. 
     
153.     std::cout << "Verify inverse: " << ( e * d % ( nPrime ) ) << std::endl;
     
154. 
     
155.     std::cout << "message: " << myletter << std::endl;
     
156. 
     
157.     code = power( message, e, n );
     
158.     decode = power( code, d, n );
     
159. 
     
160.     std::cout << "Code: " << code << std::endl;
     
161.     std::cout << "Decode: " << decode.asr() << std::endl;
     
162. 
     
163.     if( message != decode )
     
164.         std::cout << "OOPS: " << std::endl;
     
165.     else
     
166.         std::cout << "Success!!!!" << std::endl;
     
167. 
     
168.     return 0;
     
169. }

复制代码

游客，如果您要查看本帖隐藏内容请回复

RSA方法源于Mark Allen Weiss的实现。

183560656

看看，呃呃呃

andalousie

由于发帖字数限制，完全的源代码只有回复下载了才能看到。这里可以提供运行过后的一个截图。很成功的~

bulangzhe

支持楼主  这个挺好 研究研究

2014On_The_Way

hhhhhhhhh呵呵呵

黑暗漩涡

回帖是一种美德

黑暗漩涡

回帖是一种美德

章伯魂

这东西不错呀，非常感谢楼主分享。。。！

irvine726

谢谢分享

jsqking99

感谢楼主无私分享！！！！！

irvine726

谢谢分享~

郭兴华

顶顶顶顶顶顶顶

wyds591101

一句话，支持你，支持开源，支持原创。

王虬鹏

很好噶

jsqking99

感谢楼主无私分享！！

xykj2011

看看。。。。。。。。。。。。。。。

OSKer

学习一下。。。

dAb

四处找资料，，恶补知识

fabuer

谢谢分享，辛苦了

我是桃川人

谢谢分享！学习它。