|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.CifrarioDiHill History
Hide minor edits - Show changes to output
Changed line 143 from:
* E allora moltiplico entrambi i membri dell'equazione per X'^-1^' to:
* E allora moltiplico entrambi i membri dell'equazione per '''X'^-1^''''
Changed lines 63-65 from:
E come si trova la matrice inversa di una data matrice, sempre tenendo in considerazione il nostro caro modulo 26?
Il barbatrucco è to:
E come si trova la matrice inversa di una data matrice, sempre tenendo in considerazione il nostro caro modulo 26? Ricordiamo che il Δ deve essere diverso da 0, per avere l'inversa.
Il barbatrucco è semplice, '''se ho Δ = 1''': Added lines 83-115:
'''Se invece il Δ NON è 1,''' (e ovviamente non è 0...), devo fare altrimenti:
# inverto ancora gli elementi sulla diagonale principale
# degli altri due prendi l'inverso additivo
# moltiplico tutta la matrice per l''''inverso moltiplicativo del Δ'''
Che cos'è l'inverso moltiplicativo del Δ? È quel numero che risolve l'equazione
Δ * x = 1 mod 26
Vi ricordo che, per avere un inverso in Z'_26_', occorre che Δ e 26 siano coprimi.
Per esempio, l'inverso della matrice
5 8 9 2
17 3 è 1 15
Notate come mi sono stufato di fare la grafichina bella in ASCII.
Come ho ottenuto sta roba? Beh, come ho appena detto, ho invertito gli elementi della diagonale principale e ho preso l'inverso additivo di 8 e 17:
3 -8 3 18
-17 5 = 9 5
Il Δ della matrice originaria è 5*3 - 8*17 = -121, che in modulo 26 è 9.
L'inverso del Δ è quindi quel numero che, moltiplicato per Δ, mi dà 1.
Δ * x = 1 mod 26
Si dà il caso che 9 * 3 = 27 = 1 mod 26, quindi Δ'^-1^' = 3
E allora moltiplico il tutto, sempre modulando con il 26:
3 18 3*3 18*3 9 54 9 2
9 5 * 3 = 9*3 3*5 = 27 15 modulo 26 = 1 15
Oh, siamo felici!:) Checcarinoooo:) Changed lines 118-145 from:
to:
Se m=2, Hill nasconde la frequenza dei bigrammi. Se m = 3, nasconde anche quella dei trigrammi etc. etc.
Questo vuol dire che è ben resistente ad un attacco in cui si conosce solo il testo cifrato, perché non c'è analisi della frequenza che tenga.
Ma è invece vulnerabile ad un attacco known plaintext, ovvero quando ho una coppia testo in chiaro - testo cifrato. Anzi, ad essere precisi, qui mi servono '''m coppie''' di testo in chiaro e cifrato.
Il motivo è piuttosto semplice. Qui parliamo di matrici, che indico con le lettere maiuscole.
* '''X''' è la matrice dei miei m testi in chiaro, messi per colonna
* '''Y''' è la matrice dei corrispondenti m testi cifrati, messi anche loro per colonna
* '''K''' è la matrice della chiave, a me ignota
Sappiamo come è fatto Hill:
Y = K * X
dove K * X è una moltiplicazione per matrici.
Ma se è vero questo, allora è sicuramente vero che:
Y * X'^-1^' = K * X * X'+-1+' => Y * X'^-1^' = K
Infatti, se ho X, so anche calcolare la sua inversa (se possibile), e se moltiplico a destra e a sinistra, ottengo esattamente la cosa qui sopra, ovvero la matrice K!
Spiegandomi meglio:
* io, conoscendo la matrice '''X''' dei testi in chiaro, so anche trovarne l'inversa.
* una matrice per la sua inversa mi dà la matrice identità
* la matrice identità è quella matrice che, moltiplicata per qualsiasi altra matrice, mi dà l'altra matrice. È l'equivalente dell'1 nella moltiplicazione
* Ecco quindi che '''X * X'^-1^' = I''', dove '''I''' è la matrice identità
* In generale Hill funziona così: '''Y = K * X'''
* E allora moltiplico entrambi i membri dell'equazione per X'^-1^'
* Ottengo: '''Y * X'^-1^' = K * X * X'+-1+''''
* So che '''X * X'^-1^'''' = I, quindi posso ben dire che '''Y * X'^-1^' = K * I = K''', visto che '''K * I = K'''
Changed line 67 from:
# gli altri due elementi li sostituisco con il loro '''inverso additivo''' in modulo 26, ovvero quel numero che, sommato ad un altro, ottiene il neutro della somma, cioè 0 to:
# gli altri due elementi li sostituisco con il loro '''inverso additivo''' in modulo 26, ovvero quel numero che, se lo sommo al mio numero, ottengo il neutro della somma, cioè 0
Deleted line 44:
┌┐└┘││
Changed line 36 from:
Per risolvere codesta cosa, moltiplichiamo il '''vettore colonna''' per la matrice. Questo vuol dire che, come dicevo sopra faccio: to:
Per risolvere codesta cosa, moltiplichiamo il '''vettore colonna''' per la matrice. Questo vuol dire che, come dicevo sopra, faccio:
Changed lines 56-57 from:
%sottotitolo%'''Crittografia''' to:
%sottotitolo%'''Decrittografia''' Changed line 72 from:
┌ ┐ ┌ ┐ ┌ ┐ to:
┌ ┐ ┌ ┐ ┌ ┐ Changed line 74 from:
│ │ => │ │ => │ │ to:
│ │ => │ │ => │ │ Changed line 76 from:
└ ┘ └ ┘ └ ┘ to:
└ ┘ └ ┘ └ ┘
Changed lines 16-17 from:
c'_1_' = k'_11_'p'_1_' + k'_12_'p'_2_' + ... k'_1m_'p'_m_'
to:
c'_1_' = k'_11_'p'_1_' + k'_12_'p'_2_' + ... k'_1m_'p'_m_' mod 26
c'_2_' = k'_21_'p'_1_' + k'_22_'p'_2_' + ... k'_2m_'p'_m_' mod 26 Changed lines 19-20 from:
c'_m_' = k'_m1_'p'_1_' + k'_m2_'p'_2_' + ... k'_mm_'p'_m_' to:
c'_m_' = k'_m1_'p'_1_' + k'_m2_'p'_2_' + ... k'_mm_'p'_m_' mod 26 Changed lines 25-26 from:
c'_1_' = k'_11_'p'_1_' + k'_12_'p'_2_'
to:
c'_1_' = k'_11_'p'_1_' + k'_12_'p'_2_' mod 26
c'_2_' = k'_21_'p'_1_' + k'_22_'p'_2_' mod 26
Per rappresentarlo in modo compatto, lo possiamo vedere in forma matriciale:
┌ ┐ ┌ ┐ ┌ ┐
│ k11 k12 │ │ p1 │ │ c1 │
│ │ │ │ = │ │ mod 26
│ k21 k22 │ │ p2 │ │ c2 │
└ ┘ └ ┘ └ ┘
Per risolvere codesta cosa, moltiplichiamo il '''vettore colonna''' per la matrice. Questo vuol dire che, come dicevo sopra faccio:
c'_1_' = k'_11_'p'_1_' + k'_12_'p'_2_' mod 26
c'_2_' = k'_21_'p'_1_' + k'_22_'p'_2_' mod 26
Questo è il modo in cui si segna la moltiplicazione di una matrice per una colonna, ed è il modo con cui si rappresenta sotto forma matriciale un sistema lineare di m equazioni.
In modo '''alternativo''', se decido di '''non''' usare la forma del sistema lineare, posso usare la '''matrice trasposta''', ma mettere il testo in chiaro in una matrice '''[1 x 2]'''.\\
Tradotto graficamente, è così:
┌┐└┘││
┌ ┐
┌ ┐ │ k11 k21 │ ┌ ┐
│ p1 p2 │ │ │ = │ c1 c2 │ mod 26
└ ┘ │ k12 k22 │ └ ┘
└ ┘
In '''questo''' caso, con i valori '''k''' disposti in questo modo, le moltiplicazioni sono sempre le stesse. Da notare quindi che i valori '''k''' sono stati trasposti, ovvero nella prima '''colonna''' c'è quella che prima era una riga, ovvero i primi 2 valori di '''k''', e nella seconda '''colonna''' c'è la seconda riga.
Occorre quindi mettersi d'accordo su come è rappresentata la matrice, perché nel primo caso essa è la diretta rappresentazione di un sistema lineare, su cui è basato il cifrario di Hill. Nel secondo, non lo è affatto, ma è la sua trasposta. I conti escono tuttavia uguali.
%sottotitolo%'''Crittografia'''
La decrittografia è semplice: devo moltiplicare la '''matrice inversa''' per il mio vettore colonna di testo cifrato, ed ottenere così il vettore colonna di testo in chiaro.
Quindi, se diamo alle matrici nomi di lettere maiuscole, abbiamo:
C = KP
P = CK'^-1^'
E come si trova la matrice inversa di una data matrice, sempre tenendo in considerazione il nostro caro modulo 26?
Il barbatrucco è semplice:
# inverto gli elementi della diagonale principale, ovvero quella che va dall'alto in basso, e da sx a dx
# gli altri due elementi li sostituisco con il loro '''inverso additivo''' in modulo 26, ovvero quel numero che, sommato ad un altro, ottiene il neutro della somma, cioè 0
Facciamo un esempio per intenderci, per vedere com'è la matrice inversa.
┌ ┐ ┌ ┐ ┌ ┐
│ 3 2 │ │ 5 2'^-1^' │ │ 5 24 │
│ │ => │ │ => │ │
│ 7 5 │ │ 7'^-1^' 3 │ │ 19 3 │
└ ┘ └ ┘ └ ┘
Infatti, per ottenere 0 a partire da 2, in modulo 26, devo sommare 24 (ovvero, sottrarre 2 a 26). Idem per il 7: sottraggo 7 a 26, ed ottengo 19.
Poi si risolve il sistema lineare esattamente come prima.
La cosa funziona anche per la matrice trasposta, ovviamente, ricordandosi di mettere la matrice 1x2 prima etc. etc.
%sottotitolo%'''Attacchi crittografici'''
''...coming soon...''
Added lines 1-28:
(:title Crittografia - Il cifrario di Hill:)
%titolo%''':: Crittografia - Il cifrario di Hill ::'''
[[Torna alla pagina di Crittografia -> Crittografia]]
%sottotitolo%'''Crittografia'''
Il cifrario di Hill è basato su di un sistema lineare di m equazioni in m incognite, quindi facilmente risolvibile.
A che servono queste equazioni? Servono per produrre m lettere in output a partire da m lettere di testo in chiaro, aumentando quindi la '''diffusione'''.
Il testo in chiaro lo vediamo come un array di lettere, così indicizzate: '''p0, p1, p2 ... pn'''.
Il sistema lineare invece è il seguente:
c'_1_' = k'_11_'p'_1_' + k'_12_'p'_2_' + ... k'_1m_'p'_m_'
c'_2_' = k'_21_'p'_1_' + k'_22_'p'_2_' + ... k'_2m_'p'_m_'
..............................
c'_m_' = k'_m1_'p'_1_' + k'_m2_'p'_2_' + ... k'_mm_'p'_m_'
Questo vuol dire che le lettere da c'_1_' a c'_m_' saranno l'output delle lettere da p'_1_' a p'_m_'.
Visto che scritto così è caotico, facciamo il caso di '''m = 2''':
c'_1_' = k'_11_'p'_1_' + k'_12_'p'_2_'
c'_2_' = k'_21_'p'_1_' + k'_22_'p'_2_'
[[Torna alla pagina di Crittografia -> Crittografia]]
|
|
