1

、 、、の要因を見つける方法はp、RSA 暗号化アルゴリズムで知られています。検索してみましたが、ソースが見つかりませんでした。ヒント、参照、または解決策で十分です。qedn

(e,n)と(d,n)はそれぞれ公開鍵と秘密鍵であり、n = pq.

4

1 に答える 1

0

ドイツ語で書かれたソース (page 12+13)を見つけましpたq。

アルゴリズム：

  1. 計算してs = max { t : 2t | (ed-1) }k = (ed-1) / (2s)
  2. で乱数aを選ぶ[2,n-1]
  3. 計算するg = gcd(a,n)
  4. 場合g > 1 ⇒ g = pとq = n/g。
    それ以外の場合t = s-1, ... ,0:
    1. g = gcd( ak ⋅ 2t, n )
    2. 場合g < n ⇒ g = pとq = n/g。
      それ以外の場合は、新しい乱数を選択aし[2,n-1]て 3 に進みます。

a乱数 (一様分布)を選択した場合、pとが見つかる確率qは1/2であるため、2 回の試行で解が得られることが期待されます。

これが機能するという証明は、中国の剰余定理と関係があります。

注意: すでに秘密鍵を持っている場合、同じ に対してn複数の鍵のペアが存在することはないため、 の因数を計算する理由はおそらくありません。しかし、このアルゴリズムを使用して、RSA の解読が因数分解と同じくらい難しいことを証明できます。( とがあれば秘密鍵を簡単に計算できるため、RSA は因数分解ほど難しくありません) 。(e,d)nndpq

于 2014-05-27T17:02:29.650 に答える