ネット上では、膨大な通信が行われています。
通信はバケツリレー方式で、パケットという小分けした文が行き来します。途中で盗み見られたら困ります。

そこで、ネット通信では暗号システムが利用されます。Webでは「https」からはじまるURLは通信内容を暗号化し、より安全性が高くなっていると。
では、暗号化とは？

ネットで解りやすく紹介しているサイトが案外少なかったので、最も簡潔かつ分かりやすいサイトから一部を引用ご紹介します。

 

ITトレンド社の　https://it-trend.jp/encryption/article/64-0056

RSA暗号とは？仕組みや応用事例を初心者にもわかりやすく解説！

2024年12月04日 最終更新

暗号化のアルゴリズムとして活用されるRSA暗号ですが、セキュリティ対策を考える中で暗号化の仕組みが気になっている人は多いでしょう。
この記事ではRSA暗号の概要から暗号化と復号の流れ、そして応用例まで解説します。ぜひ参考にして、暗号化技術への理解を深めてください。

目次

から一部を引用ご紹介

RSA暗号とは

RSA暗号とは、素数を掛けあわせた数字の素因数分解の仕組みを利用した暗号技術の一つです。ここではRSA暗号の概要について詳しく解説します。

素因数分解が困難であることを利用したアルゴリズム

　大きな数字を素因数分解するのは困難です。総当たりする以外に素因数を見つけ出す方法がないためです。したがって、コンピュータで素因数分解しようとしても、大きな数であれば膨大な時間がかかります。

　この素因数分解の困難さを仕組みとして利用したのがRSA暗号です。RSAは発明した３人の名前「R. L. Rivest、A. Shamir、L. Adleman」に由来します。

　素因数分解の難しさを安全性の根拠にするということは、逆にいえば素因数分解されてしまうと解読されるということです。膨大な時間を掛けてコンピュータで計算したり、量子コンピュータを活用したりすれば素因数分解されてしまいます。

　しかし、それまでには情報が古くなり価値が失われているため、暗号として機能するのです。

公開鍵暗号方式のアルゴリズムの一種

　暗号化方式には公開鍵暗号方式と共通鍵暗号方式の２つがあり、RSA暗号は公開鍵暗号に該当します。公開鍵暗号方式とは、暗号鍵と復号鍵が別々の暗号方式です。データを解読するために使うのは復号鍵であって、暗号鍵ではありません。つまり、暗号鍵は第三者に見られても問題ないということです。暗号鍵は第三者を含め誰にでも公開されて使われることから、公開鍵暗号方式と呼ばれます。

　RSA暗号も公開鍵暗号方式で使われるアルゴリズムの一種ですが、鍵の交換だけでなく暗号化とデジタル署名を実現するアルゴリズムです。暗号とデジタル署名を両方とも達成できるアルゴリズムとして、世界で初めて登場しました。

RSA暗号を使ったやり取りの仕組み

RSA暗号を使ったやり取りの仕組み　

 

RSA暗号における、鍵を交換する仕組みを見ていきましょう。

１．受信者が公開鍵と秘密鍵を生成する

　始めに、データを受信する側が公開鍵と秘密鍵を準備しなければなりません。以下の手順で鍵を生成します。

  1. １．異なる２つの大きな素数「p」「q」を任意にとる
  2. ２．n＝pqとする
  3. ３．(p-1)(q-1)と互いに素な自然数eを任意にとる
  4. ４．edを(p-1)(q-1)で割った余りが１となる自然数dを任意にとる

　「互いに素」とは、最大公約数が１という意味です。こうして用意したnとeを公開鍵としてメッセージ送信側に渡します。p・q・dは秘密鍵であるため公開しません。では、上の手順の具体例を見ていきましょう。

  1. １．p＝７、q＝５とする
  2. ２．n＝７×５＝35
  3. ３．(p-1)(q-1)＝６×４＝24なため、e＝５とする
  4. ４．d＝５とする。このとき、
    　　ed÷((p-1)(q-1))＝26÷25＝１余り１
    　　となる

２．送信者がメッセージを暗号化する

　次はメッセージの送信側が作業します。受信側から受け取った公開鍵であるnとeを使い、以下の手順でメッセージを暗号化しましょう。

  1. １．送りたいメッセージを自然数xとする。ただしx＜nとする
  2. ２．xをe乗し、これをnで割った余りをyとする

　こうして算出されたyが暗号文です。これを受信側に送信します。では、上の手順の具体例を見ていきましょう。

  1. １．x＝12とする。これはx＜nを満たす（n＝35）
  2. ２．12を５乗し（＝248832）これを35で割ると余りy＝17となる

３．受信者がメッセージを復号する

　最後に、受信側は送られてきた暗号文yを復号し、平文（暗号化されていないデータ）を得ます。解き方の手順は以下のとおりです。

  1. １．yをd乗する
  2. ２．これをnで割った余りが平文xとなる

　では、上の手順の具体例を見ていきましょう。

  1. １．17を５乗する（＝1419857）
  2. ２．これを35で割った余りが平文12となる

　復号するにはdが必要ですが、これは受信者しか持たない秘密鍵であるため、第三者には復号されません。

　第三者がdを得るにはpとqが必要ですが、これらも秘密鍵です。p×qで算出されるnは公開されていますが、nからpとqを逆算するには素因数分解をしなければなりません。ここで膨大な手間がかかるため、現実的な時間では第三者に解読されることがないとされています。

以下省略

 

このようなRSA暗号システムを成り立たせるためには何が必要なの？

RSA暗号が使えるためには、極端に大きな数となるべき乗（多数回の乗数）計算と、割り算のあまり演算が高速で行えることが必要です。
Geminiに質問した結果を以下ご紹介（これが正しいのかどうか判断できませんが、調査の一助にはなりそう）

Q:　RSA暗号が成立するためには、乗数計算と割り算の余り計算が高速にできる必要がありますが、どんな方法があるのでしょうか？

Ans　：　RSA暗号の成立には、確かに乗数計算と剰余計算の高速化が不可欠です。これらの計算を効率的に行うための主な方法は以下の通りです。

1. 乗数計算の高速化

  • バイナリ法（繰り返し二乗法）:
    • べき乗指数を2進数で表現し、指数を左から右にスキャンします。
    • 各ビットに対して、自乗と乗算を条件に応じて繰り返すことで、計算量を大幅に削減します。
    • 例えば、x^13を計算する場合、13を2進数で表すと1101です。
    • この2進数表現に従って、x^1, x^2, x^4, x^8を計算し、必要なものを掛け合わせます。
  • モンゴメリ乗算:
    • 剰余演算と組み合わせることで、さらに高速な乗算を可能にします。
    • 特に、大きな数の乗算において効果を発揮します。

2. 剰余計算の高速化

  • バレットリダクション:
    • 除数の逆数を事前に計算しておくことで、剰余計算を高速化します。
    • 特に、同じ除数で繰り返し剰余計算を行う場合に有効です。
  • モンゴメリリダクション:
    • モンゴメリ乗算と組み合わせることで、効率的な剰余計算を実現します。
    • 除算を伴わない演算に置き換えることで、高速化を図ります。

3. ハードウェアによる高速化

  • 専用の暗号処理プロセッサ:
    • RSA暗号の演算に特化したハードウェアを使用することで、ソフトウェアよりもはるかに高速な処理が可能です。
  • GPU（Graphics Processing Unit）:
    • 並列処理能力の高いGPUを利用して、複数の剰余乗算を同時に実行することで、高速化を図ります。

これらの技術を組み合わせることで、RSA暗号の演算を効率的に実行し、実用的な速度を実現しています。