Criptograf´ıa Cl´asica - users.dsic.upv.esusers.dsic.upv.es/asignaturas/eui/cri/CrClasica.pdf ·...

CriptografıaClasica

Contenidos deltema

Aritmeticamodular

Sistemas mo-noalfabeticos

Sistemaspolialfabeticos

Sistemaspoligraficos

Sistemas portransposicion

Cifrado enflujo

Maquinas derotores

Criptografıa Clasica

DSIC-UPV

2012

(DSIC-UPV) Criptografıa Clasica 2012 1 / 45


Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Introduccion a la Criptografıa

Aritmetica modularSistemas de cifrado monoalfabeto: Cifrado porDesplazamiento, cifrado por Sustitucion y cifrado AfınSistemas de cifrado polialfabeto: Cifrado VigenereSistemas de cifrado poligrafico: Cifrado Playfair, cifradoHillSistemas de cifrado por transposicion: Cifrado porpermutacionSistemas de cifrado en flujo: Cifrado Autoclave, cifradoVernam

Cifrado en flujo sıncrono vs asıncronoCaracterısticas de secuencias pseudoaleatorias. Postuladosde GolombGeneracion de secuencias pseudoaleatorias

Maquinas de rotores: Enigma, Hagelin



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Introduccion a la Criptografıa

Aritmetica modularSistemas de cifrado monoalfabeto: Cifrado porDesplazamiento, cifrado por Sustitucion y cifrado AfınSistemas de cifrado polialfabeto: Cifrado VigenereSistemas de cifrado poligrafico: Cifrado Playfair, cifradoHillSistemas de cifrado por transposicion: Cifrado porpermutacionSistemas de cifrado en flujo: Cifrado Autoclave, cifradoVernam

Cifrado en flujo sıncrono vs asıncronoCaracterısticas de secuencias pseudoaleatorias. Postuladosde GolombGeneracion de secuencias pseudoaleatorias

Maquinas de rotores: Enigma, HagelinCriptoanalisis basico



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Aritmetica modular

Zm = {0, 1, . . . ,m − 1}



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Aritmetica modular

Zm = {0, 1, . . . ,m − 1}

Congruencia modulo m

a ≡ b (mod m)

Relacion de equivalencia



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Aritmetica modular

Zm = {0, 1, . . . ,m − 1}


a ≡ b (mod m)


Reduccion modulo m

a mod m



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Aritmetica modular

Zm = {0, 1, . . . ,m − 1}


a ≡ b (mod m)


Reduccion modulo m

a mod m

(Zm,+, ·) posee estructura de anillo conmutativo



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Aritmetica modular

Zm = {0, 1, . . . ,m − 1}


a ≡ b (mod m)


Reduccion modulo m

a mod m


Calculo de inversos para el producto:Teorema:ax ≡ b (mod m) tiene una unica solucion siimcd(a,m) = 1



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Aritmetica modular

Zm = {0, 1, . . . ,m − 1}


a ≡ b (mod m)


Reduccion modulo m

a mod m


Calculo de inversos para el producto:Teorema:ax ≡ b (mod m) tiene una unica solucion siimcd(a,m) = 1

Si mcd(a,m) = 1 entonces a y m son relativamente primos



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Sistemas monoalfabeticos: Desplazamiento

Cifrado Caesar:

e(x) = x + 3 mod 27d(y) = y − 3 mod 27

e(CENTRAL NUCLEAR) = FHPWUDN PXFNHDU



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores


Cifrado Caesar:

e(x) = x + 3 mod 27d(y) = y − 3 mod 27


Cifrado por desplazamiento:

ek(x) = x + k mod 27dk(y) = y − k mod 27



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores


Cifrado Caesar:

e(x) = x + 3 mod 27d(y) = y − 3 mod 27


Cifrado por desplazamiento:

ek(x) = x + k mod 27dk(y) = y − k mod 27

Espacio de claves: Desplazamientos posibles

Numero de claves: Talla del alfabeto



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Criptoanalisis monoalfabetico: Desplazamiento

La seguridad de un sistema criptografico no depende demantener en secreto el metodo de cifrado utilizado

(Principio de Kerchhoff)

Niveles de Ataque:

Solo texto cifrado : Se dispone de un criptograma

Mensaje conocido : Ademas de disponer de un criptogramaası como de parte del mensaje original

Mensaje escogido : El descifrador escoge un mensaje x y escapaz de obtener el mensaje cifrado

Criptograma escogido : El descifrador puede a partir de unmensaje cifrado obtener el corresondiente mensaje



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Criptoanalisis monoalfabetico: Desplazamiento

Frecuencia Alta Frecuencia Media Frecuencia Baja

e 14.0 u 4.9 v 1.1a 12.3 t 3.8 g 1.0o 9.8 c 3.6 j 0.6

s 7.6 m 2.7 f 0.5n 6.6 p 2.1 z 0.4r 6.2 q 2.0 n 0.2

i 5.6 b 1.5 x 0.04l 5.5 y 1.4 k 0.0004d 5.3 h 1.2 w 0.0002



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Sistemas monoalfabeticos: Sustitucion simple

Sustitucion simple:

A B C D E F G H I J K L M N N OO C T A V I P Z B D E F G H J K

P Q R S T U V W X Y Z

L M N N Q R S U W X Y



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Sistemas monoalfabeticos: Sustitucion simple

Sustitucion simple:

A B C D E F G H I J K L M N N OO C T A V I P Z B D E F G H J K

P Q R S T U V W X Y Z

L M N N Q R S U W X Y

ek(x) = π(x)dk(y) = π−1(y)

e(CENTRAL NUCLEAR) = TVHQNOF HRTFVON

Espacio de claves: Permutaciones posibles del alfabeto

Numero de claves: (Talla del alfabeto)!



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Criptoanalisis monoalfabetico: Sustitucion simple


e 14.0 u 4.9 v 1.1a 12.3 t 3.8 g 1.0o 9.8 c 3.6 j 0.6

s 7.6 m 2.7 f 0.5n 6.6 p 2.1 z 0.4r 6.2 q 2.0 n 0.2

i 5.6 b 1.5 x 0.04l 5.5 y 1.4 k 0.0004d 5.3 h 1.2 w 0.0002



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores



e 14.0 u 4.9 v 1.1a 12.3 t 3.8 g 1.0o 9.8 c 3.6 j 0.6

s 7.6 m 2.7 f 0.5n 6.6 p 2.1 z 0.4r 6.2 q 2.0 n 0.2

i 5.6 b 1.5 x 0.04l 5.5 y 1.4 k 0.0004d 5.3 h 1.2 w 0.0002

Bigramas mas frecuentes: es, ue, en, de, qu, os, er, el, as, ra



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores



e 14.0 u 4.9 v 1.1a 12.3 t 3.8 g 1.0o 9.8 c 3.6 j 0.6

s 7.6 m 2.7 f 0.5n 6.6 p 2.1 z 0.4r 6.2 q 2.0 n 0.2

i 5.6 b 1.5 x 0.04l 5.5 y 1.4 k 0.0004d 5.3 h 1.2 w 0.0002

Bigramas mas frecuentes: es, ue, en, de, qu, os, er, el, as, raTrigramas mas frecuentes: que, est, ent, oqu, del, con, ien, ues,ade, aqu



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Sistemas monoalfabeticos: Afın

ea,b(x) = ax + b mod 27

da,b(y) = a−1(y − b) mod 27



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores



da,b(y) = a−1(y − b) mod 27

Por ejemplo, tomando a = 2 y b = 5e(P) = aP + b mod 27 = 2 · 16 + 5 mod 27 = 10 → K

d(K ) = a−1(K − b) mod 27 = 2−1(10 − 5) mod 27 = 16 → P



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores



da,b(y) = a−1(y − b) mod 27


d(K ) = a−1(K − b) mod 27 = 2−1(10 − 5) mod 27 = 16 → P

e(PLANTA NUCLEAR) = KAFERF ETJANFN



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores



da,b(y) = a−1(y − b) mod 27


d(K ) = a−1(K − b) mod 27 = 2−1(10 − 5) mod 27 = 16 → P

e(PLANTA NUCLEAR) = KAFERF ETJANFN

Trabajando modulo m:

m =n

∏

i=1

pei

i φ(m) =n

