Che tecniche usate una volta di scrivere i vostri metodi di crittografia?[chiuso]

StackOverflow https://stackoverflow.com/questions/118374

Domanda

Per anni, forse 10, sono stato affascinato con la crittografia.Ho letto un libro che parla di XOR bit di crittografia, e sono stato sempre legato cosa.

Credo sia più giusto dire che sono affascinato da quelli che possono rompere i vari metodi di crittografia, ma sto divagando.

Per il punto-che metodi utilizzate durante la scrittura di crittografia?È offuscamento bene in crittografia?

Io uso due basati su chiave di crittografia XOR, varie tecniche di hashing (SHA1) sui tasti, e le cose semplici come l'inversione di stringhe di qua e di là, etc.

Sono interessato a vedere cosa pensano gli altri e di provare durante la scrittura di un non-così-out-of-the-box metodo di crittografia.Anche -- qualche info su come i pro andare su "breaking" varie tecniche di crittografia pure sarebbe interessante.

Per chiarire -- non ho nessuna voglia di utilizzare questo codice di produzione, o qualsiasi codice di miniera per quella materia.Sono interessato a imparare come funziona attraverso giocando intorno, non reinventare la ruota.:)

Ian

È stato utile?

Soluzione

Per contraddire ciò che tutti gli altri hanno detto finora, provaci! Sì, il tuo codice potrebbe contenere vulnerabilità di buffer overflow e potrebbe essere lento, errato, ecc., ma lo stai facendo questo per DIVERTENTE ! Comprendo appieno il divertimento ricreativo riscontrato giocando con criptovalute.

Detto questo, la crittografia non si basa affatto sull'offuscamento (o almeno non dovrebbe esserlo). La buona crittografia continuerà a funzionare, anche una volta che Eve ha frugato nel tuo codice offuscato e completamente capisce cosa sta succedendo. IE: molti giornali hanno codice di sostituzione enigmi che i lettori cercano di rompere durante la colazione. Se iniziassero a fare cose come invertire l'intera stringa, sì, sarebbe più difficile, ma Joe Reader sarebbe ancora in grado di romperlo, neve tuohtiw gnieb dlot.

Una buona crittografia si basa su problemi che si presume siano (nessuno ancora provato, AFAIK) davvero difficili. Esempi di questo includono factoring primes , trova il registro , o qualsiasi altro NP-complete problema.

[Modifica: snap, nessuno dei due è provato NP-completo. Sono tutti non provati, ma diversi. Spero che tu veda ancora il mio punto: crypto si basa su funzioni a senso unico. Quelle sono operazioni facili da fare, ma difficili da annullare. cioè moltiplicare due numeri vs trovare i fattori primi del prodotto. Buona cattura tduehr ]

Più potere per te quando giochi con un ramo della matematica davvero interessante, ricorda solo che la criptovaluta si basa su cose difficili, non complicate. Molti algoritmi di crittografia, una volta che li capisci davvero, sono incredibilmente semplici, ma funzionano ancora perché si basano su qualcosa di difficile, non solo per cambiare le lettere.

Nota: Detto questo, alcuni algoritmi aggiungono stranezze extra (come lo string seversal) per rendere bruta la loro forzatura molto più difficile. Una parte di me ha la sensazione di averlo letto da qualche parte facendo riferimento a DES , ma non ci credo ... [EDIT: avevo ragione, vedi 5 ° paragrafo di questo articolo per un riferimento alle permutazioni come inutili.]

A proposito: se non l'avessi mai trovato prima, immagino che TEA / XTEA / XXTEA sarebbe interessante.

Altri suggerimenti

Il miglior consiglio che posso darti è: resistere alla tentazione di reinventare la ruota. La crittografia è più difficile di quanto pensi.

Ottieni il libro di Bruce Schneier Crittografia applicata e leggilo attentamente.

La risposta corretta è non fare qualcosa di simile a questo.Il metodo migliore è quello di scegliere una delle tante librerie di crittografia per questo scopo e applicazione.Sicurezza attraverso l'oscurità non funziona mai.

Scegli il corrente standard per algoritmi di crittografia, come pure.AES per la crittografia, hash SHA256 per.Elgamal a chiave pubblica.

La lettura di Crittografia Applicata è una buona idea pure.Ma la maggior parte del libro è dettagli di implementazioni che non è necessario per la maggior parte delle applicazioni.

Edit:Per espandere le nuove informazioni fornite in modifica.La stragrande maggioranza di corrente crittografia comporta un sacco di matematica complicata.Anche i cifrari a blocchi che sembrano tutti i tipi di munging di bit sono uguali.

