it-swarm-eu.dev

C'è un semplice esempio di una routine di crittografia / decrittografia asimmetrica?

Riesco a capire molto bene il codice Java, Perl e JavaScript. Il resto, non ho studiato, ma immagino di riuscire a capire come leggere/tradurre.

Vorrei sapere qual è la più semplice delle routine asimmetriche. È davvero troppo complesso di cui preoccuparsi?

Sono davvero curioso di sapere come è possibile avere una chiave di sola crittografia! Mi sembra incredibile poter resistere al reverse engineering, quindi voglio sapere come funziona!

  1. È troppo complicato per quello.
  2. Qual è (una delle) routine di crittografia asimmetrica standard più semplice per cui posso cercare un'implementazione?
  3. Se ti capita di avere qualche esempio di codice minimo che sarebbe bello.

Ho già controllato paragrafi di Wikipedia su come funziona , ma non c'è stata alcuna scomposizione matematica o descrizione dell'implementazione, solo molte implementazioni . Non volevo davvero scegliere in modo casuale quale guardare, né volevo prendere quello più comune che mi aspetto sia il più robusto e complicato.

Qualche idea?

11
Bryan Field

Il merito va a La risposta di Jeff per i dettagli e La risposta di Steve che è stato anche utile. Il merito va anche a la risposta di tylerl che includeva collegamenti a Wikipedia per tutte le funzioni, in particolare modInverse , inoltre ha chiarito l'ambiguo punto di partenza per e. Grazie, Ho votato a fondo le tue risposte e, usando le informazioni combinate di tutte e tre le risposte, ho creato quella che spero sia una risposta migliore.

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

Algoritmo RSA (basato su the Java Code )

I calcoli seguenti devono essere eseguiti con numeri interi di precisione arbitraria . (Come BigInt o BigInteger)

Generazione delle chiavi:

  • La lunghezza della chiave costante è l.
  • Di solito costante _e_start_ can _=3_ per semplicità. Tuttavia, _0x10001_ è più comune, in ogni caso, un numero primo è il migliore (per motivi di prestazioni di generazione chiave e probabilmente altri motivi).
  • p e q sono i numeri primi positivi generati casualmente, che richiedono fino a l bit per la memorizzazione. (Per mantenerli 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)_ viene utilizzato per convertire e in d, che verrà utilizzato per la decrittografia.
  • _while(_ gcd _(e,m)>1){e+=2}_ Questo è necessario per il passaggio successivo.
  • _d=_ modInverse _(e,m)_ Esegue un'operazione aritmica standard. Probabilmente non vale la pena esaminare molto, soprattutto se il tuo linguaggio di programmazione lo ha incorporato

Per crittografare o decrittografare, innanzitutto convertire i byte in un singolo numero intero di precisione arbitraria.

Crittografia: encrypted=(plain^e)%n

Nota: Se _plain>=n_, è necessario dividere plain in due o più valori più piccoli e crittografarli separatamente.

Decrittazione: 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.

6
Bryan Field

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 ti aiuterà a fare semplicemente clic su qualcosa in passaggi come quello. Per gli articoli di Wikipedia, devi guardare l'articolo dell'algoritmo reale: RSA per la matematica che corrisponde.

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

Per la vostra comprensione, non esiste una chiave di sola crittografia. Piuttosto, ci sono due chiavi uguali che annullano le operazioni dei loro partner. Assegniamo arbitrariamente una coppia come privata e una come pubblica. Le cose crittografate con una chiave possono essere decifrate con l'altra chiave. Questo è il principio usato per la firma.

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

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

13
Jeff Ferland

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 un singolo pagina, ma abbastanza breve da poter essere letta e compresa in pochi minuti.

Poiché la crittografia/decrittografia può essere eseguita in un singolo comando incorporato - exp(PLAINTEXT,KEY,MODULUS) - Inoltre, eseguo anche l'intero processo di derivazione della chiave.

Troverai il codice qui: https://Gist.github.com/1239116

Quando si esegue il codice, viene richiesto di immettere sotto forma di >12345 o <12345, dove il > prefisso gli dice di applicare la chiave privata al numero, mentre < gli dice di applicare la chiave pubblica. Nell'interesse della semplicità, codifica solo numeri; ma una volta ottenuto ciò, la codifica di dati arbitrari è solo una questione di formattazione.

6
tylerl

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

Quindi per crittografare hai qualcosa del tipo: EncryptedBits = (PlainText ^ YourPublicKey)% Modulus

E per decrittografare hai qualcosa del tipo: PlainText = (EncryptedBits ^ YourPrivateKey)% Modulus

Mi sono imbattuto in un documento piuttosto facile da leggere qui: http://mathaware.org/mam/06/Kaliski.pdf

Non sono sicuro di tutte le biblioteche da guardare però.

5
Steve

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

È stata stampata su una maglietta, incluso un codice a barre per renderla leggibile dal computer, insieme alla frase " Questa maglietta è una munizione " . Questa affermazione era accurata negli Stati Uniti prima che la crittografia forte fosse riclassificata nel 1996 per non essere più tecnicamente una "munizione". Ma era ancora ampiamente illegale esportare una crittografia avanzata dagli Stati Uniti fino a quando i regolamenti sull'amministrazione delle esportazioni (EAR) non fossero rivisto nel 20 :

Il software è stato anche distribuito come tatuaggio, firma e-mail, etichetta postale e in molte altre forme e persino apparso (in forma sfocata) nel New York Times (l'articolo, senza la foto, è online all'indirizzo Between a Hacker And a Hard Place ). Una versione a 2 righe più recente è:

print pack"C*",split/\D+/,`echo "16iII*o\[email protected]{$/=$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" Unix per l'aritmetica di precisione arbitraria. Una versione pure-Perl, con annotazioni, è disponibile all'indirizzo

2
nealmcb