Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Algoritmi - Differenza tra algoritmo di cifratura, di codifica e di criptazione
Forum - Algoritmi - Differenza tra algoritmo di cifratura, di codifica e di criptazione

Avatar
()
Newbie


Messaggi:
Iscritto:

Segnala al moderatore
Postato alle 1:00
Giovedì, 01/01/1970
Ciao a tutti. Premetto che mi sto affacciando adesso al mondo degli algoritmi, da informazioni lette qua e là incontro termini come:
- Algoritmo di cifratura;
- Algoritmo di codifica;
- Algoritmo di criptazione;

Che differenza c'è? in cosa consistono nello specifico?

PM Quote
Avatar
TheKaneB (Member)
Guru^2


Messaggi: 1792
Iscritto: 26/06/2009

Segnala al moderatore
Postato alle 16:30
Mercoledì, 10/03/2010
in termini puramente formali (da leggersi: informatica teorica, teoria dei linguaggi formali e degli algoritmi), un algoritmo di codifica serve a convertire un dato da un formato X qualunque in una sequenza di numeri interi. La decodifica è l'opposto ovviamente.

La criptazione serve per manipolare un numero intero in modo tale da rendere "molto difficile" risalire al dato originario se non si possiede la cosidetta "chiave di cifratura", che sarebbe poi un'altro numero intero.
La definizione di "molto difficile" significa in sostanza che un metodo ci sarebbe, ma la sua complessità algoritmica è esponenziale o superiore, quindi bisogna fare un numero di tentativi di decodifica provando un numero molto alto di chiavi di cifratura (tendenzialmente dello stesso ordine di grandezza dell'intero spazio delle chiavi).

Sono argomenti puramente teorici e le definizioni possono variare in base all'autore e al testo di riferimento... cmq almeno adesso hai qualche definizione da cui partire per i tuoi approfondimenti ;)
Ciao!

PS: cifratura e criptazione sono usati spesso come sinonimi...

Ultima modifica effettuata da TheKaneB il 10/03/2010 alle 16:30
PM Quote
Avatar
()
Newbie


Messaggi:
Iscritto:

Segnala al moderatore
Postato alle 20:20
Venerdì, 12/03/2010
Ciao TheKaneB... intanto grazie mille per le definizioni... Veramente molto esaustive... quello che stavo cercando...

Tuttavia, dato che sembri molto esperto dell'argomento, vorrei chiederti due cose se non ti è di fastidio:
1) Cos'è specificamente una chiave di Cifratura? Cioè io l'ho inteso come un "qualcosa" che applicato al dato di partenza, ne dà il dato risultante.. Ma specificatamente cosa sarebbe?
2) Tu dici che "molto difficile" vuol dire avere un numero di possibilità di indovinare la chiave molto basso (cioè "devo provare molte chiavi prima di prendere quella giusta"). Tuttavia da assoluto ignorante in materia, mi sono chiesto: "Se comunque di algoritmo si tratta, avuto questo algoritmo, non basterebbe semplicemente leggerlo al contrario (uso questa perifrasi rozza per dire terra terra "applicare un processo al contrario") per poter arrivare al punto di partenza?

Grazie mille e scusa l'insistenza da ignorante...

Ultima modifica effettuata da il 12/03/2010 alle 20:21
PM Quote
Avatar
TheKaneB (Member)
Guru^2


Messaggi: 1792
Iscritto: 26/06/2009

Segnala al moderatore
Postato alle 12:05
Sabato, 13/03/2010
Testo quotato

Postato originariamente da a_butta:

Ciao TheKaneB... intanto grazie mille per le definizioni... Veramente molto esaustive... quello che stavo cercando...

Tuttavia, dato che sembri molto esperto dell'argomento, vorrei chiederti due cose se non ti è di fastidio:



Non sono un esperto, ho conoscenze di livello appena universitario sull'argomento... cmq cercherò di risponderti :)

Testo quotato



1) Cos'è specificamente una chiave di Cifratura? Cioè io l'ho inteso come un "qualcosa" che applicato al dato di partenza, ne dà il dato risultante.. Ma specificatamente cosa sarebbe?




Semplificando al massimo, gli algoritmi crittografici si applicano su numeri interi. Quindi abbiamo un messaggio in chiaro M, una chiave di cifratura C, un messaggio criptato X, e una chiave di decifratura D.

Questi 4 "oggetti" sono numeri interi, quindi potremmo avere, M = 25, C = 3, X = 71, D = 29 (ho sparato numeri a casaccio).

In generale un computer lavora esclusivamente con i numeri. I caratteri, le immagini, i suoni, e tutto il resto possono essere "codificati" in numeri (in linea puramente teorica, una sequenza di bit, 0 e 1, formano un numero intero in base 2). Partendo da questo presupposto, possiamo facilmente generalizzare gli algoritmi crittografici in modo da operare su piccoli numeri interi (per meglio comprenderne il meccanismo), ma la sostanza non cambia se al posto di piccoli numeri lavoriamo con grandi files (che sono scomponibili comunque in piccoli blocchi, ciascuno dei quali rappresenta un numero intero di una certa lunghezza di bit, tipicamente si lavora in blocchi da 32bit fino a 4096bit o anche oltre).

Ecco che la crittografia sostanzialmente si riduce allo studio di formule matematiche, che combinando opportunamente le chiavi C e i messaggi M, genera come risultato i messaggi cifrati X e le chiavi di decrittazione D.