∏

i=1

(pei

i − pei−1i )

Espacio de claves: (# Factores) · (# Desplazamientos)Numero de claves: φ(m) · m



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Criptoanalisis monoalfabetico: Afın


e 14.0 u 4.9 v 1.1a 12.3 t 3.8 g 1.0o 9.8 c 3.6 j 0.6

s 7.6 m 2.7 f 0.5n 6.6 p 2.1 z 0.4r 6.2 q 2.0 n 0.2

i 5.6 b 1.5 x 0.04l 5.5 y 1.4 k 0.0004d 5.3 h 1.2 w 0.0002



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores


Texto cifrado:“ENZKGYLFSOZPPCYSXNZFIYPXYRPDRGXNFTZ”



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores



Sımbolos mas frecuentes: Y 4 veces, P 4 veces, Z 4 veces,F 3 veces, N 3 veces, X 3 veces



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores




Suponemos e(E ) = Y y e(A) = P , por lo tanto



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores





{

4a + b mod 27 = 25

b mod 27 = 16⇒

{

a = 9

b = 16

La suposicion no era correcta



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores





{

4a + b mod 27 = 25

b mod 27 = 16⇒

{

a = 9

b = 16

La suposicion no era correcta

la conjetura valida es: e(E ) = Y y e(A) = F

Mensaje:“PROBLEMASCONNUESTROAGENTEINFILTRADO”



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Sistemas polialfabeticos: Vigenere

Clave: k = (k1, k2, . . . , km), donde ki ∈ Z27



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores



Denotando con xi el i -esimo sımbolo a cifrar:ek(xi ) = xi + ki mod m mod 27



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores




Denotando con yi el i -esimo sımbolo cifrado:dk(yi) = yi − ki mod m mod 27



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores




Denotando con yi el i -esimo sımbolo cifrado:dk(yi) = yi − ki mod m mod 27

Tomando k = (C ,L,A,V ,E ) = (2, 11, 0, 22, 4)

e(COCODRILO) = EZCKHTSLK



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Criptoanalisis polialfabetico: Vigenere

Basado en la deteccion del numero de alfabetos utilizado y laaplicacion de tecnicas basadas en analisis de frecuencias



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores



Kasiski: Un grupo de sımbolos que aparezca k vecesen un texto, sera cifrado k/n veces con elmismo alfabeto, donde n denota el numerode alfabetosDado un determinado segmento, si lasdistancias entre estas posiciones sond1, d2, ..., dk , el periodo es divisor delmaximo comun divisor de las distancias



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores



Kasiski: Un grupo de sımbolos que aparezca k vecesen un texto, sera cifrado k/n veces con elmismo alfabeto, donde n denota el numerode alfabetosDado un determinado segmento, si lasdistancias entre estas posiciones sond1, d2, ..., dk , el periodo es divisor delmaximo comun divisor de las distancias

Ind. de coincidencia: Se fundamenta en la distribucion de lafrecuencia de los sımbolos en un texto cifrado yen el lenguaje natural



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Criptoanalisis polialfabetico: Kasiski

Criptograma:

FSGWHAYPVJFRNIIYVRHLRMVRGNPBSGWD~NNWGBAG~NHFcu~nn

FCBSMHAAANAUEVNHDCFVJFRNICFAHcu~nnWG~NSOUFMUMCGS

AXHSJKZUEIWZCUFHYLQYJIYHMYK~NBSOFSFXWYCFTOAG~NAP

UQYUJIYWG~NNQCWRHSBJLUDJLHYKVJKRNWAFSIHAJYKGCV~N

XWFUNAUWGKWPCWQYMRWFCFHTCSWQYLPMAD~NAJUUCHWAGAC

KAACHAKHPULVGIYCU~NWACHWGGSGUEDFA~NNWAFFHGXAJYKG

JLZJ~NVGARHMCNWG~NKIWMIMSYCLHULSOWFJFSMWPOWA~NWGF

HGYCFHYFHJLQYWANSAWZ~NMWGULVXW~NNIRMHRFKRNNY~NSQJ

VR~NHQJWGJWGFWKRJEISVRVAYSICWHPJFJCFPYFHYI



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Criptoanalisis polialfabetico: Kasiski

Criptograma:

FSGWHAYPVJFRNIIYVRHLRMVRGNPBSGWD~NNWGBAG~NHFcu~nn

FCBSMHAAANAUEVNHDCFVJFRNICFAHcu~nnWG~NSOUFMUMCGS







VR~NHQJWGJWGFWKRJEISVRVAYSICWHPJFJCFPYFHYI

El tetragrama CUNN aparece en las posiciones 43 y 76 deltexto



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Criptoanalisis polialfabetico: Indice de Coincidencia

Dado un texto cifrado es posible establecer una medida dedispersion de las frecuencias de los sımbolos del mensajerespecto a una distribucion uniforme:



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores



MD =

26∑

i=0

(

pi −1

n

)2

=

26∑

i=0

(

p2i −

2pi

n+

1

n2

)2

=

26∑

i=0

(

p2i

)

− 0,037



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores



MD =

26∑

i=0

(

pi −1

n

)2

=

26∑

i=0

(

p2i −

2pi

n+

1

n2

)2

=

26∑

i=0

(

p2i

)

− 0,037

En un texto donde los sımbolos presentan una distribucionpropia del castellano:

IC =

26∑

i=0

(

p2i

)

= 0,072 ⇒ 0 ≤ MD ≤ 0,035

Intuitivamente, el IC mide la probabilidad de que dos sımbolostomados al azar de un texto cifrado sean iguales.



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores


El IC puede estimarse utilizando la frecuencia de los sımbolosen el criptograma:



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores



IC ≃

∑26i=0 fi (fi − 1)

N(N − 1)

donde fi denota el numero de ocurrencias del caracter i -esimoen un criptograma de N sımbolos



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores



IC ≃

∑26i=0 fi (fi − 1)

N(N − 1)

donde fi denota el numero de ocurrencias del caracter i -esimoen un criptograma de N sımbolos De este modo:

IC = MD + 0,037 ⇒ 0,037 ≤ IC ≤ 0,072

p = 1 IC = 0,072 p = 4 IC = 0,046p = 2 IC = 0,054 p = 10 IC = 0,040p = 3 IC = 0,049 p >> IC = 0,037



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores


Criptograma (mas extenso):

FSGWHAYPVJFRNIIYVRHLRMVRGNPBSGWD~NNWGBAG~NHFCU~NN

FCBSMHAAANAUEVNHDCFVJFRNICFAHCU~NNWG~NSOUFMUMCGS







VR~NHQJWGJWGFWKRJEISVRVAYSICWHPJFJCFPYFHYI ...



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores












p = 1 ⇒IC = 0,0471363



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores












p = 1 ⇒IC = 0,0471363p = 2 ⇒IC = {0,0479231, 0,0463764}



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores












p = 1 ⇒IC = 0,0471363p = 2 ⇒IC = {0,0479231, 0,0463764}p = 3 ⇒IC = {0,0739754, 0,0753505, 0,072086}



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores












p = 1 ⇒IC = 0,0471363p = 2 ⇒IC = {0,0479231, 0,0463764}p = 3 ⇒IC = {0,0739754, 0,0753505, 0,072086}p = 4 ⇒IC = {0,0470939, 0,046151, 0,0487458, 0,0464554}



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Criptoanalisis polialfabetico

Una vez detectado el numero de alfabetos, puede aplicarseun analisis de frecuencias como el ya visto

Efectivamente, el numero de alfabetos es 3

Mensaje:

LASCONEXIONESPUEDENSERDEMUCHASCLASESHISTORicas

NOHAYNINGUNAMISOPINIONESPOLITicasESTABANYATOMA

NDOFORMAMUCHOANTESDEQUEOYERAHABLARDELINGUISTIC

AYLAQUEESTUDIEENA~NOSPOSTERIORESENLAUNIVERSIDAD

ERAUNAESPECIEDETECNOLOGIADESCRIPTIVACONENMIOPI

NIONPOCASIMPLICACIONESMASAMPLIASENLOSDIVERSOSM

OVIMIENTOSESTRUCTURALISTASFUERONFRECUENTESLOSI

NTENTOSDEENSANCHARESASIDEASPEROELRESULTADODETO

DOESOESCREOMUYDEBILYPOCOCONVINCENTE ...



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Sistemas poligraficos: Playfair

Cifra el mensaje considerando pares de dos sımbolos(s1, s2)



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores



La clave es una matriz donde se disponen los sımbolos delalfabeto (9 × 3)



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores



La clave es una matriz donde se disponen los sımbolos delalfabeto (9 × 3)

Algoritmo: sean (x1, y1) y (x2, y2) las coordenadas de s1 y s2 enla matriz clave.

Si x1 = x2 ⇒ ((x1, y1 + 1 mod 9), (x2, y2 + 1 mod 9))

Si y1 = y2 ⇒ ((x1 + 1 mod 3, y1), (x2 + 1 mod 3, y2))

Si x1 6= x2 ∧ y1 6= y2 ⇒ ((x1, y2), (x2, y1))

Si s1 = s2 insertar un sımbolo sin significado

Si al final queda un unico caracter sin cifrar, insertar unsımbolo sin significado



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores


a j r b k s c l tclave: d m u e n v f n w

g o x h p y i q z

mensaje: EV ID EN CI AD EL

criptograma: NF GF NV FC DG NB



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Sistemas poligraficos: Hill

Cifra el mensaje considerando bloques de k sımbolos

La clave es una matriz Kk×k de valores en Zm tal quemcd(|K |, 27) = 1

K =

a11 a12 . . . a1k

a21 a22 . . . a2k

. . .ak1 ak2 . . . akk

;



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores




K =

a11 a12 . . . a1k

a21 a22 . . . a2k

. . .ak1 ak2 . . . akk

;

Algoritmo: considerando el mensaje x = x1x2x3x4 . . .

K ·

x1

x2...xk

=

y1

y2...

yk

;



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores




K =

a11 a12 . . . a1k

a21 a22 . . . a2k

. . .ak1 ak2 . . . akk

;

Algoritmo: considerando el mensaje x = x1x2x3x4 . . .

K ·

x1

x2...xk

=

y1

y2...

yk

; K−1 ·

y1

y2...

yk

=

x1

x2...xk



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores


Tomando K =

(

3 52 5

)

; K−1 =

(

1 265 6

)

; X = GATO



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores


Tomando K =

(

3 52 5

)

; K−1 =

(

1 265 6

)

; X = GATO

e(GA) =

(

3 52 5

)

·

(

60

)

=

(

1812

)



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores


Tomando K =

(

3 52 5

)

; K−1 =

(

1 265 6

)

; X = GATO

e(GA) =

(

3 52 5

)

·

(

60

)

=

(

1812

)

e(TO) =

(

3 52 5

)

·

(

2015

)

=

(

07

)



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Criptoanalisis Hill

Ataque basado en mensaje conocido



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Criptoanalisis Hill


Sea x = x1x2x3 . . . un fragmento del mensaje ey = y1y2y3 . . . su correspondiente criptograma



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Criptoanalisis Hill



Suponiendo la clave de tamano 3, es posible construir elsistema:

K ·

x1 x4 x7

x2 x5 x8

x3 x6 x9

=

y1 y4 y7

y2 y5 y8

y3 y6 y9



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Criptoanalisis Hill



Suponiendo la clave de tamano 3, es posible construir elsistema:

K ·

x1 x4 x7

x2 x5 x8

x3 x6 x9

=

y1 y4 y7

y2 y5 y8

y3 y6 y9

Es posible calcular la clave si la matriz mensaje esinvertible



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Sistemas de cifrado por transposicion

Permutacion

El mensaje se cifra en bloques de k simbolos

La clave consiste en una permutacion π de {1, 2, . . . , k}

Tomando k = 5 y π = {3, 4, 5, 2, 1}

mensaje: reuni onenp isofr ancoxcriptograma: unier enpno ofrsi coxna



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Cifrado en flujo: Propiedades

Cifrado de sımbolos individuales mediante unatransformacion que varıa con el tiempo

Facilmente implementables en hardware (rapidos)

Utiles en determinados casos (telecomunicaciones) dondeel almacenamiento temporal esta limitado

Poco sensibles a errores en la transmision

El diseno de los sistemas de cifrado en flujo se basa engeneradores de claves pseudoaleatorias (no segurosincondicionalmente pero computacionalmente seguros)



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Cifrado en flujo: Autoclave

Cifra el texto en bloques de sımbolos (m1,m2, ...,mn)

Se utiliza una clave primaria para cifrar los m primerossımbolos, sirviendo el propio mensaje como clave de cifrado

x : R E U N I O N D I A . . .k : c l a v e

x : 18 4 21 13 8k : 2 11 0 22 4

y : 20 15 21 8 12y : T O U I M



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Cifrado en flujo: Autoclave

Cifra el texto en bloques de sımbolos (m1,m2, ...,mn)

Se utiliza una clave primaria para cifrar los m primerossımbolos, sirviendo el propio mensaje como clave de cifrado

x : R E U N I O N D I A . . .k : c l a v e r e u n i . . .

x : 18 4 21 13 8 15 13 4 8 0 . . .k : 2 11 0 22 4 18 4 21 13 8 . . .

y : 20 15 21 8 12 6 17 24 21 8 . . .y : T O U I M G Q X U I . . .



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Cifrado en flujo: Vernam

Algoritmo:

Obtener una codificacion binaria del mensaje y la clave

El mensaje cifrado aparece cuando se opera un “Oexclusivo” bit a bit sobre el mensaje y la clave

El mismo proceso sirve como descifrado del mensaje



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Cifrado en flujo: Vernam

Algoritmo:

Obtener una codificacion binaria del mensaje y la clave

El mensaje cifrado aparece cuando se opera un “Oexclusivo” bit a bit sobre el mensaje y la clave

El mismo proceso sirve como descifrado del mensaje

Propiedades:

Incondicionalmente seguro si:

Clave compuesta por una secuencia binaria de la mismalongitud que el mensajeClave unica para cada mensaje



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Cifrado en flujo sıncrono

Flujo de claves generado independientemente del mensajey del criptograma Funcion de cambio de estado:

σi+1 = f (σi , k)Funcion de generacion de clave: zi = g(σi , k)Funcion de cifrado: ci = h(zi ,mi )

CIFRADO

f

g h

σi

k

mi

ci

σi+1

zi



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Cifrado en flujo sıncrono

Flujo de claves generado independientemente del mensajey del criptograma Funcion de cambio de estado:

σi+1 = f (σi , k)Funcion de generacion de clave: zi = g(σi , k)Funcion de cifrado: ci = h(zi ,mi )

CIFRADO

f

g h

σi

k

mi

ci

σi+1

zi

DESCIFRADO

f

g h−1

σi

k

ci

mi

σi+1

zi



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Cifrado en flujo sıncrono: Propiedades

Necesidad de sincronizacion entre EMISOR y RECEPTOR.Incorporacion de marcas a intervalos regulares(reinicializacion)

No sensible a errores en la transmision. Los erroresprovocan unicamente errores locales en el descifrado

Sensible a ataques activos (insercion, borrado o repeticionde sımbolos en el criptograma)



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Cifrado en flujo sıncrono: Propiedades

Necesidad de sincronizacion entre EMISOR y RECEPTOR.Incorporacion de marcas a intervalos regulares(reinicializacion)

No sensible a errores en la transmision. Los erroresprovocan unicamente errores locales en el descifrado

Sensible a ataques activos (insercion, borrado o repeticionde sımbolos en el criptograma)

Binary additive stream cipher: Sistema de cifrado en flujosıncrono donde:

El mensaje, la clave y el criptograma son secuenciasbinarias

La funcion de cifrado y descifrado (h) es la funcion XOR



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Cifrado en flujo autosıncrono

Flujo de claves generado como una funcion de la clave decifrado y un numero prefijado de los ultimos sımbolos delcriptograma Estado del sistema:

σi = (ci−t , ci−t+1, ci−t+2, . . . , ci−1)Funcion de generacion de clave: zi = g(σi , k)Funcion de cifrado: ci = h(zi ,mi )

CIFRADO

g h

. . .

k

mi

cizi



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Cifrado en flujo autosıncrono

Flujo de claves generado como una funcion de la clave decifrado y un numero prefijado de los ultimos sımbolos delcriptograma Estado del sistema:

σi = (ci−t , ci−t+1, ci−t+2, . . . , ci−1)Funcion de generacion de clave: zi = g(σi , k)Funcion de cifrado: ci = h(zi ,mi )

CIFRADO

g h

. . .

k

mi

cizi

DESCIFRADO

g h−1

. . .

k

ci

mizi



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Cifrado en flujo autosıncrono: Propiedades

Autosincronizacion. El descifrado depende de los ultimossımbolos del criptograma, ası, la perdida de sincronizacionse corrige una vez se analiza una secuenciasuficientemente larga

Propagacion limitada de errores: debida a la modificacion(insertado o borrado)

Menos sensible a ataques activos. El efecto de un ataqueactivo provoca una secuencia limitada de errores

Debido a la influencia del mensaje en el cifrado de lossımbolos siguientes, se desvirtuan las propiedadesestadisticas del texto en el criptograma. Menos sensibles aataques basados en redundancias en el texto del mensaje



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Secuencias binarias pseudoaleatorias

El periodo de una cadena pseudoaleatoria debe ser muygrande

Racha: Una racha de longitud k en una secuencia de bitses un segmento de longitud k del mismo bit entre dos bitsdistintosFuncion de autocorrelacion: medida de similitud entre unasecuencia periodica x = x0, x1, x2, ..., xT de periodo T y lasecuencia y resultante de desplazar d posiciones lasecuencia x (yi = x(i+d)modT ). Para k = 1...T se define:

ACT (k) = A − F

T

donde A y F denotan respectivamente el numero decoincidencias y fallos en las secuencias x e y . Si x es unasecuencia aleatoria, se esperan valores de ACT (k)pequenos para 0 < k < T



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Secuencias binarias pseudoaleatorias: Propiedades

Postulados de Golomb:

P1: En un periodo, la diferencia entre el numero debits distintos (0s y 1s) ha de ser a lo sumo 1

P2: Denotando el total de rachas con r , el numero derachas de longitud l en el periodo debe ser a losumo r

2l

P3: Para cualquier valor de k no multiplo de T (fuerade fase) el valor de ACT (k) es constante.

(Notese que en caso que k sea multiplo de T ,ACT (k) = 1)



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Generadores pseudoaleatorios de claves: LFSR

Linear Feedback Shift Registers

Propiedades:

Capaces de proporcionar secuencias pseudoaleatorias congran periodoCapaces de proporcionar secuencias con buenaspropiedades estadısticasFacilmente implementables en hardwarePosibilidad de analizarlos algebraicamente



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores


Linear Feedback Shift Registers

Propiedades:

Capaces de proporcionar secuencias pseudoaleatorias congran periodoCapaces de proporcionar secuencias con buenaspropiedades estadısticasFacilmente implementables en hardwarePosibilidad de analizarlos algebraicamente

Descripcion:

La Etapa 0 da lugar a un valor de la secuencia de salidaEl contenido de la Etapa i -esima se desplaza a la Etapa(i − 1)-esima (1 ≤ i ≤ L − 1)El contenido de la Etapa L − 1 se obtiene comocombinacion lineal (modulo 2) de los contenidos de(algunos de) los registros en el estado precedente



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores


Etapa

L − 1Etapa

L − 2. . . Etapa

1Etapa

0

AND AND . . . AND AND

c1 c2 c3 c4

output

⊕ ⊕

. . .⊕ ⊕



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores


Ejemplo:

Reg . 3 Reg . 2 Reg . 1 Reg . 0 output

⊕



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores


Ejemplo:

Reg . 3 Reg . 2 Reg . 1 Reg . 0 output

⊕

t R3 R2 R1 R0 t R3 R2 R1 R0

0 0 1 1 0 8 1 1 1 01 0 0 1 1 9 1 1 1 12 1 0 0 1 10 0 1 1 13 0 1 0 0 11 1 0 1 14 0 0 1 0 12 0 1 0 15 0 0 0 1 13 1 0 1 06 1 0 0 0 14 1 1 0 07 1 1 0 0 15 0 1 1 0



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Generadores pseudoaleatorios de claves: FSR

Feedback Shift Registers (no lineales)

Propiedades:

Basados en funciones booleanas

funcion booleana: funcion con n entradas y una salida,todas ellas binariasExisten 22n

funciones booleanas distintas de n variables



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores


Feedback Shift Registers (no lineales)

Propiedades:

Basados en funciones booleanas

funcion booleana: funcion con n entradas y una salida,todas ellas binariasExisten 22n

funciones booleanas distintas de n variables

Descripcion:

La Etapa 0 da lugar a un valor de la secuencia de salida

El contenido de la Etapa i -esima se desplaza a la Etapa(i − 1)-esima (1 ≤ i ≤ L − 1)

El contenido de la Etapa L − 1 es el resultado de unafuncion booleana f que toma como entrada los valores enla etapa anterior de todos los registros



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores


Etapa

L − 1Etapa

L − 2. . . Etapa

1Etapa

0output

f (sj−1, sj−1, . . . , sj−L)

sj−1

sj−2 sj−L+1sj−Lsj



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Combinaciones de LFSR

Las secuencias de un LFSR son facilmente predecibles



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores



Con objeto de romper la linealidad de las secuencias, seplantean tres aproximaciones:



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores




Combinando la salida de varios LFSR mediante unafuncion no lineal



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores




Combinando la salida de varios LFSR mediante unafuncion no linealUtilizando una funcion de filtrado sobre los registros de ununico LFSR (Nonlinear filter generators)



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores




Combinando la salida de varios LFSR mediante unafuncion no linealUtilizando una funcion de filtrado sobre los registros de ununico LFSR (Nonlinear filter generators)Utilizando un LFSR para controlar el reloj de uno (o mas)LFSR (Clock controlled generators)



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Combinaciones de LFSR: Funcion de salida

booleana

LFSR 1

LFSR 2

LFSR 3

. . .

LFSR n

outputf



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Combinaciones de LFSR: Nonlinear filter generators

Etapa

L − 1Etapa

L − 2. . . Etapa

1Etapa

0

AND AND . . . AND AND

c1 c2 c3 c4

⊕ ⊕

. . .⊕ ⊕

output

f



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Combinaciones de LFSR: Clock controlled

generators

Alternating step generator

clock LFSR 1

NO

AND

AND

LFSR 2

LFSR 3

⊕

output



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Combinaciones de LFSR: Clock controlled

generators

Shrinking generator

clock

LFSR 1

LFSR 2

¿ai = 1?

¿ai = 0?

considerar bi

descartar bi

ai

ai

bi

bi



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Maquinas de rotores

Banco de t rotores cada uno con tantos contactos comosımbolos en el alfabeto. Los rotores estan conectadosindependientemente

El resultado es un cifrado polialfabetico donde el numerode alfabetos considerado es muy alto



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Maquinas de rotores



ENIGMA

(ultimas versiones) 4 rotores, 26 conexiones cada uno

periodo = 264 = 456,976 alfabetos



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Maquinas de rotores



ENIGMA

(ultimas versiones) 4 rotores, 26 conexiones cada uno

periodo = 264 = 456,976 alfabetos

HAGELIN

6 rotores con 17,19,21,23,25 y 26 conexiones cada uno(numeros primos entre si)

periodo alrededor de 100 millones de alfabetos



Contenidos deltema

Aritmeticamodular





Cifrado enflujo

Maquinas derotores

Maquinas de rotores: Recursos

Historia de la maquina Enigma desde los orıgenes. Estudiode las bases del criptanalisis (por Roman Ceano): enlace

Enigmaco.de: simulador flash de una maquina de tresrotores (por Frank Spieß): enlace

Informacion historica y tecnica tanto de Enigma como deHagelin (incluye simuladores): enlace


http://www.kriptopolis.org/enigma

http://enigmaco.de/enigma/enigma.swf

http://users.telenet.be/d.rijmenants/index.htm

Criptograf´ıa Cl´asica - users.dsic.upv.esusers.dsic.upv.es/asignaturas/eui/cri/CrClasica.pdf ·...

Documents

Transcript of Criptograf´ıa Cl´asica - users.dsic.upv.esusers.dsic.upv.es/asignaturas/eui/cri/CrClasica.pdf ·...