公開鍵暗号

公開鍵暗号について解説します。共通鍵暗号についてはこちらをご覧ください。https://sc-exam.com/common-key/

公開鍵暗号とは

共通鍵暗号では暗号化と復号に同じ鍵を使用しているため鍵の配送問題がありました。公開鍵暗号では"公開鍵"と"秘密鍵"という２つの鍵を使って暗号化，復号を行います。公開鍵は名前の通り公開用の鍵です。秘密鍵を事前に共有しておく必要がない暗号で，非対称鍵暗号とも呼ばれます。

公開鍵暗号の特徴

受信者が事前に公開鍵を公開しておき，通信相手がその公開鍵で暗号化し，受信者の秘密鍵で復号します。共通鍵暗号は計算がシンプルで処理の負荷が少ないものでしたが，公開鍵暗号は計算が複雑なため処理が遅いです。

管理する鍵の数

公開鍵暗号では単純に 2n で求められます。Aさんに送りたい人が10人いても100人いても，Aさんは公開鍵とキーペアの秘密鍵があれば暗号化されたデータを受信できます。
Aさん，Bさん，Ｃさんがそれぞれ公開鍵を公開して，対応する秘密鍵を持っていればそれぞれで暗号化したデータの送受信が可能です。この場合公開鍵３つ，秘密鍵３つの計６つの鍵が必要となります。つまり2n(2*3)です。

公開鍵暗号方式の種類

ここでは代表的なものを取り上げます。

・RSA
素因数分解が困難なことを利用した暗号です。よく使われているものです。後の節で詳しく解説します。
・DSA
離散対数問題を利用しています。こちらは公開鍵暗号ですが，署名に使われるものですので別のページで解説予定です。
・ECC(楕円曲線暗号)
楕円曲線上の離散対数問題を根拠としている暗号です。RSAと比べて短い鍵長で安全性がほぼ同等であり，処理も比較的速いためRSAの代替となる暗号方式として注目されています。
・DH
これは離散対数問題を利用した鍵共有の方式です。これ単体ではデータを暗号化して送信はできませんが，DHで鍵を作成して共通鍵暗号で通信をしたりすることができます。

RSA

ここから下は手を動かして計算してみようのコーナーです。興味のある方はやってみてください。定理などの解説は省略していますので興味がある方は調べるか本などを買ってください。

鍵生成

・まず乱数を２つ(p,q)用意します。
この乱数は素数でなければなりません。今回はp=19,q=29とします。
実際にはそれぞれ数百桁やそれ以上のとても大きな素数を使います。大きな素数を作るには乱数を生成して，その乱数が素数か判定し，素数だったらそれを採用，素数でなかったら作り直しという工程を繰り返して選定します。

・次にNを計算します。これはpとqの積です。
p=19,q=29ですので551です。この値は暗号化にも復号にも使用します。つまり公開します。

・Lを求めます。(p-1)と(q-1)の最小公倍数となります。
最小公倍数は p*q/最大公約数で求めます。最大公約数はユークリッドの互除法を使用します。今回はとりあえず計算できればいいのでふーんくらいで構いません。
(19-1)と(29-1)の最小公倍数は252です。

・Eを求めます。この数は(L+1)と互いに素の数です。今回は11とします。
このEはよく65537が使われます。サイトの証明書の公開鍵情報の指数というところを見てみると見つかると思います。

・最後はDです。これは秘密鍵となり，Eの対となるものです。Eと同じ条件ですが，(L+1)=E*Dである必要があります。今回は23となります。(253=11*23)

これで鍵生成ができました。以下に計算した値を並べます。
・p:19
・q:29
・N:551(公開鍵，復号にも使用する)
・L:252
・E:11(公開鍵)
・D:23(秘密鍵)
※公開鍵以外の秘密鍵でない値も秘匿にする必要があります。その値から秘密鍵が推測されてしまうためです。

暗号化

やっと準備フェーズが終わり，暗号化フェーズになりました。
暗号化は平文^E mod N です。計算してみましょう。平文はわかりやすく12にしてみます。ちなみに，暗号化できる数値はNより小さいものです。今回の場合は550まで暗号化できます。
12^11 mod 551 この程度であればパソコンの関数電卓でも計算できると思いますが，指数表記になってしまう場合はweb上で計算できるツールを探してください。以下にツールを提供しているページリンクを貼りますが，当サイトとはなんら関係がないことに留意してください。
べき乗(^):Tamral Blog Tools
剰余(mod):miniwebtool
まず12^11を計算すると12ケタの数字が出ますね。これをmodすると46となります。この46が暗号文です。

復号

暗号文46を復号します。といっても暗号化とほぼ変わらず，平文を暗号文に，EをDに置き換えるだけです。
暗号文^D mod N　今回の値を入れると 46^23 mod 551 です。まず 46^23を計算します。39ケタの数値が出てきたかとおもいます。この程度の短い鍵長でもこんなに計算が大きくなってしまうので，実際にHTTPSなどで使われる際にとても負荷が掛かっていることが想像できるかと思います。
ちょっと脱線しましたが，最後に剰余を求めましょう。先ほどの39ケタの数値 mod 551です。出ましたでしょうか。12がでました！最初の平文が正しく復号できたのが確認できたかと思います。ぜひ他の数値でも試してみてください。

RSA暗号ですこし長くなってしまったのでDH法などは別ページにもう少し深堀りしたことを書く予定です。ここまでお読みいただきありがとうございます。パソコンの移行をする予定なので少し更新に時間がかかりそうです。

おすすめコンテンツ！

現在作成中