Introduccion Criptografia LFSR 20 21 ot PDF

Preview

Summary

ETSETB: ENTELF. [email protected] UPCIntroducción a la Criptografía 1TRANSMISIÓN DE DATOSINTRODUCCIÓN A LACRIPTOGRAFÍAFRANCISCO J. RICO, OCTUBRE 2020ETSETB: ENTELF. [email protected] UPCIntroducción a la Criptografía 2Introducción####### ꞏ Criptología :Criptografía y Criptoanálisis Criptografía : Comuni...

Description

F.J. Rico [email protected]

UPC

ETSETB: ENTEL

TRANSMISIÓN DE DATOS

INTRODUCCIÓN A LA CRIPTOGRAFÍA FRANCISCO J. RICO, OCTUBRE 2020

F.J. Rico [email protected]

Introducción a la Criptografía

UPC

1

Introducción

ꞏ Criptología:Criptografía y Criptoanálisis – Criptografía: Comunicaciones en un

ETSETB: ENTEL

ambiente:

• Hostil • Vulnerable • Desconfianza mutua entre los comunicantes

– Criptoanálisis: Violación de los sistemas criptográficos Introducción a la Criptografía

2

1

F.J. Rico [email protected]

UPC

Impacto de computación cuántica: el algoritmo de Grover divide por 2 la longitud de la clave

La red de minería de Bitcoin tiene 115 veces esa capacidad (28/09/2020)

Órdenes de Magnitud

ꞏ Ejemplo. Potencia de cálculo:

10 18 IPS

ETSETB: ENTEL

ꞏ Clave 128 bits: diez billones de años 1038 bytes

• Tiempo: • Memoria:

ꞏ Clave 256 bits: • Tiempo: • Memoria:

4 1069 años 1077 bytes

Toda la materia de licúe: Átomos en el Universo:

1064(2212 )años 1077(2256 )

F.J. Rico [email protected]

Introducción a la Criptografía

ETSETB: ENTEL

UPC

3

Criptoanálisis: un primer contacto

ꞏ Tipología de los ataques: – Texto Cifrado Conocido – Parejas Texto Claro-Texto Cifrado – Texto Claro Escogido (Fijo y Adaptativo) – Texto Cifrado Escogido – “ La Clave o La Vida”

Introducción a la Criptografía

4

2

F.J. Rico [email protected]

UPC

Objetivos Criptoanalíticos

ꞏ Ruptura Total del Algoritmo

Puede descifrarse cualquier criptograma cifrado con cualquier clave

ꞏ Ruptura Total de la Clave ETSETB: ENTEL

Se encuentra la clave de cifrado

ꞏ Ruptura Parcial

Se descifra un criptograma en concreto (sin hallar la clave)

ꞏ Información Parcial

Se obtiene algún conocimiento sobre el texto claro a partir del criptograma

F.J. Rico [email protected]

Introducción a la Criptografía

ETSETB: ENTEL

UPC

5

Seguridad de un Algoritmo

ꞏ Seguridad Incondicional

P(M|C) =

P(M)

Vernam

ꞏ Seguridad Computacional Demostrable RSA ꞏ Seguridad Probable DES, AES ꞏ Seguridad Condicional Vigenère, Código Navajo Introducción a la Criptografía

6

3

F.J. Rico [email protected]

ETSETB: ENTEL

UPC

Nivel de Seguridad

2 Recetas

(¿ de Perogrullo?):

ꞏ El tiempo de cobertura ha de ser superior al periodo de validez de la información ꞏ El coste de la seguridad ha de ser inferior al perjuicio de la violación

F.J. Rico [email protected]

Introducción a la Criptografía

ETSETB: ENTEL

UPC

7

Escenario de Ataques (I)

ꞏ Identificación del Enemigo ꞏ Hipótesis acerca de la Capacidad de Acción del Enemigo ꞏ Protección frente a esos Ataques

Introducción a la Criptografía

8

4

F.J. Rico [email protected]

Los Personajes

ETSETB: ENTEL

UPC

Comunicante Desprotegido

Enemigo Operativo

Comunicante Protegido Enemigo Contrarrestado

F.J. Rico [email protected]

Introducción a la Criptografía

ETSETB: ENTEL

UPC

9

Escenario de Ataques (II)

ꞏ Ataque Pasivo Alicia

Blas Carlos

Alicia

Blas Carlos Introducción a la Criptografía

10

5

F.J. Rico [email protected]

UPC

Escenario de Ataques (III)

ꞏ Ataque Activo

ETSETB: ENTEL

