간단하게 rsa 암호 소스를 짜봤다.
#include<iostream>
#include<cmath>
#include<iomanip>
#include<time.h>
using namespace std;
//딥다큰 소수 두개. 소수를 찾는일은 따로 알아보자.
#define LPRIME_1 1175003
#define LPRIME_2 1249921
int gcd(long a, long b){
long r =0;
if(b>a){
long tmp = a;
a = b;
b = tmp;
}
r = a%b;
while(r>0){
a = b;
b = r;
r = a%b;
}
return b;
}
long getPublicKey_e(long pi_N){
long e=0;
long tmpGcd;
while(1){
e = (long)(rand()%pi_N+1);
if(e == 1)
continue;
tmpGcd = gcd(e, pi_N);
if(tmpGcd == 1)
break;
}
return e;
}
//확장 유클리드알고리즘. fine private key
long extendedEuclid(long e, long pi_N){
long E, N, q, r,s,t,u;
E = e;
N = pi_N;
t = 0; u = 1;
while(E!=1)
{
q = N/E;
r = N - E*q;
s = t - u*q;
N = E;
E = r;
t = u;
u = s;
}
if(u < 0)
u = u+pi_N;
return u;
}
//암호화 또는 복호와의 핵심 (M^e(mod N) or C^e(mod N) )
long expX_modN(long X, long exp, long N){
long tmp=1;
while(exp!=0){
while(exp%2 ==0){
exp = exp/2;
X = (X*X)%N;
}
exp--;
tmp = (tmp*X)%N;
}
return tmp;
}
int main(){
srand(time(0));
char message[256]={0,};
long plainM;
long cipherC;
int smallp=3, smallq = 37; //for test
long N = smallp*smallq;
long pi_N = (long)((smallp-1)*(smallq-1));
long e = getPublicKey_e(pi_N);
long d = extendedEuclid(e, pi_N);
plainM = 78; //plainM은 N보다 작아야겠죠
cipherC = expX_modN(plainM, e, N); //cription
cout<<"평문 : "<<plainM<<"암호문 : "<<cipherC<<endl;
plainM = expX_modN(cipherC, d, N);
cout<<"복호문 : "<<plainM<<endl;
return 0;
}