Domanda:
Dove posso imparare la crittografia / crittoanalisi nel modo più duro, senza andare a scuola? Qualche buon libro?
jokoon
2011-07-26 18:07:48 UTC
view on stackexchange narkive permalink

Non sono così bravo in matematica:

So cosa sono le p-list e le p-combinazioni, conosco l'algebra delle matrici, so cos'è uno XOR, so come dire se il numero è un numero primo, ecc: non sono il programmatore che odia la matematica perché non è bravo in questo, ma non ho neanche un dottorato di ricerca.

Non sono nemmeno un cattivo informatico, beh almeno in termini di cultura informatica generale:

Conosco C, C ++ (entrambi imparati a scuola), Python, alcuni haskell, quali codifiche di testo esistono, come funziona UNICODE, so come un file possono essere compressi o crittografati, quali sono gli algoritmi comuni disponibili (diffie-hellman, l'algoritmo LZMA, DES, AES, Serpent, Blowfish, SHA, MD5 ...). Mi sono molto interessato alla crittografia su wikipedia o altri siti web, ma non credo che wikipedia possa insegnarmi la crittografia senza dettagliare algoritmi o senza pratica; per esempio so cos'è la crittografia sincrona e cos'è asincrona (chiave pubblica / privata).

Mi piacerebbe imparare come implementare correttamente e in sicurezza gli algoritmi più diffusi e come renderli affidabili: un libro o buoni tutorial o corsi. Ho cercato rapidamente su Khan Academy, ma questo argomento non è banale e richiede sia conoscenze in matematica, informatica e / o elettronica.

Non voglio leggere pagine e pagine di teoria le cose di base che potrei già sapere o potrebbero non essere realmente rilevanti per la crittografia odierna, come un documento scritto da un ricercatore, solo qualcosa di pratico, con problemi e problemi di crittoanalisi, per gli studenti.

Al momento ho molto tempo libero, ho solo 26 anni, e sono sicuro di poter imparare queste cose, non solo per l'aumento di stipendio che mi può portare ma anche perché sono sempre stato affascinato dalla crittografia senza capirla davvero, posso semplicemente ' t trovare del buon materiale.

Stai parlando di imparare la * teoria *, come vengono definiti gli algoritmi, ecc. O come implementare soluzioni pratiche? Questi si escludono quasi a vicenda, per la maggior parte delle situazioni.
Impari meglio leggendo o facendo? Questo farà la differenza.
più leggendo, ma anche facendo, voglio dire che la crittografia non ha senso senza la crittoanalisi.
@jokoon, Vedi https://www.schneier.com/crypto-gram-9910.html. Ci sono anche molte risorse di lettura consigliate in https://www.schneier.com/paper-self-study.html
Otto risposte:
#1
+46
Thomas Pornin
2011-07-26 19:24:07 UTC
view on stackexchange narkive permalink

(LZMA è un algoritmo di compressione, non crittografico.)

Allo scopo di implementare algoritmi crittografici, il metodo generico sta ottenendo lo standard descrittivo pertinente, afferrando la tastiera, e provando. La maggior parte degli standard include "vettori di test", ovvero valori di esempio che consentono di sapere se l'implementazione restituisce le risposte corrette. A quel punto, le cose differiscono, a seconda del tipo di algoritmo che stai prendendo in considerazione.

Crittografia simmetrica:

Gli algoritmi simmetrici coprono la crittografia simmetrica, le funzioni hash, e codici di autenticazione dei messaggi (MAC). Non è necessario conoscere molta matematica per gestirli; la maggior parte riguarda l'aggiunta di interi a 32 e 64 bit (che è aritmetica modulare, con 232 o 2 64 come modulo) e operazioni bit per bit (XOR, AND ...).

Tale codice viene solitamente eseguito in C. Buone prestazioni si ottengono avendo alcune nozioni su come il compilatore C comprenderà e tradurre il codice in istruzioni per la CPU; la conoscenza dell'assemblaggio non è strettamente obbligatoria, ma piuttosto utile. Un parametro importante è la memoria cache: lo srotolamento del ciclo è solitamente un buon strumento, ma se lo esageri, le prestazioni calano drasticamente.

Suggerisco di iniziare implementando le classiche funzioni hash (la famiglia SHA, descritta in FIPS 180-3) e cercando di renderli veloci. Come punto di confronto, prendi OpenSSL e utilizza lo strumento della riga di comando openssl speed per vedere che tipo di prestazioni è possibile ottenere (questo strumentoè già incluso in qualsiasi distribuzione Linux decente e funziona anche su Windows e MacOS). Ad esempio, sul mio PC:

  $ openssl speed sha256Fare sha256 per 3s su blocchi di 16 dimensioni: 4842590 sha256's in 3.00sFare sha256 per 3s su 64 size blocchi: 2820288 sha256's in 2.99sFare sha256 per 3s su blocchi di dimensioni 256: 1262067 sha256 in 2,99 s Fare sha256 per 3 su blocchi di dimensioni 1024: 395563 sha256 in 3,00
Fare sha256 per 3s su 8192 blocchi di dimensioni: 53564 sha256's in 3.00sOpenSSL 0.9.8o 01 giugno 2010 costruito: mercoledì 23 febbraio 00:47:27 UTC 2011 opzioni: bn (64,64) md2 (int) rc4 (ptr, char) des (idx, cisc, 16, int) compilatore aes (parziale) blowfish (ptr2): cc -fPIC -DOPENSSL_PIC -DZLIB -DOPENSSL_THREADS -D_REENTRANT -DDSO_DLFCN-DHAVE_DLFCN_H -m64 -DL_ENDIAN -DTERMaIO -O3 - nogex -Wall -DMD32_REG_T = int-DOPENSSL_BN_ASM_MONT -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DMD5_ASM -DAES_ASM opzioni di temporizzazione disponibili: TIMES TIMEB HZ = 100 [valore sysconf] funzione di temporizzazione utilizzata: tempiI 'numeri' byte. Byte per secondo 64 byte 256 byte 1024 byte 8192 bytessha256 25827.15k 60367.37k 108056.57k 135018.84k 146265.43k  

il che significa che OpenSSL include un'implementazione SHA-256 ottimizzata a mano in assembly, che raggiunge 146 MB / s durante l'elaborazione di messaggi da 8 kB. Sulla stessa macchina, un'implementazione C pura dovrebbe arrivare ad almeno 130 MB / s.

Per un esempio di come le funzioni hash sono implementate in C e Java e come la velocità di hashing può essere misurata in un modo significativo, vedere sphlib.

Successivamente, puoi provare la crittografia simmetrica, in particolare l'AES ( FIPS 197). Aiuta un po 'a sapere cos'è un campo finito della caratteristica 2, ma lo standard è abbastanza chiaro da guidarti attraverso un'implementazione superficiale. Quindi, prova a ottimizzare le cose. OpenSSL può servire da punto di confronto e trarre ispirazione dalle implementazioni AES di Brian Gladman. Per quanto riguarda la sicurezza, c'è stata qualche preoccupazione su quali informazioni dipendenti dalla chiave potrebbero essere trapelate attraverso l'uso di tabelle di ricerca nell'implementazione (provare a cercare "AES cache timing attack"); cercare di riprodurre quel tipo di attacco è un ottimo esercizio (attenzione, non è facile, ma se riesci a dimostrarlo in condizioni di laboratorio, avrai imparato molto su come funzionano le implementazioni crittografiche).

Crittografia asimmetrica:

La crittografia asimmetrica riguarda gli algoritmi che coinvolgono più di una parte. Ciò include la crittografia asimmetrica (RSA, ElGamal), lo scambio di chiavi (Diffie-Hellman) e le firme digitali (di nuovo RSA, DSA ...). I contenuti matematici sono molto più grandi lì e l'ottimizzazione è un argomento molto più ampio rispetto alla crittografia simmetrica, perché ci sono diversi modi per implementare ogni algoritmo, invece di un singolo percorso di implementazione "ovvio".

Un buon riferimento è la Guida alla crittografia a curva ellittica. Sebbene si tratti principalmente di curve ellittiche, include una trattazione generale dell'implementazione di operazioni in campi finiti, e così accade che questo sia il capitolo campione che può essere scaricato gratuitamente all'URL collegato sopra. Quindi prendilo e leggilo ora. Un altro riferimento indispensabile è il Handbook of Applied Cryptography, che può essere scaricato gratuitamente; il capitolo 14, in particolare, riguarda l'implementazione efficiente.

RSA è abbastanza semplice ed è adeguatamente descritto in PKCS # 1. Sono possibili attacchi a tempo su RSA, che vengono contrastati mediante mascheramento (sì, questo è un documento "scritto da un ricercatore", ma in materia di crittografia i ricercatori sono le persone che capiscono cosa sta succedendo sopra). Se conosci l'aritmetica modulare, puoi provare a implementare DSA ( FIPS 186-3). Diffie-Hellman è matematicamente semplice (non ha bisogno di nient'altro di quanto è necessario per implementare DSA) ma il suo standard descrittivo (ANSI X9.42) non è scaricabile gratuitamente.

Le curve ellittiche sono un popolare futuro sostituto del modulare aritmetica; Le varianti EC di DSA e Diffie-Hellman sono più veloci e ritenute più sicure con chiavi pubbliche più brevi. Ma questa è più matematica. Anche in questo caso, la Guida alla crittografia a curva ellittica è il riferimento indispensabile.

Esistono altri tipi di algoritmi di crittografia asimmetrica, ad es. il McEliece crittosistema (crittografia asimmetrica; esiste una variante per le firme descritta da Niederreiter) e algoritmi basati sulla riduzione del reticolo. Ma non beneficiano (ancora) degli standard pubblicati che si prendono cura dei dettagli di implementazione e non ci sono così tante implementazioni esistenti con cui confrontarsi. Faresti meglio a iniziare con RSA e DSA.

Cryptanalysis:

Cryptanalysis utilizza una dose molto più alta di matematica rispetto all'implementazione.

Per la crittografia simmetrica, i due strumenti principali sono la crittoanalisi differenziale e lineare; vedi questo tutorial.

Il mio percorso verso la crittografia è iniziato implementando DES, e poi implementando la crittoanalisi lineare di Matsui su una versione ridotta di DES (8 round invece di 16). DES è descritto in FIPS 46-3, che è stato ufficialmente ritirato, ma ancora disponibile. Da DES si possono definire Triple-DES (tre istanze DES, con tre chiavi distinte, quella centrale utilizzata nella direzione di "decrittografia") e sono pubblicati vettori di test per Triple-DES (noti anche come "TDES", "3DES" o talvolta "DES", che è probabilmente fonte di confusione).

Per gli algoritmi asimmetrici, la crittoanalisi implica principalmente il lavoro sulla struttura matematica delle chiavi, ad es. provando a fattorizzare grandi numeri interi non primi per rompere le varianti RSA. La matematica qui va dal non banale al totalmente inimmaginabile, quindi questa potrebbe essere una curva di apprendimento troppo ripida per iniziare la crittografia cercando di rompere l'RSA ...

Wow. Ottima risposta. Hai offerto una bella rassegna di crittografia in un linguaggio di facile comprensione con riferimenti preziosi. Grazie.
@Thomas, Il tuo post non parla di come diventare un ** crittanalista **.
#2
+10
Robert David Graham
2011-07-27 04:34:18 UTC
view on stackexchange narkive permalink

Due cose, davvero:

  1. Procurati un buon libro. La "crittografia applicata" di Bruce Schneier è adeguata.
  2. Impara gli strumenti "openssl" e impara a usarli.

La cosa più importante da imparare sulla crittografia è l'umiltà . Non vuoi mai creare una nuova soluzione a un problema: vuoi copiare nel miglior modo possibile le soluzioni che sono state ben testate da altri. La maggior parte dei fallimenti crittografici sono dovuti a persone che hanno un'idea brillante, pensando di poter fare qualche ottimizzazione per migliorare una soluzione esistente. Sono solo gli estremamente umili che alla fine riescono a trovare nuovi modi di fare le cose.

La lezione successiva è che hai disimparato i tuoi pregiudizi che hai ottenuto dalla TV e dai film, dove un hacker si siede a un computer e rompe la crittografia. Questi non sono correlati alla crittografia o una drammatizzazione di ciò che accade davvero. Ad esempio, il film "Sneaker" è una drammatizzazione di ciò che accadrebbe se qualcuno sviluppasse un chip che potrebbe fattorizzare numeri interi di grandi dimensioni.

La cosa più difficile nell'apprendimento della crittografia è distinguere tra i concetti tecnici necessari per capire il campo in generale e quelli di cui avrai bisogno solo quando sarai specializzato in un'area ristretta. Prendi, ad esempio, il post molto apprezzato sopra. Devi capire la differenza tra un algoritmo "simmetrico" e un algoritmo "asimmetrico" e un "hash", ma quando l'autore di quel post dice "Aiuta un po 'a sapere cos'è un campo finito di caratteristica 2", Non sono d'accordo: ha senso solo per i dottori di ricerca che ricercano criptovalute, non per il resto di noi che vogliono semplicemente capire come usarle correttamente.

Un buon modo per approfondire i dettagli tecnici è scegliere un obiettivo e lavorare a ritroso. Ad esempio, oggi Apple ha aggiornato il sistema operativo iPhone / iPad alla versione 4.3.5 per correggere un bug nella convalida delle catene di certificati X.509. Capire il problema e perché hanno dovuto risolverlo è esattamente il genere di cose di cui stai discutendo nel tuo post originale. Scopri cos'è un certificato X.509, quali sono le catene e perché devono essere convalidate e perché se non lo fai, un hacker che utilizza uno strumento come "sslsniff" può annullare la crittografia. Una volta compreso appieno tutto ciò, avrai raggiunto gran parte del tuo obiettivo che descrivi nel tuo post originale.

Un altro esempio è un post del blog sulla verifica della chiave dell'hacker di Comodo

Ancora una volta, scopri cosa ha fatto l'hacker di Comodo (ha creato certificati firmati per Google e Yahoo), come funziona la revoca dei certificati e come utilizzare gli strumenti per convalidare quel certificato. Lo consiglio come un buon post perché è un buon punto di partenza per utilizzare gli strumenti "openssl", che sono standard nel nostro settore.

Buona fortuna!

#3
+10
kroosec
2011-12-27 18:14:34 UTC
view on stackexchange narkive permalink

Registrati al corso di crittografia online di Stanford che inizierà il prossimo gennaio. È gratuito, online, include sia teoria (lezioni video e quiz) che pratica (compiti di programmazione), ti permette di lavorare al tuo ritmo e otterrai una dichiarazione di realizzazione se ci riesci. Visti i vari echi che ho avuto durante la precedente sessione di corsi online di Stanford, mi sto decisamente iscrivendo a questo corso (così come a quello di Computer Security).

  • Sul lato teorico:

Principi di progettazione dell'ingegneria della crittografia e applicazioni pratiche di Niels Ferguson e Bruce Schneier. Il libro vuole essere un aggiornamento della venerabile crittografia applicata, gli autori sono ben noti nel campo e le recensioni sono buone.

  • Sul lato pratico:

Puoi dare un'occhiata a vari concorsi di hacking / sicurezza CTF (Capture The Flag). Generalmente includono sfide di crittografia. Sono divertenti e ti portano fuori dalla tua zona di comfort per risolvere i problemi in un tempo limitato. Ecco un buon calendario CTF. Inoltre, guarda alcuni commenti sui precedenti CTF, ho trovato molti molto istruttivi e ben spiegati.

sembra molto interessante e abbastanza eccitante, mi sono iscritto, ma non lo so, sarà gratuito?
@jokoon mi sono iscritto ... penso che la tassa sia per ottenere il certificato.
#4
+6
bethlakshmi
2011-07-26 19:13:13 UTC
view on stackexchange narkive permalink

Per gli algoritmi crittografici:

Cryptography: Theory and Practice di Stinson

esegue i calcoli di molti algoritmi crittografici in un modo che li renderebbe equi facile da implementare, se è quello che volevi fare.

Anche la Applied Cryptography di Scheiner è un libro importante sull'argomento. Probabilmente si sovrappone un po ', ma con alcuni algoritmi diversi.

Per quanto riguarda un libro che ti dice esplicitamente come implementarli, non ho niente. Commercialmente, questi non sono sempre implementati nel software ed è un settore abbastanza di nicchia. Dal punto di vista del gioco, direi che procurati un libro che spieghi l'algoritmo, implementalo e confronta il tuo risultato con una libreria comunemente usata per lo stesso algoritmo.

Allo stesso modo, non ho nulla sulla crittoanalisi , anche se sospetto che se scegli un algoritmo e google per cose come "debolezza" e "chiavi deboli" troverai alcuni documenti interessanti e altre informazioni. L'ultima volta che ho dovuto scrivere un articolo su qualcosa di simile (10 anni fa) è essenzialmente quello che ho fatto ...

#5
+4
D.W.
2011-10-01 11:49:56 UTC
view on stackexchange narkive permalink

Consiglio Ingegneria della crittografia: principi di progettazione e applicazioni pratiche. È il libro perfetto per te. Descrive come progettare e implementare i crittosistemi, dal punto di vista di un progettista e implementatore di sistemi. È un libro molto pragmatico, con una prospettiva derivata dagli anni di esperienza degli autori. La parola "ingegneria" nel titolo è davvero azzeccata. Penso che lo troverai una risorsa inestimabile che ti aiuterà a dare la priorità a ciò per cui dovresti spendere la maggior parte delle tue energie preoccupandoti, cosa può andare storto e come assicurarti che quelle cose brutte non ti accadano.

#6
+3
user432944
2012-03-23 18:41:16 UTC
view on stackexchange narkive permalink

Se vuoi comprendere la teoria della crittografia, scritta in un modo accessibile ai professionisti, prova "Introduzione alla crittografia moderna" di Katz e Lindell.

#7
+3
ack__
2013-08-05 00:07:31 UTC
view on stackexchange narkive permalink

Vorrei anche aggiungere che dai un'occhiata alle sfide crittografiche di Matasano dato che hai già alcune capacità di programmazione.

Dal loro sito web:

QUANTO CRYPTO DEVO SAPERE? Nessuna. Questo è il punto.

COSA DEVO SAPERE? Dovrai essere in grado di programmare in modo efficiente in qualsiasi lingua. Abbiamo ricevuto richieste in C, C ++, Python, Ruby, Perl, Visual Basic, X86 Assembly, Haskell e Lisp.

Tutte le loro sfide sono basate su vulnerabilità crittografiche del mondo reale, quindi dovresti imparare cose carine risolverli.

#8
  0
chris pete
2018-04-28 20:13:15 UTC
view on stackexchange narkive permalink

Imparare la crittografia da zero a volte può sembrare una cosa difficile, ma se hai le risorse giuste la adorerai. I seguenti sono i miei siti preferiti per iniziare a imparare la crittografia oggi stesso.

  1. Impara la crittografia a Kifanga per principianti assoluti a livelli più avanzati.
  2. La crittografia pratica è davvero utile per gli articoli di crittoanalisi
  3. La crittografia di apprendimento è ottima per le funzioni hash


Questa domanda e risposta è stata tradotta automaticamente dalla lingua inglese. Il contenuto originale è disponibile su stackexchange, che ringraziamo per la licenza cc by-sa 3.0 con cui è distribuito.
Loading...