PDF de programación - Criptologia clásica

Criptologia

Dr. Roberto Gómez Cárdenas

Criptologia clásica

Roberto Gómez Cárdenas

[email protected]

@i

http://webdia.cem.itesm.mx/ac/rogomez

1

La criptografia en la historia

.

1500
1500

1600
1600

1700
1700

1800
1800

1900
1900

2000
2000

Escrito
Sistemas a mano
Mecanico
Electro-Mecanico
Electrónica
Programa almacenado
Llave pública

Fuente: Xerox Palo Alto Research Center

2

Criptologia Básica

1

Criptologia

Dr. Roberto Gómez Cárdenas

Procedimientos clásicos de encripción

• Primeros metodos criptograficos

– epoca romana hasta siglo XX

• Basados en dos técnicas

– transposición
– substitución

3

Procedimientos clásicos de

encripción

• Transposición

barajar los símbolos del mensaje original
– “barajar” los símbolos del mensaje original
colocandolos en un orden distinto, de manera que
el criptograma contenga los mismos elementos
del texto claro, pero colocados de tal forma que
resulten incomprensibles.

Sustitución
• Sustitución
– establecer correspondencia entre las letras del

alfabeto en el que está escrito el mensaje original
y los elementos de otro conjunto que puede ser el
mismo o distinto alfabeto.

Criptologia Básica

2

Criptologia

Dr. Roberto Gómez Cárdenas

Una primera clasificación

Esteganografia
(ocultar)

Adición

Generación

Substitución

Escritura
secreta

Critptografia
(revolver)

Transposición

Susbtitución

Códigos
(a nivel palabras)

Criptosistemas
(a nivel letras)

Criptosistemas basados en sustitución

Establecer correspondencia entre las letras
del alfabeto en el que está escrito el mensaje
original y los elementos de otro conjunto que
puede ser el mismo o distinto alfabeto.

5

6

Criptologia Básica

3

Criptologia

Dr. Roberto Gómez Cárdenas

Primer criptosistema sustitución

• Una de las más viejas descripciones de encripción

por sustitución aparece en el Kama Sutra
por sustitución aparece en el Kama-Sutra
– texto escrito en el siglo IV D.C. por Brahmin scholar

Vatsyayana, basado en manuscritos que datan del siglo
IV A.C.

• Kama-Sutra recomienda que la mujer debe estudiar

64 artes,
ió
– cocina, vestido, masaje y preparación perfumes
– tambien incluye: ajedrez, carpinteria
– número 45 de la lista: mlecchita-vikalpa, el arte de

id

f

i

j

escritura secreta

Criptosistema de Cesar

y p

• Sustituye primera letra del alfabeto A, por la
cuarta D; la segunda, B, por la quinta E, etc.
• También conocido como Ceaser shift cipher
• Dos alfabetos:

, p

– alfabeto texto plano/claro: el alfabeto usado para

escribir el mensaje original (texto claro)
escribir el mensaje original (texto claro)

– alfabeto criptosistema (o de encripción): las

letras de este alfabeto substituyen a las letras del
alfabeto texto claro

7

8

Criptologia Básica

4

Criptologia

Dr. Roberto Gómez Cárdenas

Ejemplo encripción Cesar

Alfabeto original

correspondencias

A B C D E F G H I

J K L M N O P Q R S T U V W X Y Z

J K L M N O P Q R S T U V W X Y Z

A B C

D E F G H I
Alfabeto
desfasado

f

Mensaje:
Llave:
Criptograma:

VENI
DDDD
YHQL

VIDI
DDDD
YLGL

VICI
DDDD
YLFL

Ejemplo decripción Cesar

alfabeto plano:

A B C D E F G H I

J K L M N O P Q R S T U V W X Y Z

alfabeto del criptosistema

correspondencias

X Y Z

A B C D E F G H I

J K L M N O P Q R S T U V W

Criptograma:
Llave:
Mensaje:

YHQL
DDDD
VENI

YLGL
DDDD
VIDI

YLFL
DDDD
VICI

9

10

