アルゴリズムの最近のブログ記事

それほど頻繁にではありませんが、トポロジカルソートというものを使うと効率よく問題が解ける場合があります。

トポロジカルソートとは、循環路がない有向グラフに帰着できるような問題において、半順序関係を満たすように並び替えることを言います。実際にどのように並び替えるかは、縦型探索を行うことによって実現できます。

今日、「暗号技術入門（結城浩著）」という本を借りてきました。結城さんはプログラム関連の本をたくさん書いていて、しかも丁寧かつ分かりやすい本が多いです。（厚めの本が多いですが・・・。）もし、詳しい参考書がほしいなら、この人の本を候補に入れてみるといいと思います。

さて、タイトルにあるRSA暗号なんですが、これは現在WWWで最もよく使われている暗号の１つです。公開鍵方式で、アルゴリズム自体は簡単です。暗号化は

暗号文 ← 平文のE乗 mod N

で実行できて、復号化は

平文　←　暗号文のD乗 mod N

で実現されます。公開鍵は[ E , N ]で、秘密鍵は[ D , N ]です。で、公開鍵を相手に送信して暗号化してもらって、暗号文を受信したら秘密鍵で復号します。

E,D,Nはそれぞれ、ある数学的な関連があります。まず、なるべく大きな素数p,qを掛け算してNを求めます。

N = p * q (p,q : 素数)

また、lcm(X,Y)を「XとYの最小公倍数」とするとき、仮にL = lcm(p-1,q-1)とおきます。

そして、Eは次のように求めることができます。EとLは互いに素です。

gcd( E , L ) = 1 (1 < E < L)

gcdは最小公約数を示します。これでEを計算した後、次のようなDを計算します。

(E * D) mod L = 1 (1 < D < L)

これで、公開鍵、秘密鍵が両方ともできたことになります。ちょっとややこしいんですが、プログラムで書くとわりと簡単に実装できます。ただ実際に暗号文を作るのは時間がかかりますけどね。