Alicia

Blas Carlos

Alicia

Blas Carlos

F.J. Rico [email protected]

Introducción a la Criptografía

ETSETB: ENTEL

UPC

11

Servicios de Seguridad

ꞏ ꞏ ꞏ ꞏ

Confidencialidad Autenticidad Verificabilidad (Firma Digital) Coordenabilidad (Esteganografía)

Introducción a la Criptografía

12

6

F.J. Rico [email protected]

Ejemplo de esteganografia: steghide

ETSETB: ENTEL

UPC

F.J. Rico [email protected]

Introducción a la Criptografía

UPC

13

Ejemplo de esteganografia: steghide >steghide embed -cf foto-original_small.JPG -ef Enigma.pdf Anotar salvoconducto: [pocacosamariposa] Re-ingresar salvoconducto: [pocacosamariposa] adjuntando "Enigma.pdf" en "foto-original_small.JPG"... hecho >steghide info foto-original_small.JPG "foto-original_small.JPG": formato: jpeg

ETSETB: ENTEL

capacidad: 119,8 KB ¿Intenta informarse sobre los datos adjuntos? (s/n) s Anotar salvoconducto: [pocacosamariposa] archivo adjunto "Enigma.pdf": tamaño: 31,0 KB encriptado: rijndael-128, cbc compactado: si

>steghide extract -sf foto-original_small.JPG Anotar salvoconducto: ya existe el archivo "Enigma.pdf". ¿lo sobreescribo? (s/n) s anoté los datos extraídos en "Enigma.pdf".

Introducción a la Criptografía

14

7

F.J. Rico [email protected]

Fichero protegido con steghide: Enigma.pdf

ETSETB: ENTEL

UPC

F.J. Rico [email protected]

Introducción a la Criptografía

15

No se puede Detectar Puede Contrarrestarse

Ataque Pasivo

ꞏ Confidencialidad

UPC

ETSETB: ENTEL

Alicia

Blas Carlos

ꞏ Confidencialidad y verificabilidad

Alicia

Blas Carlos Introducción a la Criptografía

16

8

F.J. Rico [email protected]

No se puede Evitar Puede Detectarse

Ataque Activo

ꞏ Confidencialidad y Autenticidad

UPC

ETSETB: ENTEL

Alicia

Blas Carlos

ꞏ Confidencialidad y Verificabilidad Alicia

Blas Carlos 17

F.J. Rico [email protected]

Introducción a la Criptografía

UPC

ETSETB: ENTEL

CRIPTOGRAFÍA CLÁSICA

Introducción a la Criptografía

18

9

F.J. Rico [email protected]

UPC

Criptografía Clásica

ꞏ C. Clásica versus C. Moderna

ETSETB: ENTEL

– Único Secreto: La Clave

ꞏ Dos técnicas básicas: – Sustitución: Confusión – Transposición:Difusión

F.J. Rico [email protected]

Introducción a la Criptografía

19

Cifrado de César

UPC

xbp wvalza jhwlyl jhwpha

ETSETB: ENTEL

qui potest capere capiat

CLAVE: 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 h i j k l m n o p q r s t u v w x y z a b c d e f g Introducción a la Criptografía

20

10

F.J. Rico [email protected]

Método de Vigenère

UPC

E+H=L

ETSETB: ENTEL

L

J. Rico [email protected]

Introducción a la Criptografía

21

Método de Vigenère (ejemplo)

E L M A R T E S E N T R A R E M O S E N L A P L A Z A Y T O M A R E M O S L A F O R T A L E Z A H I N O J O H I N O J O H I N O J O H I N O J O H I N O J O H I N O J O H I N O J O H I N O J O L

T Z O A H L A R B C F H Z R A X G L V Y O Y Z H H N M C C T I

UPC

E S V C Z T N T X F A I Y S I O

ꞏ Texto Aleatorio:

B: ENTEL

P (coincidenc ias ) 

1 1 26  3.84% 26 26

ꞏ Texto Castellano:

L 4,2% O 4,2% I 4,2% S 2,1% Y 0,0% I 6,3% A

2 P (coincidenc ias )  p ( A ) 2  p (B ) 2    p (Z )2  cast  6.8% T L O I S Y I

Z T L O I S Y

O A H Z O A T Z O L T Z O L T I O L S I O

L H A O Z T L

A L H A O Z T

R B A R L A H L A H O A Z O

C F H B C F R B C A R B L A R H L A A H L

Z R A H Z R F H Z C F H B C F R B C A R B

X A R Z H F C

G X A R Z H F

