Tema 2:

Criptografía

Podemos decir que la criptografia es "el arte" de ocultar la información, se basa en una serie de metodos para transformar la información en otra que no puedan entender unos ojos ajenos.

El criptoanalisis es descifrar la información de forma "no licita" (sin saber los algoritmos, o las claves, etc)

Para definir un metodo criptografico lo podemos hacer como una herramienta capaz de transformar una información en otra inentendible, y además esa transformación ha de ser inversible completamente si se tiene la autorización.

El mecanismo para establecer el proceso de cifrado y descifrado de forma autorizada requiere el elemento denominado clave. El secreto de esta clave es lo que da la seguridad al sistema.
 

Criptosistema

Un criptosistema es una quintupla formada por los cinco elementos denominados como (M C K E D)
           M.- Conjunto de todos los posibles mensajes en claro
           C.- Conjunto de todos los posibles mensajes cifrados
           k.- Conjunto de todas las posibles claves
           E.- Conjunto de todas las posibles transformaciones de cifrado
           D.- Conjunto de todas las posibles transformaciones de descifrado

Un criptosistema debe cumplir que la función de descifrado con una clave cualquiera de un mensaje cifrado y al  aplicarle el descifrado con la clave vuelve a dar el anterior.

Existen dos grandes grupos de criptosistemas:
           De clave privada: Son los más sencillos y antiguos. Existe una unica clave para cifrar y descifrar (clave privada) y son más rapidos y faciles de implementar. Se les denomina simetricos.
           De clave publica: Existen dos claves, una publica y la otra privada (se les denomina criptosistemas asimetricos). De estas dos claves una se usa para cifrar y la otra para descifrar lo que se ha cifrado con la primera, por eso dada una clave privada existe una y solo una publica, es por esto que si se cifra con la privada solo se puede descifrar con la publica, garantizandose la autenticidad. El problema de estos algoritmos es que son muy costosos de implementar y tienen un coste algoritmico muy grande.
 

Concepto de Entropia

Entropia: Es la medida del desorden, en un sistema hay mucha entropia cuando existe mucha imprevisibilidad (es  una magnitud que va relacionada con el deterioro de los sistemas).

La entropia de un sistema es  (logaritmo en base 2). En un experimento donde todas las posibilidades son equiprobables, la entropia es maxima.
Ejemplo para un dado:

La entropia en dos variables:
        P(xi,yj)
        P(xi/yj) = P(xi,yj) / P(yj)


                                                               

Entonces para la entropia total:
        H(x,y) = H(x) + H(y/x)

Y si analizamos las formulas nos encontramos que H(x/y) <= H(x) por lo que si x e y son independientes H(x/y) = H(x).

Cantidad de información que una variable contiene sobre otra:
        I(x,y) = H(y) - H(y/x)

Teniendo en cuenta esta formula, se define Criptosistema seguro de Shannon  a aquel que cumple que I(C,M)= 0, esto es alcanzable de forma dificil y tambien se denomina criptosistema ideal.
La formula significa que por el hecho de conocer C, no sabemos nada sobre M, y para conseguir esto se necesita que el cardinal del conjunto de claves ha de ser por lo menos igual que el cardinal de mensajes.

Un criptosistema seguro de Shannon tambien es, si H(M) = H(M / C) .
Desinformación de un sistema criptografico es H(M / C).
La distancia de ciclidad se define como la longitud minima de mensaje cifrado que lleva H(K / C) a cero.

Las tecnicas basicas para ocultar la redundancia son:
    La confusion: Intentar ocultar la relacion directa entre el texto plano y el cifrado, y el mecanismo mas simple es la sustitucion (sustituir un simbolo del texto plano por otro simbolo).
    La difusion: Consiste en diluir la redundancia del texto por todo el texto cifrado, y se consigue normalmente por transposicion.
 

Matematica Discreta

Aritmetica Modular: Es la aritmetica que trabaja con conjuntos de numeros restringidos a un numero determinado.
Por ejemplo, dados a, b,n E N
diremos que a c b (mod n) (a congruente b en aritmetica modular con modulo n)
                 si a = b + Kn

Si  m.c.d.(a , n) = 1 -> a / tiene inversa modulo n
existe a-1      a * a-1 = 1 (mod n)
Se dice que dos numeros que cumplen esta propiedad, son primos entre si.

Dado un numero n denominaremos conjunto de residuos a:
        CR = {1, 2, ..., n-1}
Y conjunto reducido de residuos a los primos entre si:
        CRR = {1, 5, 7, 11} (para n = 12)
El cardinal de CRR = función de Euler 

donde 
Esta forma de calcular el cardinal implica conocer la descomposicion en factores primos, que se puede conseguir por la exponenciacion rapida.
La exponenciación rapida parte de: b = 20b0 + 21b1  + 22b2 + ... + 2nbn  <- b en binario
ab = a 20b0  + 21b1  + 22b2 + ... + 2nbn  = a20b0 + a21b1 + a22b2 + ... + a2nbn = 

El algoritmo queda:

exp_r(a, b)
    z = b;
    x = a;
    r = 1;
    mientras (z > 0) {
        si z % r = 1
            r = r * x;
        x = x * x;
        z = z / 2; }
    r;

Numeros Primos:
Los numeros primos son aquellos que solo tienen la posibilidad de ser divididos por 1 u por ellos mismos. No existe ninguna formula que permita crear los numeros primos ni ninguna forma razonable de descomponer un numero en sus factores primos, la unica forma es por fuerza bruta.
Para saber si un numero es primo sin tener que descomponerlo, se pueden utilizar algunos test que dan unas probabilidades que lo sea:

Test de Lennan:
Se elige un numero P
y     a < P

        b =   a(p - 1) / 2 mod P

Si b != 1 y b != P - 1 -> El numero no es primo, en caso contrario hay un 50% de probabilidad de que lo sea.

Para conseguir un numero primo grande, se busca un numero aleatorio (grande ) y se divide por una tabla de numeros primos prefijada (por ejemplo los primos hasta 2000), y se le pasa el test de Lenan varias veces, así, si da positivo, hay muchas posibilidades que sea primo

Un numero es aleatorio si es completamente impredecible, para conseguirlo en C se puede: randomize(time(NULL)).

Se definen los primos fuertes cuando cumplen: