PARI/GP 暗号プログラム

PARI/GP で作成した暗号プログラムのサンプルを紹介します．

機能概要
RSA 暗号で使用する暗号鍵（秘密鍵，公開鍵）を生成するプログラムです．公開鍵 n，e と秘密鍵 d を生成します．ソースプログラムは， rsa_kgen.gp です．
プログラム
プログラムは，以下の処理を行う関数 (rsa_kgen) を定義しています．また，この関数を使用してランダムなメッセージを暗号化・復号して動作を確認します．
1. 素数 p，q をビット長 nb/2 でランダムに生成する（p > q）．
2. p - 1 と q - 1 の最小公倍数 λ(n) を計算し，λ(n) と互いに素で λ(n) より小さな任意の整数 e を選ぶ．
  
  λ(n) = LCM (p-1, q-1)
  
  e ∈ Z_λ(n)　 (3 ≦ e ≦ n - 1, 　GCD (e, λ(n)) = 1)
3. ed ＝ 1 mod λ(n)を満たす d を求める．
  
  d = 1/e mod λ(n)
4. 鍵ベクトル [p, q，n, e，d] を返す．
```
rsa_kgen (nb, eb)

  引数：
    nb：公開鍵 n のビット長
    eb：公開鍵 e のビット長
　戻り値：
    鍵：[p, q, n, e, d]
```

機能概要
RSA 暗号で暗号化されたデータを解読するプログラムです．公開鍵 n，e と暗号文 C が与えられたときに，平文 M を求めます．ソースプログラムは， rsa_dec.gp です．
プログラム
プログラムは，以下の処理を行う関数を定義しています．
1. n を素因数分解し，素数 p，q を求める．
2. 秘密鍵 d を求める．
3. 暗号文 C を復号する．
4. 戻り値として，平文 M を返す．
```
rsa_dec (c, e, C)

  引数：
    n：公開鍵 n
    e：公開鍵 e
    C：暗号文 C
　戻り値：
　　平文 M
```

機能概要
楕円 ElGamal 暗号アルゴリズム (楕円ElGamal暗号) を用いた暗号化・復号機能を確認するプログラムです．ソースプログラムは， elgamal.gp です．
プログラム
プログラムでは，以下の処理を行っています．
1. 指定した楕円曲線パラメータで楕円曲線を生成する．
2. 乱数で秘密鍵 x を生成した後，対応する公開鍵 P を生成する．
3. 暗号化対象メッセージ m をランダムに生成し，楕円点の X 座標とする．
4. メッセージの暗号化処理を行い，暗号文 (C1, C2) を生成する．
5. 暗号文を復号し，復号結果が正しいか（元のメッセージに戻るか）を確認する．