RSApgm

rsa2.cpp

#include <iostream>
#include <random>
#include <math.h>
using namespace std;

void Eratosthenes(unsigned *prime_arr,unsigned N){
    unsigned arr[N];
    for(int i = 0; i < N; i++){
        arr[i] = 1;
        if(i < N / 2) prime_arr[i] = 0;
    }
    for(int i = 2; i < sqrt(N); i++){
        if(arr[i]){
            for(int j = 0; i * (j + 2) < N; j++){
                arr[i *(j + 2)] = 0;
            }
        }
    }
    int k=0;
    for(int i = 2; i < N; i++){
        if(k == 50) break;
        if(arr[i]){
            prime_arr[k] = i;
            k++;
        }        
    }
}

unsigned gcd(int a, int b){
    if (b == 0) return a;
    return gcd(b, a % b);
}

unsigned lcm(int a, int b){
    return a * b / gcd(a, b);
}

int extgcd(int a, int b, unsigned &x, unsigned &y){
    int d = a; 
    if (b == 0){
        x = 1;
        y = 0;
    }
　else {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }
    return d;
}

int main(int argc,char *argv[]){
    random_device rnd;
    mt19937 mt(rnd());
    uniform_int_distribution<int> rnd50(1, 50);
    unsigned prime_arr[50];
       unsigned p, q;
    unsigned n, e;
      unsigned d, x, y;

    Eratosthenes(prime_arr, 1000);
    do{
        p = prime_arr[rnd50(mt)];
        q = prime_arr[rnd50(mt)];
    }while(p == q);
    n = p * q;
    cout << "n = " << n <<endl;
    uniform_int_distribution<int> rndlcm(1, lcm(p - 1, q - 1));
    while(true){
        e =  rndlcm(mt);
        if(e > 1 && gcd(e, lcm(p - 1, q - 1)) == 1) break; 
    }
    cout << "e = " << e << endl;

    d = extgcd(e, lcm(p - 1,q - 1), x, y);
    unsigned privatekey = x;
    cout << "private = " << privatekey <<endl;


//ここからテスト
    cout<< "\n\n---------test---------" <<endl;
    unsigned k = 0;
    unsigned test_num = 252;
    unsigned enc = 1;
    unsigned temp = e;
    cout << "source = " << test_num <<endl;
    while(true){
        temp /= 2;
        k++;
        if(temp <= 0) break; 
    }
    cout << "bit_length = " << k <<endl;
    for(int i = k - 1;i >= 0;i--){
        enc = enc * enc % n;
        if(((e >> i) & 1) == 1) enc = enc * test_num % n;
    }

    cout << "encrypted = " << enc << endl;
    unsigned dec = 1;
    k = 0;
    temp = privatekey;
    while(true){
        temp /= 2;
        k++;
        if(temp <= 0) break;
    }
    for(int i = k - 1;i >= 0;i--){
        dec = dec * dec % n;
        if((privatekey >> i) & 1 == 1) dec = dec * enc % n;
    }

    cout << "decrypted = " << dec <<endl;
}