Home

Federica EU

1/11

Maria De Falco » 6.Cifrario di Cesare. Cifrario di Vigenere. Metodo di Hill

Definizione di crittografia

La crittologia è la scienza delle scritture nascoste, nel suo duplice significato: da un lato comprende infatti l’ideazione di metodi sempre più sicuri per occultare il reale significato di determinati segni (crittografia), dall’altro riguarda la decifrazione di testi occultati senza conoscerne a priori il metodo usato (crittoanalisi).
Il termine deriva dal greco kriptòs (nascosto) e logos (discorso), ovvero discorso nascosto.
La crittografia (dall’unione di due parole greche: kryptós che significa “nascosto”, e graphía che significa “scrittura”) è la branca della crittologia che tratta delle “scritture nascoste”, ovvero dei metodi per rendere un messaggio “offuscato” in modo da non essere comprensibile/intelligibile a persone non autorizzate a leggerlo.
Un tale messaggio si chiama comunemente crittogramma e le tecniche usate tecniche di cifratura.

Definizione di crittosistema

Un sistema crittografico oppure crittosistema oppure cifrario è una quadrupla
(M , C , f , $\bar{f}^{-1}$ ),
in cui M è l’insieme delle unità di messaggio in chiaro, C è l’insieme delle unità di messaggio cifrate, f è una funzione iniettiva di M in C, $\bar{f}^{-1}$ l’inversa della funzione $\bar{f}$ ottenuta da f restringendo il codominio alle immagini.
La funzione f viene detta funzione di cifratura.
La funzione $\bar{f}^{-1}$ viene detta funzione di decifratura.
Si dice inoltre che i parametri necessari per individuare f costituiscono la chiave di cifratura, mentre i parametri necessari per individuare $\bar{f}^{-1}$ costituiscono la chiave di decifratura.

Definizione di crittoanalisi

Per crittoanalisi (dal greco kryptós, “nascosto”, e analýein, “scomporre”), o crittanalisi, si intende lo studio dei metodi per ottenere il significato di informazioni cifrate senza avere accesso all’informazione segreta che è di solito richiesta per effettuare l’operazione. Tipicamente si tratta di trovare una chiave segreta. La crittoanalisi è la “controparte” della cittografia, vale a dire lo studio delle tecniche per occultare un messaggio, ed assieme formano la crittologia, la scienza delle scritture nascoste.
Con crittoanalisi ci si riferisce non solo ai metodi per violare un cifrario, ma anche ad ogni tentativo di eludere la sicurezza di algoritmi crittografici e protocolli crittografici. Anche se la crittanalisi di solito esclude metodi di attacco che non sono diretti alle debolezze intrinseche al metodo da violare, come ad esempio la corruzione, la coercizione fisica, il furto, l’ingegneria sociale, questi tipi di attacco, spesso più produttivi della crittoanalisi tradizionale, ne sono comunque un’importante componente.
Anche se il fine è sempre lo stesso, i metodi e le tecniche di crittoanalisi sono drasticamente cambiate durante la storia della crittografia, adattandosi al continuo aumentare dell’efficienza della crittografia, iniziando dai metodi basati su carta e penna del passato, passando per le macchine crittografiche come l’Enigma della seconda guerra mondiale, per arrivare agli schemi basati sui computer del presente. Insieme sono cambiati anche i risultati della crittoanalisi: non è più possibile ottenere un successo illimitato nella violazione dei codici e si stila perciò una graduatoria dei risultati conseguiti dagli attacchi. A metà degli anni settanta fu introdotta una nuova classe crittografica: la crittografia asimmetrica. I metodi per violare questa classe sono ben diversi da quelli utilizzati in passato e normalmente coinvolgono la risoluzione di problemi matematici altamente complessi, come la ben nota scomposizione in numeri primi.

Leggi un brano tratto dal romanzo “Enigma” di Robert Harris, Mondadori Editore.

Alcuni esempi di costruzione di M

Si presenteranno alcuni esempi di meccanismi per la costruzione dell’insieme M delle unità di messaggio in chiaro di un cifrario.
Si supponga di avere un alfabeto ordinato Σ di ordine m.
(1) Esiste una biezione naturale tra Σ e l’insieme {0, … , m-1} e quindi tra Σ e Z_m .
Si pone allora M=Z_m.
(2) Si fissa un intero k>0 e si suddivide il testo da cifrare in blocchi di k lettere.
Se σ₁ … σ_k è un blocco di k lettere, esso individua una k-pla (a₁ , … , a_k) appartenente a {0, … , m-1}^k, che a sua volta individua il numero a₁m^k-1+…+a_k-1m+a_kappartenente a {0, … , m^k-1} e quindi un elemento di $\mathbf{Z}_{m^k}$ .
Si pone allora M= $\mathbf{Z}_{m^k}$ .

Alcuni esempi di costruzione di M

(3) Si supponga di aver fatto fatto uno dei seguenti passi:
(a) Sia $\bar{\Sigma}$ =Σ e si sia stabilita una biezione tra $\bar{\Sigma}$ e Z_m ,come nel punto (1)
oppure
(b) Sia $\bar{\Sigma}$ l’insieme dei blocchi di lettere di lunghezza k, (dove k è un intero positivo) e si sia stabilita una biezione tra $\bar{\Sigma}$ e $\mathbf{Z}_{m^k}$ , come nel punto (2).
In entrambi i casi, si ha una biezione tra $\bar{\Sigma}$ e un opportuno Z_r . A questo punto si fissa un intero h>0 e si suddivide il testo da cifrare in blocchi di h elementi di $\bar{\Sigma}$ .
Se λ₁ … λ_h è un blocco di h elementi di $\bar{\Sigma}$ , esso individua una h-pla ([a₁]_r , … ,[a_h]_r) appartenente a $\mathbf{Z}_r ^h$ e quindi una matrice
$\left(\begin{array}{l} \left[a_1 \right]_r \\ ... \\ \left[a_h \right]_r \end{array}\right)$
appartenente all’anello M_h1(Z_r) delle matrici su Z_r con h righe e una colonna.
Si pone allora M=M_h1(Z_r).

Cifrari di tipo Cesare

Un crittosistema (M , C , f , f^-1) si dice “di tipo Cesare” se verifica le seguenti due condizioni:

M = C = Z_r per qualche intero r>1
f: Z_r → Z_r ed esiste un elemento [b]_r di Z_rtale che f(P)=P+[b]_r per ogni PєZ_r.

In tale crittosistema la chiave di cifratura è [b]_r (o anche b, se 0≤b≤r-1).
Inoltre, f^-1è ovviamente la funzione di Z_r in Z_r che ad ogni elemento C associa C-[b]_r , sicché la chiave di decifratura è -[b]_r=[r-b]_r (o anche r-b, se 0≤b≤r-1).

Cifrari affini

Un crittosistema (M , C , f , f^-1) si dice affine se verifica le seguenti due condizioni:

M = C = Z_r per qualche intero r>1
f: Z_r → Z_r ed esistono un elemento [a]_r di Z_r^* e un elemento [b]_r di Z_r tale che f(P)=[a]_rP+[b]_r per ogni PєZ_r .

In tale crittosistema la chiave di cifratura è la coppia ([a]_r , [b]_r) (o anche la coppia (a,b), se 0≤a≤r-1 e 0≤b≤r-1).
Inoltre, f^-1è ovviamente la funzione di Z_r in Z_r che ad ogni elemento C associa [a]_r^-1C – [a]_r^-1[b]_r , sicché la chiave di decifratura è la coppia ( [a]_r^-1,- [a]_r^-1[b]_r ).
Si noti che nel caso che sia [a]_r=[1]_r , si ritrova un cifrario di tipo Cesare.

Cifrari di Vigenere

Un crittosistema (M , C , f , f^-1) si dice di Vigenere se verifica le seguenti due condizioni:

M = C = $\mathbf{Z}_r ^k$ , con r>1 e k>0
f: $\mathbf{Z}_r ^k$ → $\mathbf{Z}_r ^k$ ; esiste una k-pla ([b₁]_r , … , [b_k]_r) appartenente a $\mathbf{Z}_r ^k$ tale che f(([a₁]_r , … , [a_k]_r))=([a₁]_r+[b₁]_r , … , [a_k]_r+[b_k]_r).

