57

次のRSAキーを考えると、 pとqの値をどのように決定するのでしょうか。

Public Key: (10142789312725007, 5)
Private Key: (10142789312725007, 8114231289041741)
4

12 に答える 12

145

あなたの先生はあなたに与えました：

公開鍵：（10142789312725007、5）

つまり、

n = 10142789312725007
e = 5

ここで、nはモジュラス、eはパブリック指数です。

さらに、あなたは与えられます

秘密鍵：（10142789312725007、8114231289041741）

つまり

 d = 8114231289041741

ここで、dは秘密にしておく必要のある復号化指数です。

「n」をその「p」および「q」素因数に因数分解する方法を知ることにより、RSAを「破る」ことができます。

n = p * q

最も簡単な方法は、おそらくnの平方根のすぐ下から始まるすべての奇数をチェックすることです。

Floor[Sqrt[10142789312725007]] = 100711415

4回の試行で最初の要素が得られます。

10142789312725007 mod 100711415 = 100711367
10142789312725007 mod 100711413 = 100711373
10142789312725007 mod 100711411 = 100711387
10142789312725007 mod 100711409 = 0 <-- Winner since it evenly divides n

だから私たちは

 p = 100711409

今、

 q = n / p 
   = 10142789312725007 / 100711409
   = 100711423

何でこれが大切ですか？これは、 dが次のような特別な数であるためです。

d = e^-1 mod phi(n)
  = e^-1 mod (p-1)*(q-1)

これを確認できます

d * e = 40571156445208705 = 1 mod 10142789111302176

平文メッセージmがある場合、暗号文は次のようになるため、これは重要です。

c = m^e mod n

そしてあなたはそれを解読します

m = c^d = (m^e)^d = (m^(e*d)) = (m^(e*e^-1)) = m^1 (mod n)

たとえば、先生の公開鍵を使用してメッセージ123456789を「暗号化」できます。

m = 123456789

これにより、次の暗号文が得られます。

c = m^e mod n 
  = 123456789^5 mod 10142789312725007
  = 7487844069764171

（「m」の値が小さい場合はnを超えないため、実際には「e」ははるかに大きくする必要があることに注意してください）

とにかく、今は「c」があり、「d」で逆にすることができます

m = c^d mod n
  = 7487844069764171^8114231289041741 mod 10142789312725007
  = 123456789

明らかに、128,808,202,574,088,302桁であるため、「7487844069764171 ^ 8114231289041741」を直接計算することはできません。したがって、べき乗剰余のトリックを使用する必要があります。

「実世界」では、nは明らかにはるかに大きいです。HTTPSが617桁のnと65537のeでRSAを使用する実際の例を知りたい場合は、私のブログ投稿「HTTPS接続の最初の数ミリ秒」を参照してください。

于 2010-11-02T15:22:26.180 に答える
16

これは、それを見る比較的簡単な方法です（そして手作業で実行できる方法です）。数値を完全に因数分解する場合、考慮する必要がある最大の因数はsqrt（N）です。

sqrt(10142789312725007) = 100711415.9999997567

この下の最初の素数は100711409で、sqrt（N）のすぐ下にあります。

10142789312725007 / 100711409 = 100711423

したがって、これらはNの2つの要因です。教授はそれを非常に簡単にしました-トリックは、誰も小さなpまたはqを選択しないことを認識することです。したがって、チェックを下から開始することは（誰かが投稿したPythonスクリプトのように）悪い考えです。 。手作業で実用化する場合、大きなpとqはsqrt（N）の近くになければなりません。

于 2010-11-02T15:14:03.633 に答える
14

、、、およびをn与えられた因数分解の問題を解決するためのさまざまな高速アルゴリズムがあります。このようなアルゴリズムの適切な説明は、 『応用暗号化ハンドブック』の第8章のセクション8.2.2にあります。これらの章は、ここから無料でダウンロードしてオンラインで見つけることができます。アルゴリズムは本質的に、この質問に対するHennoBrandsmaの答えを注意深く精緻化したものです。ned

2019年9月25日更新：

以下のコメントで、ユーザーImperishable Nightは、少なくとも概念的に理解しやすい代替方法を提案しています。

e彼は通常小さいと述べています。実際eには、ほとんどの場合65537eです。小さい場合は、未知の素数で2次方程式を作成できるため、たとえば2次p方程式を使用して簡単に解くことができます。続行するには、x = pを設定して、を解きます。これは、慣例に従うためです。私たちはそれを知っています、または同等に 。ここで、を設定し、したがって、両側に項を乗算して項を再配置すると、 k * x 2 +（d * e --k * n --k --1）* x + k * n = 0 になります。これで、次の形式の方程式が得られます。 ax 2 + bx + c = 0であり、2次方程式を使用してxを解くことができます。だから私たちはの値を試すことができますxed = 1 mod phi(n)ed - 1 = k * (p-1)*(q-1)x=pn/x=qx

