RSA

/* rsa.c */
 
#include <gmp.h>
#include <stdio.h>
#include <assert.h>
 
/* проверяет, является ли число простым. Если нет, то делает таковым. */
/* Просто́е число́ это натуральное число, 
которое имеет ровно 2 различных делителя (только 1 и самоё себя). */
 
void check_for_prime(mpz_ptr p)
{
	int forprimep = mpz_probab_prime_p (p, 50);
	while (forprimep == 0) {
		mpz_add_ui (p, p, 1);
		forprimep = mpz_probab_prime_p (p, 50);
	};
}
 
const int SIZE = 512; 	/* Размер ключей. */
 
/* --------------------------------  MAIN  --------------------------------- */
int main (int argc, char* argv[])
{
	mpz_t p, q;
 
/* Инициализация рандома */
	gmp_randstate_t state;
	gmp_randinit_default(state);
 
/* 1. Генерируется случайные простые числа p и q */
	mpz_init2(p,SIZE);
	mpz_urandomb(p, state, SIZE);
 
	check_for_prime(p);
 
	mpz_init2(q,SIZE);
	mpz_urandomb(q, state, SIZE);
 
	check_for_prime(q);
 
	puts("p = ");
	mpz_out_str (stdout, 10, p);
	puts("\nq = ");
	mpz_out_str (stdout, 10, q);
 
/* 2. Вычисляется их произведение n = pq */
	mpz_t n;
	mpz_init(n);
	mpz_mul(n,p,q);
 
	puts("\nn = ");
	mpz_out_str (stdout, 10, n);
 
/* 3. Вычисляется значение функции Эйлера от числа n.
 
Функция Эйлера  ( phi(n), где n — натуральное число ) 
равна количеству натуральных чисел, не больших n и взаимно простых с ним. */
	mpz_t fi;
	mpz_init(fi);
 
	mpz_t p_m, q_m;
	mpz_init(p_m);
	mpz_init(q_m);
	mpz_sub_ui(p_m, p, 1);
	mpz_sub_ui(q_m, q, 1);
 
	mpz_mul(fi, p_m, q_m);
 
	puts("\nfi = ");
	mpz_out_str (stdout, 10, fi);
 
/* 4. Выбирается целое число e, взаимно простое со значением функции fi
 
время выполнения операций растёт с увеличением количества ненулевых 
битов в двоичном представлении открытой экспоненты e. 
Чтобы увеличить скорость шифрования, значение e 
часто выбирают равным 17, 257 или 65537 — простым числам, 
двоичное представление которых содержит лишь две единицы: 
17 = 0x11, 257 = 0x101, 65537 = 0x10001 (простые числа Ферма). */
 
	int possible_values[] = {
		17, 257, 65537
	};
 
	mpz_t e;
	mpz_init(e);
	mpz_t gcd;
	mpz_init(gcd);
	int i = 0;
	for (; i < 3; ++i)
	{
		mpz_set_ui(e,possible_values[i]);
		mpz_gcd(gcd, e, fi);
		int compgcd = mpz_cmp_ui(gcd, 1);
		if (compgcd == 0)
			break;
	}
	assert(i != 3); 	/* выбор был сделан */
	puts("\ne = ");
	mpz_out_str (stdout, 10, e);
 
/* 5. Вычисляется число d мультипликативное обратное к числу e по модулю fi */
	mpz_t d;
	mpz_init(d);
 
	mpz_invert(d, e, fi);
	puts("\nd = ");
	mpz_out_str (stdout, 10, d);
 
/* Пара P = (e,n) публикуется в качестве открытого ключа RSA */
/* Пара S = (d,n) играет роль секретного ключа RSA */
 
/* ------------------------------------------------------------------------- */
/* Цифровая подпись. (Все переменные имеют приставку 's_') */
 
/* Открытый текст */
/* В качестве текста возьмем рандомное число. Так или иначе, текст 
   необходимо привести к какому-то числу */
	mpz_t s_M;
	mpz_init2(s_M,SIZE / 2);
	mpz_urandomb(s_M, state, SIZE / 2);
	puts("\ns_M = ");
	mpz_out_str (stdout, 10, s_M);
 
/* Создаем цифровую подпись sigma с помощью своего секретного ключа S */
	mpz_t s_sigma;
	mpz_init(s_sigma);
 
	mpz_powm(s_sigma, s_M, d, n);
	puts("\ns_sigma = ");
	mpz_out_str (stdout, 10, s_sigma);
 
/* Проверяем подлинность подписи (Pa должно равняться M) */
	mpz_t s_Pa;
	mpz_init(s_Pa);
 
	mpz_powm(s_Pa, s_sigma, e, n);
	puts("\ns_Pa = ");
	mpz_out_str (stdout, 10, s_Pa);
 
	int compgcd = mpz_cmp(s_M, s_Pa);
	if (compgcd == 0) {
		puts("\ns_M == s_Pa");
	}
	else {
		puts("\ns_M != s_Pa");
	}
 
/* ------------------------------------------------------------------------- */
/* Шифрование. */
	mpz_t M;
	mpz_init2 (M,SIZE / 2);
//	mpz_urandomb (M, state, SIZE / 2);
	mpz_set_ui(M, 11);
	puts ("\nM = ");
	mpz_out_str (stdout, 10, M);
 
/* Шифрование. */
	mpz_t Pa;
	mpz_init (Pa);
 
	mpz_powm (Pa, M, e, n);
	puts ("\nPa = ");
	mpz_out_str (stdout, 10, Pa);
 
/* Дешифрование. */
	mpz_t Sa;
	mpz_init (Sa);
 
	mpz_powm(Sa, Pa, d, n);
	puts("\nSa = ");
	mpz_out_str (stdout, 10, Sa);
 
/* Проверка. */
	if (mpz_cmp(M, Sa) == 0) {
		puts("\nM == Sa");
	}
	else {
		puts("\nM != Sa");
	}
 
/* ------------------------------------------------------------------------- */
/* Text encription. */
 
	int i = 0;
 
 
	mpz_t text [32];
	mpz_t Pa_2 [32];
	char text_M[] = "some text.";
	puts("");
	puts("initial text:");
	puts (text_M);
	puts("");
 
	puts("codes:");
	for ( i=0; text_M [i] != '\0'; i++ ) {
		mpz_init ( Pa_2[i] );
		mpz_init ( text[i] );
		mpz_set_ui ( text[i], text_M[i] );
 
		mpz_powm ( Pa_2[i], text[i], e, n );
		mpz_out_str ( stdout, 10, Pa_2[i] );
		puts ("");
	}
 
/* ------------------*/
	mpz_t Sa_2[32];
 
	puts("");
	puts("result text:");
 
	for ( i=0; text_M [i] != '\0'; i++ ) {
		mpz_init ( Sa_2[i] );
		mpz_powm ( Sa_2[i], Pa_2[i], d, n );
 
		putchar ( (char)mpz_get_si(Sa_2[i]) );
	}
/* ------------------*/
 
	return 0;
}