RSA暗号の公開鍵と秘密鍵を生成する

いよいよRSA暗号です。（最近忙しくて遅れました）今回はRSA暗号で用いる公開鍵と秘密鍵を生成するプログラムを紹介します。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define RANDOMIZE() srand(time(NULL))
#define RANDOM(x)   (rand()%(x))
#define N   28
#define MAX 3000
#define PRM 500

//---Prime Number Search---
int prime_search(int ptable[])
{
  int i, j, count=0;
  int p[MAX];
  for(i=0 ; i<MAX ; i++){
    p[i] = 0;
  }
  p[0] = 1;
  for(i=2 ; i<=MAX/2 ; i++){
    for(j=2 ; i*j<=MAX ; j++){
      if(p[i*j-1] == 0){
       p[i*j-1] = 1;
      }
    }
  }
  for(i=0 ; i<MAX ; i++){
    if(p[i] == 0){
      ptable[count] = i+1;
      count++;
    }
  }
  return count;
}

int gcd(int x, int y)
{
  while(y != 0) {
    int temp = y;
    y = x%y;
    x = temp;
  }
  return x;
}

int add_gcd(int a, int b)
{
  int r_pre = a, r = b, r_next;
  int x_pre = 1, x = 0, x_next;
  int y_pre = 0, y = 1, y_next;
  int ans_x, ans_y, ans_gcd, ans, q, k = 1;
  while((r_next = r_pre%r) != 0){
   q = r_pre / r;
   k++;
   x_next = q*x + x_pre;
   y_next = q*y + y_pre;
   r_pre = r;
   r = r_next;
   x_pre = x;
   x = x_next;
   y_pre = y;
   y = y_next;
  }
  ans_x = pow(-1, k) * x;
  ans_y = pow(-1, k+1) * y;
  ans_gcd = (ans_x * a)+(ans_y * b);
  if(ans_gcd == 1) ans = (ans_x + b)%b;
  else ans = 0;
  return ans;
}

int main()
{
  int e, d, p, q, n, euler;
  int count, ptable[PRM];
  
  RANDOMIZE();
  count = prime_search(ptable);
  
  do{
    p = ptable[RANDOM(count)];
    q = ptable[RANDOM(count)];
    n = p * q;
  }while(n > N*N*N || n < N*N);
  euler = (p - 1) * (q - 1);
  do{
    e = RANDOM(euler);
  }while(gcd(e, euler) != 1);
  d = add_gcd(e, euler);

  printf("(e, n) = (%d, %d)\n(d, n) = (%d, %d)\n",
         e, n, d, n);
  
  return 0;
}

今回は簡単のために3000までの素数を扱うことにします。鍵生成までのステップは次のようになります。

1．素数表からp、qを選ぶ（疑似乱数を使用）
2．n = p * q を計算し、N^2 < n < N^3 （今回はN=28）であることを確かめる（満たさない場合はp、qを選びなおす）
3．オイラー関数φ(n) = (p-1)(q-1)を計算する
4．オイラー関数φ(n)より小さい正の整数eを選ぶ（eはオイラー関数と互いに素である）
5．φ(n)を法としたeの逆元を求め（拡張ユークリッドを使用）、この逆元をdとする
6．(e, n)を公開鍵、(d, n)を秘密鍵とする