wake-up-neo.com

Kurze RSA-Schlüssel knacken

Wie kann man unter Berücksichtigung der folgenden RSA-Schlüssel bestimmen, wie hoch die Werte von p und q sind?

Public Key: (10142789312725007, 5)
Private Key: (10142789312725007, 8114231289041741)
50
Donald Taylor

Dein Lehrer gab dir:

Öffentlicher Schlüssel: (10142789312725007, 5)

was bedeutet

n = 10142789312725007
e = 5 

dabei ist n der Modul und e der öffentliche Exponent.

Darüber hinaus sind Sie gegeben

Privater Schlüssel: (10142789312725007, 8114231289041741)

bedeutet, dass

 d = 8114231289041741

dabei ist d der Entschlüsselungsexponent, der geheim bleiben soll.

Sie können RSA "brechen", indem Sie wissen, wie "n" in die Primfaktoren "p" und "q" zerlegt wird:

n = p * q

Am einfachsten ist es wahrscheinlich, alle ungeraden Zahlen ab der Quadratwurzel von n zu überprüfen:

Floor[Sqrt[10142789312725007]] = 100711415

Sie würden den ersten Faktor in 4 Versuchen erhalten:

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

Also haben wir

 p = 100711409

Jetzt,

 q = n / p 
   = 10142789312725007 / 100711409
   = 100711423

Warum ist das wichtig? Es ist, weil d eine spezielle Zahl ist, so dass

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

Wir können das überprüfen

d * e = 40571156445208705 = 1 mod 10142789111302176

Dies ist wichtig, da bei einer Klartextnachricht m der Chiffretext lautet

c = m^e mod n

und Sie entschlüsseln es von

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

Zum Beispiel kann ich die Nachricht 123456789 mit dem öffentlichen Schlüssel Ihres Lehrers "verschlüsseln":

m = 123456789

Dies gibt mir den folgenden Chiffretext:

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

(Beachten Sie, dass "e" in der Praxis viel größer sein sollte, da Sie für kleine Werte von "m" nicht einmal n überschreiten.)

Wie auch immer, jetzt haben wir "c" und können es mit "d" umkehren

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

Offensichtlich können Sie "7487844069764171 ^ 8114231289041741" nicht direkt berechnen, da es 128.808.202.574.088.302 Stellen hat. Daher müssen Sie den Trick modulare Exponentiation verwenden.

In der "realen Welt" ist n offensichtlich viel größer. Wenn Sie ein reales Beispiel sehen möchten, wie HTTPS RSA unter der Decke mit einem 617-stelligen n und einem e von 65537 finden Sie in meinem Blog-Beitrag " Die ersten paar Millisekunden einer HTTPS-Verbindung ".

125
Jeff Moser

Hier ist eine relativ einfache Sichtweise (und eine, die von Hand gemacht werden kann). Wenn Sie die Zahl vollständig faktorisieren würden, wäre der höchste Faktor, den Sie berücksichtigen müssten, sqrt (N):

sqrt(10142789312725007) = 100711415.9999997567

Die erste Primzahl darunter ist 100711409, nur 6 unter dem Quadrat (N).

10142789312725007 / 100711409 = 100711423 

daher sind dies zwei Faktoren von N. Ihr Professor hat es ziemlich einfach gemacht - der Trick besteht darin, zu erkennen, dass niemand ein kleines p oder q wählen würde, um Ihren Check von unten zu beginnen (wie in python script jemand hat geschrieben) ist eine schlechte idee. Wenn es von Hand praktikabel sein soll, müssen das große p und q in der Nähe von sqrt (N) liegen.

15
ine

Es gibt verschiedene schnelle Algorithmen, um das Problem der Berücksichtigung von n bei n, e und d zu lösen. Eine gute Beschreibung eines solchen Algorithmus finden Sie im Handbuch für Angewandte Kryptographie, Kapitel 8 , Abschnitt 8.2.2. Sie finden diese Kapitel online zum kostenlosen Download hier .

11
James K Polk

Wolframalpha sagt mir, dass die Faktoren 100711409 und 100711423 sind

Ich habe gerade ein naives Python Skript geschrieben, um es zu brachialisieren. Wie amdfan hervorhob, ist es besser, von oben zu beginnen:

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

Dies könnte stark verbessert werden, aber es funktioniert immer noch ohne Probleme. Sie könnten es verbessern, indem Sie nur Primfaktoren testen, aber für kleine Werte wie Ihren sollte dies ausreichen.

10
Juri Robl

Hier ist eine Java Implementierung der Fast Factoring-Methode aus dem Handbuch für Angewandte Kryptographie Kapitel 8 Abschnitt 8.2.2 (Dank an GregS für das Auffinden):