In questo caso quindi di leggere Crittografia Applicata e quindi ottenere il libro Handbook of Applied Cryptography che si può scaricare gratuitamente.

Entrambi questi hanno un sacco di informazioni su ciò che accade in un algoritmo di crittografia.Alcune spiegazioni su cose come la crittoanalisi differenziale e lineare.Un'altra risorsa è Citeseer che ha un certo numero di pubblicazioni accademiche a cui fa riferimento, sia di quei libri per il download.

La crittografia è un campo difficile e con una grande storia accademica per andare ovunque.Ma se si hanno le competenze è abbastanza gratificante come l'ho trovato.

Fai gli esercizi qui:

http://www.schneier.com/crypto-gram-9910. html # SoYouWanttobeaCryptographer

Per cominciare, guarda il documento sull'attacco del cubo ( http://eprint.iacr.org/2008/ 385 ) e prova a rompere alcuni algoritmi con esso. Dopo aver familiarizzato con la rottura degli schemi crittografici, diventerai più bravo a crearli.

Per quanto riguarda il codice di produzione, ripeterò ciò che è già stato detto: basta usare ciò che è disponibile sul mercato, dal momento che tutti gli schemi tradizionali hanno già attraversato molteplici cicli di crittoanalisi.

Tutti i consigli sopra riportati sono validi. Offuscamento cattivo. Non mettere in produzione la tua criptovaluta senza prima lasciarlo battere per un po '.

un paio di cose da aggiungere:

  • La codifica non è non crittografia. Di recente ho ignorato il sistema di autenticazione di un sito Web a causa del malinteso degli sviluppatori qui.

  • Scopri come rompere anche i sistemi più elementari. Saresti sorpreso dalla frequenza con cui la conoscenza di semplici cifre di rotazione è effettivamente utile.

  • A ^ B = C. Hai dichiarato di aver lavorato con la crittografia XOR a due chiavi. Quando costruisci un cryptosystem verifica sempre che i tuoi passi stiano effettivamente realizzando qualcosa. nel caso XOR a due chiavi stai davvero usando una chiave diversa.

  • A ^ A = 0. La crittografia XOR è molto debole contro attacchi di testo in chiaro noti o scelti. Se conosci tutto o parte del testo in chiaro, puoi ottenere tutto o parte della chiave. Testo normale ^ Cyphertext = Key

  • Un altro buon libro da leggere è The Code Book di Simon Singh. Ripercorre parte della storia della crittografia e dei metodi per rompere la maggior parte dei sistemi crittografici che copre.

  • Due algoritmi da imparare (imparali e la storia dietro di loro):

    • 3DES: sì, è obsoleto ma è un buon punto di partenza per l'apprendimento di fiestel e blocchi di cypher e ci sono alcune buone lezioni nella sua creazione da DES. Inoltre, il ragionamento per la metodologia di crittografia, decrittografia e crittografia utilizzata è una buona cosa da imparare.
    • RSA: Mostrerò qui il mio fanatico della matematica interiore. Probabilmente l'algoritmo di crittografia più semplice oggi in uso. I metodi per romperlo sono noti (solo fattore chiave) ma computazionalmente estremamente difficili. m ^ d mod n dove n = p * q (p e q primo) e gcd (d, n) = 1. Un po 'di teoria dei gruppi / numeri spiega perché questo non può essere facilmente invertito senza conoscere p e q. Nel mio corso di teoria dei numeri abbiamo dimostrato la teoria alla base di almeno una mezza dozzina di modi.

Una nota per PhirePhly:

la scomposizione in fattori primi e il log discreto non sono NP-Complete o NP-Hard. Sono entrambi sconosciuti nella complessità. Immagino che otterrai una discreta quantità di fama solo nel capire quella parte. Detto questo, il resto della tua affermazione è corretto. La buona crittografia si basa su cose che sono facili da fare ma difficili da annullare senza la chiave.

A meno che tu non stia (diventando) un esperto nel settore, non utilizzare criptovalute fatte in casa nei prodotti di produzione. È stato detto abbastanza.

NON!

Anche gli esperti fanno fatica molto a sapere se hanno fatto bene. Al di fuori di una classe CS crittografica, basta usare il codice di altre persone. Codice di porta solo se è assolutamente necessario e quindi testare lo snot da esso con un buon codice noto.

La maggior parte degli esperti concorda sul fatto che l'apertura sia più preziosa dell'offuscamento nello sviluppo di metodi e algoritmi crittografici.

