C言語でRSA暗号(公開鍵暗号)を作ってみた

はじめに

Web業界にいると良く聞く公開鍵暗号ですが、それがどのような理由で考えられ、どのような仕組みになっているか気になり、その一種であるRSA暗号を作ってみようと思いました。

RSA暗号とは

公開鍵暗号アルゴリズムの一つです。
まず、公開鍵暗号とは、鍵輸送問題というものを解決するべく考えられました。
公開鍵暗号が考えられる以前、対称暗号というものがありました。これは、秘密の文章を特定の人だけに読めるような形で送信したい場合に、その文章を暗号化するための鍵を作成し、その鍵をもって文章を暗号化し相手に送信するということをおこなっていました。
そして、暗号化された文章を受け取った人は、そのままでは読めないので、送信した人から暗号化した際に使用した鍵を送ってもらい、その鍵で復号します。
そうなると、この鍵を送信している間に盗まれたら、盗んだ人は誰でも文章を復号できてしまいます。
これが、鍵の輸送問題です。
この問題を解決するべく幾つかの手法が考えられ、その中でも強力であったのが、公開鍵暗号方式です。

公開鍵暗号方式は対象暗号方式と違い、暗号化の鍵(公開鍵)と復号の鍵(プライベートキー)が別のものとなっています。

公開鍵を使った秘密の文章のやりとりを簡単にまとめると以下のようになります。

1. Aさんが公開鍵とプライベートキーを公開鍵暗号アルゴリズムを用い、作成します。
2. Aさんは、Bさんに自分の公開鍵をおくります。
3. Bさんは、Aさんにおくってもらった公開鍵で送りたい秘密の文章を暗号化します
4. BさんはAさんに暗号化した文章をおくります
5. Aさんはプライベートキーで受け取った暗号文を復号します

上記により、安全に秘密の文章をやりとりできます。なぜなら、公開鍵では、暗号文を復号できないからです。

やり取りの説明の中ででてきた公開鍵暗号アルゴリズムの一種が今回作成したRSA暗号となります。

RSA暗号の実装

まず、RSA暗号の暗号式と復号式をみてみましょう。

• 暗号式

\begin{align}
C &= P ^ E \bmod N\\
\end{align}

• 復号式

\begin{align}
P &= C ^ D \bmod N\\
\end{align}

Cは暗号文を表し、Pは平文を表しています。そして、E,N公開鍵を表し、D,Nがプライベートキーを表しています。
なので、E,D,Nを求めるということが、公開鍵とプライベートキーを作成するということを意味しています。

簡単な手順としては、

1. Nをもとめる
2. Eをもとめる
3. Dをもとめる
   という順におこなっていきます。

コードを見ながら、どのように公開鍵(暗号鍵)　とプライベートキー(復号鍵)を求め、暗号文と復号分を作り出しているか見てみましょう。

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

unsigned int power( unsigned int a, unsigned int k, unsigned int n );

void main(){

srand((unsigned) time(NULL));

int flg = 0;
while(flg == 0){
  //Nを求める
  int N,p,q,p1,q1,flag = 0;

  //p素数判定
  while(flag == 0){
    p1 = rand() % 100000;
    int a,l;
    for(l=2; l<=sqrt(p1); l++){
      a = p1 % l;
      if(a == 0){
        //素数でない時
        flag = 0;
        break;
      }
      flag = 1;
    }
  }

  //q素数判定
  int flag1 = 0;
  while(flag1 == 0){
    q1 = rand() % 100;
    int b,m;
    for(m=2; m<=sqrt(q1); m++){
      b = q1 % m;
      if(b == 0){
        //素数でない時
        flag1 = 0;
        break;
      }
      flag1 = 1;
    }
  }

  p = p1;
  q = q1;

  N = p * q;

  //Lを求める
  int x,y,r,gcd,L;
  
  if( p > q ){
      x = p - 1;
      y = q - 1;
  }else{
      x = q - 1;
      y = p - 1;
  }
  
  //最大公約数を求める
  while((r = x % y) != 0){
    x = y;
    y = r;
  }

  gcd = y;

  //最小公倍数を求める
  L = (p - 1) * (q - 1) / gcd;

  //Eを求める
  int E,n,e1,gcdEL;

  while(gcdEL != 1){
    e1 = 0; //e1 reset
    while(e1 <= 1){
      e1 = rand() % L;
    }

    x = e1;
    y = L;

    while((r = x % y) != 0){
      x = y;
      y = r;
    }
    gcdEL = y;
  }

  E = e1;

  //Dを求める
  int x1 = 1;
  int y1 = 0;
  int z1 = L;
  int x2 = 0;
  int y2 = 1;
  int z2 = E;

  while(z2 != 0){
    int q = z1 / z2;
    int x3 = x1 - q * x2;
    int y3 = y1 - q * y2;
    int z3 = z1 - q * z2;
    x1 = x2;
    y1 = y2;
    z1 = z2;
    x2 = x3;
    y2 = y3;
    z2 = z3;
  }
  if(y1 < 0) continue;
  int D = y1;

  printf("\nN:%d\nL:%d\nE:%d\nD:%d\n",N,L,E,D);

  int hirabun;
  printf("暗号化したい数値を入力して下さい\n");
  scanf("%d",&hirabun);

  //暗号化
  int angou = power(hirabun,E,N);
  printf("平文:%d\n",hirabun);
  printf("暗号化:%d\n",angou);

  //復号
  int motobun = power(angou,D,N);
  printf("復号:%d\n", motobun);


  flg = 1;
}


}