k周囲の小さな範囲でe、二次方程式の整数解は1つだけである必要があります。これは、正しいkの解です。

ノート：

  1. すべてが整数である必要があるため、判別式は完全な正方形である必要があります。そうでない場合は、kを破棄して次の判別式を試すことができます。また、分子はで割り切れる必要があります2*k。
  2. オイラーのファイ関数の代わりにカーマイケルラムダ関数が使用されることがあります。を推測する必要があるため、これは少し複雑になりg = gcd(p-1, q-1)ます。gは常に偶数であり、多くの場合2であり、それ以外の場合はほとんどの場合2の小さな倍数です。

2019年9月26日更新：

が小さいk場合、実際には非常に簡単に見つけることができます。e方程式 ed - 1 = k * (p-1)*(q-1)を取り、両側を除算することにより、nそれをかなり簡単に確認できfloor((ed-1)/n) + 1 == kます。MJ Wienerの「短いRSA秘密指数の暗号解読」の式31と32を使用するpと、直接回復できますq。

于 2010-11-03T01:21:52.803 に答える
11

Wolframalphaは、ファクターが100711409と100711423であると教えてくれます

単純なPythonスクリプトを作成して、ブルートフォース攻撃を行いました。amdfanが指摘したように、上から始めるのがより良いアプローチです。

p = 10142789312725007
for i in xrange(int(p**0.5+2), 3, -2):
    if p%i == 0:
        print i
        print p/i
        break

これは大幅に改善される可能性がありますが、それでも問題なく機能します。primfactorsをテストするだけで改善できますが、自分のような小さな値の場合はこれで十分です。

于 2010-11-02T15:01:22.787 に答える
4

RSAの定義は、モジュラスがであることを示していますn = pq。あなたは知っているので、2つの数をn見つける必要があり、それを乗算してを生成します。あなたはそれを知っていて素数なので、これが素因数分解の問題です。pqnpq

比較的少数のブルートフォースでこれを解決できますが、RSAの全体的なセキュリティは、この問題が一般的に手に負えないという事実に依存します。

于 2010-11-02T15:13:38.220 に答える
4

これは、Handbook of Applied Cryptographyの第8章セクション8.2.2からの高速因数分解メソッドのJava実装です（それを見つけてくれたGregSに感謝します）：

/**
 * Computes the factors of n given d and e.
 * Given are the public RSA key (n,d)
 * and the corresponding private RSA key (n,e).
 */
public class ComputeRsaFactors
{
    /**
     * Executes the program.
     *
     * @param args  The command line arguments.
     */
    public static void main(String[] args)
    {
        final BigInteger n = BigInteger.valueOf(10142789312725007L);
        final BigInteger d = BigInteger.valueOf(5);
        final BigInteger e = BigInteger.valueOf(8114231289041741L);

        final long t0 = System.currentTimeMillis();

        final BigInteger kTheta = d.multiply(e).subtract(BigInteger.ONE);
        final int exponentOfTwo = kTheta.getLowestSetBit();

        final Random random = new Random();
        BigInteger factor = BigInteger.ONE;
        do
        {
            final BigInteger a = nextA(n, random);

            for (int i = 1; i <= exponentOfTwo; i++)
            {
                final BigInteger exponent = kTheta.shiftRight(i);
                final BigInteger power = a.modPow(exponent, n);

                final BigInteger gcd = n.gcd(power.subtract(BigInteger.ONE));
                if (!factor.equals(BigInteger.ONE))
                {
                    break;
                }
            }
        }
        while (factor.equals(BigInteger.ONE));

        final long t1 = System.currentTimeMillis();

        System.out.printf("%s %s (%dms)\n", factor, n.divide(factor), t1 - t0);
    }


    private static BigInteger nextA(final BigInteger n, final Random random)
    {
        BigInteger r;
        do
        {
            r = new BigInteger(n.bitLength(), random);
        }
        while (r.signum() == 0 || r.compareTo(n) >= 0);
        return r;
    }
}

典型的な出力は

100711423 100711409 (3ms)
于 2010-11-03T20:31:11.367 に答える
3

これらの2つの論文はおそらく役に立つかもしれません

連分数に関する基礎研究をしているときに、彼らに出くわしました。

于 2010-11-05T23:07:07.300 に答える
3

これを行うためのアルゴリズムは次のとおりです（これは、どのコンピューターでも簡単に因数分解できるこの小さなアルゴリズムだけでなく、どのような例でも機能します）。

