RSA暗号の原理

Question

わかりますか？
簡潔にお願いします！

https://youtu.be/qF5N6f4SsTU?list=PLH9ew0Q6JwWiS9a0jDWcIwkfeoTBH8M2y&t=268
上は見ないでここから見てください！
https://youtu.be/qF5N6f4SsTU?list=PLH9ew0Q6JwWiS9a0jDWcIwkfeoTBH8M2y&t=268
https://youtu.be/qF5N6f4SsTU?list=PLH9ew0Q6JwWiS9a0jDWcIwkfeoTBH8M2y&t=548

ありものがたり · Accepted Answer

RSA暗号は、主にオイラーの定理に基づく。
「オイラーの定理」と名のつく定理は数多いが、今回のは、
剰余系での冪乗に関するオイラーの定理だ。
それは、フェルマーの小定理を拡張したものである。

まず、フェルマーの小定理。
素数 p と、 p とは互いに素な整数 a について
a^(p-1) ≡ 1 (mod p) が成り立つ。

これを、mod の法が素数でない場合にも拡張したのがオイラーの定理。
オイラー関数 と呼ばれる関数 φ があって、
自然数 n と、 n とは互いに素な整数 a について
a^φ(n) ≡ 1 (mod n) が成り立つ。
φ は、 ｎ の素因数分解 n = (p1^h1)(p2^h2)...(pm^hm) に対して
φ(n) = n(1 - 1/p1)(1 - 1/p2)...(1 ^ 1/pm) という値を取る。

オイラーの定理を使うと、
x^y ≡ (x を n で割った余り)^(y を φ(n) で割った余り)　(mod n)
が言えて、mod n における 大きい数^大きい数 の計算に役立つ。

さて、このオイラーの定理を使う面白いトリックがある。

素数 p, q に対して、
n = pq, m = φ(n) = (p-1)(q-1) と置き、 m と素な整数 e をひとつ取る。
ed ≡ 1 (mod m) となる d は mod m で一意に定まるので、
その中から d をひとつとる。

オイラーの定理により、n と互いに素な整数 x に対し
x^(ed) ≡ x^1 (mod n) であるから、
x^e ≡ y (mod n) のとき y^d ≡ x (mod n) が成り立つ。

情報を受診する人は、以上の数値を用意し、 n, e を公開する。
p, q, d は非公開鍵として受診者が秘匿する。
情報を発信する人は、送りたい情報 x に対して
x^e ≡ y (mod n) を計算して y を送信する。
受診した人は、 y^d ≡ x (mod n) によって x を得ることができる。

通信 y を傍受した人は、公開された情報 n, e も知っているが、
d は知らない。 n を素因数分解して p, q を知ることができれば、
m = (p-1)(q-1) を計算して ed ≡ 1 (mod m) を解くことは易しいが、
p, q が大きくなると、 n を素因数分解することは難しく、
傍受者は d を得ることが事実上できない。

これが、RSA暗号のしくみである。
割と盲点なのが、 x が n と互いに素でなければならない
という点だが、送信者は n の値を知っているので、
送りたい平文 x0 を加工して、受信者が後で x を復元できるような
n とは素な x を作ることはできるのだ。

joshua01 · Answer

こんにちは。
　確かに、質問者さんがどの点を疑問視しておられるかわからないのですが、次のような説明ではいかがでしょうか。

○　RSA暗号とは、割り算の余りを使用した「ちょっと特殊なかけ算」での暗号。（モジュロかけ算とでも呼ぼう）
 ○　例えばパスワード数字の「21」を暗号化して送りたいとき、受信側がみんなに見えるように「送りたい数字に143でモジュロかけ算して送るよう」に指示する。 
　この時の「モジュロかけ算」が暗号化法。143が暗号鍵。ただし、どちらもみんなに見えているので暗号鍵は「公開鍵」。 
○　そこで、送信側でモジュロかけ算してみたら「3004」が生成できたので、それを送る。これもみんなに見えている。
 ○　受信側は、これを、13でモジュロ割り算し、さらに11でモジュロ割り算する。すると21が見える。 