L G X A R Z H

V L G X A R Z

Y V L G X A R

O Y V L G X A

Y Z O Y Y O V Y L V G L X G

H Z Y O Y V L

H H Z Y O Y V

N M H N H H Z H Y Z O Y Y O

C M N H H Z Y

C C M N H H Z

T C C M N H H

I T C C M N H

E I T C C M N

S E I T C C M

V S E I T C C

C V S E I T C

Z T C Z V C S V E S I E T I

N T Z C V S E

T N T Z C V S

X T N T Z C V

F X T N T Z C

A F X T N T Z

I Y A I F A X F T X N T T N

Introducción a la Criptografía

S Y I A F X T

I O S I Y S I Y A I F A X F

22

11

F.J. Rico [email protected]

Criptoanálisis de Vigenére H H N M C C

T I E S V C

Z T N T X F

A I Y S I O

H I N O X C

B I J O P Y D

C J K P Q Z E

D K L Q R A F

E L M R S B G

L T Z O A H

L A R B C F

H Z R A X G

H

I

N O X C

L H E

T Z O A H L A R B C F H Z R A X G L V Y O Y Z H H N M C C T I E S V C Z T N T X F A I Y S I I N O X C H I N O X C H I N O X C H I N O X C H I N O X C H I N O X C H I N O X C H I N O X L M A D F E S E N F D A R E M A E E N L A B X A Z A Y F A M A R E Y A S L A F A D T A L E L

ETSETB: ENTE

L V Y O Y Z

A H I N O X C

L T R Y S F

T U V WX

F G H I

J

ꞏ La única palabra que empieza por “hino” y tiene seis letras es HINOJO ꞏ La Clave debe ser ALEATORIA

F.J. Rico [email protected]

Introducción a la Criptografía

UPC

23

Vernam

ꞏ ¿Por qué no es el único que se usa? – Requisitos poco prácticos en redes abiertas

ETSETB: ENTEL

ꞏ Requisitos: – Clave aleatoria – De un sólo uso – Tan larga como el mensaje Ejemplo: Mensaje:

000100100100100100100

Clave:

001011111010001000011

Criptograma: 001111011110101100111 Introducción a la Criptografía

24

12

F.J. Rico [email protected]

Método de Playfair E N U N L U G A R D E L A M A N C H A

ETSETB: ENTEL

UPC

G

N

T

A

J

P

I

F

O W/Ñ

B

H

Y

R

E

C

M

U X/Z

Q

D

S

V

K

L

C G C A V Z N J H V Z Q T U J T D C J U

F.J. Rico [email protected]

Introducción a la Criptografía

UPC

25

Métodos de Transposición

E

L

C

A

M ELCAMINOESTASEMBRADODETRAMPAS

I

N

O

E

S

ETSETB: ENTEL

EITBDMLNAREPCOSATAAEEDRSMSMOAX

T

A

S

E

M ELCAMINOESTASEMBRADODETRAMPAS

B

R

A

D

O

D

E

T

R

A

M

P

A

S

X Introducción a la Criptografía

26

13

F.J. Rico [email protected]

Criptografía Clásica Sistemas Clásicos

UPC

ETSETB: ENTEL

Sustitución

Transposición

Escítalo MonoAlfabética

Monográmica

Poligrámica

César

Playfair

Polialfabética

Periódica

Vigenère

Aperiódica

Vernam 27

F.J. Rico [email protected]

Introducción a la Criptografía

UPC

ETSETB: ENTEL

CRIPTOGRAFÍA MODERNA ALGORITMOS SIMÉTRICOS

Introducción a la Criptografía

28

14

F.J. Rico [email protected]

UPC

Criptografía Moderna

ꞏ El único secreto debe ser la clave. – Existen tendencias “involucionistas”

ETSETB: ENTEL

ꞏ Los algoritmos deben “rodarse”.

Deben probarse

– Demasiados algoritmos “milagrosos” – Demasiados “expertos”

ꞏ Punto de inflexión importante: – Algoritmos Asimétricos o de Clave Pública

F.J. Rico [email protected]

Introducción a la Criptografía

UPC

29

Algoritmos Simétricos y Asimétricos

ꞏ Simétricos

ETSETB: ENTEL

– Una única clave para cifrar y descifrar – Ventajas: Rapidez – Inconvenientes: Gestión de Claves

ꞏ Asimétricos (dos claves) – Una clave de cifrado (pública) – Otra de descifrado (secreta) – Ventajas: Gestión de Claves – Desventajas: Lentitud Introducción a la Criptografía

30

