RSA暗号の「破られにくさ」の根拠
-
angel_p_57
- 4777
- 7
- 0
- 0
-
- いいね！0
導入
angel (as ㌵㌤の猫)
@angel_p_57
なんか最近RSA暗号の話を引き摺ってる気もするけど。実際なんでRSA暗号が安全なのか、言葉を替えると「なぜ公開鍵だけで第三者が破れないのか」そこのところは私もよく知らないところだったりする。
2022-09-23 17:13:05
angel (as ㌵㌤の猫)
@angel_p_57
まあなので、この方のようにそこは当然疑問になるよね、と。簡単に整理してみようかと思う。と言ってもこの部分は本当に詳しくないので、かなり不確定な話にはなるけど。 twitter.com/yst4ttt/status…
2022-09-23 17:13:30
いすと(yst)
@yst4ttt
@Tomuo2000 数学ど素人ですが: 笑わない数学 興味深く拝見しています。 RSA暗号なぜ公開鍵で復号無理なのかの例えが欲しい想いです。 (値をe乗してNで割った余り値が10なら.Nを何倍にしたか(に+10)をe乗で作る元値の逆算は無理(数学常識とか?)なのでしょうか?(なら素数とどう関係が?何故p,qが必要？がモヤモヤで)
2022-09-19 22:33:21
angel (as ㌵㌤の猫)
@angel_p_57
まず、RSA暗号は「素因数分解が困難であること」がその安全性の根拠だという話が有名だし、実際安全性の評価も「どの程度素因数分解に時間がかかるか ( どの程度の計算量を要するか )」が基準になっている。
2022-09-23 17:14:00
angel (as ㌵㌤の猫)
@angel_p_57
その「素因数分解にかかる時間 ( 計算量 )」は、N の桁数によってもちろん増えていくもので。この数値はRSA暗号における「鍵長」とされていて、bit数、つまり2進数での桁数で表現される。
2022-09-23 17:14:30
angel (as ㌵㌤の猫)
@angel_p_57
今なら最低でも2,048bit、できれば3,072bit以上が良いとされている。10進数の桁数に直すなら大体×0.3すれば良いので、なので「Nとしては10進数で600桁以上の数値が使われる」ということになる。
2022-09-23 17:14:49
angel (as ㌵㌤の猫)
@angel_p_57
なお「鍵長」という言葉は、他の様々な暗号関連技術で共通に使われる用語で。古くは2000年前後でも「128bit SSL対応!」的な形で目にした人もいると思うけど。 参考: internet.watch.impress.co.jp/www/article/20…
2022-09-23 17:15:17
angel (as ㌵㌤の猫)
@angel_p_57
じゃあ「128bitに比べてRSAが2,048bit…それはさぞや強固な暗号なんじゃね?」と考えると勘違いのもとなので、一応注意。方式によって鍵長の示す暗号強度 ( 破られにくさ ) は変わってくるので、単純には比較できない。
2022-09-23 17:15:45RSAを破る素因数分解以外の2つの道筋(候補)
angel (as ㌵㌤の猫)
@angel_p_57
で、ここからが本題になるけど。RSAの計算の中で数式を単純に眺めた場合。攻略の糸口になるのは、なにも素因数分解だけではない。
2022-09-23 17:16:10
angel (as ㌵㌤の猫)
@angel_p_57
ただ、なぜ「素因数分解できればRSAを破れる」のかというと、NHKの「笑わない数学」や私のまとめでも計算のデモをやってた通り、N=pq の結果が分かっていれば、同じく公開される e ( 番組内で 17 だった数値 ) を使って復号できるから。これは単純な話。
2022-09-23 17:16:55
angel (as ㌵㌤の猫)
@angel_p_57
逆に「素因数分解できなかったらなぜできないの?」というと、e から復号に使う d ( 実際には秘密鍵の一部 ) を計算する時に (p-1)(q-1) を知っている必要があって、これは N から直接は分からないからだ。
2022-09-23 17:17:32
angel (as ㌵㌤の猫)
@angel_p_57
しかし、他に2通りの候補がある。一つは暗号化の計算 M^e≡C mod N と、復号の計算 C^d≡M mod N だ。( C は暗号文に対応する数値を表す )
2022-09-23 17:17:58
angel (as ㌵㌤の猫)
@angel_p_57
これただ、数式の中で「何が未知数か」に注意が必要。 まず暗号化の計算 M^e≡C mod N の場合、「誰かが用意した未知の M から作られた暗号文 C を入手した」状況を想定することになる。
2022-09-23 17:18:28
angel (as ㌵㌤の猫)
@angel_p_57
ということは、^e ( e乗 ) の逆計算ができるようなら、なにも素因数分解できなくても M が分かってしまうのだから、それで「RSAが破れた」ということになってしまう。
2022-09-23 17:18:46
angel (as ㌵㌤の猫)
@angel_p_57
で、mod N というモジュラー演算がなければ、みんな学校でべき乗の逆計算「べき乗根 ( n乗根 )」というのを習ってるはずで。例えば 2^3=8, 3^3=27, 4^3=64 という3乗の計算に対して [3]√8=2, [3]√27=3, [3]√64=4 というのが3乗根になる。 ※n乗根のnとRSAのNは無関係なので注意
2022-09-23 17:19:33
angel (as ㌵㌤の猫)
@angel_p_57
この「べき乗根」自体の計算は、たとえ17乗根でも65537乗根でも、コンピュータならそんな難しいものではない。それではRSAでの逆計算として M≡[e]√C mod N とも言うべき計算はどうなのか。そこが問題となる。これで1つ。
2022-09-23 17:20:05
angel (as ㌵㌤の猫)
@angel_p_57
次に復号の計算 C^d≡M mod N。こちらについては「d は未知だが、適当なメッセージから暗号文は作れるので、自分で好きに決めた M から作られた C が分かっている」という状況を想定している。
2022-09-23 17:21:18
angel (as ㌵㌤の猫)
@angel_p_57
で、たった一組でもいいので、C,M の組から d が分かれば、他のメッセージに対する暗号文を解読するのに使えるようになるため、これもRSA暗号を破る糸口になっているのである。
2022-09-23 17:21:39
angel (as ㌵㌤の猫)
@angel_p_57
これは ^d ( d乗 ) の逆計算ではあるんだけど、べき乗根ではなく「指数」に対する逆の「対数」に相当する計算となる。つまり、2^10=1024 や 3^4=81 といった指数計算に対し、log[2]1024=10, log[3]81=4 というのが対数だ。
2022-09-23 17:22:21
angel (as ㌵㌤の猫)
@angel_p_57
この「対数」も、やはり mod N が絡まなければ難しい計算ではない。それではRSAでの逆計算として d=log[C,mod N]M 的な計算はどうなのかという話になる。これで2つだ。
2022-09-23 17:22:41ちなみに、自分で mod(x^y, N) を計算してみると分かるけど、得られる結果はとびとびの値になって、全体で見てもまるでバラバラ、何らかの規則性を見出すのは難しい。
だから mod N でないべき乗根、対数に比べると難しいんだろうな、というのは感覚的に分かるところではあるんだけど。
離散対数問題
angel (as ㌵㌤の猫)
@angel_p_57
ということで、N=pq の素因数分解の他、M≡[e]√C mod N 的な計算、d=log[C,mod N]M 的な計算の2つも糸口になるということなんだけど。順番を逆にして最後の d=log[C,mod N]M 的な計算から考えてみる。
2022-09-23 17:22:58
angel (as ㌵㌤の猫)
@angel_p_57
これは「『対数』に相当する計算」と説明した通りで、ほぼ同じ話題として「離散対数問題」というのがある。その中で代表てきなのは a^x≡b mod p ( pは素数 ) に対する逆計算 x=log[a,mod p]b 的なもので、「離散対数」といったらこの mod p での話を指すことも多い。
2022-09-23 17:23:40