Domanda

Dato il seguente chiavi RSA, come si fa a determinare quali sono i valori di p e q sono? 

Public Key: (10142789312725007, 5)
Private Key: (10142789312725007, 8114231289041741)
È stato utile?

Soluzione

Il tuo insegnante ti ha dato:

  

Public Key: (10142789312725007, 5)

che significa 

n = 10142789312725007
e = 5

dove n è il modulo e e è l'esponente pubblico.

In aggiunta, si è dato

  

Chiave Privata: (10142789312725007, 8114231289041741)

che significa che 

 d = 8114231289041741

dove D è l'esponente di decrittazione che dovrebbe rimanere segreto.

È possibile "rompere" RSA da saper fattore "n" nel suo "p" e "q" fattori primi: 

n = p * q

Il modo più semplice è probabilmente quello di controllare tutti i numeri dispari a partire proprio sotto la radice quadrata di n: 

Floor[Sqrt[10142789312725007]] = 100711415

Si potrebbe ottenere il primo fattore in 4 tentativi: 

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

Quindi dobbiamo 

 p = 100711409

Ora, 

 q = n / p 
   = 10142789312725007 / 100711409
   = 100711423

Perché è importante? È perché D è un numero speciale, che 

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

Possiamo verificare questo 

d * e = 40571156445208705 = 1 mod 10142789111302176

Questo è importante perché se si dispone di un messaggio in chiaro m , quindi il testo cifrato è 

c = m^e mod n

e si decifrarlo da 

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

Per esempio, posso il messaggio 123456789 utilizzando la chiave pubblica del tuo insegnante "Encrypt": 

m = 123456789

Questo mi darà il seguente testo cifrato: 

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

(nota che "e" dovrebbe essere molto più grande in pratica perché per piccoli valori di "m" non addirittura superare n)

In ogni modo, ora abbiamo "c" e in grado di invertire con "d" 

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

Ovviamente, non è possibile calcolare "7487844069764171 ^ 8114231289041741" direttamente perché ha 128,808,202,574,088,302 cifre, quindi è necessario utilizzare il modulare l'elevamento a potenza trucco.

Nel "mondo reale", n è ovviamente molto più grande. Se vuoi vedere un vero e proprio esempio di come HTTPS utilizza RSA sotto le coperte con un 617 cifre, n e e di 65537, vedi il mio post sul blog "< a href = "http://www.moserware.com/2009/06/first-few-milliseconds-of-https.html" rel = ""> noreferrer i primi millisecondi di un HTTPS Connection ."

Altri suggerimenti

Ecco un modo relativamente semplice di vedere le cose (e uno che è fattibile a mano). Se si dovesse fattore il numero completamente, quindi il fattore più alto si avrebbe bisogno di prendere in considerazione è sqrt (N): 

sqrt(10142789312725007) = 100711415.9999997567

Il primo capo di sotto di questo è 100.711.409, a soli 6 sotto lo sqrt (N). 

10142789312725007 / 100711409 = 100711423

dunque questi sono due fattori di N. Il tuo professore ha reso abbastanza facile - il trucco è quello di riconoscere che nessuno avrebbe scegliere un piccolo p o q così partire il vostro controllo dal basso (come in lo script python qualcuno ha postato) è una cattiva idea. Se sta andando essere pratico a mano, la grande p e q devono trovarsi vicino sqrt (N).

Ci sono vari algoritmi veloci per risolvere il problema del factoring n dato n, e e d. È possibile trovare una descrizione bene di un tale algoritmo in Handbook of Applied Cryptography, Capitolo 8 , sezione 8.2.2. È possibile trovare questi capitoli on-line per il download gratuito qui . L'algoritmo è essenzialmente una attenta elaborazione di di Henno Brandsma risposta a questa domanda.

UPDATE 25 settembre 2019:

Nel commento sotto , utente Imperishable Notte suggerisce un metodo alternativo che dovrebbe essere, almeno concettualmente più facile da capire.

Si fa notare che di solito e è piccolo. In realtà è quasi sempre e 65537. Nel caso in cui e è piccolo si può sviluppare un'equazione quadratica nel p primo sconosciuto e quindi facilmente risolvere per usando per esempio la formula quadratica . Per procedere, lascia set x = p e risolvere per x, solo per attaccare con convenzione. Sappiamo che ed = 1 mod phi(n), o equivalentemente ed - 1 = k * (p-1)*(q-1). Ora l'impostazione x=p, e quindi n/x=q, moltiplicando entrambi i lati da x e riorganizzare termini abbiamo
k * x 2 + (D * e - k * n - k - 1) * x + k * n = 0.
 Ora abbiamo un'equazione della forma ax 2 + bx + c = 0 e possiamo risolvere x utilizzando la formula quadratica. Così possiamo provare valori di k in un piccolo intervallo intorno e e ci dovrebbe essere solo una soluzione intera al quadratica, la soluzione per il corretto k.

Note:

  1. Tutto deve essere un numero intero, così la discriminante deve essere un quadrato perfetto o si può scartare k e provare la seguente. Inoltre, il numeratore deve essere divisibile per 2*k.
  2. A volte la funzione lambda Carmichael è usato al posto della funzione phi di Eulero. Questo complica le cose solo un po 'perché dobbiamo ora anche indovinare il g = gcd(p-1, q-1). g è sempre anche, è spesso 2, ed è comunque quasi sempre un piccolo multiplo di 2.