15

F.J. Rico [email protected]

UPC

Algoritmos Simétricos

ꞏ Dos filosofías de funcionamiento: Cifrado en Flujo Cifrado en Bloque

ETSETB: ENTEL

m1

c1

m2

c2

Sin Memoria

mn

Con Memoria

mi

K

cm

K

ci  E Z  mi  Z  f (K ,i)

  1,,mn  C  c 1,,cn  E K m

Introducción a la Criptografía

F.J. Rico [email protected]

31

Cifrado en Flujo Síncrono Iv

UPC

Cifrador en flujo

ETSETB: ENTEL

ci

mi

Iv Cifrador

K

en flujo

ci

K

mi

– No propaga errores de transmisión – Si se pierde un bit es necesario reiniciar la comunicación. Introducción a la Criptografía

32

16

F.J. Rico [email protected]

Cif. Flujo Autosincronizante

UPC

ETSETB: ENTEL

K

mi

Registro

Registro

Cifrador

Cifrador

en flujo

en flujo

ci

K

mi

– Propaga errores de transmisión – Si se pierde un bit la comunicación se autosincroniza

F.J. Rico [email protected]

Introducción a la Criptografía

ETSETB: ENTEL

UPC

33

Características Deseables de la Fuente Pseudoaleatoria

ꞏ Características Estadísticas Análogas a las Fuentes Aleatorias. ꞏ Reproducibilidad en en Receptor (Determinismo) ꞏ Realización Sencilla y Económica

LFSR Introducción a la Criptografía

34

17

F.J. Rico [email protected]

Registros de Desplazamiento Linealmente Realimentados (topología Galois)

ꞏ Topología

UPC

s0

ETSETB: ENTEL

c0

s1

s2 c2

c1

s3

s4 c4

c3

c5

ꞏ Ecuaciones de Estado

si (n) = s4(n-1)ci+si-1 (n-1)

F.J. Rico [email protected]

Introducción a la Criptografía

Descripción Polinómica s0

UPC

35

c0

s1 c1

s2 c2

s3

s4 c4

c3

c5

ETSETB: ENTEL

ꞏ Polinomio de Conexiones

C(D)= c0+c1D1 +...+c5D5 ꞏ Polinomio de Estado

S(D)= s0+s1D1 +...+s4D4 Introducción a la Criptografía

36

18

O b se rva c io ne s  LO S C O EFIC IENTES DE A MBO S

PO LINO MIO S SATISFA C EN Q UE

SI,CI  0,1}  LA SUMA SE REALIZA MÓ DULO 2 (XO R)

0+0=0 0+1=1 1+0=1 1+1=0 (1 = -1)

Eje m p lo (Ite ra c ió n Nº 0) 0

0

1 c2

c0

0

1

c3

c5

Sucesión de Estados: 0

0

1

0

1

19

Eje m p lo (Ite ra c ió n Nº 1) 1

0

c0

1 c2

0

0

c3

c5

Sucesión de Estados: 0

0

1

0

1

1

0

1

0

0

Eje m p lo (Ite ra c ió n Nº 2) 0

1

0 c2

c0

1

0

c3

c5

Sucesión de Estados: 0

0

1

0

1

1

0

1

0

0

0

1

0

1

0

20

Visió n Po linó m ic a S

(D)= D S(N-1) (D) MÓD C(D)

(N)

DEMO STRAC IÓ N L

SL-1D +

SL-2D

L-1

L

+...+ L-1

SL-1 D + SL-1 CL-1D +...+ (SL-1 CL-1+SL-2)D SI

(N)

(N-1)

= SL-1

L-1

L

S0 D

L1

D +CL-1D +...+C1D+1

SL-1 C1 D + SL-1

SL-1

+..+ (SL-1 C1+S0)D+ SL-1

(N-1)

CI+SI-1

Eje m p lo (Ite ra c ió n Nº 3) 0

0

c0

1 c2

0

1

c3

c5

Sucesión de Estados:

Repetición

0

0

1

0

1

1

0

1

0

0

0

1

0

1

0

0

0

1

0

1

21

Esta d o NULO 0 c0

c1

0

0 c2

0 c3

0

c4

c5

Sucesión de Estados: 0

0

0

0

0

0

0

0

0

0

O b se rva c io ne s  El siste m a e s C íc lic o (Pe río d o 3 e n

e ste e je mp lo )  El Esta do Nulo e s ABSO RBENTE  El Pe ríd o Má xim o e s

25 -1

22

F.J. Rico [email protected]

ETSETB: ENTEL

UPC