RSAに対するフェルマー攻撃 - Qiita

はじめに（Introduction） RSAの鍵ペアの生成方法にミスがあり脆弱性となってしまった実装例があったようです。 元の文献を機械翻訳（ちょっと修正）してみます。 原文のデモをやってみたところ、案外動いたので先にデモを記します。 デモ（Demo） まずは、素数$p$と$q$を生成して$N$を求めるところです。 ※：鍵長が2048bitなので多少時間がかかります。 問題となったライブラリがこのようなロジックであったかは不明ですが、翻訳した資料を参考に作成しています。 import random as rnd import sympy key_length = 2048 distance = 10000 p = 0 q = 0 # 乱数Xを生成する。 X = rnd.randrange(2, pow(2, key_length)) for i in range(distance): #

[sora_h]

「RSAに脆弱性が発見されたようです」ではない。脆弱な鍵の作り方としてwidely knownだし、そうなってしまっている実装が発見されたのが正しいのでは。

[Vorspiel]

RSAの既知の制限事項(近い素数の対を使うな)を無視している、よろしくない実装があるってことね

[BlueSkyDetector]

なるほど、生成する素数同士が近い場合は平方根から元の素数をすぐに見つけられるから、その場合はRSAが脆弱になる、と。つまり近い素数になるような変な生成アルゴリズムになっている場合のみ脆弱性がある。Rambus……

[osamu0329]

一部の実装では生成される鍵の素数ペアが近すぎることがあり、そのようなペアは簡単に因数分解されてしまい（実装が）脆弱であると

[kenkoudaini]

2021の素因数分解みたいなやつ(2025-4=45^2-2^2=(45-2)(45+2))

[mohno]

「pの次の素数を探索し、それをqとする」←いや、そりゃダメだろ。「フェルマーの因数分解アルゴリズム」とか知らなくても平方根近くに素数があるって分かるじゃん。

[ys0000]

数学的手法同士で発生した脆弱性といえるかな。既知のものであり正しい実装をしないと脆弱である。本当に数学は偉大だなぁ。その足元にも立っていないと実感しますわ。

[oono_n]

ふむふむ。

[mather314]

一行目の文言を修正してもらった

[tmatsuu]

わいわい。悩ましいのは、利用しているツールやライブラリが正しい実装になっているか気づきにくい点か。信頼できるものを使いましょうだがこのRambus社の暗号ライブラリは高信頼を謳っていたようなので難しいね。

[swdrsker]

RSAの仕組みを分かってる人がそんな実装するわけないし、RSAの仕組みを分かってない人が製品レベルの鍵生成の実装に携わるわけないし、どういう経緯でその実装になったんだろう

[aya_momo]

pとqが近いときに求める方法は昔から知られているね。本で読んだ気がする。/隣でなくてもある程度近ければすぐに求められるアルゴリズムがあったはず。/ p=x-y q=x+y N=x^2-y^2だから、xをceil(√N)から1ずつ大きくすればよい。

[smoking186]

id:kusomamma これは素因数分解に使うフェルマー法の話で、フェルマーの小定理（a**(p-1) ≡1 (mod p)）はまた別の話です。

[kusomamma]

俗にフェルマーの最終定理といわれるアレではなく、フェルマーの小定理と言われるほうのヤツと書いてくんないと素人にはキツい

[itochan]

ま、この作り方をして脆弱性がないと思うほうがどうかしてる。どうしてこうなった？

[sc3wp06ga]

『富士フイルムのプリンターが脆弱な証明書を生成。キヤノンのプリンター脆弱なCSRを生成imageRUNNERとimagePROGRAFシリーズ。これはRSAの弱点でしょうか？いいえ、正しい鍵生成機能を持つRSAライブラリは影響を受けません』

[hirorinya]

ほーん

[mattn]

めちゃめちゃ分かりやすい記事だった。