UPDATE 26 settembre 2019:

Finding k in realtà è molto facile quando e è piccolo. Prendendo l'equazione ed - 1 = k * (p-1)*(q-1) e dividendo entrambi i lati da n è abbastanza facile vedere che floor((ed-1)/n) + 1 == k. Ora, usando equazioni 31 e 32 di M.J. di Wiener "Cryptanalysis di Short RSA Segreto Esponenti" si può recuperare direttamente p e q.

WolframAlpha mi dice che i fattori sono 100.711.409 e 100.711.423

Ho appena scritto uno script Python ingenuo bruteforzare esso. Come amdfan sottolineato, partendo dalla cima è un approccio migliore: 

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

Questo potrebbe essere fortemente migliorata, ma funziona ancora senza problemi. Si potrebbe migliorarla primfactors solo test, ma per valori piccoli come la vostra Questo dovrebbe essere sufficiente.

La definizione di RSA si dice che il n = pq modulo. Sai n in modo che solo bisogno di trovare due numeri p e q che si moltiplicano ai prodotti n. Voi sapete che p e q sono primi, quindi questo è il problema fattorizzazione primo.

Si può risolvere questo con la forza bruta per relativamente piccoli numeri, ma la sicurezza complessiva del RSA dipende dal fatto che questo problema è intrattabile in generale.

Ecco un'implementazione Java del metodo di factoring veloce dal Manuale di Applied Cryptography sezione capitolo 8 8.2.2 (grazie a Gregs per trovarlo): 

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

Un tipico output è 

100711423 100711409 (3ms)

Questi due documenti potrebbe tornare utile

Mi sono imbattuto in loro quando stavo facendo qualche ricerca di base sulle frazioni continue.

L'algoritmo per fare questo è (e questo funziona per qualsiasi esempio, non solo questa piccola che può essere scomposto facilmente da qualsiasi computer):

ed - 1 è un multiplo di phi(n) = (p-1)(q-1), quindi è almeno un multiplo di 4.
ed - 1 può essere calcolato come 40571156445208704 pari 2^7 * 316962159728193, e che noi chiamiamo s=7 e t = 316962159728193. (In generale: qualsiasi numero pari è una potenza di 2 volte un numero dispari). Ora scegliere una di [2,n-1) a caso, e calcolare (dalle successive n quadratura modulo) la sequenza a^t (mod n), a^(2t) (mod n), a^(4t) (mod n).. fino al massimo a^((2^7)*t) (mod n), dove l'ultimo è garantito essere 1, dalla costruzione di e e d.

Ora guardiamo per la prima 1 in quella sequenza. Quella prima che possa essere sia +1 o -1     (Una radice banale di 1, mod n) e rifare con un diverso a, o qualche numero x che non è uguale o +1 -1 mod n.     Nel caso gcd(x-1, n) quest'ultimo è un divisore non banale di n, e così p o q, ed è fatta. Si può dimostrare che un un caso lavorerà con probabilità circa 0,5, quindi abbiamo bisogno di un paio di tentativi, ma non molti in generale.

vi consiglio di leggere la quadratica Sieve . Se si implementa uno voi stessi, questo è sicuramente vale la pena di credito. Se si capisce i principi, è già guadagnato qualcosa.

Ci scusiamo per la necromanzia, ma un amico mi ha chiesto di questo, e dopo di lui indicando qui, mi sono reso conto che non ho davvero come una delle risposte. Dopo factoring il modulo e ottenere i numeri primi (p e q), è necessario trovare il totient, che è (p-1)*(q-1).

Ora, per trovare l'esponente privato, si trova l'inverso della esponente pubblico mod l'totient. 

public_exponent * private_exponent = 1 mod totient

E ora avete la vostra chiave privata, così facile. Tutto questo, tranne per la fattorizzazione può essere fatto quasi istantaneamente per grandi numeri interi.

ho scritto un po 'di codice: 

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

}

L'algoritmo di fattorizzazione che ho usato è stupido, ma conciso, così grano di sale lì. In questo particolare esempio, il codice viene eseguito quasi istantaneamente, ma che è in gran parte perché l'istruttore in questione ha fornito un esempio che utilizza due numeri primi di fila, che non è davvero realistico per RSA.

Se si voleva tagliare fuori la mia stupida ricerca iterativa, si potrebbe mettere in qualche algoritmo di fattorizzazione reali, e le chiavi fattore probabilmente fino a circa 256 bit in un ragionevole lasso di tempo.

È necessario fattorizzare il modulo, che è il primo parametro della chiave pubblica, 10142789312725007. bruta forza farà (controllare ogni numero dispari da 3 a sqrt (n) se si tratta di un fattore), anche se esistono più sofisticate / algoritmi veloci .

Dal momento che il numero è troppo grande per essere in un intero convenzionale (anche a 64 bit), si potrebbe desiderare un libreria numerico che supporti arbitrari-lenth interi. Per C, c'è GMP e MPIR (più di Windows-friendly). Per PHP, c'è bignum. Pitone viene fornito con un built-in uno -. Incorporati integer tipo di dati è già arbitraria lunghezza

C'è un sacco di cattiva speculazione circa fattorizzazione di grandi numeri primi semi che vanno in vigore bruta o setacciatura nessuno dei quali è necessario per fattorizzare il primo semi. 64 bit richiede 1 - 2 secondi sul mio pc, e 256 bit in genere meno di 2 giorni

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top