RSA暗号と量子コンピューティング 〜 公開鍵暗号方式のおさらい

まえがきのまえがき

専門家の方から正確な指摘を頂いているのでコメント欄を参照ください。
この記事の内容は正確性に欠けるので以下の記事を参照してください。
https://qiita.com/angel_p_57/items/897bf94160be8d637585

丁寧なコメントを頂いているので記事自体は残しておきます。

↓
↓
↓
↓
↓
↓
↓

まえがき

2020年8月13日（米国時間）、クラウド上で量子コンピューティングを提供するサービス『Amazon Braket』が公開された。
これにより誰もが安価に量子コンピューティングにアクセスできる時代になったわけだ。

量子コンピューティングの可能性はこれから先駆者たちの試行錯誤によって切り開かれていくと思わる。
しかしここに一つの既知の可能性、もとい脅威がある。
インターネットセキュリティの基盤をなしているRSA暗号が量子コンピューティングに脅かされるというものだ。
（先に言っておくと、ざっと調べた感じ、差し迫った驚異ではなさそうだ）

というわけで自分の理解を整理するために、何回かに分けてサクッとRSA暗号と量子コンピューティングについておさらいしてまとめてみる。
大丈夫、そんなに難しいものじゃない。しらんけど。

公開鍵暗号方式のおさらい

暗号方式には大きく分けて共通鍵暗号方式と公開鍵暗号方式がある。
暗号化鍵と復号鍵が、同一か異なるかという分類観点だ。

それぞれに特徴と課題があるが今回着眼するのは公開鍵暗号方式だ。

HTTPS接続を示すアイコンが南京錠マークなのは非常にセンスがあると思う。

暗号化鍵による暗号化＝金庫に南京錠をセットすること
復号鍵による復号化＝南京錠を開けること

に相当する。自分も混乱したときはよく使っているイメージだ。

暗号化鍵と復号鍵が異なることで共通鍵方式ではできない面白い使い方が２つできる。

公開鍵暗号通信

共通鍵暗号方式では同じ鍵を持つ者同士は平文が見えてしまうので秘密を知られたくない人間には死守しなければならない。
しかし公開鍵暗号方式では受信者が復号鍵さえ死守すれば平文が見られることはない。

1. 受信者が暗号化鍵を公開する
2. 送信者が暗号化して暗号文を送る
3. 受信者が復号して平文を入手

わかりやすい図はインターネットにいくらでもあるのでそちらを参考に。

デジタル署名

こちらは逆に復号鍵を公開して暗号化鍵を保管する。

1. 送信者が復号鍵を公開する
2. 送信者が送信文のメッセージダイジェストを暗号化する（デジタル署名）
3. 受信者がデジタル署名を復号して送信文のメッセージダイジェストと一致するか確認する（改竄検知）

こちらもわかりやすい図は探して。

公開鍵認証とかサーバ証明書に使われるやつ。

公開鍵暗号の信頼性

暗号の信頼性はざっと以下の感じだろうか。

1. 暗号文から平文を推定できないこと ２. 暗号化鍵から復号化鍵を推定できないこと（復号鍵から暗号化鍵を推定できないこと）
2. 暗号化鍵では平文を取り出せないこと（復号鍵で暗号化できないこと）

1は方式に関わらず暗号に求められる要件、2-3は公開鍵方式特有の要件だ
3に関しては一方向性といってとても重要な性質になってくる。

関数の一方向性

エンジニア向けなのでコードで書くが、以下の関係が成立する必要がある。

crypt = encrypt(text, encryptKey)          # (A)
recieved_text = decrypt(crypt, decryptKey) # (B)

assert text == recieved_text

一方向性とは(A)において『cryptとencryptKeyがわかってもtextが逆算できない』という性質になる。
（Bにおいても同様）
情報の損失を許すならそんな計算式はいくらでもある。（底関数、剰余算、絶対値など）
しかし復号可能となると普通の数学教養の範囲だとあまりお目にかからない。

ここが公開鍵暗号方式の肝要であり難しいところだ。

RSA暗号化方式

公開鍵暗号方式の実装の中で最もメジャーな実装。というか唯一の実用化ではなかろうか。
ssh-keygenコマンドで誰でも鍵を作ることができるし、やったことがある人も多いと思う。

おわりに

まずは公開鍵方式のおさらいから。
長くなったのでRSA暗号方式は次の記事で。

参考

詳しくはWiki見て

Wikipedia: 公開鍵暗号
https://ja.wikipedia.org/wiki/%E5%85%AC%E9%96%8B%E9%8D%B5%E6%9A%97%E5%8F%B7