キーワード辞典
公開鍵暗号方式

登録日 09/02/07   更新日 09/02/07




公開鍵暗号方式

暗号化と復号とに別の鍵を使い、暗号化の為の鍵を公開できるようにした暗号方式。 暗号化する鍵が公開されている為、共通鍵暗号方式に見られる様な問題が起きず、 復号する鍵を本人だけが持つことで盗聴を防ぐ。 有名なものにRSAが有るが、RSAだけが公開鍵暗号方式では無いので、 混同してはいけない。


RSA

有名な公開鍵暗号方式のアルゴリズムの一つ。 片方の鍵で暗号化するともう片方の鍵でないと復号出来ない関係を持つ一対の鍵を使用する。 片方を誰でも使える公開鍵、もう片方を自分だけの秘密鍵にし、 送信時の暗号化に受信者の公開鍵、受信時の復号に受信者の秘密鍵、を使用することで、 誰でも暗号化が出来るがそれを復号出来るのは受信者のみとなる。
RSAは、開発した3人の技術者の頭文字。

「2つの素数p、qの積Nを法(N−1までしか数が存在せず1を加えると0に戻る)とする、 計数機の様な世界では、 或る数を、 n×(p−1とq−1の最小公倍数)+1)乗した値は、元の数と等しくなる(nは任意の整数)」 ことを利用している。
具体的には、

  1. 2つの素数pとqを決める。
  2. pとqを掛けて法Nを求める。
  3. (p-1)と(q-1)の最小公倍数Lを求める。
    Lは、元の数に戻る、べき乗数の周期。
    L+1は、1乗を除き、最初に元の数に戻る時のべき乗数。
  4. e×dを(p-1)×(q-1)で割った余りが1となり、 3以上でLより小さく、Lとの最大公約数が1(=互いに素)である、 整数eと整数dを決める
  5. Nとeが公開鍵、Nとdが秘密鍵になる。
  6. 暗号化は、公開鍵を使って、暗号文=平文 mod N
    復号は、秘密鍵を使って、平文=暗号文 mod N

RynもEXCELでやってみた。
2つの素数p=3、q=11とすると、法Nは33。
(p−1)の2と(q−1)の10との最小公倍数Lは10。
(e×d)mod((p−1)×(q−1))=1で、3以上L未満、Lと互いに素である、eとdを求める。
e=7、d=3、とすると、
(7×3)mod(2×10)=1となる。

例1(図の赤丸)
平文3を暗号化する場合は、公開鍵(N=33,e=7)を使って、3 mod 33=9
暗号文9を復号する場合は、秘密鍵(N=33,d=3)を使って、9 mod 33=3

例2(図の緑丸)
平文8を暗号化する場合は、公開鍵を使って、8 mod 33=2
暗号文2を復号する場合は、秘密鍵を使って、2 mod 33=8




小さい数では余り面白くないが、 非常に大きな数においては、素数×素数の計算は簡単だが、 因数分解した2つの数値が素数かどうかを調べるのは無茶苦茶時間がかかる事から、 経験則としてセキュリティが高いとされている。 しかし、アルゴリズムが複雑で処理に時間がかかるので、 通常は平文全体をRSA方式で暗号化する事はせず、 送信者は、平文を、その時限りで作成した共通鍵暗号方式の秘密鍵(セション鍵)で暗号化し、 その秘密鍵をRSA方式の受信者の公開鍵で暗号化して、 暗号文と暗号化されたセション鍵の2つを送信する事が多い。 受信者は、RSA方式の自分だけの秘密鍵でセション鍵を復号した後、 そのセション鍵を使って暗号文を復号する。

物凄く乱暴な一例
実際はもっと複雑な処理をしています。勿論。

送信者の暗号化手順

  1. 平文をセション鍵3で暗号化する。
    「ロクジニエキ」→「リオゲテアエ」
  2. セション鍵3を受信者の公開鍵(33と7)で暗号化する
    mod 33=9
  3. 暗号文「リオゲテアエ」と暗号化されたセション鍵9を相手に送付する
受信者の復号手順
  1. セション鍵9を受信者の秘密鍵(33と3)で復号する
    mod 33=3
  2. 復号されたセション鍵3を使って、暗号文を復号する。
    「リオゲテアエ」→「ロクジニエキ」





[ 赤い玉の画像 ] 「キーワード辞典」の目次へ

[ 黒板消しとチョーク受けの画像 ]