Advertisement
Guest User

Untitled

a guest
Dec 7th, 2019
133
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.78 KB | None | 0 0
  1. #include <iostream>
  2. #include <math.h>
  3. #include <string.h>
  4. #include <string>
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include "InfInt.h"
  8. #include <time.h>
  9. #include <clocale>
  10. bool Miller(InfInt prime, int iteration);
  11. InfInt calculateE( InfInt t );
  12. InfInt greatestCommonDivisor( InfInt e, InfInt t );
  13. InfInt FindD( InfInt e, InfInt t );
  14. InfInt encrypt( InfInt i, InfInt e, InfInt n );
  15. InfInt decrypt(InfInt i, InfInt d, InfInt n );
  16. InfInt generate();
  17. //генерация числа
  18. InfInt generate(){
  19. InfInt t = 1;
  20. srand(time(NULL));
  21. for (int i = 0; i < 128; i++){
  22. if (rand() % 100 < 51){
  23. t++;
  24. }
  25. t=t*2;
  26. }
  27. std::cout << t << std::endl;
  28. return t;
  29. }
  30. //умножение по модулю
  31. InfInt multmod(InfInt a, InfInt b, InfInt mod){
  32. InfInt x = 0,y = a % mod;
  33. while (b > 0){
  34. if (b % 2 == 1){
  35. x = (x + y) % mod;
  36. }
  37. y = (y * 2) % mod;
  38. b /= 2;
  39. }
  40. return x % mod;
  41. }
  42. //возведения в степень по модулю
  43. InfInt powmod(InfInt base, InfInt exp, InfInt mod){
  44. if (exp == 0){
  45. return 1;
  46. }
  47. InfInt z = powmod(base, exp/2, mod);
  48. if (exp % 2 == 0){
  49. return (z * z) % mod;
  50. }
  51. else{
  52. return (base * z *z) % mod;
  53. }
  54. }
  55. bool Miller(InfInt p,int iteration){
  56. clock_t startm = clock();
  57. srand(time(NULL));
  58. if (p < 2){
  59. return false;
  60. }
  61. if (p != 2 && p % 2==0){
  62. return false;
  63. }
  64. InfInt s = p - 1;
  65. while (s % 2 == 0){
  66. s /= 2;
  67. }
  68. for (int i = 0; i < iteration; i++){
  69. InfInt a = (InfInt)rand() % (p - 1) + 1;
  70. InfInt temp = s;
  71. InfInt mod = powmod(a, temp, p);
  72. while (temp != p - 1 && mod != 1 && mod != p - 1){
  73. mod = multmod(mod, mod, p);
  74. temp *= 2;
  75. }
  76. if (mod != p - 1 && temp % 2 == 0){
  77. return false;
  78. }
  79. }
  80. clock_t endm = clock();
  81. double seconds = (double)(endm - startm) / CLOCKS_PER_SEC;
  82. printf("Время прохождения теста Миллера-Рабина: %f секунд\n", seconds);
  83. return true;
  84. }
  85. InfInt calculateE( InfInt t ){
  86. InfInt e;
  87. for ( e = 2; e < t; e++ ){
  88. if (greatestCommonDivisor( e, t ) == 1 ){
  89. return e;
  90. }
  91. }
  92. return -1;
  93. }
  94. //НОД
  95. InfInt greatestCommonDivisor( InfInt e, InfInt t ){
  96. while ( e > 0 ){
  97. InfInt Temp;
  98. Temp = e;
  99. e = t % e;
  100. t = Temp;
  101. }
  102. return t;
  103. }
  104. InfInt FindD(InfInt e, InfInt t){
  105. InfInt inv, u1, u3, v1, v3, t1, t3, q;
  106. InfInt iter;
  107. u1 = 1;
  108. u3 = e;
  109. v1 = 0;
  110. v3 = t;
  111. iter = 1;
  112. while (v3 != 0)
  113. {
  114. q = u3 / v3;
  115. t3 = u3 % v3;
  116. t1 = u1 + q * v1;
  117. u1 = v1;
  118. v1 = t1;
  119. u3 = v3;
  120. v3 = t3;
  121. iter = -iter;
  122. }
  123. if (u3 != 1)
  124. return 0;
  125. if (iter < 0)
  126. inv = t - u1;
  127. else
  128. inv = u1;
  129. return inv;
  130. }
  131. InfInt encrypt( InfInt i, InfInt e, InfInt n ){
  132. InfInt current, result;
  133. current = i - 97;
  134. result = 1;
  135. result = powmod(current, e, n);
  136. return result;
  137. }
  138. InfInt decrypt(InfInt i, InfInt d, InfInt n){
  139. InfInt current, result;
  140. current = i;
  141. result = 1;
  142. result = powmod(current, d, n);
  143. return result + 97;
  144. }
  145. int main( ){
  146. setlocale(LC_CTYPE, "rus");
  147. clock_t start = clock();
  148. InfInt p, q, n, t, e, d;
  149. InfInt encryptedText[100];
  150. memset(encryptedText, 0, sizeof(InfInt));
  151. InfInt decryptedText[100];
  152. memset(decryptedText, 0, sizeof(InfInt));
  153. bool flag1;
  154. std::string msg;
  155. std::cout << "Генерация простого длинного числа p...." << std::endl;
  156. p = generate();
  157. do{
  158. flag1 = Miller( p, 2);
  159. if ( flag1 == false ){
  160. p++;
  161. std::cout << p << std::endl;
  162. }
  163. } while ( flag1 == false);
  164. std::cout << "Генерация простого длинного числа q....:" << std::endl;
  165. q = generate();
  166. do{
  167. flag1 = Miller( q, 2);
  168. if ( flag1 == false ){
  169. q++;
  170. std::cout << q << std::endl;
  171. }
  172. } while ( flag1 == false);
  173. n = p * q;
  174. std::cout << "\nМодуль n чисел p и q = " << n << std::endl;
  175. t = ( p - 1 ) * ( q - 1 );
  176. std::cout << "\nФункция Эйлера для чисел p и q = " << t << std::endl;
  177. e = calculateE( t );
  178. d = FindD(e,t);
  179. std::cout << "\nОткрытый ключ (n = " << n << ", e = " << e << ")" << std::endl;
  180. std::cout <<"Закрытый ключ (n = " << n << ", d = " << d << ")" << std::endl;
  181. std::cout << "\nВведите сообщение : " << std::endl;
  182. std::getline( std::cin, msg );
  183. std::cout << "\nВаще сообщение : " << msg << std::endl;
  184. for (long int i = 0; i < msg.length(); i++){
  185. setlocale(LC_CTYPE, "rus");
  186. encryptedText[i] = encrypt(msg[i], e, n);
  187. }
  188. std::cout << "\nВаше закодированное сообщение :" << std::endl;
  189. for ( long int i = 0; i < msg.length(); i++ ){
  190. printf( "%i", encryptedText[i] );
  191. }
  192. for (long int i = 0; i < msg.length(); i++){
  193. decryptedText[i] = decrypt(encryptedText[i], d, n);
  194. }
  195. std::cout << "\nВаше раскодированное сообщение:" << std::endl;
  196. for (long int i = 0; i < msg.length(); i++){
  197. setlocale(LC_CTYPE, "rus");
  198. printf( "%c", (unsigned char)decryptedText[i].toInt() );
  199. }
  200. clock_t end = clock();
  201. double seconds = (double)(end - start) / CLOCKS_PER_SEC;
  202. printf("\nThe time: %f seconds\n", seconds);
  203. std::cout << std::endl << std::endl;
  204. return 0;
  205. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement