Cracking a N bit numeri modulo RSA

Question

Questo è legato alla mia precedente postale, dove la mia unica opzione era di avere un algoritmo RSA che sembrava relativamente debole. Supponiamo che voglio codificare un numero di 35 bit (da 0 fino a 34.359.738,367 mila) con un modulo 36 bit (tra 34.359.738,368 mila fino a 68.719.476,735 mila).

Facendo riferimento a http://en.wikipedia.org/wiki/RSA posso vedere che il mio n è compreso tra 34.359.738,368 mila fino 68.719,476735 millions un totient casuale (di modulo p-1 * q-1). Prendo un d casuale ed e. Ho codificare un numero e dimostrare che sull'interfaccia utente.

Ai fini della discussione supponiamo che un utente può visualizzare fino a 1.000 tali uscite. Può utilizzare alcuni algoritmi come Polla del o qualcosa di simile per rompere il mio D, E o n e, quindi, iniziare a prevedere nuovi numeri? Se è così come è difficile sta per essere? (Con solo sapendo dire 1000 insiemi di ingressi / uscite)

Come esempio (non 6 uscite come campione in formato input / output),

1. 10001621865,31116156015
2. 10001621866,33031668326
3. 10001621867,37351399313
4. 10001621868,06071714212
5. 10001621869,01188523761
6. 10001621870,18341011998

Qualcuno può dirmi qual è il mio n, d, e era? (N tra 34.359.738,368 mila fino a 68.719.476,735 mila)

Voglio semplicemente sapere come violabile è, quindi se potesse fornire informazioni su quanto tempo, quanto velocemente, quante uscite si fa si deve vedere, ciò che gli algoritmi si può usare, ecc sarà grande.

PS: l'utente non vede la "e", come l'algoritmo standard RSA. Egli può vedere solo i set di input output.

dettaglio aggiunto Sto cercando di presentare un sequenziale user-id dal db per l'utente. Perché è sequenziale non voglio un utente di indovinare id di un altro utente facendo un paio di registrazioni. Per evitare questo devo rimescolare ad un questa domanda .

Anche il valore di n, d ed e non è noto per l'utente. Il massimo che un utente può vedere è un paio di ingresso ouput campioni (a titolo di registrare più volte)

Accettare la risposta inviato da Accipitridae poiché l'algoritmo "Jacobi" può essere utilizzato per rompere questo nel giro di pochi secondi. Senza sapere n, e o p.

Answer 1

Un utente malintenzionato può indovinare un fattore p di n ed e mod (p-1). Ogni congettura può essere controllata prendendo un messaggio m, calcolando m ^ e mod p e poi il confronto con c mod p, dove c è il testo cifrato corrispondente. Poiché p ed e mod (p-1) sono forse 20 bit ciascuno, ciò significa che la sicurezza del sistema non è più grande di 40 bit.

Ma 40 bit è solo molto grezzo limite superiore. Un utente malintenzionato può fare molto meglio. Per esempio si può intuire un fattore di p. Poi calcola i simboli Jacobi dei messaggi e testi cifrati. Se un messaggio m è un residuo quadratico mod p allora il testo cifrato deve essere un residuo quadratico mod p e viceversa. Quindi se questa relazione non è soddisfatta per un paio messaggio / testo cifrato può rifiutare l'ipotesi per p. O l'attaccante in grado di calcolare logaritmi discreti tra messaggio e testo cifrato. Questo dà un candidato molto più veloce per l'e mod (p-1).

Questo dovrebbe dare un livello di sicurezza di 20-30 bit, quindi richiede pochi secondi per rompere. Se si estende il numero di campioni da 20 Potrei provare alcuni benchmark.

Aggiornamento: Dal momento che non mi ha dato 20 campioni per eseguire un esperimento, ho dovuto generare io stesso. Con i seguenti esempi

m = 10001621865  c = 31116156015
m = 10001621866  c = 33031668326
m = 10001621867  c = 37351399313
m = 10001621868  c = 6071714212
m = 10001621869  c = 1188523761
m = 10001621870  c = 18341011998
m = 10001621871  c = 7620400191
m = 10001621872  c = 36106912203
m = 10001621873  c = 37615263725
m = 10001621874  c = 7795237418
m = 10001621875  c = 34774459868
m = 10001621876  c = 4555747045
m = 10001621877  c = 33123599635
m = 10001621878  c = 34836418207
m = 10001621879  c = 33962453633
m = 10001621880  c = 6258371439
m = 10001621881  c = 7500991556
m = 10001621882  c = 5071836635
m = 10001621883  c = 911495880
m = 10001621884  c = 39558568485

come input, l'algoritmo sopra descritto si trovano i fattori 201821 e 206.153  a 20ms. Come descritto in questo non ha bisogno di sapere e, anche se la scelta di e = 65537 è facile da indovinare e può essere sfruttato come bene.

La forza di RSA è che essa si basa sulla difficoltà di fattorizzazione di grandi numeri. Qui si rimuove questa difficoltà e ciò che rimane sono tutte le debolezze (cioè relazioni matematiche) di RSA. Costruire un cifrario a blocchi basata su RSA è un'idea orribile. Io davvero non capisco perché non si desidera utilizzare una costruzione Luby-Rackoff come ho proposto in precedenza.

Answer 2

RSA è vulnerabile nei confronti di un attacco con testo cifrato scelto. Cioè, diciamo che vogliamo rompere testo cifrato y, possiamo usare una delle coppie testo cifrato testo in chiaro per romperlo.

Come romperlo:

scegliere un x0 e y0, dove x0 e y0 è una coppia in chiaro-testo cifrato che è stato fornito.

y1 = y0 y * n y1 mod è un altro dei 1000 cifrati fornite all'utente che soddisfa questi criteri. x1 è la decrittografia di y1, che è anche dato, ciò significa:

x1 = y1 ^ d mod n (questo è stato dato a noi, sappiamo già x1)

x1 = (y0 * y) ^ d mod n x1 = y0 ^ d * y ^ d mod n Ξ x0 * x

x1 x0 * ^ -1 = x

x è la decrittografia di y.

Questo è ovviamente dipendente o meno y0 y * mod n produce un altro testo cifrato che abbiamo già, e poiché abbiamo a 1000 di tali coppie di lavorare, è improbabile ma non irrealizzabile rompere. Non vi resta che scegliere con estrema attenzione le coppie.

Vorrei anche aggiungere che la dimensione di n si sta lavorando con consente un'euristica di factoring per trovare la fattorizzazione primi di n abbastanza rapidamente. Inoltre, RSA è vulnerabile agli attacchi di temporizzazione, ma che può essere facilmente contrastato.

Con informazioni aggiunto: Senza sapere n, D o E, non c'è assolutamente alcuna informazione fornita a tutti, il che significa indovinando combinazioni di n, D o E è buono come indovinare il testo in chiaro si. Per trovare n ed e, ci sono almeno 43,359,738,367 combinazioni di n da indovinare, così come tutte le combinazioni e potrebbe essere. Non è facile per qualcuno anche con 1000 paia testo cifrato in chiaro di essere in grado di rompere n ed e.

Answer 3

Questa è un'idea orribile, 36 bit RSA ?? Perché non basta andare con un blocco o un flusso-cifrario? In questo modo si ottiene l'1:. Mappatura 1 e in un modo molto più sicura

Una soluzione alternativa che mi sento di raccomandare sarebbe quella di utilizzare un hash SHA come UID e memorizzare il numero sequenziale per ogni utente nel database come una colonna separata.