ed - 1はの倍数phi(n) = (p-1)(q-1)であるため、少なくとも4の倍数です。
ed - 1はに等しい40571156445208704として計算でき、と2^7 * 316962159728193を呼び出します。（一般的に、偶数は奇数の2倍の累乗です）。ここで、ランダムにaを選択し、シーケンスを（モジュロを法として連続して二乗することにより）最大でまで計算します。最後のシーケンス は、との構築によって1であることが保証されます。s=7t = 316962159728193[2,n-1)na^t (mod n), a^(2t) (mod n), a^(4t) (mod n)..a^((2^7)*t) (mod n)ed

ここで、そのシーケンスの最初の1つを探します。その前のものは+1または-1 （1の自明なルートmod n）のいずれかになり、別のa、またはまたはと等しくないいくつかの数でxやり直します。後者の場合、、などの自明でない約数であり、これで完了です。ランダムなaが約0.5の確率で機能することを示すことができるので、数回の試行が必要ですが、一般的にはそれほど多くはありません。+1-1 mod ngcd(x-1, n)npq

于 2010-12-17T20:37:07.277 に答える
1

二次ふるい法について読むことをお勧めします。自分で実装する場合、これは確かにクレジットの価値があります。原則を理解していれば、すでに何かを得ています。

于 2010-11-02T15:13:11.847 に答える
1

降霊術で申し訳ありませんが、友人がこれについて私に尋ねました、そしてここで彼を指さした後、私は答えのどれも本当に好きではないことに気づきました。モジュラスを因数分解し、素数（pとq）を取得した後、トーティエントを見つける必要があります。これは(p-1)*(q-1)です。

ここで、プライベート指数を見つけるには、パブリック指数modの逆関数をtotientに見つけます。

public_exponent * private_exponent = 1 mod totient

そして今、あなたはあなたの秘密鍵を持っています、それは簡単です。因数分解を除くこれらすべては、巨大な整数に対してほぼ瞬時に実行できます。

私はいくつかのコードを書きました：

// tinyrsa.c
//
// apt-get install libgmp-dev
// yum install gmp-devel
//
// gcc tinyrsa.c -o tinyrsa -lm -lgmp

#include<stdio.h>
#include<gmp.h>

int main()
{
  // declare some multi-precision integers
  mpz_t pub_exp, priv_exp, modulus, totient, fac_p, fac_q, next_prime;

  mpz_init_set_str(pub_exp,"5",10);
  mpz_init_set_str(modulus,"10142789312725007",10);

  mpz_init(priv_exp);
  mpz_init(totient);
  mpz_init(fac_p);
  mpz_init(fac_q);

  // now we factor the modulus (the hard part)
  mpz_init(next_prime);
  mpz_sqrt(next_prime,modulus);
  unsigned long removed=0;
  while(!removed)
  {
    mpz_nextprime(next_prime,next_prime);
    removed=mpz_remove(fac_p,modulus,next_prime);
  }

  mpz_remove(fac_q,modulus,fac_p);
  // we now have p and q

  // the totient is (p-1)*(q-1)  
  mpz_t psub, qsub;
  mpz_init(psub);
  mpz_init(qsub);

  mpz_sub_ui(psub,fac_p,1);
  mpz_sub_ui(qsub,fac_q,1);
  mpz_mul(totient,psub,qsub);

  // inverse of the public key, mod the totient..
  mpz_invert(priv_exp,pub_exp,totient);

  gmp_printf("private exponent:\n%Zd\n",priv_exp);

}

私が使用した因数分解アルゴリズムは愚かですが、簡潔なので、そこに塩の粒があります。この特定の例では、コードはほぼ瞬時に実行されますが、これは主に、問題のインストラクターが2つの素数を連続して使用する例を提供したためです。これはRSAでは実際には現実的ではありません。

私のばかげた反復検索を切り取りたい場合は、実際の因数分解アルゴリズムを導入して、妥当な時間内に最大約256ビットの素因数分解キーを使用できます。

于 2012-06-19T20:22:42.340 に答える
0

公開鍵10142789312725007の最初のパラメーターである係数を因数分解する必要があります。より洗練された高速のアルゴリズムが存在しますが、ブルートフォースは実行します（3からsqrt（n）までのすべての奇数をチェックします）。

数値が大きすぎて従来の整数（64ビットでも）に収まらないため、任意の長さの整数をサポートする数値ライブラリが必要になる場合があります。Cには、GMPとMPIR（よりWindowsに適した）があります。PHPの場合、Bignumがあります。Pythonには組み込みのものが付属しています-組み込みの整数データ型はすでに任意の長さです。

于 2010-11-02T15:20:01.077 に答える
0

力ずくになる大きな半素数の因数分解や、半素数を因数分解するためにどちらも必要とされないふるい分けについては、多くの悪い憶測があります。私のPCでは64ビットは1〜2秒かかり、256ビットは通常2日未満です

于 2017-05-31T12:13:42.983 に答える