今回は、RSAアルゴリズムについて解説します。素数の法則を使ったアルゴリズムで「暗号化するための鍵と、暗号解読するための鍵が異なる」という、面白い性質があります。普通であれば、理解するのが難しいと思いますので、この記事では実際に数字を使って解説します。
まずは、公開鍵暗号方式について
さっそく小難しくなってすいませんでしたー。
暗号の詳細に興味ない方は、
「公開鍵Bで鍵かけたら秘密鍵Cでしか開けられないよ」
「逆に秘密鍵Cで鍵かけたら公開鍵Bでしか開けられないよ」
↑この謎技術を実現させてるのがRSAアルゴリズムだよ
これだけわかってればいいです。次行きましょう。
ーーーここからは小難しいことーーー✂︎ーーー
RSAアルゴリズムは 公開鍵暗号方式 という、暗号化の鍵を公開して使う暗号方式で使います。
ここで「暗号化の鍵を公開したら、暗号化してる意味がないのでは？」という疑問が湧いてきます。
ということで、 共通鍵方式 というものと比較してみましょう。
共通鍵方式では、私たちがよく使う「鍵」と同じ性質を持っています。
共通鍵Aで鍵をかけると、共通鍵Aでしか開きません。
一方 公開鍵方式では、公開鍵で鍵をかけ、秘密鍵で鍵を開けています。
これは公開鍵と秘密鍵の特性によるものです。
この不思議な特性を実現させているのが、RSAアルゴリズムです。
これを踏まえた上で、どのようにそれを実現しているか、実際に見ていきましょう！
では、実際その暗号化を使ってみよう。
注目！！！
ここ👇この記事で唯一、感覚的に楽しめるところとなっています。１回試してみてね！
まずは使ってみましょう。電卓を用意してください。
（１桁の数字の７乗ができれば不要です。頑張ってください😉）
- １桁の数字を一つ思い浮かべてください。これが暗号化前の平文となります。
- その数字を３乗して、１の位のみ覚えていてください。これが暗号文です。
- ではその数字を７乗してください。その時、１の位が最初に選んだ数字（平文）になります。
試しに８でやってみましょう
- ８の３乗＝５１２
- １の位なので ２ が暗号文になります。
- では、暗号解読 ２の７乗＝１２８
- １の位なので ８
- 見事に解読成功です。（因みに、暗算しました…）
- 嘘です。
この問題における鍵は、公開鍵（3と10）秘密鍵（7と10）です。
※１０というのは「１の位のみ覚える」という部分に関係します。（１の位の数字 ＝ 10で割った余り）
そして、暗号化の過程では３乗し、暗号解読（復号化）の過程では７乗しています。
公開鍵で鍵を閉め、秘密鍵で鍵を開けているわけですね。
実際はこれよりもっと大きな数字でやっていますが、原理は一緒です。
なんかすごい（小並感
この３や７、１０という数字は、もちろんテキトーに言っているのではではありません。
この数字の選定方法、解説します。
数学アレルギーの人は考えるのではなく、感じましょう。
じゃあ、実際のアルゴリズムを解説…しますか…ﾊｧ〜（長い溜め息
では。。。よろしくお願いします。
すいません。やります。
わかりやすく解説できるよう努力しますので、よろしくお願いします。
手順を下に書きます。頑張って解読してくださいw
- まず、このアルゴリズムを使う上で数字がいくつか出てきます。アルファベットで書きますが多いので、紙にでも書かないと分かりづらいかもしれません。（すべて整数）p, q, n, d, e, φ(n)
- 大きい素数を２つ選定します。これらを p, q とします（大きくなくても動くがセキュリティ低）
- p × q を計算し、これを n とします。
- (p-1)×(q-1)を計算し、 φ(n) とする
- 1 < e < φ(n) であり、eとφ(n)が互いに素であるような e を選ぶ
- (e * d) % φ(n) = 1 の条件を満たす d を求める（X％Yは、 XをYで割った時の余り）
- 公開鍵は(e, n) 秘密鍵は(d, n) とする。
- 暗号化: 暗号文C ≡ 平文M^e (mod n) nとeを知っている必要がある。
- 復号化: 平文M ≡ 暗号文C^d (mod n) nとdを知っている必要がある。
これで選定は完了！！
見事 解説コスト10、解読コスト90の説明ができましたね！
３とか７とか１０の選定の流れを見て貰えば分かりやすいかな…ということで貼っときます。
- 素数を２つ選定 p = 5, q = 2
- nを計算 n = 5×2 = 10
- φ(n)を計算 φ(n) = (5-1)×(2-1) = 4×1 = 4
- eを選定 （1 < e < 4で、eと4が互いに素） e = 3
- dを選定 （(3 * d) % 4 = 1） d = 7（(3×7)%4 = 21%4 = 1ですね）
- 公開鍵は(3,10) 秘密鍵は(7,10)
- 暗号化は (M^3)%10 復号化は (M^7)%10
これで30,70だな…
結局、公開鍵方式がなんで便利か
それは、ズバリ、 相手分鍵を持たなくていいから です。
画像使いまわしてすいません。
例えば、すべての暗号化を共通鍵で行うとどうなるでしょう？
答えは、やりとりする相手分鍵を持たなくてはいけません。
あなたとAさんで暗号文をやりとりしたとして、Bさんとも同じ共通鍵でやりとりしていたら、あなた・Aさんの他にBさんも暗号を解読できてしまいます。
そのため、あなたはAさんとやりとりする用の鍵、Bさんとやりとりする用の鍵を持たなくてはいけなくなります。管理も大変だし、相手によって変えるのも面倒ですよね。
ここで登場 公開鍵方式！！
AさんにもBさんにも、全員に公開鍵を渡してしまうんです。そして、公開鍵で暗号化された文章を開けられる秘密鍵だけ大事に隠して持っておけばいいわけです。
これにより１つの鍵で大勢とやりとりできる。さらに、情報も覗かれない。
お手軽で最強のセキュリティゲットです。
※ただし弱点もあります。例えば 暗号化・復号化処理が重いです。
累乗して余りを求めるので、計算がめんどくさい ＝ 時間がかかる ってことです。
これ考えた人は天才ですね。このシステム設計もそうですが、何より、素数の規則性の無さと、それによる「素数を挙げることはできても、ある条件から素数を導き出すことの困難さ」を活かすという発想力が素晴らしいと思います。
これだから、アルゴリズムの勉強は楽しいんです！感動に近しい気持ちですね。
皆さんにもこの感動が伝われば幸いです。
これからもアルゴリズム解説 挙げていこうと思いますのでよろしくお願いします！！！
ars_create