In altre parole, tutti sembrano essere in grado di progettare un nuovo codice che tutti possono rompere tranne loro. Il miglior crypto sopravvive alla prova di avere l'algoritmo e alcuni messaggi crittografati messi in circolazione e fare in modo che i migliori hacker crittografici provino a romperlo.

In generale, la maggior parte dei metodi di offuscamento e hashing semplice (e ne ho fatti molti anche io) sono molto facilmente rotti. Ciò non significa che non siano divertenti da sperimentare e conoscere.

Elenco di libri di crittografia (da Wikipedia)

Questa domanda ha attirato la mia attenzione perché al momento sto rileggendo Cryptonomicon di Neal Stephenson , che non è una brutta panoramica in sé, anche se è un romanzo ...

Per fare eco a tutti gli altri (per i posteri), non implementare mai la tua crittografia. Usa una biblioteca.

Detto questo, ecco un articolo su come implementare DES:

http://scienceblogs.com/goodmath/2008/09/des_encryption_part_1_encrypti.php

Permutazione e rumore sono cruciali per molti algoritmi di crittografia. Il punto non è tanto oscurare le cose, ma aggiungere passaggi al processo che rendono impraticabili gli attacchi di forza bruta.

Inoltre, ottieni e leggi Crittografia applicata . È un grande libro.

Devo essere d'accordo con altri poster. Non farlo a meno che non ci stia scrivendo un documento e non sia necessario fare qualche ricerca o qualcosa del genere

Se pensi di sapere molto a riguardo, vai a leggere la Crittografia applicata libro. Conosco molta matematica e quel libro mi ha ancora preso a calci. Puoi leggere e analizzare dal suo pseudo-codice. Il libro ha anche un sacco di riferimenti nella parte posteriore per scavare più a fondo se vuoi.

Crypto è una di quelle cose che molte persone pensano sia molto interessante, ma la matematica reale dietro i concetti è fuori dalla loro portata. Ho deciso molto tempo fa che non valeva la pena di sforzo mentale per me arrivare a quel livello.

Se vuoi solo vedere COME è fatto (studia le implementazioni esistenti nel codice) suggerirei di dare un'occhiata al libreria Crypto ++ anche se normalmente non codifichi in C ++ è una buona visione degli argomenti e delle parti dell'implementazione della crittografia.

Bruce ha anche un buon elenco di risorse che puoi ottenere dal suo sito.

