さんぽみち

なにか思いついたときとかに気まぐれに更新されます。

Haskellの勉強 その1

はじめに

 Haskell の勉強記録を書いていこうとして、熱中して気づけば5時間ほど書いていたのですが、なんというか、すごく長くなってしまいました!!

 これではいかんと思い、もともと分割するつもりでは書いていましたがさらに細かく分割することにしました。

 でも、分割しすぎると何のための関数を書いているのかわからなくなるため、このエントリで全体を俯瞰的に示したいと思います。

RSA暗号を扱うために必要な機能

  • 鍵生成
  • 暗号化
  • 復号

  ただし、鍵生成は元となる二つの素数 p, q 及び公開鍵である e を渡されるものとする。

各機能で行う処理

鍵生成

 法となる n の計算

 φ(n) の計算

 秘密鍵 d の生成

 対となる鍵のペアを生成

暗号化・復号

 暗号化

 復号

 冪乗の計算

処理に対応する関数名とその内容

鍵生成

 法となる整数 n の計算 : genN

  RSA暗号は、数字を割った余りの世界(剰余類)での話となります。

  この時の割る数を "法" と呼びます。

  法 n の世界で考えたいときは、式の右端に (mod n) と書きます。

  また、この世界では左辺と右辺の値が等しくても、本当に等しいかわかりません。

  なので等号記号 "=" の変わりに合同記号 "≡" を使います。

   (左辺) ≡ (右辺)          (mod n)

  のように書きます。

  単に a を b で割った余り r を求めたいだけの場合は、

   r = a mod b

  と書きます。

 φ(n) の計算 : genPhiN

  φ(n) はオイラーのトーシェント関数といい、その定義は

   1 ~ n - 1 の範囲で n と互いに素であるものの個数を数える

  というものです。

  RSA暗号の基盤となっている "オイラーの定理" で重要な数字となります。

  大雑把なイメージとしては、

   条件付き*1だけど冪乗に周期性があって一周*2したら元の数字に戻るんだなぁ

  くらいに思ってもらえると十分です!

 秘密鍵 d の生成 : genD, gcdex

  φ(n) と公開鍵 e  から秘密鍵 d を生成します。

  平文を e 乗した状態が暗号文、暗号文を d 乗したら一周して平文に戻ります。

  e と d と φ(n) の関係は

   e × d ≡ 1          (mod φ(n))

    割った余りの世界へ、割ってなくなった数を足すと元に戻るので、

    以下のような整数 m が存在するはず

   e × d + φ(n) × m = 1

  となります。

  ここで、 gcdex は拡張ユークリッドの互除法を実装した関数です。

  これは整数 a, b の最大公約数 gcd 及び

   a × x + b × y = gcd

  を満たす最小の x, y を求めることができる方法です。

   a = e, x = d, b = φ(n), m = y, gcd = 1

  としてやると変形した式がこの形となるため、これより d を求めるわけです。

 対となる鍵のペアを生成 : genKeyPair

  これは元から与えられている公開鍵と上で生成した秘密鍵、法となる n を

  セットにして返すだけの関数です。

  プログラムとしてはこの関数だけを公開して鍵生成処理への入口とします。

 暗号化・復号

 暗号化 : ecrypt

  公開鍵 e と法 n を使って暗号化します。

  やることは平文を法 n の世界で e 乗するだけです。

 復号 : decrypt

  秘密鍵 d と法 n を使って復号します。

  やることは暗号文を法 n の世界で n 乗するだけです。

 冪状の計算 : power

  法 n の世界での冪乗を行います。

おわりに

 これ書くだけでも結構な量になった!

 前のエントリでRSA暗号の説明はしないって書いたけど、結局何やってるかわかんなかったらソースが読めないと思って概要と計算手順だけでも書いたらこうなりました。

 気を取り直して明日からこそプログラム書いていきます。

 Haskell の文法とかも書いた方がいいかなぁって思ったけど、実際のコードと比べながらの方がわかりやすいと思ったので、少なくともここには書かずに別エントリとします。

参考

 参考を書こうか考えたけど、各関数実装時に張った方がよさそうなのでここでは無とします。

*1:底と法が互いに素であることが条件

*2:一周でなくても整数周であればよい