PDF de programación - Códigos y Griptografía

Códigos y Criptografía

Francisco Rodríguez Henríquez

CINVESTAV

[email protected]

Códigos y Criptografía

Francisco Rodríguez Henríquez

Las tres leyes de la seguridad:

1. NO existen los Sistemas absolutamente seguros

Códigos y Criptografía

Francisco Rodríguez Henríquez

Las tres leyes de la seguridad:

2. Reducir nuestras vulnerabilidades

a la mitad implica incrementar los gastos al doble

Códigos y Criptografía

Francisco Rodríguez Henríquez

Las tres leyes de la seguridad:

3. Típicamente la criptografía no se rompe,

se brinca

Códigos y Criptografía

Francisco Rodríguez Henríquez

Terminología

Criptología: Término genérico utilizado para designar la
disciplina que estudia cómo lograr comunicaciones seguras
sobre canales que no lo son, junto con otros problemas
relacionados.
Criptografía: Diseño de sistemas y esquemas para realizar
comunicaciones confiables sobre canales inseguros.
Criptoanálisis: Disciplina que estudia cómo romper esquemas
criptográficos.
Texto en claro: mensaje que desea transmitirse de manera
segura.
cifra: documento que resulta después de haber cifrado el texto
en claro.
Llave o clave: información secreta que permite cifrar/descifrar
documentos.

Códigos y Criptografía

Francisco Rodríguez Henríquez

Aspectos de la criptografía
moderna

•La criptografía moderna depende de manera directa

de las matemáticas y del uso de sistemas digitales.

•Más específicamente se puede decir que está en la

intersección de tres disciplinas: matemáticas, ciencias

computacionales e ingeniería electrónica.

•Si no se tiene una comprensión profunda de las

técnicas de criptoanálisis es

imposible diseñar

sistemas criptográficos confiables y seguros.

Códigos y Criptografía

Francisco Rodríguez Henríquez

Comunicación Segura

Llave de cifrado

Llave de descifrado

Alicia

Texto claro

Cifrado

Texto cifrado

Descifrador

Beto

Eva

Adversario

Códigos y Criptografía

Francisco Rodríguez Henríquez

Objetivos del Adversario [Eva]

1. Discernir si acaso Alicia está

comunicándose con Betito o no

2. Leer el mensaje original

3. Obtener la llave secreta de Alicia.

4. Modificar el contenido del mensaje

original.

5. Usurpar la identidad de Alicia

Códigos y Criptografía

Francisco Rodríguez Henríquez

Principio de Kerckhkoff

•

se parte de la premisa que el oponente conoce el
algoritmo criptográfico utilizado. Por lo tanto, la
seguridad del sistema debe estar basada en:

• La calidad (fortaleza) del algoritmo
• El tamaño del espacio de la llave (tamaño en

bits de la llave)

Códigos y Criptografía

Francisco Rodríguez Henríquez

Métodos de ataque

1. Ciphertext only: El adversario sólo posee copias del texto

cifrado.

2. Known Plaintext: A partir del conocimiento de textos en

claro con sus correspondientes cifras, eva intenta deducir la
llave secreta.

3. Chosen Plaintext: Eva conoce la cifra que corresponde a

un texto en claro de su elección, el cual ella cree que puede
ser útil para deducir la clave secreta

4. Chosen Ciphertext: Eva conoce el texto en claro que

corresponde a un texto cifrado de su elección, el cual ella
cree que puede ser útil para deducir la clave secreta

Códigos y Criptografía

Francisco Rodríguez Henríquez

Longitud de llaves en criptosistemas

• Suponga que un criptosistema tiene un espacio de llaves con
cardinalidad de 1030, y que se pueden probar 109 llaves en un
segundo.
•Puesto que un año hay aproximadamente 3x107 segundos, un
ataque de fuerza bruta implica una duración de más de 3x1013
años, lo cual excede la predicción del tiempo de vida total de
nuestro universo.

•Así, para un criptoanalista el ataque por fuerza bruta debiera

ser su último recurso. En vez, es necesario sacar ventaja de las

debilidades propias del algoritmo o de su implementación,

intentado reducir el número de llaves candidatas
Códigos y Criptografía

Francisco Rodríguez Henríquez

Criptografía de llave simétrica

Formalmente un criptosistema puede ser definido como una

quíntupla {P,C,K,E,D}, donde:

P es el conjunto finito de los posibles textos en claro.
C es el conjunto finito de los posibles textos cifrados.
K el espacio de llaves, es un conjunto finito de todas las llaves

posibles.

Códigos y Criptografía

Francisco Rodríguez Henríquez