Criptologia Básica

5

Criptologia

Dr. Roberto Gómez Cárdenas

Una variante de Cesar

• Usar como llave una palabra que no tenga letras

repetidas.

id

• La palabra es el inicio del alfabeto de encripción y

el resto son las letras del alfabeto en orden
creciente.

Alfabeto texto claro:

A B C D E F G H I

J K L M N O P Q R S T U V W X Y Z

Llave: Murcielago

Alfabeto de encripción
M U R

C I E L A G O B D F H J K N P Q S T V W X Y Z

Criptosistemas monoalfabeticos

• Administradores arabes usaban criptosistemas

parecido al de Cesar
parecido al de Cesar.

• También usaban criptosistemas que contenían otros

• Un criptosistema de substitución monoalfabético es el
l

tipos de símbolos:
– a puede ser reemplazada por #
– b puede ser reemplazada por +
U
nombre que se le da a cualquier criptosistema en el
cual el alfabeto del criptosistema consiste de letras o
símbolos, o una combinación de los dos.

lf béti

b tit

i t

i t

d

ió

11

12

Criptologia Básica

6

Criptologia

Dr. Roberto Gómez Cárdenas

Otros criptosistemas monoalfabeticos

• El criptosistema de Bacon
• El Polybius square
• Checker board
• Pigpen
• Atbash
• Ejemplos en la literatura

– Arthur Conan Doyle
– Edgar Allan Poe

El criptosistema de Bacon

(

• Francis Bacon (1521-1626) y su fraternidad
“Rosicrucian” hizo uso de diferentes tipos de
criposistemas.

) y

• Uno de los más simples utiliza grupos de cinco

letras y el resultado es un criptosistema
monoalfabetico de caracteres

• Utiliza un criptosistema de 24 letras con I, J, U y

W usados intercambiadamente

13

14

Criptologia Básica

7

Criptologia

Dr. Roberto Gómez Cárdenas

Ejemplo criptosistema Bacon

A = aaaaa
B = aaaab
C= aaaba
D= aaabb
E= aabaa
F= aabab
G= aabba
H= aabbb

I/J= abaaa
K= abaab
L = ababa
M = bbabb
N = bbbaa
O = bbbab
P = bbbba
Q= bbbbb

R = baaaa
S = baaab
T = baaba
U/V= babbb
W = babba
X = babab
Y = babba
Z = babbb

Texto claro: s u c c e s s

baaab babbb aaaba aaaba aabaa baaab baaab

Para encriptar: letra inicial de cada letra indica a o b A - M=a , N-Z=b

s = baaab
u = babbb

s

u

b a a a b b a b b b ...

Criptograma We are looking for you where is possible to take ...

15

El criptosistema Polybius Square

• Polybius era un escritor anciano Griego que
d d

propuso substituir las letras con números de dos
dígitos.

b i

i

l

l

• El alfabeto es escrito en una matriz de 5 x 5 con

los renglones y columnas numeradas:

1 2 3 4 5
1 A B C D E
1 A B C D E
2 F G H I/J K
3 L M N O P
4 Q R S T U
5 V W X Y Z

16

Criptologia Básica

8

Criptologia

Dr. Roberto Gómez Cárdenas

Encriptando en Polybius Square

• Para encriptar sustituir cada letra con las

i

coordenadas de la letra en la matriz.

d l

d

d

l

l

• Por ejemplo:

F: es igual a 21

R E N A C I M I E N T O
4215 331113 24 32 2415 33 44 34

1 2 3 4 5
1 A B C D E
2 F G H I/J K
3 L M N O P
4 Q R S T U
5 V W X Y Z
5 V W X Y Z

• Es más un código que un criposistema
• Fue usado para transmitir mensajes de larga

distancia en la noche usando antorchas.

Checker Board

• Similar al de Polybius
• La llave esta constituida por tres palabras

– dos están en la columna y renglón de la matriz de 5 x 5

y forman las coordenadas de las entradas

– estas palabras no pueden contener palabras similares

para proporcionar coordenadas únicas

