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;
  printf("Please Input Public key n:");
  scanf("%d",&n);
  printf("please Input Public key e:");
  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;
  printf("Please Input Public key n:");
  scanf("%d",&n);
  printf("please Input Public key d:");
  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];
}

苦労した覚えがあるのはRSAのアルゴリズムではなくファイルのやりとりである。
しかもテキストファイルのやりとりができないという何故これでレポートが通過したのかよくわからない。

今回、Pythonで多少改良したRSAの実装は以下の通り、

# 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!"

これでも暗号としては脆弱だと思う。
数学に明るくない悪い人を追い払う程度の性能である。