# RSA暗号を実装する

まずは昔レポート課題として書いたC言語によるRSAの実装を見てみる。

#include<stdio.h>
#include<math.h>
int gcd(int a,int b);//Calculate GCD(a,b)
int lcm(int a,int b);//Calculate LCM(a,b)
int public_e(int L);//Generate publickey e
int private_d(int L,int e);//Generate privatekey d
int Generatekey();
int Decode();
int Encode();

int main(void)//RSA System
{
int t;
printf("This is RSA cipher System\n");
printf("Now Would you select Mode\n");
printf("1.Generate RSA Key\n");
printf("2.Encoding\n");
printf("3.Decoding\n");
printf("Otherwise:Exit\n");
printf("Select the Number:");
scanf("%d",&t);
if(t==1)Generatekey();
if(t==2)Encode();
if(t==3)Decode();

}

int Encode(void)
{
FILE *fopen(),*fpr,*fpw;
char cc;
char namer[20],namew[20];
int n,e,x,y,i;
scanf("%d",&n);
scanf("%d",&e);
printf(" input file name? : ");
scanf("%s",namer);
printf(" output file name? : ");
scanf("%s",namew);
if((fpr=fopen(namer,"r")) == NULL) exit(-1);
if((fpw=fopen(namew,"w")) == NULL) exit(-1);
//Use only "fscanf" and "fprintf"
while((fscanf(fpr,"%c",&cc)) != EOF){
x=cc;
y=x%n;
for(i=2;i<=e;i++){//Compute y\equiv x^{e} mod n
y=(x*y)%n;

}
fprintf(fpw,"%d ",y);
}
fclose(fpr);
fclose(fpw);
return 0;
}

int Decode(void)
{
FILE *fopen(),*fpr,*fpw;
char namer[20],namew[20];
int n,d,x,y,i;
scanf("%d",&n);
scanf("%d",&d);
printf(" input file name? : ");
scanf("%s",namer);
printf(" output file name? : ");
scanf("%s",namew);
if((fpr=fopen(namer,"r")) == NULL) exit(-1);
if((fpw=fopen(namew,"w")) == NULL) exit(-1);
while((fscanf(fpr,"%d",&x)) != EOF){
y=x%n;
for(i=2;i<=d;i++){//Compute y\equiv x^{d} mod n
y=(x*y)%n;
}
fprintf(fpw,"%c",y);
}
fclose(fpr);
fclose(fpw);
return 0;
}

int Generatekey(void)
{
int p,q,n,L,d,e;
printf("Example 17 19");
printf("Please Input prime Number P Q:");
scanf("%d %d",&p,&q);
n=p*q;
L=lcm(p-1,q-1);
e=public_e(L);
d=private_d(L,e);
printf("Public key n is %d\n",n);
printf("Public key e is %d\n",e);
printf("Private key d is %d\n",d);
return 0;
}

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

int lcm(int a,int b)
{
int z;
z=gcd(a,b);
z=(a*b)/z;//a*b=GCD(a,b)*LCM(a,b)
return z;
}

int public_e(int L)
{
int e;
for(e=2;e<=L-1;e++){
if(gcd(e,L)==1){
return e;
}
else if(e==L-1){
printf("ERROR");//avoid infinite loop
return 0;
}
}
}

int private_d(int L,int e)
{
int q,x[3],y[3],r[3];
r[0]=L;r[1]=e;//default value
x[0]=1;x[1]=0;//default value
y[0]=0;y[1]=1;//default value
while(r[1]!=0){
r[2]=r[0]%r[1];
q=(r[0]-r[2])/r[1];
x[2]=x[0]-q*x[1];
y[2]=y[0]-q*y[1];
x[0]=x[1];x[1]=x[2];
y[0]=y[1];y[1]=y[2];
r[0]=r[1];r[1]=r[2];
}
if(y[0]<0)y[0]=y[0]+L;
return y[0];
}


しかもテキストファイルのやりとりができないという何故これでレポートが通過したのかよくわからない。

# coding: UTF-8

import math
import random
import fractions

def lcm(a,b):
return a*b/fractions.gcd(a,b)

def create_public_e(L):
for e in xrange(2,L):
if fractions.gcd(e,L) == 1:
return e;
elif e == L-1:
print "ERROR"

def create_public_d(L,e):
r_list = [L,e,0]
x_list = [1,0,0]
y_list = [0,1,0]
while (r_list[1] != 0):
r_list[2] = r_list[0] % r_list[1]
q = (r_list[0]-r_list[2]) / r_list[1]
x_list[2] = x_list[0] - q * x_list[1]
y_list[2] = y_list[0] - q * y_list[1]
x_list[0],x_list[1] = x_list[1],x_list[2]
y_list[0],y_list[1] = y_list[1],y_list[2]
r_list[0],r_list[1] = r_list[1],r_list[2]
while (y_list[0] < 0):
y_list[0] += L
return y_list[0]

def generate_key():
def primegen(x=10000):
while True:
if not [i for i in xrange(2,int(math.sqrt(x))+1) if x % i == 0]:
yield x
x += 1
p = primegen()
primes = [p.next() for x in xrange(1000)]
prime_key = random.sample(primes,2)
n = prime_key[0]*prime_key[1]
L = lcm(prime_key[0]-1,prime_key[1]-1)
e = create_public_e(L)
d = create_public_d(L,e)
print "Public key n is",n
print "Public key e is",e
print "Private key d is",d

def encode():
public_e = raw_input('Input Public key e: ')
public_n = raw_input('Input Public key n: ')
f_input_name = raw_input('Input File Name: ')
f_output_name = raw_input('Output File Name: ')
f_input = open(f_input_name,"r")
f_output = open(f_output_name,"w")
for line in f_input:
for text in map((lambda x: pow(ord(x),int(public_e),int(public_n))),list(line)):
f_output.write(str(text+int(public_n)*random.choice(xrange(int(public_n))))+" ")
f_input.close()
f_output.close()

def decode():
public_n = raw_input('Input Public key n: ')
private_d = raw_input('Input Private key d: ')
f_input_name = raw_input('Input File Name: ')
f_output_name = raw_input('Output File Name: ')
f_input = open(f_input_name,"r")
f_output = open(f_output_name,"w")
for line in f_input:
#print map(int,line.split())
for text in map(int,line.split()):
f_output.write(chr(pow(text,int(private_d),int(public_n))))
#f_output.write(str(text)+" ")
f_input.close()
f_output.close()

print "RSA Cipher System"
print "Select Mode"
print "1.Generate RSA Key"
print "2.Encoding"
print "3.Decoding"
select = int(raw_input('Input Mode Number: '))
if select == 1:
generate_key()
elif select == 2:
encode()
elif select == 3:
decode()
else:
print "Bye!"


これでも暗号としては脆弱だと思う。