Testo quotato


2) Tu dici che "molto difficile" vuol dire avere un numero di possibilità di indovinare la chiave molto basso (cioè "devo provare molte chiavi prima di prendere quella giusta"). Tuttavia da assoluto ignorante in materia, mi sono chiesto: "Se comunque di algoritmo si tratta, avuto questo algoritmo, non basterebbe semplicemente leggerlo al contrario (uso questa perifrasi rozza per dire terra terra "applicare un processo al contrario") per poter arrivare al punto di partenza?



La tua è un'osservazione molto acuta e merita una spiegazione degna :) Cercherò di essere chiaro ma senza entrare troppo nei dettagli.

tra tutte le operazioni matematiche che si possono calcolare, ce ne sono alcune che richiedono pochi passi elementari (ad esempio la moltiplicazione) ed altri che invece richiedono un tempo di calcolo molto superiore (ad esempio la scomposizione in fattori primi).

Sfruttando questa caratteristica è possibile definire algoritmi che sono "facili" da calcolare in una direzione, ma molto difficili nella direzione opposta:

Es: 13 x 17 = 221

Per calcolare la moltiplicazione basta effettuare alcune semplici operazioni, tra le quali una ricerca in una tabella (la famosa tavola pitagorica) e la somma finale dei risultati parziali. A sua volta la somma finale può essere vista come una ricerca in una tabella di somme a singola cifra.
Tutte queste operazioni sono semplici e soprattutto il loro numero è moderato. Si dimostra che il calcolo della moltiplicazione richieda un numero elementare di operazioni che è direttamente proporzionale al numero totale delle cifre dei fattori calcolati.
Direttamente proporzionale significa che se raddoppio le cifre, raddoppio il tempo di calcolo; se moltiplico per 10 il numero di cifre, moltiplico per 10 il tempo di calcolo; ecc...

Procedimento inverso:
dato 221, trovare i suoi fattori primi.

Per questo compito sono noti molti algoritmi, alcuni dei quali molto sofisticati. Un esempio banale sarebbe quello di "provare" a dividere 221 per ogni numero a partire da 2, e verificare il resto della divisione.
221 : 2 = 110 resto 1
221 : 3 = 73 resto 2
221 : 4 = 55 resto 1
221 : 5 = 44 resto 1
...
..
221 : 13 = 17 resto 0 --- Trovato!

quindi prendere i due numeri, 13 e 17, e ripetere su di loro lo stesso procedimento, per verificare che siano effettivamente primi, oppure se possono essere scomposti ulteriormente.

Esistono algoritmi che effettuano meno operazioni rispetto a questo molto elementare, ma tutti gli algoritmi noti hanno comunque una complessità esponenziale rispetto al numero di cifre dell'input. Ciò significa che se aggiungo una cifra, moltiplico per 10 il numero di operazioni da fare; se aggiungo 2 cifre, moltiplico per 100; in generale, se aggiungo N cifre, moltiplico per 10 elevato N il numero di operazioni necessarie.

Ecco perchè la crittografia funziona! Alla base ci sono operazioni come questa, che possono essere eseguite in senso diretto con pochi calcoli, ma per essere eseguite in senso inverso (senza avere la "chiave") richiedono un numero di operazioni elementari talmente elevato (quando le cifre sono a centinaia o migliaia), da risultare "praticamente incalcolabili". Si calcola che, per decrittare un messaggio crittato con ElGamal, con chiavi da 4096 bit, usando in parallelo tutti i computer e supercomputer del mondo, occorra un tempo miliardi di miliardi di volte maggiore a quello della vita stimata dell'universo.

Alcuni problemi matematici usati in crittografia sono:
Scomposizione in fattori primi (RSA)
Calcolo del logaritmo discreto (ElGamal, DSA, Diffie-Hellman)
Interpolazione di curve ellittiche su campi discreti (Elliptic DSA, Elliptic Diffie-Hellman)

Ovviamente, se un giorno un brillante matematico dovesse scoprire un algoritmo "veloce" (cioè con tempo polinomiale rispetto al numero di cifre, anzichè esponenziale) per risolvere questi problemi, tutti gli attuali sistemi crittografici diverrebbero inutilizzabili, e si dovrà ricorrere ad altri metodi.

Spero di averti chiarito un po' le idee... per approfondimenti leggi su wikipedia (possibilmente quella inglese) o procurati qualche dispensa universitaria sulla crittografia e sull'algebra dei gruppi (si trovano gratuitamente sui siti delle varie università)

Ciao ;)

PM Quote
Avatar
()
Newbie


Messaggi:
Iscritto:

Segnala al moderatore
Postato alle 13:47
Sabato, 13/03/2010
TheKaneB ti faccio veramente i più sentiti complimenti! :hail:
Mi hai chiarito TANTISSIMI dubbi sul mondo degli algoritmi... adesso posso iniziare a studiarli più approfonditamente!
Grazie infinitamente!

PM Quote
Avatar
TheKaneB (Member)
Guru^2


Messaggi: 1792
Iscritto: 26/06/2009

Segnala al moderatore
Postato alle 17:04
Sabato, 13/03/2010
you're welcome... fa sempre piacere vedere persone interessate a questi argomenti ;)

PM Quote