RSA暗号は、インターネットで安全に情報をやり取りするための代表的な暗号方式のひとつで、現在のオンライン通信の基盤として広く使われています。
最近、私はRSA暗号の仕組みについて学習したため、その復習としてまとめてみます。
言葉だけでなく、数式も用いて解説していきます！
なお、共通鍵暗号方式と公開鍵暗号方式について理解している前提で解説しています。
RSA暗号の基本原理
いきなり数式から入っても理解しずらいと思ったので、RSA暗号の概要と暗号として機能する理由についてざっくりと解説します。
RSA暗号は、数学の素因数分解の難しさを基盤としています。
具体的には、巨大な素数を掛け合わせてできた数（積）から元の素数を求める（因数分解する）のが非常に困難である、という性質に依存しています。
この「因数分解が難しい」という問題により、暗号化と復号の間に大きな差が生まれます。
暗号化と復号について
平文を暗号化する方法について確認していきましょう。
自然数Nを求める
まず大きな自然数Nを作るために、２つの素数p, qを選びます。
$$ N = pq $$
このときpとqは巨大な素数を選びます。
オイラーのファイ関数を求める
次に\(φ(N)\)を求めます。\(φ(N)\)はオイラーのファイ関数です。その定義は、
自然数nについて\(φ(n)\)とは、n以下の正の整数でnと互いに素な数の個数である。
\(φ(n)\)は以下の式で求めることが可能です。
\(φ(n)=(p-1)(q-1) \\
ただし、n = pqを満たす\)
例えば、\(φ(91)\)は\(91=13*7\)であるため、\(φ(91)=(13-1)*(7-1)\)で求めることができます。
しかし、この式を使わず自力で1から順番に調べていくと大変です。nを作る２つの素数が分かればファイ関数を求めることが容易だということがわかりました。（このことは後から重要になっていくので頭の片隅に入れておいてください）
公開鍵を決める
公開鍵として使うeを求めます。eは1より大きく\(φ(N)\)より小さい整数かつ、\(φ(N)\)と互いに素である必要があります。
秘密鍵を求める
公開鍵eに対して秘密鍵dを求めます。dは以下の式を満たす整数です。
$$e*d\equiv 1 \mod φ(N)$$
このdが秘密鍵の一部となります。
この結果、(n, e)が公開鍵として公開され、(n, d)が秘密鍵として保管されます。
鍵の生成方法がわかったので暗号化していきます。
鍵を使って暗号化する
暗号化は、公開鍵を用いて行います。メッセージを暗号化するには、次の式を使います：
$$C=M^e \mod N$$
ここで、Mはメッセージ(平文)であり、Cが暗号化されたメッセージ（暗号文）です。MはN未満の整数である必要があるため、メッセージが長すぎる場合は適切に分割して暗号化します。
復号の方法
送信者が公開鍵で暗号化した暗号文を秘密鍵で復号します。暗号文Cを復号するには、次の式を使います：
$$M=C^d \mod N$$
文字の意味は暗号化と同じです。dは秘密鍵を表しています。
こうすることで、元のメッセージ M が得られます。
この過程は数学的に証明されており、d が公開されない限り、暗号文から元のメッセージを復元することは非常に困難です。
おまけ
暗号化と復号は以下の通りに行いました。
暗号化：\(C=M^e \mod N\)
復号：\(M=C^d \mod N\)
つまり、\(M^{ed} \equiv M \mod N\)が成り立つということです。
これはフェルマーの小定理から導けます。
フェルマーの小定理
$$ a^{p-1} \equiv 1 \mod p$$
ただし、pは素数、aはpと互いに素な整数である。
まとめ
RSA暗号は、公開鍵暗号の基本を成す仕組みであり、現代の情報社会で欠かせないセキュリティ技術です。
数式だらけで難しいと思いますが、一つ一つ丁寧に確認していけば理解できます！
（補足）素因数分解の困難さで成り立つRSA暗号は計算コストが高いという課題があります。そのため、ハイブリッド暗号方式を用いることもあります。
最後までご覧いただき、ありがとうございます。お疲れ様でした。
コメント