/**
 * 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;
    }
}

Eine typische Ausgabe ist

100711423 100711409 (3ms)
4
starblue

Die Definition von RSA besagt, dass der Modul n = pq. Sie kennen n, also müssen Sie nur zwei Zahlen p und q finden, die sich multiplizieren, um n zu erzeugen. Sie wissen, dass p und q Primzahlen sind, daher ist dies das Primfaktorisierungsproblem.

Sie können dies mit brachialer Gewalt für relativ kleine Zahlen lösen, aber die Gesamtsicherheit von RSA hängt von der Tatsache ab, dass dieses Problem im Allgemeinen nicht lösbar ist.

4
Cameron Skinner

Diese beiden Papiere könnten möglicherweise nützlich sein

Kam auf sie zu, als ich Grundlagenforschung über fortgesetzte Brüche betrieb.

3
user498884

Der Algorithmus hierfür ist (und dies funktioniert für jedes Beispiel, nicht nur für dieses kleine, das von jedem Computer problemlos berücksichtigt werden kann):

ed - 1 Ist ein Vielfaches von phi(n) = (p-1)(q-1), also mindestens ein Vielfaches von 4.
ed - 1 Kann als 40571156445208704 berechnet werden, was 2^7 * 316962159728193 Entspricht, und wir rufen s=7 Und t = 316962159728193 Auf. (Im Allgemeinen: Jede gerade Zahl ist eine Potenz von 2 mal einer ungeraden Zahl.) Wählen Sie nun zufällig ein in [2,n-1) Und berechnen Sie (durch aufeinanderfolgendes Quadrieren von Modulo n) die Sequenz a^t (mod n), a^(2t) (mod n), a^(4t) (mod n).. bis höchstens a^((2^7)*t) (mod n), wo die letzte man ist garantiert 1, durch die Konstruktion von e und d.

Wir suchen nun nach der ersten 1 in dieser Reihenfolge. Die vorhergehende ist entweder +1 Oder -1 (Eine triviale Wurzel von 1, mod n) Und wir wiederholen mit einem anderen a oder einer Zahl x, das nicht gleich +1 oder -1mod n ist. Im letzteren Fall ist gcd(x-1, n) ein nicht trivialer Teiler von n, und so p oder q, und wir sind fertig. Man kann zeigen, dass ein zufälliges a mit einer Wahrscheinlichkeit von etwa 0,5 funktioniert. Wir brauchen also ein paar Versuche, aber im Allgemeinen nicht sehr viele.

3
Henno Brandsma

Tut mir leid für die Nekromantie, aber ein Freund hat mich danach gefragt, und nachdem ich ihn hierher geführt hatte, stellte ich fest, dass mir keine der Antworten wirklich gefiel. Nachdem Sie den Modul berücksichtigt und die Primzahlen (p und q) erhalten haben, müssen Sie den Totienten finden, der (p-1)*(q-1) Ist.

Um nun den privaten Exponenten zu finden, finden Sie die Umkehrung des öffentlichen Exponenten und den Totienten.

public_exponent * private_exponent = 1 mod totient

Und jetzt haben Sie Ihren privaten Schlüssel so einfach. All dies, mit Ausnahme der Faktorisierung, kann für große ganze Zahlen fast augenblicklich durchgeführt werden.

Ich habe Code geschrieben:

// 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);

}

Der Faktorisierungsalgorithmus, den ich verwendet habe, ist dumm, aber prägnant, also Salzkorn da. In diesem speziellen Beispiel wird der Code fast sofort ausgeführt. Dies liegt jedoch hauptsächlich daran, dass der betreffende Kursleiter ein Beispiel bereitgestellt hat, das zwei Primzahlen hintereinander verwendet, was für RSA nicht wirklich realistisch ist.

Wenn Sie meine dumme iterative Suche unterbinden möchten, können Sie einen echten Faktorisierungsalgorithmus und Faktorschlüssel mit einer Wahrscheinlichkeit von bis zu 256 Bit in angemessener Zeit eingeben.

2
pierce

Ich schlage vor, Sie lesen über das Quadratische Sieb . Wenn Sie selbst eines implementieren, ist dies mit Sicherheit die Ehre wert. Wenn Sie die Prinzipien verstehen, haben Sie bereits etwas gewonnen.

1
Yuval F

Sie müssen den Modul faktorisieren, das ist der erste Parameter des öffentlichen Schlüssels, 10142789312725007. Brute Force wird ausgeführt (überprüfen Sie jede ungerade Zahl von 3 bis sqrt (n), wenn es sich um einen Faktor handelt), obwohl komplexere/schnellere Algorithmen existieren.

Da die Zahl zu groß ist, um in eine herkömmliche Ganzzahl (sogar 64-Bit) zu passen, möchten Sie möglicherweise eine numerische Bibliothek, die Ganzzahlen mit beliebiger Länge unterstützt. Für C gibt es GMP und MPIR (Windows-freundlicher). Für PHP gibt es Bignum. Python wird mit einem integrierten Datentyp geliefert - der integrierte Integer-Datentyp ist bereits beliebig lang.

0
Seva Alekseyev

Es gibt viele schlechte Spekulationen über die Faktorisierung von großen Semi-Primzahlen, die in rohe Gewalt geraten oder gesiebt werden, von denen keine zur Faktorisierung der Semi-Primzahl erforderlich ist. 64 Bit dauert auf meinem PC 1 - 2 Sekunden und 256 Bit im Allgemeinen weniger als 2 Tage

0
Mick Press