Esiste un semplice esempio di una routine di crittografia / decrittografia asimmetrica?

Il credito va a La risposta di Jeff per i dettagli e La risposta di Steve che è stata anche utile. Il credito va anche a la risposta di tylerl che includeva collegamenti a Wikipedia per tutte le funzioni, in particolare modInverse , inoltre ha chiarito l'ambiguità punto di partenza per e . Grazie, ho upvoted le tue risposte e, utilizzando le informazioni combinate di tutte e tre le risposte, ho creato quello che spero sia una risposta migliore.

La chiave per rendere reverse-engineering così costoso sta usando power-of . La radice quadrata non è così difficile, la potenza di 3 significa che hai bisogno di una radice cubica, ma la potenza di 34.051.489 è piuttosto difficile. Esistono altre operazioni matematiche difficili da decodificare. Ci sono anche diversi modi per creare un algoritmo asimmetrico, ma questa risposta si concentra su RSA. Il più vecchio e il più comune.

Algoritmo RSA (basato su il codice Java )

I seguenti calcoli devono essere eseguiti con numeri interi precisi arbitrari . (Come BigInt o BigInteger)

Generazione delle chiavi:

• La lunghezza della chiave costante è l .
• Di solito costante e_start può =3 per semplicità. Tuttavia, 0x10001 è più comune, in ogni caso, un numero primo è il migliore (per motivi di prestazioni di generazione di chiavi e probabilmente altri motivi).
• p e q sono i numeri primi positivi generati casualmente, che richiedono fino a l bit per la memorizzazione. (Per mantenere questi positivi, il primo bit sarà sempre 0 )
• n = p*q Viene utilizzato sia per la crittografia che per la decrittografia.
• e inizia come e_start . Questo alla fine sarà la parte della chiave di crittografia.
• m = (p-1)*(q-1) è usato per convertire e in d , che sarà usato per la decrittazione.
• while( gcd (e,m)>1){e+=2} Questo è necessario per il prossimo passo di lavoro.
• d= modInverse (e,m) Esegue un'operazione aritmetica standard. Probabilmente non vale la pena esaminare molto, specialmente se il tuo linguaggio di programmazione ha questo incorporato

Per crittografare o decrittografare, converti prima i tuoi byte in un singolo intero di precisione arbitrario.

Crittografia: encrypted=(plain^e)%n

Nota: se plain>=n , devi dividere plain in due o più valori più piccoli e crittografarli separatamente.

Decrittografia: plain=(encrypted^d)%n

La crittografia asimmetrica è in genere meno efficiente della crittografia simmetrica. A volte la crittografia asimmetrica viene utilizzata solo per lo scambio di chiavi.

Per quanto riguarda RSA, questo fornisce un buon esempio che può essere seguito e mostra esempi corrispondenti di input e output. Questa applicazione demo ti guiderà attraverso i vari passaggi e ti consentirà di controllare il lavoro. A volte basta fare clic su qualcosa in passaggi del genere. Per gli articoli di Wikipedia, devi consultare l'articolo dell'algoritmo attuale: RSA per la matematica che corrisponde.

Per quanto riguarda l'implementazione, puoi riunirlo chiaramente in Java in meno di 30 righe .

Per tua comprensione, non esiste una chiave di sola crittografia. Piuttosto, ci sono due chiavi uguali che invertono le operazioni dei loro partner. Assegniamo arbitrariamente una delle coppie come private e una come pubblica. Le cose cifrate con una chiave possono essere decodificate con l'altra chiave. Questo è il principio usato con la firma.

Non è un problema di anti-reverse engineering che rende le chiavi sicure, ma piuttosto un concetto matematico che non è possibile controllare ragionevolmente l'enorme spazio delle chiavi (quando la chiave utilizza uno spazio numerico molto grande) per trovare la chiave corrispondente . Non c'è una vera accelerazione per il lavoro di factoring.

Ci sono altri algoritmi chiave asimmetrici da imparare, ma mentre guardi fuori proverei a capire prima RSA, il più vecchio e il più comune.

Ho messo insieme una dimostrazione di RSA usando python (Python è molto facile da leggere anche se non l'hai mai visto prima). Il codice è abbastanza lungo da non adattarsi a una singola pagina, ma abbastanza breve da poter essere letto e compreso in pochi minuti.

Poiché la crittografia / decrittografia può essere eseguita in un unico comando integrato - exp(PLAINTEXT,KEY,MODULUS) - passo anche all'intero processo di derivazione della chiave.

Troverai il codice qui: link

Quando esegui il codice, ti chiede l'input sotto forma di >12345 o <12345 , dove il prefisso > dice di applicare la chiave privata al numero, mentre < lo dice a applica la chiave pubblica. Nell'interesse della semplicità, codifica solo numeri; ma una volta ottenuto ciò, codificare dati arbitrari è solo questione di formattazione.

In realtà, la matematica è piuttosto semplice, come ho capito. Prendi un valore alla potenza di un numero primo ridicolmente grande (migliaia di cifre) e fai un mod da un altro numero.

Quindi per crittografare hai qualcosa di simile: EncryptedBits = (PlainText ^ YourPublicKey)% Modulus

E per decodificare hai qualcosa di simile: PlainText = (EncryptedBits ^ YourPrivateKey)% Modulus

Mi sono imbattuto in un documento piuttosto facile da leggere su di esso qui: link

Non sono sicuro di nessuna libreria da guardare.

Se vuoi una soluzione perl carina e minimale, ce n'è una classica di Adam Back di 1995 :

• export-a-cripto-system sig

È stato stampato su una maglietta, incluso un codice a barre per renderlo leggibile dal computer, insieme alla frase " Questa maglietta è una munizione ". Questa affermazione è stata accurata negli Stati Uniti prima che la crittografia avanzata fosse riclassificata nel 1996 per non essere più tecnicamente una "munizione". Ma era ancora ampiamente illegale esportare una strong crittografia dagli Stati Uniti fino a quando le EAR (Export Administration Regulations) erano revisionate nel 2000 :

Il software è stato anche distribuito come tatuaggio, firma e-mail, etichetta postale e in molte altre forme, ed è anche apparso (in forma sfocata) nel New York Times (l'articolo, senza la foto, è online all'indirizzo Tra un hacker e un luogo difficile ). Una versione a due righe più recente è:

print pack"C*",split/\D+/,'echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc'

Si noti che l'approccio originale si basa sul programma "dc" di Unix per aritmetica di precisione arbitraria. Una versione pure-perl, con annotazione, è

• RSA in 5 righe di perl