Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <math.h>
- #include <string.h>
- #include <string>
- #include <stdio.h>
- #include <stdlib.h>
- #include "InfInt.h"
- #include <time.h>
- #include <clocale>
- bool Miller(InfInt prime, int iteration);
- InfInt calculateE( InfInt t );
- InfInt greatestCommonDivisor( InfInt e, InfInt t );
- InfInt FindD( InfInt e, InfInt t );
- InfInt encrypt( InfInt i, InfInt e, InfInt n );
- InfInt decrypt(InfInt i, InfInt d, InfInt n );
- InfInt generate();
- //генерация числа
- InfInt generate(){
- InfInt t = 1;
- srand(time(NULL));
- for (int i = 0; i < 128; i++){
- if (rand() % 100 < 51){
- t++;
- }
- t=t*2;
- }
- std::cout << t << std::endl;
- return t;
- }
- //умножение по модулю
- InfInt multmod(InfInt a, InfInt b, InfInt mod){
- InfInt x = 0,y = a % mod;
- while (b > 0){
- if (b % 2 == 1){
- x = (x + y) % mod;
- }
- y = (y * 2) % mod;
- b /= 2;
- }
- return x % mod;
- }
- //возведения в степень по модулю
- InfInt powmod(InfInt base, InfInt exp, InfInt mod){
- if (exp == 0){
- return 1;
- }
- InfInt z = powmod(base, exp/2, mod);
- if (exp % 2 == 0){
- return (z * z) % mod;
- }
- else{
- return (base * z *z) % mod;
- }
- }
- bool Miller(InfInt p,int iteration){
- clock_t startm = clock();
- srand(time(NULL));
- if (p < 2){
- return false;
- }
- if (p != 2 && p % 2==0){
- return false;
- }
- InfInt s = p - 1;
- while (s % 2 == 0){
- s /= 2;
- }
- for (int i = 0; i < iteration; i++){
- InfInt a = (InfInt)rand() % (p - 1) + 1;
- InfInt temp = s;
- InfInt mod = powmod(a, temp, p);
- while (temp != p - 1 && mod != 1 && mod != p - 1){
- mod = multmod(mod, mod, p);
- temp *= 2;
- }
- if (mod != p - 1 && temp % 2 == 0){
- return false;
- }
- }
- clock_t endm = clock();
- double seconds = (double)(endm - startm) / CLOCKS_PER_SEC;
- printf("Время прохождения теста Миллера-Рабина: %f секунд\n", seconds);
- return true;
- }
- InfInt calculateE( InfInt t ){
- InfInt e;
- for ( e = 2; e < t; e++ ){
- if (greatestCommonDivisor( e, t ) == 1 ){
- return e;
- }
- }
- return -1;
- }
- //НОД
- InfInt greatestCommonDivisor( InfInt e, InfInt t ){
- while ( e > 0 ){
- InfInt Temp;
- Temp = e;
- e = t % e;
- t = Temp;
- }
- return t;
- }
- InfInt FindD(InfInt e, InfInt t){
- InfInt inv, u1, u3, v1, v3, t1, t3, q;
- InfInt iter;
- u1 = 1;
- u3 = e;
- v1 = 0;
- v3 = t;
- iter = 1;
- while (v3 != 0)
- {
- q = u3 / v3;
- t3 = u3 % v3;
- t1 = u1 + q * v1;
- u1 = v1;
- v1 = t1;
- u3 = v3;
- v3 = t3;
- iter = -iter;
- }
- if (u3 != 1)
- return 0;
- if (iter < 0)
- inv = t - u1;
- else
- inv = u1;
- return inv;
- }
- InfInt encrypt( InfInt i, InfInt e, InfInt n ){
- InfInt current, result;
- current = i - 97;
- result = 1;
- result = powmod(current, e, n);
- return result;
- }
- InfInt decrypt(InfInt i, InfInt d, InfInt n){
- InfInt current, result;
- current = i;
- result = 1;
- result = powmod(current, d, n);
- return result + 97;
- }
- int main( ){
- setlocale(LC_CTYPE, "rus");
- clock_t start = clock();
- InfInt p, q, n, t, e, d;
- InfInt encryptedText[100];
- memset(encryptedText, 0, sizeof(InfInt));
- InfInt decryptedText[100];
- memset(decryptedText, 0, sizeof(InfInt));
- bool flag1;
- std::string msg;
- std::cout << "Генерация простого длинного числа p...." << std::endl;
- p = generate();
- do{
- flag1 = Miller( p, 2);
- if ( flag1 == false ){
- p++;
- std::cout << p << std::endl;
- }
- } while ( flag1 == false);
- std::cout << "Генерация простого длинного числа q....:" << std::endl;
- q = generate();
- do{
- flag1 = Miller( q, 2);
- if ( flag1 == false ){
- q++;
- std::cout << q << std::endl;
- }
- } while ( flag1 == false);
- n = p * q;
- std::cout << "\nМодуль n чисел p и q = " << n << std::endl;
- t = ( p - 1 ) * ( q - 1 );
- std::cout << "\nФункция Эйлера для чисел p и q = " << t << std::endl;
- e = calculateE( t );
- d = FindD(e,t);
- std::cout << "\nОткрытый ключ (n = " << n << ", e = " << e << ")" << std::endl;
- std::cout <<"Закрытый ключ (n = " << n << ", d = " << d << ")" << std::endl;
- std::cout << "\nВведите сообщение : " << std::endl;
- std::getline( std::cin, msg );
- std::cout << "\nВаще сообщение : " << msg << std::endl;
- for (long int i = 0; i < msg.length(); i++){
- setlocale(LC_CTYPE, "rus");
- encryptedText[i] = encrypt(msg[i], e, n);
- }
- std::cout << "\nВаше закодированное сообщение :" << std::endl;
- for ( long int i = 0; i < msg.length(); i++ ){
- printf( "%i", encryptedText[i] );
- }
- for (long int i = 0; i < msg.length(); i++){
- decryptedText[i] = decrypt(encryptedText[i], d, n);
- }
- std::cout << "\nВаше раскодированное сообщение:" << std::endl;
- for (long int i = 0; i < msg.length(); i++){
- setlocale(LC_CTYPE, "rus");
- printf( "%c", (unsigned char)decryptedText[i].toInt() );
- }
- clock_t end = clock();
- double seconds = (double)(end - start) / CLOCKS_PER_SEC;
- printf("\nThe time: %f seconds\n", seconds);
- std::cout << std::endl << std::endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement