iacZbPCp

1#include "stdio.h"
2#include <iostream>
3#include <time.h>
4#include <cmath>
5#include <map>
6#define ll long long
7using namespace std;
8
9
10/* Написать криптографическую библиотеку 
11	1. Функция быстрого возведения числа в степень по модулю
12	2. Обобщенный алгоритм Евклида
13	3. Ключ двух абонентов Диффи-Хельман
14	4. Дискретный алгоритм. Шаг великана, шаг младенца */
15
16long long int fast_power(long long int a, long long int x, long long int p)
17	/* быстрое возведение в степень. a^x (%p) */
18{
19	long long int answ_powered = 1;
20	while (x != 0)
21	{		
22		if ((x & 1) == 1) // если на данном шаге в x стоит единица, т.е степень определяющая разложение a^x
23			answ_powered = (answ_powered * a) % p;
24		a = (a * a) % p;
25		x >>= 1; // деление на два, необходдимо для поиска нужных степеней двойки
26	}
27	return answ_powered;
28}
29
30long long int gcd (ll int a, ll int b, ll int& x, ll int& y)
31	/* Обобщенный алгоритм Евклида. решение уравнения a*x+b*y=gcd(a,b)
32		задается а и б. x и y необходимо найти
33	*/
34{
35	map <int, ll int> u;
36	map <int, ll int> v;
37	map <int, ll int> t;
38	
39	u[1] = a; u[2] = 1; u[3] = 0;
40	v[1] = b; v[2] = 0; v[3] = 1;
41		
42	while (v[1] != 0)
43	{
44		ll int q = u[1] / v[1];
45		t[1] = u[1] % v[1]; t[2] = u[2] - q * v[2]; t[3] = u[3] - q * v[3];
46		u[1] = v[1]; u[2] = v[2]; u[3] = v[3];
47		v[1] = t[1]; v[2] = t[2]; v[3] = t[3]; 
48	}
49	x = u[2]; y = u[3];
50	while (b != 0)
51	{
52		ll int r = a % b;
53		a = b;
54		b = r;
55	}
56	return a;
57}
58
59bool isPrime(ll int num)
60{
61 	bool flag = false;
62
63  	for(int i = 2; i <= num/2; ++i)
64  	{
65      	if(num%i == 0)
66      	{
67          	flag = true;
68         	break;
69      	}
70 	}
71  	return flag;
72}
73
74long long int dha()//(ll int public_B, ll int public_a, ll int g, ll int p)
75/* Алгоритм Диффи-Хеллмана. секретный ключ g^ab mod p. public_B - публичный ключ полученный от корреспондент */
76{
77	srand (time(NULL));
78	ll Q = rand() % 1000000000;
79	while (isPrime(Q) && (isPrime(2*Q+1)) == false) // Generating Q and 2*Q+1 Prime?
80	   Q = rand() % 1000000000;
81	   
82	ll int p = 2*Q + 1;
83	ll int g = 1 + rand() % (p-1); // g: 1...(p-1)
84	
85	ll int secret_a = rand() % 1000000000; // private key 1
86	ll int public_A = fast_power(g, secret_a, p); // g^a mod p 
87	ll int secret_b = rand() % 1000000000; // private key 2
88	ll int public_B = fast_power(g, secret_b, p); // g^b mod p 
89		
90	ll int secret_key = fast_power(public_B, secret_a, p); //(g^b mod p)^a mod p == g^ab mod p
91	
92	cout << endl << "Diffi-Hellman" << endl << "Q == " << Q << " p = 2*Q+1 == " << p << "  g == " << g << endl;
93	cout << "private a key == " << secret_a << "; private b key == " << secret_b << endl <<". Public A, B: " \
94		<< public_A << ", " << public_B << endl;
95	cout << "Secret key is " << secret_key << endl;
96	
97	return secret_key;
98}
99
100long long int discr_log(ll int& a, ll int& p, ll int& b)
101	/*
102		a^x mod p = b. Find x
103	*/
104{
105	cout << endl << "Discrete Logarithm" << endl;
106	cout << "Basis == " << a << " modul == " << p << " answ == " << b << endl;
107	ll int k = (ll int) sqrt (p) + 1; // k*k >= p
108	
109	map <ll int, ll int> map_aik_i;
110	
111	for (int i = 1; i <= k; i++) 
112		map_aik_i[fast_power(a, i * k, p)] = i; // a^ik mod p
113	
114	ll int checker = k;
115	for (int j = 0; j <= k-1; j++) 
116	{// a^j * b mod p
117		ll int temp = b * fast_power(a, j, p) % p;
118		checker++;
119		if (map_aik_i[temp]) // esli sovpalo -> to nuzhni i, j. x=i*k+j
120		{
121			ll int answ = map_aik_i[temp] * k - j;
122			cout <<"shagov == "<< checker << endl;
123			return (answ);
124		}
125	}
126	return -1;
127}
128	
129int main ()
130{
131	cout << "Fast power equatation" << endl; // (a^x) mod p
132	srand (time(NULL));
133	long long int power = rand()%1000000000;
134	long long int basis = rand()%1000000000;
135	long long int modulus = rand()%1000000000;
136	ll int answer = fast_power(basis, power, modulus);
137	cout << basis << " ^ " << power << " mod " <<  modulus << " == |" << answer << endl;
138	
139	cout << endl << "greatest common divisor" << endl; // a*x+b*y=gcd(a,b)
140	srand (time(NULL));
141	ll int x, y, gc = 0;
142	ll int a = 28;//rand()%1000000000;
143	ll int b = 19;//rand()%1000000000;
144	gc = gcd(a, b, x, y);
145	cout << a << "*x + " << b << "*y == "  << gc << " | x==" << x << " y==" << y << endl;
146	
147	dha();
148	
149	ll int discretlog_power = discr_log(basis, modulus, answer);
150	cout << endl << "Discret Logarithm(a^x mod p) x == " <<  discretlog_power << endl;
151	ll int answer2 = fast_power(basis, discretlog_power, modulus);
152	cout << basis << " ^ " << discretlog_power << " mod " <<  modulus << " == " << answer2 << endl;
153	cout << "plog p == " << modulus * log(modulus) << endl;
154	
155	
156	return 0;
157}