アルゴリズム 一覧

トポロジカルソート

  • 更新日:
  • アルゴリズム

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

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

RSA暗号

  • 更新日:
  • アルゴリズム

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

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

暗号文 ← 平文の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)

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

このページの上部へ

About

tetsuの日記・雑記です。
日々経験したことを記録していきます。

広告

サイト内検索

最近のピクチャ

  • リアディレーラ

月別アーカイブ

最近のコメント