Ho partecipato a una sessione di sicurezza del codice in questi anni Aus TechEd. Parlando dell'algoritmo AES in .Net e di come è stato selezionato, il presentatore (Rocky Heckman) ci ha raccontato una delle tecniche utilizzate per violare la crittografia precedente. Qualcuno era riuscito a utilizzare una termocamera per registrare la firma del calore di una cpu mentre stava crittografando i dati. Sono stati in grado di utilizzare questa registrazione per accertare quali tipi di calcoli stava facendo il chip e quindi decodificare l'algoritmo. Avevano troppo tempo a disposizione e sono abbastanza sicuro che non sarò mai abbastanza intelligente da battere le persone in quel modo! : (

  • Nota: spero sinceramente di aver trasmesso la storia correttamente, in caso contrario - l'errore è probabilmente mio, non quello del presentatore menzionato.

È già stato picchiato a morte che non dovresti usare la crittografia domestica in un prodotto. Ma ho letto la tua domanda e dichiari chiaramente che lo stai facendo solo per divertimento. A me sembra il vero spirito geek / hacker / accademico. Sai che funziona, vuoi sapere perché funziona e provare a vedere se riesci a farlo funzionare.

Lo incoraggio completamente e faccio lo stesso con molti programmi che ho scritto solo per divertimento. Suggerisco di leggere questo post ( http: //rdist.root .org / 2008/09/18 / dangers-of-amateur-crittografia / ) su un blog chiamato " rootlabs " ;. Nel post ci sono una serie di link che dovresti trovare molto interessanti. Un ragazzo interessato alla matematica / crittografia con un dottorato in Informatica e che lavora per Google ha deciso di scrivere una serie di articoli sulla programmazione della crittografia. Ha fatto diversi errori non ovvi che sono stati segnalati dall'esperta del settore Nate Lawson.

Ti suggerisco di leggerlo. Se non ti incoraggia a continuare a provare, senza dubbio ti insegnerà comunque qualcosa.

Buona fortuna!

Sono d'accordo con il non reinventare la ruota.

E ricorda, la sicurezza attraverso l'oscurità non è affatto sicurezza. Se una qualsiasi parte dei tuoi meccanismi di sicurezza usa la frase & Quot; nessuno lo capirà mai! & Quot ;, non è sicuro. Pensa a AES: l'algoritmo è pubblicamente disponibile, quindi tutti sa esattamente come funziona, eppure nessuno può romperlo.

Per altre risposte: inventare uno schema di crittografia è sicuramente una cosa per gli esperti e ogni nuovo schema di crittografia proposto deve davvero essere sottoposto a controllo pubblico per ogni ragionevole speranza di convalida e fiducia nella sua solidità. Tuttavia, implementare algoritmi e sistemi esistenti è uno sforzo molto più pratico & Quot; per divertimento & Quot; e tutti i principali standard hanno buoni vettori di test per aiutare a dimostrare la correttezza della tua implementazione.

Detto questo, per le soluzioni di produzione, le implementazioni esistenti sono abbondanti e in genere non dovrebbe esserci motivo per cui occorra per implementare un sistema da soli.

Sono d'accordo con tutte le risposte, sia " non scrivere il proprio algoritmo crittografico per l'uso in produzione " e " diavolo sì, provaci per la tua edificazione " ;, ma mi viene in mente qualcosa che credo venerabile che Bruce Schneier scriva spesso: " è facile per qualcuno creare qualcosa che loro stessi non possono rompere. "

L'unica crittografia che un non esperto dovrebbe essere in grado di aspettarsi di ottenere correttamente è una semplice cifra di One Time Pad. 

CipherTextArray = PlainTextArray ^ KeyArray;

A parte questo, tutto ciò che vale la pena guardare (anche per svago) avrà bisogno di un alto livello in matematica.

Non voglio approfondire le risposte corrette che sono già state fornite (non farlo per la produzione; semplice inversione non sufficiente; offuscamento male; ecc.)

Voglio solo aggiungere il principio di Kerckoff, " Un cryptosystem dovrebbe essere sicuro anche se tutto ciò che riguarda il sistema, tranne la chiave, è di dominio pubblico " ;.

Mentre ci sono, menzionerò anche il Principio di Bergofsky (citato da Dan Brown in Digital Fortress): " Se un computer ha provato abbastanza chiavi, è stato matematicamente garantito di trovare quello giusto. La sicurezza di un codice & # 8217; non era che la sua chiave di accesso non era trovabile ma piuttosto che la maggior parte delle persone non aveva & # 8217; t aveva il tempo o l'attrezzatura da provare. & Quot;
Solo che non è intrinsecamente vero; Dan Brown l'ha inventato.

Risposta a PhirePhly e tduehr, sulla complessità del factoring:

Si può facilmente vedere che il factoring è in NP e coNP. Quello che dobbiamo vedere è che i problemi & Quot; dati n e k, trovano un fattore primo p di n con 1 & Lt; p < = k " e " mostrano che non esiste tale p " sono entrambi in NP (il primo è la variante di decisione del problema del factoring, il secondo è la variante di decisione del complemento).

Primo problema: data una soluzione candidata p, possiamo facilmente (cioè in tempo polinomiale) verificare se 1 < p < = k e se p divide n. Una soluzione p è sempre più breve (nel numero di bit utilizzati per rappresentarla) di n, quindi il factoring è in NP.

Secondo problema: data una completa scomposizione in fattori primi (p_1, ..., p_m), possiamo verificare rapidamente che il loro prodotto sia n e che nessuno sia compreso tra 1 e k. Sappiamo che PRIMES è in P, quindi possiamo verificare la primalità di ogni p_i in tempo polinomiale. Poiché il primo più piccolo è 2, ci sono al massimo log_2 (n) fattori primi in qualsiasi fattorizzazione valida. Ogni fattore è più piccolo di n, quindi usano al massimo bit O (n log (n)). Quindi se n non ha un fattore primo tra 1 e k, esiste una breve prova (dimensione polinomiale) che può essere verificata rapidamente (in tempo polinomiale).

Quindi il factoring è in NP e coNP. Se fosse NP-completo, allora NP sarebbe uguale a coNP, cosa che spesso viene considerata falsa. Questo può essere preso come prova del fatto che il factoring non è effettivamente NP-completo; Preferirei solo aspettare una prova ;-)

Di solito, inizio ottenendo un dottorato in teoria dei numeri. Poi faccio circa un decennio di ricerche e seguo con un sacco di pubblicazioni e revisione tra pari. Per quanto riguarda le tecniche che utilizzo, sono diverse dalle mie ricerche e da quelle dei miei colleghi. Di tanto in tanto, quando mi sveglio nel cuore della notte, svilupperò una nuova tecnica, la implementerò, troverò buchi in essa (con l'aiuto della mia teoria dei numeri e dei colleghi di informatica) e poi perfezionerò da lì.

Se dai a un mouse un algoritmo ...

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