In tale crittosistema la chiave di cifratura è la k-pla ([b₁]_r , … , [b_k]_r) (o anche la k-pla (b₁ , … , b_k ), se 0≤b_i≤r-1).
La parola σ₁ … σ_k corrispondente alla k-pla ([b₁]_r , … , [b_k]_r) viene detta anche parola chiave del cifrario.
Inoltre, f^-1è ovviamente la funzione di $\mathbf{Z}_r ^k$ in $\mathbf{Z}_r ^k$ che ad ogni elemento C=([c₁]_r , … , [c_k]_r) associa ([c₁]_r-[b₁]_r , … , [c_k]_r-[b_k]_r).
Dunque la chiave di decifratura è la k-pla (-[b₁]_r , … , -[b_k]_r)=([r-b₁]_r , … , [r-b_k]_r) (o anche la k-pla (r-b₁ , … , r-b_k ) se 0≤b_i≤r-1).
Si noti che nel caso che sia k=1, si ritrova un cifrario di tipo Cesare.

Esempio

Esempio di cifratura con un cirafrio di Vigenere.
Si supponga che l’alfabeto Σ sia l’alfabeto italiano con l’aggiunta dello spazio ‗ , sicché si ha la seguente corrispondenza tra Σ e l’insieme {0,…,21}:
A=0, B=1, C=2, D=3, E=4, F=5, G=6, H=7, I=8, L=9, M=10, N=11, O=12, P=13, Q=14, R=15, S=16, T=17, U=18, V=19, Z=20, ‗=21
Sia dato un cifrario di Vigenere
$(\mathbf{Z}_{22}^4 \; , \; \mathbf{Z}_{22}^4\; , \; f \; , \; {f}^{-1})$
in cui la parola chiave è SOLE, cioé la chiave di cifratura è la 4-pla ([16]₂₂ , [12]₂₂ , [9]₂₂ , [4]₂₂ ).
Si cifrerà ora il messaggio ATTACCATE‗OGGI:
Il messaggio va suddiviso in blocchi di 4 lettere: ATTA CCAT E‗OG GI‗‗
Dunque la sequenza di unità di messaggio in chiaro è
([0]₂₂ , [17]₂₂ , [17]₂₂ , [0]₂₂ ) ([2]₂₂ , [2]₂₂ , [0]₂₂ , [17]₂₂ ) ([4]₂₂ , [21]₂₂ , [12]₂₂ , [6]₂₂ ) ([6]₂₂ , [8]₂₂ , [21]₂₂ , [21]₂₂ )
Applicando la funzione f a ciascuna unità di messaggio in chiaro, si ottiene la seguente sequenza di unità di messaggio cifrate:
([16]₂₂ , [29]₂₂ , [26]₂₂ , [4]₂₂ ) ([18]₂₂ , [14]₂₂ , [9]₂₂ , [21]₂₂ ) ([20]₂₂ , [33]₂₂ , [21]₂₂ , [10]₂₂ ) ([22]₂₂ , [20]₂₂ , [30]₂₂ , [25]₂₂ )
Dunque il messaggio cifrato è SHEEUQL‗ZN‗MAZID

Cifrari di Hill

L.S. Hill: “Concerning certain linear transformation apparatus of cryptography”, American Math. Monthly 38 (1931), 135—154.
Un crittosistema (M , C , f , f^-1) si dice “di Hill” se verifica le seguenti due condizioni:

M = C = M_h1(Z_r) per qualche intero r>1
f: M_h1(Z_r) → M_h1(Z_r) ; esistono una matrice A appartenente a GL_h(Z_r) ed una matrice B appartenente a M_h1(Z_r) tali che f(P)=AP+B per ogni PєM_h1(Z_r) .

In tale crittosistema la chiave di cifratura la coppia (A,B).
Inoltre, f^-1è ovviamente la funzione di M_h1(Z_r) in M_h1(Z_r) che ad ogni C associa A^-1C-A^-1B , sicché la chiave di decifratura è la coppia (A^-1,-A^-1B).

Matrici invertibili

Sia A una matrice quadrata appartenente a M_h(Z_r).
Allora A appartiene a GL_h(Z_r) se e solo se det(A) appartiene a Z_r*.
In quest’ultimo caso, l’elemento di posto ij di A^-1 è (-1)^i+j∙detA_ji∙(detA)^-1.
In particolare se
$A=\left(\begin{array}{ll}a\hspace{0.5cm} b \\ c\hspace{0.5cm} d \end{array}\right)$
è invertibile, allora, posto D=detA, si ha
$A^{-1}=\left(\begin{array}{ll}dD^{-1}\hspace{0.5cm}-cD^{-1}\\ -bD^{-1}\hspace{0.5cm}aD^{-1}\end{array}\right)$