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.

Ii=-log2(P(xi))

    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: H(X//Y)=H(X)

    Redundancia: La entropía es un indicador de la redundancia de la información. Definimos índice de un lenguaje de
        longitud k:

rk=Hk(M)/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á:
R=log2(m)
        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: D=R-r

        El índice de redundancia será: I=D/r

    Definiciones:
        Cantidad de información que contiene una variable sobre otra: I(X,I)=H(Y)-H(Y/X)
        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 -> mcd(a,n)=1->a^-1==1(mod n) . 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 b=a^((p-1)/2)(mod p)
            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.