＜引用文献・参考文献＞
■RSA暗号についての説明モデル及び数値計算の引用
宮野健二郎、古澤明 共著『量子コンピュータ入門』日本評論社、2016年3月、第２版、p68~72、第５章「ショアのアルゴリズム」１節「公開鍵暗号」より引用。
■計算方法に関する引用（拡張ユークリッドの互除法とバイナリ法）
N.D.マーミン「量子コンピュータ科学の基礎」木村元 訳、丸善株式会社、2009年、７月。
P101、3.8「周期関数を計算する」、p234、J.2「整数を法とする逆元を見つける方法」より引用。
■RSA問題とRSA仮定と素因数分解との関係についての参考文献
IPUSIRON著「暗号技術のすべて」株式会社シンクス、2017年8月。
P301～303「RSA問題とRSA仮定」
「RSA problem」 『フリー百科事典　ウィキペディア』
URL: en.wikipedia.org/wiki/RSA_pro...
・「The most efficient method known to solve the RSA problem is by first factoring the modulus N」
■ラビンの素数判定法について引用
「RSA暗号」 『フリー百科事典　ウィキペディア日本語版』
URL: ja.wikipedia.org/wiki/RSA%E6%...
・「桁数が大きい場合、確実に素数であると保証できる整数を見つけることは容易ではない。このため実際には、素数であるとは断言できないものの、素数である可能性が非常に高い自然数を用いる。こういった自然数の生成はMiller-Rabinテストなどの確率的素数判定法によって高速に行える。確率的素数判定法をパスした自然数を確率的素数 (probable prime) という。確率的素数には、素数の他に擬素数が含まれるが、その確率は判定回数を増やすことで極めて低くすることができる。
(なお、拡張リーマン予想が正しければ、Miller-Rabinテストは素数かどうかを正しく判定する、という事実が知られている)。
2002年8月、インド工科大学 のアグラワルらが素数判定を多項式時間で行うAKS素数判定法を発表したが、これは多項式の次数が高すぎて遅いので未だRSAの鍵生成に実用するには足らない。」
■鍵穴eについてフェルマー数が好まれる理由を引用
IPUSIRON著「暗号技術のすべて」株式会社シンクス、2017年8月。
P281「バイナリ法でより効率的な計算をするためにはeの２進数表示でなるべく１が登場しなければ良いことになります。なぜならステップ4bの処理をスキップでき、その分、乗算の回数が減るからです。「最上位ビットが１であること」と「eが奇数であること」を考慮すると、10…01bのような形式のeを選べば、暗号化の高速化が期待できます。」
■RSA暗号の複合に関する正当性の証明を引用
「RSA (cryptosystem)」 『フリー百科事典　ウィキペディア』
URL: en.wikipedia.org/wiki/RSA_(cr...
「Proofs of correctness」より引用
＜前提知識＞どちらも難しくない！小学校までの知識で大丈夫！
・合同式について（ただの時計算術！）
• 合同式（時計算術）
・ユークリッドの互除法について（最大公約数のだるま落とし！）
ja.wikipedia.org/wiki/%E3%83%...
＜台本＞
今回は、公開鍵暗号システムとRSA暗号についてのお話です。
問題設定。
差出人から受取人に、メールを送りたいとします。
このとき、盗聴者によってメールを盗聴される危険があります。
安全にメールを届けるにはどうすればよいでしょうか？
そこで登場するのが、暗号システムです。
暗号には、大きく分けて２つの種類があります。
一つは、共通鍵暗号。もう一つは、公開鍵暗号です。
今回は、公開鍵暗号について紹介します。
公開鍵暗号システムの概要。
公開鍵暗号システムは、公開鍵と秘密鍵のペアを使用します。
これはしばしば南京錠に喩えられます。
南京錠の錠に当たるのが公開鍵で、南京錠の鍵に当たるのが秘密鍵です。
公開鍵は、差出人を含む不特定多数に公開します。
秘密鍵は、公開せずに受取人が保管します。
次に、差出人は、公開鍵を使って、メッセージに鍵をかけます。これが情報の暗号化に当たります。
そして、鍵のかかったメッセージを受取人に送信します。
ここで、盗聴者が送信中のメッセージを盗聴したとしても、鍵がかかっているため解読は容易ではありません。
最後に、受取人が秘密鍵を使って、解錠します。
これにより、盗聴されることなく安全にメッセージをやり取りできるというわけです。
これが、公開鍵暗号システムの概要になります。
これはちょうど、郵便ポストのシステムに似ています。
つまりは、手紙を投函するのは簡単ですが、取り出すには容易ではありません。
次に、公開鍵暗号システムの一つであるRSA暗号についての概要を説明します。
RSA暗号では、２つの大きな素数を材料にして、鍵を作成します。。
まず、2つの素数の積をとって、合成数Nを作ります。第三者がこの巨大な合成数を素因数分解しようとすると大変困難であることが経験的に知られています。
この、巨大な合成数の頑丈さが、RSA暗号の頑丈さの、一つの保証になります。
しかし、この金属のかたまりだけでは、鍵として機能しません。
そこで、この合金を加工して、鍵穴と合鍵のペアを作成します。
この加工は、オイラーの定理という合同式の定理に基づいて行われます。
鍵穴eと合金Nのペアが公開鍵となり、鍵ｄが秘密鍵となります。
以上が、RSA暗号の鍵の作り方の概要になります。
ここからは、RSA暗号の具体的なレシピを見ていきましょう。
暗号は、３つのステップから構成されます。
それは、鍵の生成、暗号化、複合の３ステップです。
一つずつ見ていきましょう。
ステップ１、鍵の生成。
ここでは、先程の概要でも述べたように、２つの巨大素数を加工して、公開鍵と秘密鍵のペアを作ります。具体的な手順は、まる１で合成数Nと、ひと回り小さい合成数Nダッシュを作り、まる２で鍵穴eを作り、まる３で合鍵ｄを作ります。
そして、公開鍵を公開します。即ち、合成数Nと鍵穴eのペアを公開します。
ステップ２、鍵の施錠。
ここでは、差出人がメッセージMに鍵をかけて暗号化します。
具体的には、まる４のように、メッセージMをeでべき乗して、更にNで割った余りを暗号文とします。
これを、受取人に送信します。
もし、この送信中に盗聴者が、暗号文を盗聴しようとも、暗号化されているので解読は困難です。
ステップ３、鍵の解錠。
ここでは、受取人が、暗号文に秘密鍵を使って鍵を解錠し、メッセージを復元します。
具体的には、暗号文Cをｄでべき乗して、更にNで割った余りを計算します。
以上がRSA暗号のレシピになります。
最後に、実際に簡単な数値を使って計算してみましょう。
まず、差出人が数字の「５」というメッセージを受取人に送りたいとします。
ステップ１、鍵の生成。
今回は、巨大な素数を用意できなかったので、小さな素数の、３と１１で計算してみます。
まず、まる１を計算すると、３３と２０となります。
次に、まる２を計算します。このとき、２０と互いに素な自然数は沢山ありますが、どれを選んでも構いません。今回は７を選ぶことにします。
最後に、まる３を計算すると、答えは３になります。答えの候補として、２３や４３なども含まれますが、最小のもので十分です。
これで、公開鍵と秘密鍵は完成です。
そして、公開鍵である合成数33と鍵穴7のペアを公開します。秘密鍵の３は自分で保管しておきます。
ステップ２、鍵の施錠。
ここでは、差出人がまる４の計算をします。計算結果は１４となります。
これで暗号化は完了です。
この暗号文の１４を受取人に送信します。
この送信の最中に、盗聴者が暗号文の１４を盗聴したとします。また、公開鍵の33と7は、手に入れているものとします。このとき、３３、７、１４という情報から元のメッセージを復元することは可能でしょうか？
盗聴者が暗号文の作り方を知っているものとすると、
このような等式が得られます。
この等式から、元のメッセージMを復元できるでしょうか？
この問題はRSA問題と呼ばれています。
このRSA問題を効率的に解く方法が存在しない。という仮定を、RSA仮定といいます。
実際に、今の所、古典コンピュータでRSA問題を効率的に解くアルゴリズムは見つかっていません。RSA暗号の安全性の根拠は、RSA仮定が未だ破られていないという経験事実に基づいています。
ステップ３、鍵の解錠。
ここでは、受取人が、まる５の計算をします。計算結果は５となり、無事、復号が出来ました。
では、なぜ、この計算で複号できるのでしょうか？
それは、オイラーの定理を用いて証明できます。
そもそもこのRSA暗号は、オイラーの定理に基づいて作成されているのです。
Instagram ▶︎ azusa980904...
#RSA暗号
#公開鍵暗号
#素因数分解
#フェルマーの小定理
#フェルマー
#合同式