○　ところが、「143でモジュロ割り算」しても答えが出ない。とにかく、143＝13×11（これは普通のかけ算）であることを知る必要がある。 　　実は、受信側はこれを知っていて143を使ったが、「みんな」がこの暗号の結果を知るには時間の遅れが生じる。 
○　実は、このかけ算の算出は、桁数が大きくなると悲惨なくらいに時間がかかる。かけ算結果が数百桁になると、それが「○かける△」であることを知るために、数万年かかると言われている（でも、○と△を知っていれば現代のパソコンではミリ秒で解けるので、こちらは秘密鍵）。だから、暗号方式も鍵（公開鍵）も公開してしまっても「暗号」が作れる。（えらい！）

ここまできたら次もわかるでしょう。 
○　暗号方式（規格）は公開。実際にはモジュロかけ算や公開鍵の生成方法を含めてたくさんの処理が重なっている。（ま、当たり前か） 
○　公開鍵は、秘密鍵をもとに受信者の側（お店や銀行）が作る。公開鍵はみんなに見えても聞こえてもよい。（インターネットだし、不特定の人と通信するし・・・） 
○　実は秘密鍵が「大きな素数」でなければならないのは、時間差を作るため。13とか11とか桁数の小さな素数同士やそれらを複数組み合わせた数値は比較的簡単に推定されてしまうので。 逆に言えばこの暗号は解けないのではなく解くのにとても時間がかかる暗号。
　
さてさて、如何でしょうか。 
お役に立てば幸いです。

ありものがたり · Answer

＞ 通信のたびに、毎回違うのか？
＞ かわらないのか？

それは、話題が違うので、
新しい質問 https://oshiete.goo.ne.jp/qa/14044486.html
のほうに回答しておきました。

ありものがたり · Answer

あと、 n, e, y が与えられて x の方程式 
x^e ≡ y (mod n) を解くことが容易でない
ことが一番大切というか、これが話の出発点だった。
その上での、素因数分解の困難性。

tknakamuri · Answer

>素数は機密情報で金庫に入れられているみたいね？

暗号鍵は厳重に隠さなきゃいけないけど
そういう話じゃない。

鍵を「作る」のは割と簡単という話。
高強度の鍵作るのにいちいちエラストテネスとかやっていると
暗号を使う前に人類の歴史が終わってしまう(^^;

tknakamuri · Answer

RSAの暗号化アルゴリズムはシンプルだけど、
RSAの肝は
巨大な素数を割と低コストで作れるってことなんだよね。

他と重なる心配のない素数の組を低コストで作れないと、
RSAは暗号としてなりたたないので、鍵生成(素数生成/素数判定)
アルゴリズムが重要。

satoumasaru · Answer

簡潔にRSA暗号の原理を説明すればふたつの素数で公開キーと秘密キーを作成してやりとりするものです。

でもこれでは何のことかわかりませんよね。ですから簡潔に説明するなんて無理です。下記のサイトを御覧ください。

RSA暗号とは？仕組みや応用事例を初心者にもわかりやすく解説！
https://it-trend.jp/encryption/article/64-0056

RSA暗号とは？仕組みや応用事例を初心者にもわかりやすく解説！
https://it-trend.jp/encryption/article/64-0056

RSA暗号の原理

RSA暗号は、主にオイラーの定理に基づく。

こんにちは。

＞ 通信のたびに、毎回違うのか？

あと、 n, e, y が与えられて x の方程式

>素数は機密情報で金庫に入れられているみたいね？

RSAの暗号化アルゴリズムはシンプルだけど、

簡潔にRSA暗号の原理を説明すればふたつの素数で公開キーと秘密キーを作成してやりとりするものです。

似たような質問が見つかりました

このQ&Aを見た人はこんなQ&Aも見ています

関連するカテゴリからQ&Aを探す

このQ&Aを見た人がよく見るQ&A

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

＞通信のたびに、毎回違うのか？