xxEDPxPCDCPEDDEEKkkkkkkk, que talesfuncionesson :y : Cada)descifrado de (regla cifrado) de (regla Criptosistemas clásicos

Cifrador de Julio César:
A las letras del alfabeto se les asigna un número

A

0

N

B

1

O

C

2

P

D

3

Q

E

4

R

F

5

S

G

6

T

H

7

U

I

8

V

13

14

15

16

17

18

19

20

21

J

9

W

22

K

L

10

11

X

Y

M

12

Z

23

24

25

Algoritmo:
Sea P = C = K= 26 y x  P, y  C, k  K

Cifrado:
Ek(x) = x + k mod 26.
Descrifrado: Dk(x) = x - k mod 26.

Códigos y Criptografía

Francisco Rodríguez Henríquez

Criptosistemas clásicos: Cifrador Afín

Algoritmo:
Sea P = C = 26 y x  P, y  C

Cifrado: Ek(x) = y =  · x +  mod 26.
La llave k = (, ) y ,   26
Ejemplo: k = (, ) = (13, 4)

INPUT = (8, 13, 15, 20, 19) 
ALTER = (0, 11, 19, 4, 17) 

ERRER
ERRER

Tno hay una correspondencia uno a uno entre el texto

en claro y la cifra: ¿Qué salió mal?

Descifrado: Dk(x) = x = -1 · y + 
Códigos y Criptografía

Francisco Rodríguez Henríquez

Criptosistemas clásicos: Cifrador Afín

Espacio de llave:
 Puede ser cualquier número en 26 . 26 posibilidades
puesto que -1 sólo pueden escogerse enteros en 26
t.q. mcd(, 26) = 1. Los posibles candidatos son:
{1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25}
Por tanto, el espacio de llaves tiene 12 · 26 = 312 candidatos.
Tipos de ataque:
1. Ciphertext only: Búsqueda exhaustiva o análisis de frecuencia
2. Known plaintext: Dos letras del texto en claro y las

correspondientes letras del texto cifrado son suficientes para
hallar la llave:
Ejemplo : Texto en claro: IF=(8, 5) y cifra PQ=(15, 16)

8 ·  +   15 mod 26
5 ·  +   16 mod 26 

 = 17 and  = 9

Códigos y Criptografía

Francisco Rodríguez Henríquez

Criptosistemas clásicos: Cifrador Afín

Tipos de ataque:
3. Chosen plaintext: Escoja A, B como el texto en claro. La

primera letra de la cifra será igual a 0· +  =  y la segunda
será  + .

4. Chosen ciphertext : Escoja A y B como el texto cifrado.

Cifrador por substitución

Cada letra del alfabeto del texto en claro es reemplazada por

otra letra. Más técnicamente, se escoge una permutación del
alfabeto original y se aplica al texto en claro. Tanto el
cifrador afín como el cifrador de Julio César son ejemplos
de cifradores por substitución.

Dado que la cifra así producida preserva la estadística del

idioma, estos cifradores son susceptibles a ser atacados por
análisis de frecuencia.

Códigos y Criptografía

Francisco Rodríguez Henríquez

Cifradores de Vigènere

Códigos y Criptografía

Francisco Rodríguez Henríquez

Cifradores de Vigènere

Índice de coincidencia en español de 27 letras

Índice de coincidencia para una cifra uniformente

distribuida:

Cifrado:
Descrifrado:

Ek(x) = x + ki mod 27
Dk(x) = x - ki mod 27

Suponga que la longitud de la clave secreta es m, entonces la cifra producida es de la
forma:

Códigos y Criptografía

Francisco Rodríguez Henríquez

072.0)(2602iicpxI, ,,322222212111mmmmmmmmyyyYyyyYyyyY038.0261261262cI Cifradores de Vigènere: Ataque de

Kasiski

CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBW
RVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAK
LXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELX
VRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHR
ZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJT
AMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBI
PEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHRCLQOHP
WQAIIWXNRMGWOIIFKEE

La subcadena CHR ocurre en 5 lugares de la cifra, con
posiciones inciales en: 1, 166, 236, 276 y 286, así que las
distancias desde la primera ocurrencia a las otras cuatro son
165, 235, 275 y 285. El MCD de esos números es 5, así que
probablemente esa es la longitud de la clave.

Códigos y Criptografía

Francisco Rodríguez Henríquez

Cifradores de Vigènere: Ataque de

Friedman

CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBW
RVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAK
LXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELX
VRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHR
ZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJT
AMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBI
PEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHRCLQOHP
WQAIIWXNRMGWOIIFKEE

Calcule los índices de
coincidencia
para
valores candidatos a la
longitud m de la clave:

m

1

2

3

4

5

IC

0.045

0.046, 0.041

0.043, 0.050, 0.047

0.042, 0.039, 0.045, 0.040

0.063, 0.068, 0.069, 0.061, 0.072

Códigos y Criptografía

Francisco Rodríguez Henríquez

Cifradores de Vigènere: ataque de

Friedman

Suponga que hemos adivinado el tamaño de la llave, i.e., K = (k1, k2, …, km), ¿cómo
podemos determinar los valores de sus letras?

Metodo de Friedman:
1. Sea

las frecuencias de las letras del alfabeto A, B, …, Z en la
sub-cifra Yi. También definimos n’=n/m, como la longitud de la subcadena Yi.
Entonces la probabilidad de distribución de las 27 letras en Yi es:

2. Recordemos que la subcadena Yi fue cifrada con el esquema de Julio César, con

un corrimiento ki. Entonces sería de esperarse que la probabilidad:

estuviese muy cerca de la distribución de probabilidad del castellano.

Códigos y Criptografía

Francisco Rodríguez Henríquez

260,sean y 1ffmi',,'260nfnf',,'26nfnfiikk Cifradores de Vigènere: ataque de

Friedman

Suponga que hemos adivinado el tamaño de la llave, i.e., K = (k1, k2, …, km),
¿cómo podemos determinar los valores de sus letras?

Metodo de Friedman:

3. Suponga que

y defina la cantidad:

, donde pi para

0≤i ≤26, representan la distribución de probabilidad de cada una de las letras

en el idioma español. Si le atinamos y si g=ki entonces sería de esperarse que:

Códigos y Criptografía

Francisco Rodríguez Henríquez

260g260'igiignfpM2602072.0iigpM Cifradores de Vigènere: ataque de

i

1

Friedman

Valor