/*
  繰り返し自乗法を使った法nのべき乗計算( aのk乗をnで割った余りを求める )

  unsigned int a : 底
  unsigned int k : 指数
  unsigned int n : 法
*/
unsigned int power( unsigned int a, unsigned int k, unsigned int n )
{
  if ( n >= 0x10000 ) return( 0 );

  if ( a == 0 || n == 0 ) return( 0 ); 
  if ( k == 0 ) return( 1 % n );       

  unsigned int currentMod = a % n;
  unsigned int currentValue = ( ( k & 1 ) > 0 ) ? currentMod : 1;

  for ( k >>= 1 ; k > 0 ; k >>= 1 ) {
    currentMod = ( currentMod * currentMod ) % n;
    if ( ( k & 1 ) > 0 )
      currentValue = ( currentValue * currentMod ) % n;
  }

  return( currentValue );
}

まず、Nですが、Nはランダムな2つの素数の積を求めることで、求めることができます。
コードでは、擬似乱数を生成し、素数かどうかを判定し、素数であった場合は、その素数らで積を求めています。

次に、鍵ペアを作る際に必要となるLを求めます。これは、それぞれの素数から-1した数の最小公倍数です。

いよいよ、Eですが、こちらは1より大きく、Lより小さな数で、EとLの最大公約数は1でなければなりません。
このEとLの最大公約数が1になるようなEを判定するにはユークリッドの互除法を使います。

\begin{eqnarray}
  1 \lt E \lt L\\
  gcd(E, L) = 1
\end{eqnarray}

そして、Dは、Eを用いて求めます。

\begin{eqnarray}
  1 \lt D \lt L\\
  (E　\times　D) \bmod L = 1
\end{eqnarray}

上記のように鍵のペアを作成することができます。
しかし、作り方はわかったけど、これは本当に安全なのかが気になるところです。

RSA暗号の安全性

一つ目にあげられる安全性として、鍵輸送問題が解決したことが挙げられます。
しかし、秘密鍵を公開鍵から求めることができるのではないかということと、総当たりで調べられたらわかるのではないかという問題があります。

総当たりで見つけられない理由として、Dのビット数の大きさがNと同程度になるので、2つ素数の大きさを1024ビットほどに設定すれば、総当たりで見つけるのは現在のマシンでは不可能に近いでしょう。

公開鍵から秘密鍵を求めることができるかもしれない懸念については、2つの素数を求めることが現状不可能に近いので心配しなくて良いという結論になっています。
なぜなら、鍵を作成するときに、

\begin{eqnarray}
  (E　\times　D) \bmod L = 1
\end{eqnarray}

上記をおこなっており、Lは2つの素数を用いて、求められているので、Dを求めることができません。
でも、Nは公開鍵に使われているので、2つの素数を求めることができるのではないかと思われるかもしれませんが、大きなNを素因数分解を地道にひたすら続けない限り求めることはできず、これも現在のマシンパワーでは不可能に近いです。

よって、RSA暗号の安全性は他の暗号方式に比べ高いと考えられます。

作成した感想

公開鍵という仕組みを今まで何気なく安全性も考えずに使っていたが、実際に作成し、仕組みを理解すると脆弱性等も鑑みることができるようになったので良い機会でした。

参考文献

「暗号技術入門　第3版」 結城浩