読者です 読者をやめる 読者になる 読者になる

つけじょにーのすぱげていコード

主に、競技プログラミング、セキュリティのお勉強の際に書いたすぱげていコードを書き込みます

RSA@C++

試しにRSA暗号化及び複合化を行うプログラムを作成してみました(すっごいチープ。平文は整数値じゃなきゃだめ)。

試しに平文123にしてみて、暗号化、複合化をしてみたのですが、思ったように複合できませんでした

う〜ん、p, qを選ぶところがまずいのかな?

 

//公開鍵暗号

//RSA cipher

#include <iostream>

#include <cstdio>

#include <cstdlib>

using namespace std;

typedef long long ll;

int E, D, N;

 

int gcd(int a, int b) {

    if(b == 0) return(a);

    return(gcd(b, a % b));

}

 

int lcm(int m, int n) {

    if(m == 0 || n == 0) return(0);

    return(m * n / gcd(m, n));

}

 

bool isPrime(int n) {

    if(n < 2) return(false);

    for(int r = 2; r * r <= n; r++) {

        if(n % r == 0) return(false);

    }

    return(true);

}

 

void generate() {

    srand*1;

    int p, q;

    while(true) {

        p = rand() % 100;

        q = rand() % 100;

        if(isPrime(p) && isPrime(q)) break;

    }

    

    N = p * q;

    int L = lcm(p - 1, q - 1); //一時的な値

    for(int r = 1; r <= L; r++) {

        if(gcd(r, L) == 1) E = r;

    }

    for(int r = 1; r <= L; r++) {

        if((E * r) % L == 1) D = r;

    }

    cout << "------------------------------------------" << endl;

    cout << "Your public-key:" << endl;

    cout << "E:" << E << endl;

    cout << "N:" << N << endl;

    

    cout << "Your private-key:" << endl;

    cout << "D:" << D << endl;

    cout << "N:" << N << endl;

    cout << "------------------------------------------" << endl;

}

 

ll mod_pow(ll x, ll n) {

    ll res = 1;

    while(n > 0) {

        if(n & 1) res = res * x;

        

        x = x * x;

        n >>= 1;

    }

    return(res);

}

 

ll encrypt(int plain) {

    return(mod_pow(plain, E) % N);

}

 

ll decode(int cipher) {

    return(mod_pow(cipher, D) % N);

}

 

int main(void) {

    int choice; cin >> choice;//暗号化は1 複合化は2

    

    if(choice == 1) {

        generate();

        int plain; cin >> plain; //平文 ここでは数値

        cout << "cipher is " << encrypt(plain) << endl;

    } else {

        cin >> D >> N; //秘密鍵を入力

        int cipher; cin >> cipher;

        cout << "plain is " << decode(cipher) << endl;

    }

    return(0);

}

*1:unsigned)time(NULL