Manejo de claves

Teoría de la información Manejo de claves

Principios, herramientas y protocolos de criptografía Yann Frauel – Semestre 2007-1

Seguridad de un criptosistema


Todos los elementos deben ser seguros:
Algoritmo ➔ Protocolo ➔ Clave
➔



2do principio de Kerckhoffs: la seguridad no debe derivarse del secreto del algoritmo, sólo de la clave ¿Cómo medir la seguridad de una clave?

1. Teoría de la información (Claude Shannon 1948)

Teoría de la información
¿Cómo medir la cantidad de información de un mensaje?
 

Idea 1: longitud del mensaje Pero comparar:
110010101110 ➔ 439203984738
➔



Idea 2: número de bits necesarios para codificar el mensaje
binario: 1 bit/carácter ➔ decimal: 4 bits/carácter ➔ letras: 5 bits/carácter
➔

Teoría de la información¿Cómo medir la cantidad de información de un mensaje?
  

Pero no se usan todas las combinaciones posibles... Idea 3: número de bits en promedio (fraccional) Ejemplo: lanzar un dado
Lanzados 1 2 3 4 5 200 Combinaciones 6 36 216 1296 7776 4.27E+155 Bits totales 3 6 8 11 13 517 Bits/car. 3.000 3.000 2.667 2.750 2.600 2.585

Teoría de la información


¿Cómo obtener directamente el númerode bits promedio H?
5 4.5 4

Número de bits

3.5 3 2.5 2 1.5 1 0.5 0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

Número de valores posibles

H = log2(n),

n: Número de valores posibles

Teoría de la información
¿Qué pasa si no todos los valores tienen la misma probabilidad?


Ejemplo: Dado de 4 caras
p(0) = 3/4 ➔ p(1) = 1/8 ➔ p(2) =1/16 ➔ p(3) = 1/16
➔



Cambio de codificación:
➔

0→0

1 → 10

2 → 110

3 → 111



Número de bits promedio:
➔

H = 3/4 × 1 + 1/8 × 2 + 1/16 × 3 +1/16 × 3 = 11/8 = 1.38 b/c

Entropía
 

Sea una variable aleatoria X Puede tomar n valores: x1, x2... xn con probabilidades P( X = xi) = pi Se define la entropía de X:
n



HX=−

∑ pi log2  pi 
i=1



Midela cantidad de información proveida por X

Entropía


Ejemplo 1: evento equiprobable
➔ ➔ ➔

p1 = p2 = ... = pn = 1/n H(X) = log2 (n)

Volvemos a encontrar la fórmula intuitiva ➔ Es el valor máximo que se pueda encontrar para n valores


Ejemplo 2: evento seguro
➔ ➔

pi =1 y pj = 0 para j ≠ i

H(X) = 0 ➔ Es el valor mínimo que se pueda encontrar


La entropía mide laincertidumbre

Redundancia
 

Ejemplo 1: ¿Qué viene después de una letra Q? Ejemplo 2: ¿Qué significa INST NAC COMPUT CIENT? ¡Podemos reconstituir más de la mitad del mensaje! Una parte de la información de un texto normal no es necesaria, es redundante En un lenguaje natural, la entropía no es máxima:
frecuencias diferentes para diferentes letras, bigramas... ➔ reglas gramaticales,sintácticas...
➔

 



→ Los lenguajes naturales tienen mucha redundancia

Redundancia


Entropía absoluta por carácter Ha:
es la entropía máxima posible (caracteres equiprobables) ➔ para el alfabeto de 26 letras, H = 4.7 b/c a
➔



Entropía real por carácter Hr:
es la entropía calculada sobre el lenguaje real ➔ para el inglés o el español, H ~ 1.5 b/c r
➔



Redundancia porcarácter R:
➔ ➔

es la diferencia R = Ha – Hr para el inglés o el español, R ~ 3.2 b/c

Distancia de unicidad


Ataque por fuerza bruta: probamos todas las claves hasta encontrar un texto con sentido ¿Cuántos caracteres necesitamos para reconocer el texto claro sin ambigüedad? Entropía del espacio de claves:
➔





H(K) = log2 (número de claves)



Distancia de unicidad:
H K U= R

Distancia de unicidad

 

Ejemplo: substitución monoalfabética Número de claves = números de alfabetos = 26!
log 2 26! U= =28caracteres 3.2

2. Generación y almacenamiento de claves

Evolución histórica de las claves


Sin clave (sin parámetro libre): el secreto está en el algoritmo mismo
Atbash (alfabeto invertido) ➔ César (desplazamiento de 3) ➔ Tritemio...