cryptography - RSA プライベート指数決定

Question

私の質問は RSA 署名についてです。

RSA 署名の場合:

暗号化 -> y = x^d mod n、復号化 -> x = y^e mod n

• x -> 元のメッセージ
• y -> 暗号化されたメッセージ
• n -> 係数 (1024 ビット)
• e -> 公開指数
• d -> プライベート指数

x、y、n、e を知っています。これらを知っていれば、d を決定できますか?

Answer 1

n = p*q を因数分解できる場合、d*e ≡ 1 (mod m) ここで m = φ(n) = (p-1)*(q-1) (φ(m) はオイラーの全関数)この場合、拡張ユークリッド アルゴリズムを使用して e から d を決定できます。(d*e - k*m = 1 である k の場合)

これらはすべて非常に簡単に計算できますが、因数分解は非常に難しいように設計されているため、公開鍵暗号化は、秘密鍵を知らなければ解読できない便利な手法です。

したがって、実用的な意味であなたの質問に答えるには、いいえ、数百年または数千年のCPU年を待ってnを因数分解しない限り、公開鍵から秘密鍵を導出することはできません。

---

公開鍵の暗号化と復号化は逆の操作です。

x = y ^e mod n = (x ^d ) ^e mod n = x ^de mod n = x ^kφ(n)+1 mod n = x * (x ^φ(n) ) ^k mod n = x mod n

ここで (x ^φ(n) ) ^k = 1 mod n である理由は、オイラーの定理.

Answer 2

答えは、2 つの条件の下ではイエスです。1 つ、誰かが n を因数分解します。2 つ目は、誰かがアルゴリズムを巧妙にすり抜けて、署名者に x に可能ないくつかの特別な値の 1 つを使用するよう説得することです。

Applied Cryptography の 472 ページと 473 ページでは、このような 2 つのスキームについて説明しています。それらが実際にどのように機能するかを完全には理解していません。しかし、解決策は、d を決定したい人 (別名、攻撃者) が完全に制御できない x を使用することです。

これを行うにはいくつかの方法があり、いずれも x をハッシュし、予測可能な方法でハッシュの値をいじって、望ましくないプロパティをいくつか削除し、その値に署名する必要があります。これを行うための推奨される手法は「パディング」と呼ばれますが、Practical Cryptography に見られるパディング方法としてカウントされない非常に優れた手法が 1 つあります。

Answer 3

いいえ。それ以外の場合、秘密鍵は役に立ちません。