Fundamentos de criptografía
Definiciones
Criptografía: Arte de convertir una
información totalmente legible en otra totalmente ilegible para
personas que no sean
el destinatario.
Criptoanálisis: Conjunto de técnicas
cuyo objetivo es el de desvelar la informacíon criptografiada.
Método criptográfico: Herramienta
q cifra la información y que solo descifrará la información
si tiene autorización.
Criptosistema: Cinco conjuntos (M,C,K,E,D)
M: Conjunto de todos los
posibles mensajes sin cifrar.
C: Conjunto de todos los
mensajes cifrados.
K: Conjunto de todas las
posibles llaves o claves.
E: Conjunto de las transformaciones
de cifrado: 
C: Conjunto de las transformaciones
de cifrado: 
Para cifrar se haría c
= Ek(m) k C
K, Ek C E, m C M, c C
C
Para descifrar se haria m =
Dk(c) Dk C
D
Clases de criptosistemas:
Clave pública
(simétricos): Existe una única clave que interviene en
el proceso de cifrado y descifrado. Esta clave será
privada, solo la conoceran el emisor y el receptor. El incoveniente es
trasmitir la clave.
Clave privada (asimétricos):
Dos claves, una pública y otra privada de forma que a una clave
privada le corresponde
una y solo una clave pública, además no ha de ser posible
obtener la clave privada a partir de la pública La pública
se utiliza para cifrar el mensaje, por lo tanto la tiene que conocer el
emisor, y la privada se utilizará para descifrar
el mensaje, y solo podrá conocerla el receptor.
Teoría de la información
Cantidad de información: Va asociada
con la probabilidad de que ocurra un suceso. Si el suceso és el
esperado hay poca
información, pero
si és el no esperado hay más cantidad de información.
Entropía: Es la medida de desorden
de la información. la entropía H de un sistema viene definida
por la suma de los
productos de la probabilidad
de cada suceso por su cantidad de información. El valor máximo
se produce cuando
todos los datos tienen la
misma probabilidad de aparición.
Entropía condicionada de un suceso por
otro:
Si X e Y son independientes
entonces: 
Redundancia: La entropía es un indicador
de la redundancia de la información. Definimos índice de
un lenguaje de
longitud k:
Este índice indica el
nº de bits de información q aporta cada símbolo del
mensaje de longitud k.
El índice absoluto
de un lenguaje será:
siendo m el nº se símbolos
del alfabeto de dicho lenguaje y suponiendo una distribución equiprobable.
Este índice
indica el nº maximo
de bits que se pueden codificar por cada simbolo.
La redundancia de un lenguaje
se define como: 
El índice de redundancia
será: 
Definiciones:
Cantidad de información
que contiene una variable sobre otra: 
Criptosistema seguro
de Shannon: I(C,M) = 0, lo que significa que
el hecho de conocer C no dice nada acerca de M.
Desinformación
de un criptosistema: Entropía condicionada del conjunto de los
mensajes al conjunto de los mensajes
cifrados: H(M/C) = H(M)
Distancia de unicidad:
Cantidad
mínima de mensajes cifrados que necesitamos para descubrir la clave.
Lo ideal sería
que fuese infinito.
Técnicas básicas para contruir criptosistemas:
Confusión:
Sustituir unos caracteres por otros.
Difusión: Diluir
la defundancia del lenguaje repartiendola a lo largo del texto cifrado
(transposición).
Matemática discreta
Definiciones:
Aritmética módulo
n: Cuando el resultado de una operación es mayor que n, aplicamos
a esta operación módulo n.
Congluencia módulo
n: a es congluente con b cuando hablemos de módulo n y se escribe:
Inversas: MCD(a,n)=1
-> a tiene inversa mod n, es decir, 
.
Y se dice que a y n son
primos entre si.
Conjunto reducido de
costes (CRR mod n): nº primos relativos a n (conjunto de nº
que cumplen que el m.c.d es 1).
Algoritmo de Euclides
(m.c.d): Nos permite calcular el m.c.d de 2 nº.
Si m | a y m | b entonces m | a mod b
siendo | = divide
Algoritmo:
g0=a
g1=b
while (g1 != 0) {
x=g0 % g1
g0=g1
g1=x
}
Funcion de Euler:
nº de elementos de CRR
siendo pi los factores primos de n y ei su multiplicidad
Esto es un ejemplo: 
Teorema: si mcd(a,n)=1
-> 
. Por ello podremos calcular inversas:
Algoritmos
Algoritmo extendido de
Euler: Se utiliza para el calculo de la inversa.
Algoritmo:
e.e(n,a)
g0=n
g1=a
u0=1
u1=0
v0=0
v1=1
i=1
while (gi != 0) {
i = gi-1 % gi
ui + 1 = ui - 1 - c * ui
vi + 1 = vi - 1 - c * vi
i++
}
Algoritmo de exponenciación
rápida: La forma de representar un nº en binario es la
siguiente:
El
nº de bits de un nº és el log2(nº). En este
algoritmo el nº máximo de iteraciones será log2(b).
Algoritmo:
z=b
x=a
r=1
while (z > 0) {
if (z % 1 == 1)
r = r * x
x = x * x
z = z / 2
}
Algoritmo de Lehmann:
Se utiliza para saber si un nº es primo y consiste en lo siguiente:
Escogemos un nº aleatorio a tal q a < p
Calculamos 
Si b<>1 (mod p) y b<>-1 (mod p), p no es primo
Para
generar un nº primo haremos:
Generamos un nº aleatorio con las mismas cifras que queremos que tenga
nuestro nº primo.
Poner el bit de mayor y menor peso de este nº a 1, asi conseguiremos
que sea impar, como todos los primos.
Cogemos una tabla pequeña de nº primos y dividimos por estos
el nº generado (primos menores de 2000).
Se aplica el test de Lehmann un nº razonable de veces (10 a 20 veces).
Si tras el test obtenemos que no es un nº primo, incrementamos el
nº en 2 unidades y repetimos el paso 2.
Primos fuertes: P
y Q son primos fuertes si se cumple lo siguiente:
m.c.d(p-1,q-1) es pequeño.
p-1 y q-1, tienen algun factor f', q' muy grande.
p'-1 y q'-1, tienen algun factor primo muy grande.
p'+1 y q'+1, tienen algun factor primo muy grande.
Criptografía clásica
Algunos de los primeros algoritmos
criptográficos fueron:
César:
fue utilizado por Julio César. Consiste en sumar 3 al orden de cada
una de las letras, de forma que la
A?D,B?E, etc. Para descifrar bastará con restar 3 al orden. El algoritmo
es generalizable para un
desplazamiento de n posiciones. La clave será n.
Vigènere:
Se basa en la misma filosofía de sustitución que el método
de César, con la diferencia de que la clave está
formada por un conjunto de desplazamientos (frente a un único desplazamiento
en César). El primer carácter del
mensaje se desplazará utilizando la primera clave, el segundo utilizando
la segunda y así cíclicamente.
Escitalo:
se trata de un método de transposición muy antiguo. Consiste
en enrollar una tira de papel alrededor de un
bastón de un diámetro determinado. El mensaje se escribe
longitudinalmente y al desenrollarlo éste queda cifrado.
Se necesitará un bastón de las mismas dimensiones para poder
descifrar el mensaje. La clave es el grosor del
bastón.
Criptografía actual
Clave privada:
Redes
Freistel: La red de Freistel es una estructura de cifrado empleada
en muchos algoritmos. Presenta la interesante
característica de ser reversible, es decir, de poder descifrar lo
cifrado utilizando la misma estructura con tan solo
invertir el orden de las claves k.
La estructura de una Red Freistel típica es la siguiente:
L y M son las dos partes en que se divide el mensaje a cifrar.
Algoritmo
DES (Data Encryption Standart): Es un algoritmo por bloques, trabaja
con bloques de 8 bits para la
entrada y emplea claves de 8 bits aunque 1 bit es utilizado para la paridad.
Cumple dos propiedades:
Se puede implementar por puertas lógicas.
El conocimiento del texto cifrado no aporta información del texto
original.
Un método de cifrado por bloques es el siguiente:
CBC (Cipher Book Chaining mode): En éste método cada
bloque cifrado se realimenta con una operación
XOR al bloque siguiente para a continuación cifrarlo. Su esquema
de funcionamiento para el cifrado y el
descifrado es el siguiente:
La principal ventaja es que los bloques iguales ya no se cifrarán
de la misma forma (salvo que los primeros n
bloques de dos mensajes distintos sean iguales; esto se soluciona fácilmente
introduciendo al comienzo del
mensaje un bloque con información aleatoria). Si se produjese un
error en la transmisión, éste sólo afectaría
a
un total de dos bloques consecutivos.
Esquema
del DES:
Li = Ri-1
Ri = Li -1 XOR f(R1-i,Ki)
Para que este algoritmo sea efectivo se aplica varias veces, en este caso
se aplica 16 veces.
El DES no tiene estructura de grupo: esto consiste en que si tengo dos
claves y se las aplico, aparece otra
que és la combinación de ambas.
El DES utiliza 8 cajas de 6x4 (S-BOX).
Asi, el esquema general del DES será:
Clave pública:
Se
utilizan 2 claves: una privada y otra pública.
Los algoritmos pueden ser reversibles, se puede cifrar y descifrar con
la clave privada o pública.
Lo que se cifra con una clave, se descifra con la otra y solo con la otra.
Dada una clave (privada o pública) és imposible sacar la
otra.
Hay varias opciones para cifrar y descifrar:
Para comunicarse con el resto del mundo:
Para obtener autenticidad:
Para conseguir tanto secreto como autenticidad:
Algoritmo
RSA: Es uno de los algoritmos asimétricos más sencillos
de implementar. Pese a ello es unas 1000 veces
más lento que el DES. Sus especificaciones las podemos encontrar
en el documento PKCS#1 de RSA
Laboratorios.
Una clave RSA de 512 bits viene ofrecer la misma seguridad que una clave
DES de 56 bits ?clave débil. A partir
de 786 bits de clave RSA ya se comienza a considerar seguro, aunque hoy
en día ya comienzan a ser típicas
claves de 1024 o 2048 bits.
Se escogen dos número primos y secretos, p y q.
n = p x q, n debe ser público ( de n no podemos sacar p y q si n
és un nº muy grande).
De p y q cojo (p-1)(q-1)
Se coge un nº e que será 3 o 65535 que no compartiran ningun
factor con (p-1) y (q-1), si no comparte
ningun factor, podemos afirmar que existe la inversa (d).
e x d = 1 en mod (p-1)(q-1) --> e x d = (p-1)(q-1) +1
c = me en módulo n, cd en módulo n
= (me)d = med = m(p-1)(q-1)+1
= m x m(p-1)(q-1) = m x m0(n) .
Si (m < p y m < q) entonces m y n son primos entre si y m0(n)
=1,
por lo tanto he obtenido m.
Clave secreta = (d,n).
Clave pública = (e,n).
Definiciones
básicas:
Clave de sesión: número aleatorio que el emisor genera
a modo de clave privada. Tradicionalmente se utiliza en
criptografía de clave pública la criptografía de clave
privada con el objeto de reducir el coste computacional. De
esta forma únicamente se utiliza criptografía de clave pública
para la autentificación y el cifrado de esta clave de
sesión, continuando el resto de la comunicación mediante
criptografía de clave privada.
Función de resumen (hash): función matemática
que a partir de un mensaje de longitud arbitraria proporciona un
mensaje de tamaño fijo. Dado un mensaje y su resumen, cualquier
pequeño cambio en el mensaje (alteración del
contenido o de la posición, por ejemplo) produce un gran cambio
en el resultado hash. Dado un resumen, ha de
ser extremadamente difícil encontrar un mensaje que genere ese resumen.
Ejemplos de funciones hash son: MD5,
SHA1, SHA2.
Métodos
para la autentificación de las claves públicas:
Para cerciorarnos de que una clave pública pertenece efectivamente
a quién afirma poseerla tenemos dos grandes
posibilidades:
Contacto directo con la persona, por ejemplo en persona o por telefono.
Confianza en un tercero que acredite la pertenencia (notario): autoridades
certificadoras.
Otro problema és saber si las claves públicas de A y B son
realmente de A y B, para solucionar esto tenemos
dos soluciones: orizontales y verticales.
Horizontales: Si queremos conseguir la clave de C pero no la conocemos,
se la pedimos a B que el si que la
conoce, B nos debera mandar firmada la llave de C, con esto conseguiremos
autenticidad de B. A esto se
le llama conseguir claves por intermediarios.
Verticales: Consiste en introducir una 3ª persona de confianza (notario)
y que se encuentra en una escala
superior.
Certificado x509:
El estándar X509 es el de utilización más extendida
para la certificación de personas y entidades.
Los certificados X509 son objetos públicos.
Los campos más importantes de un certificado X509 son los siguientes:
Estructura del x509:
DN Subject: DN del certificado.
DN Issuer: DN de la autoridad emisora del certificado.
Clave pública del Subject.
Versión del certificado.
Número de serie del certificado (único dentro del emisor).
Fecha inicio y fecha de caducidad del certificado.
Algoritmos criptográficos utilizados.
Firma digital del emisor del certificado.
El campo DN (Distinguished Name) está a su vez formado por varios
campos. Los más habituales son:
Common Name (CN): nombre de la persona o entidad.
Email Address (EA): dirección de correo electrónico.
Organization Name (ON): nombre de la empresa o entidad.
Organizational Unit (OU): nombre de la sección o departamento dentro
de la empresa o entidad.
Country (C): código de dos letras del país según la
clasificación de Naciones Unidas.
Locality (L): nombre de la localidad.
State (ST): nombre del estado o provincia.
Los certificados de las autoridades certificadoras (CA) los pueden firmar
otras CA o pueden estar firmados por
sí misma (autofirmado). Por tanto cualquier CA podrá certificar
a personas, entidades u otras CA,
indistintamente.
Obtención de un certificado:
El principal problema de los certificados es su obtención e instalación.
Para obtenerlos la autoridad
certificadora debería de asegurarse de forma fiable de que quién
le pide el certificado y quién lo recibe es la
misma persona o entidad. Para instalarlos, deberíamos de cerciorarnos
de que podemos confiar tanto en la
autoridad certificadora como del propietario del mismo.
Los pasos para la obtención de un certificado son los siguientes:
Decidir los datos personales que aparecerán en el certificado.
Decidir el algoritmo de clave pública (normalmente será el
RSA.
Generar el par de llaves pública-privada: el estándar indica
que los debería de generar el interesado. La
legislación española reconoce el derecho del usuario a generar
su propia clave privada. En cualquier caso
la autoridad certificadora jamás debería de conocer la clave
privada del certificado, de otra forma podrá
descifrar nuestros mensajes e incluso suplantar nuestra identidad.
Petición del certificado a la autoridad certificadora. El PKCS#10
de RSA Laboratorios define la estructura
del Certificate Request (CR). El procedimiento es el siguiente:
El usuario genera el par de claves. Con ellas firma el CR (que ya estará
completado con sus datos).
De esta forma la autoridad certificadora sabrá que el poseedor de
la clave pública es quien ha
fabricado y firmado el CR.
Tras la recepción del CR la autoridad decide si emitir o no el certificado.
Si decide certificar, emitirá
un documento de carácter legal especificando qué se certifica.
Una vez todo esté correcto la CA entregará al cliente el
certificado, bien de forma personal, o bien a
través de la web u otros medios.
En el PKCS#12 se propone un objeto destinado al transporte de información
personal protegido por
contraseña.
Utilización de los certificados:
Para el trabajo cotidiano con certificados se utilizan dos bases de datos
de certificados:
Base de datos de autoridades certificadoras.
Base de datos de certificados.
Los certificados apuntarán a sus autoridades certificadoras.
Además existen otras dos bases de datos.
Base de datos de certificados propios.
Base de datos de llaves privadas.
Cada uno de los certificados propios tendrá una llave privada.
Revocación de los certificados:
Es fundamental especialmente si la clave privada ha sido comprometida.
En la base de datos de la autoridad certificadora se marca el certificado
afectado como revocado.
Ahora el problema reside en la comprobación de si un certificado
dado se encuentra o no revocado.
El X509 propone los Certificate Revocated List (CRL) como método
de comprobación de revocaciones. Se
trata de un lista emitida por la autoridad certificadora que contiene los
números de serie de aquellos
certificados que han sido revocados. Esta lista estará firmada por
la propia CA con el objeto de demostrar su
autenticidad.
El inconveniente de este método es la consulta de la CRL ya que
éstas se publican de forma periódica.
Reglas BER y DER:
Con el objeto de permitir la transferencia de certificados entre cualquier
tipo de arquitectura y máquina se han
normalizado la forma de codificación de los datos binarios.
Así la organización ISO definió el estándar
BER (Binary Encoding Rules) que se base en el formato de
estructuras de datos ASN1 (también del ISO).
Asimismo se definió el DER (Distinguished Encoding Rules) como subconjunto
reducido del BER.
Para la transferencia en texto plano de los certificados (principalmente
para su utilización a través del correo
electrónico) se definió el formato PEM (Private Enhaced Mail)
el cuál es un objeto DER codificado en MIME.