Posted By

ozkriff on 05/21/09


Tagged


Versions (?)

Who likes this?

1 person have marked this snippet as a favorite

tartar9


RSA


 / Published in: C
 

  1. /* rsa.c */
  2.  
  3. #include <gmp.h>
  4. #include <stdio.h>
  5. #include <assert.h>
  6.  
  7. /* проверяет, является ли число простым. Если нет, то делает таковым. */
  8. /* Просто́е число́ это натуральное число,
  9. которое имеет ровно 2 различных делителя (только 1 и самоё себя). */
  10.  
  11. void check_for_prime(mpz_ptr p)
  12. {
  13. int forprimep = mpz_probab_prime_p (p, 50);
  14. while (forprimep == 0) {
  15. mpz_add_ui (p, p, 1);
  16. forprimep = mpz_probab_prime_p (p, 50);
  17. };
  18. }
  19.  
  20. const int SIZE = 512; /* Размер ключей. */
  21.  
  22. /* -------------------------------- MAIN --------------------------------- */
  23. int main (int argc, char* argv[])
  24. {
  25. mpz_t p, q;
  26.  
  27. /* Инициализация рандома */
  28. gmp_randstate_t state;
  29. gmp_randinit_default(state);
  30.  
  31. /* 1. Генерируется случайные простые числа p и q */
  32. mpz_init2(p,SIZE);
  33. mpz_urandomb(p, state, SIZE);
  34.  
  35. check_for_prime(p);
  36.  
  37. mpz_init2(q,SIZE);
  38. mpz_urandomb(q, state, SIZE);
  39.  
  40. check_for_prime(q);
  41.  
  42. puts("p = ");
  43. mpz_out_str (stdout, 10, p);
  44. puts("\nq = ");
  45. mpz_out_str (stdout, 10, q);
  46.  
  47. /* 2. Вычисляется их произведение n = pq */
  48. mpz_t n;
  49. mpz_init(n);
  50. mpz_mul(n,p,q);
  51.  
  52. puts("\nn = ");
  53. mpz_out_str (stdout, 10, n);
  54.  
  55. /* 3. Вычисляется значение функции Эйлера от числа n.
  56.  
  57. Функция Эйлера ( phi(n), где n — натуральное число )
  58. равна количеству натуральных чисел, не больших n и взаимно простых с ним. */
  59. mpz_t fi;
  60. mpz_init(fi);
  61.  
  62. mpz_t p_m, q_m;
  63. mpz_init(p_m);
  64. mpz_init(q_m);
  65. mpz_sub_ui(p_m, p, 1);
  66. mpz_sub_ui(q_m, q, 1);
  67.  
  68. mpz_mul(fi, p_m, q_m);
  69.  
  70. puts("\nfi = ");
  71. mpz_out_str (stdout, 10, fi);
  72.  
  73. /* 4. Выбирается целое число e, взаимно простое со значением функции fi
  74.  
  75. время выполнения операций растёт с увеличением количества ненулевых
  76. битов в двоичном представлении открытой экспоненты e.
  77. Чтобы увеличить скорость шифрования, значение e
  78. часто выбирают равным 17, 257 или 65537 — простым числам,
  79. двоичное представление которых содержит лишь две единицы:
  80. 17 = 0x11, 257 = 0x101, 65537 = 0x10001 (простые числа Ферма). */
  81.  
  82. int possible_values[] = {
  83. 17, 257, 65537
  84. };
  85.  
  86. mpz_t e;
  87. mpz_init(e);
  88. mpz_t gcd;
  89. mpz_init(gcd);
  90. int i = 0;
  91. for (; i < 3; ++i)
  92. {
  93. mpz_set_ui(e,possible_values[i]);
  94. mpz_gcd(gcd, e, fi);
  95. int compgcd = mpz_cmp_ui(gcd, 1);
  96. if (compgcd == 0)
  97. break;
  98. }
  99. assert(i != 3); /* выбор был сделан */
  100. puts("\ne = ");
  101. mpz_out_str (stdout, 10, e);
  102.  
  103. /* 5. Вычисляется число d мультипликативное обратное к числу e по модулю fi */
  104. mpz_t d;
  105. mpz_init(d);
  106.  
  107. mpz_invert(d, e, fi);
  108. puts("\nd = ");
  109. mpz_out_str (stdout, 10, d);
  110.  
  111. /* Пара P = (e,n) публикуется в качестве открытого ключа RSA */
  112. /* Пара S = (d,n) играет роль секретного ключа RSA */
  113.  
  114. /* ------------------------------------------------------------------------- */
  115. /* Цифровая подпись. (Все переменные имеют приставку 's_') */
  116.  
  117. /* Открытый текст */
  118. /* В качестве текста возьмем рандомное число. Так или иначе, текст
  119.   необходимо привести к какому-то числу */
  120. mpz_t s_M;
  121. mpz_init2(s_M,SIZE / 2);
  122. mpz_urandomb(s_M, state, SIZE / 2);
  123. puts("\ns_M = ");
  124. mpz_out_str (stdout, 10, s_M);
  125.  
  126. /* Создаем цифровую подпись sigma с помощью своего секретного ключа S */
  127. mpz_t s_sigma;
  128. mpz_init(s_sigma);
  129.  
  130. mpz_powm(s_sigma, s_M, d, n);
  131. puts("\ns_sigma = ");
  132. mpz_out_str (stdout, 10, s_sigma);
  133.  
  134. /* Проверяем подлинность подписи (Pa должно равняться M) */
  135. mpz_t s_Pa;
  136. mpz_init(s_Pa);
  137.  
  138. mpz_powm(s_Pa, s_sigma, e, n);
  139. puts("\ns_Pa = ");
  140. mpz_out_str (stdout, 10, s_Pa);
  141.  
  142. int compgcd = mpz_cmp(s_M, s_Pa);
  143. if (compgcd == 0) {
  144. puts("\ns_M == s_Pa");
  145. }
  146. else {
  147. puts("\ns_M != s_Pa");
  148. }
  149.  
  150. /* ------------------------------------------------------------------------- */
  151. /* Шифрование. */
  152. mpz_t M;
  153. mpz_init2 (M,SIZE / 2);
  154. // mpz_urandomb (M, state, SIZE / 2);
  155. mpz_set_ui(M, 11);
  156. puts ("\nM = ");
  157. mpz_out_str (stdout, 10, M);
  158.  
  159. /* Шифрование. */
  160. mpz_t Pa;
  161. mpz_init (Pa);
  162.  
  163. mpz_powm (Pa, M, e, n);
  164. puts ("\nPa = ");
  165. mpz_out_str (stdout, 10, Pa);
  166.  
  167. /* Дешифрование. */
  168. mpz_t Sa;
  169. mpz_init (Sa);
  170.  
  171. mpz_powm(Sa, Pa, d, n);
  172. puts("\nSa = ");
  173. mpz_out_str (stdout, 10, Sa);
  174.  
  175. /* Проверка. */
  176. if (mpz_cmp(M, Sa) == 0) {
  177. puts("\nM == Sa");
  178. }
  179. else {
  180. puts("\nM != Sa");
  181. }
  182.  
  183. /* ------------------------------------------------------------------------- */
  184. /* Text encription. */
  185.  
  186. int i = 0;
  187.  
  188.  
  189. mpz_t text [32];
  190. mpz_t Pa_2 [32];
  191. char text_M[] = "some text.";
  192. puts("");
  193. puts("initial text:");
  194. puts (text_M);
  195. puts("");
  196.  
  197. puts("codes:");
  198. for ( i=0; text_M [i] != '\0'; i++ ) {
  199. mpz_init ( Pa_2[i] );
  200. mpz_init ( text[i] );
  201. mpz_set_ui ( text[i], text_M[i] );
  202.  
  203. mpz_powm ( Pa_2[i], text[i], e, n );
  204. mpz_out_str ( stdout, 10, Pa_2[i] );
  205. puts ("");
  206. }
  207.  
  208. /* ------------------*/
  209. mpz_t Sa_2[32];
  210.  
  211. puts("");
  212. puts("result text:");
  213.  
  214. for ( i=0; text_M [i] != '\0'; i++ ) {
  215. mpz_init ( Sa_2[i] );
  216. mpz_powm ( Sa_2[i], Pa_2[i], d, n );
  217.  
  218. putchar ( (char)mpz_get_si(Sa_2[i]) );
  219. }
  220. /* ------------------*/
  221.  
  222. return 0;
  223. }

Report this snippet  

You need to login to post a comment.