• Adentro de la matriz se escribe el alfabeto
lf b t

Ad t
– la tercera palabra se escribe adentro de la matriz y se

d l

t i

ib

l

rellenan las otras celdas con el resto del alfabeto

• La encripción es igual que en Polybius

17

18

Criptologia Básica

9

Criptologia

Dr. Roberto Gómez Cárdenas

Ejemplo de Checker board

G R O U P
G R O U P
W B O A R D
H C E F G H
I I/J K L M N
T P Q S T U
E V W X Y Z
E V W X Y Z

Texto claro: p r o t o c o l
Criptograma:

TGWUWRTUWRHGWRIO

El criptosistema de Pigpen

• Criptosistema de tipo monoalfabetico
• Usado por los Freemasons en los 1700s para

mantener sus registros secretos y aun es
usado hoy en día por los niños escolares

• No sustituye una letra por otra, en lugar de
estos substituye cada letra por un símbolo
de acuerdo a un patrón determinado.

í b l

d l t

t

b tit

19

20

Criptologia Básica

10

Criptologia

Dr. Roberto Gómez Cárdenas

El alfabeto

A B C
A B C

D E F
G H I

J
J
K L
K L
M N O
P Q R

T

S
S

V

U

X

W
W

Z

Y

a =
b =
:
:
z =

Ejemplo:

Criptosistema Atbash

• Se toma cada letra, se calcula el número de

lugares que lo separan de la primera letra
del alfabeto.

• Se reemplaza con una letra que se encuentra
en la misma distancia del final del alfabeto.
E lf b t
• En alfabeto español equivale a reemplazar:
– la letra a, al principio alfabeto, por la letra z
– la letra b se cambia por la letra y

ñ l

l

i

l

21

22

Criptologia Básica

11

Criptologia

Dr. Roberto Gómez Cárdenas

Ejemplo Atbash

A B C D E F G H I
A B C D E F G H I

J K L M N O P Q R S T U V W X Y Z
J K L M N O P Q R S T U V W X Y Z

Z Y X W V U T S R Q P O N M L K J I H G F E D C B A

Texto claro: MENSAJE DE PRUEBA

Criptograma: NVMHZQV WV KIFVYZ

Primer ejemplo literatura: Arthur Conan

Doyle

• Conan Doyle 1859 1930 es el autor de las

aventuras de Sherlock Holmes

h l k

d

l

• Sherlock era un experto criptoanalista y le

dice a Watson:

I am the author of a trifling monograph upon the subject
in wich I analyze one hundred and sixty separate ciphers.

• Su más fomoso criptoanalisis: Adventure of the

Dancing Men

23

24

Criptologia Básica

12

Criptologia

Dr. Roberto Gómez Cárdenas

Criptosistema de Adventures Dancing Men

Segundo ejemplo: Edgar Allan Poe

• Poe (1809-1849) tenía interes en la cripotografía.
• Escribe para el Alexander Weekly Messenger de

Filadelfia desafía a los lectores diciendo que puede
resolver cualquier criptograma.

• En 1843 escribe un historia corta acerca de

criptosistemas: The Gold Bug

53++!305))6*;4826)4+.)4+);806*;48!8`60))85;]8*:+*8!83(88)5*!;
46(;88*96*?;8)*+(;485);5*!2:*+(;4956*2(5*-4)8`8*; 4069285);)6
!8)4++;1(+9;48081;8:8+1;48!85;4)485!528806*81(+9;48;(88;4(+?3
4;48)4+;161;:188;+?;

25

26

Criptologia Básica

13

Criptologia

Dr. Roberto Gómez Cárdenas

Los retos de Allan Poe

Atacando los criptosistemas

monoalfabéticos

El criptoanálisis arábe

27

28

Criptologia Básica

14

Criptologia

Dr. Roberto Gómez Cárdenas

Criptoanálisis arabe

• Estudiantes arábes capaces destruir criptosistemas.

en realidad ellos inventaron el criptoanálisis
– en realidad ellos inventaron el criptoanálisis

• Disciplinas para criptoanálisi