エルガマル暗号のプログラム

エルガマル暗号をプログラムにしてみた。

素数とか原始元の計算は抜きにしたので、現実で使えるかと言われればダメ。
あんまりしっかりとやっていないので間違いもあり得るし、おそらく入力に対して何かしらのエラーを吐く可能性も無きにしも非ず。

まあ、参考程度ですね。

まず鍵の作成。

大きな素数prime、原始根root、有限体の要素skeyを定める。
次に
pkey≡root^skey (mod prime)
を計算し、skeyを秘密鍵、prime, root, pkeyを公開鍵とする。

暗号化。

送りたい平文をmessageとする。

乱数randomを生成し、
c1=root^random (mod prime)
c2=message*pkey^random (mod prime)
の二つのペア(c1, c2)が暗号文となる。

最後に復号化。

秘密鍵skeyを使い、次のように計算すると暗号文を復号化できる。
c1*c2^(p-1-s) (mod prime)

以下プログラム。

/* 
 * エルガマル暗号の暗号化関数
 * 
 * stdio.h、stdlib.h、time.hのインクルードが必要
 * message:平文　prime:素数　root:原始根　pkey:公開鍵　*a、*bはできあがる暗号文を返すためのもの
 */
void encode(int message, int prime, int root, int pkey, int *a, int *b)
{
    /* 
     * 素数より入力の平文が大きいときは暗号化できないので失敗
     * ふつうは平文を区切ったりするらしい
     * 
     * TODO:入力が大きくてもできるように変える
     */
    if(pkey<message){
        printf("This encode is FAILURE");
        exit(EXIT_FAILURE);
    }
    else{
        srand((unsigned)time(NULL));
        
        /* 1以上INDEX_MAX以下の乱数を生成 */
        int k = rand()%INDEX_MAX+1;

        /* 暗号文を生成 */
        *a = mod(intPow(root, k),prime);
        *b = mod(intPow(pkey,k)*message, prime);
    }    
}

/* 
 * エルガマル暗号の復号化関数 
 *
 * a,b:暗号文　prime:素数　skey:秘密鍵
 */
int decode(int a, int b,int prime, int skey)
{
    return mod(intPow(a, prime-1-skey)*b, prime);
}

/* 
 * エルガマル暗号の鍵の生成
 * 
 * prime:素数　root:原始根　skey:秘密鍵
 */
int publicKey(int prime, int root, int skey)
{
    return mod(intPow(root, skey),prime);
}

/* 
 * int型のint型の累乗の計算を行う関数
 * 
 * おそらくもっと高速に動くアルゴリズムが存在する
 * TODO:もっと高速な計算ができるようにする
 */
int</span> intPow(int a, int b)
{
    if(b<0)
        return 0;
    int result=1;

    for(int i=0; i<b; i++)
        result = result*a;

    return result;
}

/* モジュラ演算を行う関数 */
int mod(int a, int b)
{
    return a%b<0 ? a%b+b:a%b;
}