Yo estoy todavía trabajando en la parte de estadística, es bastante extenso y quiero que lo entiendan, ya que sirve mucho para descubrir patrones en cosas que deberían ser aleatorias.

Capítulo VI (Final!). Este capítulo fue escrito mientras se escuchaba: The Beatles (2009 Remastered discography).

Buenas! Hoy les traigo la última entrega del taller de Criptografía Asimétrica. La idea es que cuando todos ya estén listos, nos pongamos a crear un algoritmo nuevo. Avisen entonces cuando ya estén, asi podemos ponernos.
Esta entrega va a ser distinta de las demás, estuve trabajando en un código que hace diversos testeos en generadores pseudoaleatorios, con el fin de encontrar fallas en los mismos. Para que un PRNG sea seguro para ser usado en criptografía, debe cumplir con las siguientes normas:
- Tener períodos largos.
- La salida debe tener una distribución uniforme.
- Los espacios entre ciertos valores, no corresponden a los de una distribución aleatoria.
- No debe haber correlación entre los valores sucesivos de la salida.
El programa que creé, prueba todas menos la última, que como vamos a ver más adelante, es una de las más importantes.

NOTA: El programa crea un par de gráficos que muestran la distribución de frecuencias y otro que muestra la distribución de las diferencias. Para esto, van a necesitar un programa llamado Graph. Lo pueden bajar de aquí. Es freeware, asi que no van a tener problemas.

El código está adjuntado al post, es demasiado grande para pegarlo y realmente no confío en rapidshare y similares.
El código utiliza el PRNG que utiliza c++, que es el clásico generador lineal congruencial con distintos parámetros según el compilador. Pero se puede utilizar cualquier prng con solo codearlo en el programa.
Como entrada, el código pide un tamaño de la muestra, que luego va a ser multiplicado por 256, para que sea posible que haya al menos uno de cada uno de los 256 posibles caracteres. Utiliza memoria dinámica para guardar los valores, es claro que tiene un límite este número, si lo exceden, no va a poder asignarlo y a pesar de que tiene un chequeo, probablemente crashee.
Como salida, da algunos datos estadísticos y luego hace unas pruebas aprobadas por el FIPS140-1 para probar aleatoriedad de la muestra. Vamos a verlos uno por uno. Al final de cada medida estadística puse el valor buscado en un PRNG ideal, debemos acercarnos lo más posible a este valor.
Defino antes de empezar un par de conceptos:
Función de distribución: Muestra cuantas veces aparecen cada uno de los valores en un gráfico.
Función de distribución uniforme: Función ideal en la cual todos los valores aparecen la misma cantidad de veces, un PRNG debe aproximarse lo más posible a dicha distribución.

---

Tamaño de la muestra (n): 256 * x. Siendo "x" el tamaño que el usuario elija. Si esta excede "4000", se toman solo los primeros 4000 * 256 datos. Esto es por el teorema central del límite que dice que si se toman muestras suficientemente grandes, las medidas estadísticas van a ser idénticas con un márgen de error despreciable en comparación con las medidas de la muestra total. Es más que nada para agilizar los cálculos.

Mean, Media o promedio (Xm): Media aritmética estándar. Xm = Sum(xi) / n. Sumatoria de todos los valores dividido la cantidad de valores. Valor buscado = 127,5 (255/2).

Mode, Moda o Modo (Mo): Valor modal, es decir el más repetido de todos. Puede existir más de uno, pero solo se muestra el primero que se encuentra. Valor buscado = No definida, es decir, que no haya un valor que salga más que otros.

Anti-Mode o Anti-Moda (aMo): Probablemente tenga otro nombre que desconozco, pero representa el valor menos repetido en la muestra. Valor buscado = No definida, es decir, que no haya un valor que salga menos que otros.

Standard deviation, desviación estandar o desviación típica(Sx): Es una medida de dispersión que indica que tan distribuidos están los valores a lo largo de los rangos, en este caso, 0-255. Sx = sqrt(Sum((xi - Xm)^2) / n) = sqrt(Sum(xi^2)/n - Xm^2). Valor buscado = 73.9.

Assimetry coefficient o coeficiente de asimetría (As): Determina que tan simétrica es la distribución, si hay valores que se repiten más que otros, va a afectar la simetría. Sin embargo, si el/los valores que se repiten, lo hacen de la misma manera que x+Xm mod 256 siendo "x" el valor, entonces no va a afectar la simetría. El lado que cause la asimetría, es decir, que tenga mayor frecuencia, se denomina "sesgo". Si As > 0, entonces el sesgo está hacia la derecha, si As < 0, el sesgo estará hacia la izquierda. Si As = 0, la distribución será perfectamente simétrica. As = Sum((xi - Xm)^3) / n / Sx^3. Valor buscado = 0, es decir que sea simétrica.


Aquí vemos que el sesgo está hacia la derecha, con un As > 0.

Kurtosis o curtosis (Ks): Determina que tan distantes están distribuidos los valores al rededor de la media. Las distribuciones definidas teóricas, como por ejemplo la Normal, la de Gauss, la de Poisson, la uniforme, etc. Tienen una curtosis esperada.

Ks = Sum((xi - Xm)^4) / n / Sx^4 - 3.


D: Distribución de Laplace. Ks = 3.
S: Distribución secante hiperbólica. Ks = 2
L: Distribución logística. Ks = 1.2
N: Distribución normal. Ks = 0
C: Distribución coseno aumentada. Ks = −0.593762.
W: Distribución de Wagner. Ks = -1.
U: Distribución uniforme. Ks = -1.2.
Valor buscado = -1.2, es decir, uniforme.

Entropy o entropía (Ep): Busca la uniformidad en la muestra, se centra en la repetición de cada uno de los caracteres posibles. Ep = Sum(-fr(i) * log2(fr(i))). Donde fr(i) son las frecuencias relativas, es decir, las veces que se repite "i" sobre "n". Valor buscado = 8.

Deciles D(x): Un decil representa el valor que acumula el x*10% (siendo 0 < x < 10) de la muestra. Es decir, si tenemos un gráfico de una distribución, dividimos verticalmente el gráfico en 10 partes iguales, el valor del eje "x" en donde cae la primera división, es el primer decil, el valor del eje "x" en donde cae la segunda división, es el segundo decil y así sucesivamente. Para calcular, se deben ir sumando las frecuencias de cada uno de los valores, hasta que la siguiente suma supere n/10*x, llamamos entonces el valor de ese valor "i", a la suma de frecuencias la llamamos F(n-1) y la fórmula es: D(x) = i + (x/10 * n - F(n-1)) / f(i).

Valor buscado = x * 25.5.

---

Uno de los tests necesarios para un PRNG, es probar que no tenga un período muy corto. Todos los PRNG tienen un período, es decir, un momento en el cual vuelve a empezar la sucesión de dígitos aleatorios. Esto puede ser problemático para un algoritmo criptográfico, ya que si se consigue una parte del PRNG, se puede asumir que va a ser exactamente igual una vez que se reinicie el período. Sin embargo, los buenos PRNG, tienen períodos muy largos, por ejemplo el Mersenne Twister tiene un período de 2^19337 -1, suficiente para cualquier cifrado. Sin embargo, el PRNG que viene por defecto en C++ (linear congruential generator) tiene un período de 2^24 es decir = 16777216 o 16 Mbytes. Si uno usase eso como keystream para cifrar un archivo utilizando xor cuyo tamaño es mayor a 16 Mbytes, con conseguir parte del plaintext, se podrían descifrar otras partes del archivo.

Buscando estas fallas, el programa busca en la muestra completa primero por una cuestion de eficiencia si hay dos valores consecutivos iguales a los primeros dos valores de la muestra, si estos coinciden, prueba entonces los siguientes 10 valores (esto es modificable cambiando el define PERIOD_SAMPLE) si estos coinciden, comienza a probar toda la muestra. Si la muestra no es lo suficientemente grande como para tener dos períodos completos, entonces da un mensaje de "repetición de período" probable, si puede completar la prueba, entonces da un mensaje de "repetición de período" conclusivo. Por último muestra el tamaño del período en potencias de 2. Valor buscado >= 2^32 (4 Gbytes).

---

Estas pruebas son las estándares creadas por el FIPS, con el fin de determinar si una muestra es lo suficientemente aleatoria. Consiste en cuatro tests: Monobit test (stream y block), poker test, runs test y long run test. Todos estos tests se deben hacer con una muestra de 20000 bits o 2500 bytes. Sin embargo, en el programa utilizo para el monobit test una muestra de 500 bytes aleatoria escojida aleatoriamente, para los demás tests, se utilizan muestras aleatorias de 2500 bytes.

Monobit test (stream y block): Consiste en medir cuantos "1" y cuantos "0" hay en una muestra y sacar una razón. El test se puede aplicar tanto con streams, es decir con el total de la muestra, o con bloques de distintos tamaños, en el programa de 8192 a 16 bits y luego se promedian las razones. En definitiva, se trata de ver si hay uniformidad entre 1s y 0s como habría en una muestra realmente aleatoria. Valores buscados [0.966557 ; 1.035840] para todas las razones. Es posible que para los tests de bloques más pequeños falle el test, es decir que en alguno de los bloques, no haya ni "1" ni "0", esto significa que hay al menos una sucesion de dos o cuatro "255" o "0" y deben ser ignorados, solo en las distribuciones más perfectas esto no ocurre. Si ya falla la de 64 bits, va a fallar luego el "long run test".

Poker test: Analiza de a nibbles (grupo de 4 bits) como si fuesen manos de poker, buscando fallas en la aleatoriedad. Se busca la frecuencia de cada uno de los nibbles (es decir de 0000 a 1111) y luego se aplica esta fórmula: Pt = (16/5000) * SUM(f(i)^2) - 5000.
Valor buscado: 1.03 <= Pt <= 57.4.

Runs test: Analiza cuantas sucesiones de los mismos bits repetidos, ya sean "0" o "1", hay en una muestra. Se deben contar la cantidad de repeticiones de x bits por separado para los "1" y para los "0".
Las repeticiones de más de 6 bits, se cuentan como si fuesen de 6. Piensen que "1" significa que no se repite ni una vez, es decir que si el bit analizado es "0" el siguiente es "1" y viceversa.
Valores buscados:
                1                       2,267 - 2,733
                2                       1,079 - 1,421
                3                       502 - 748
                4                       223 - 402
                5                        90 - 223
                6+                       90 - 223

Long runs test: Este test es facil y se puede incorporar en el anterior, en definitiva, falla si se encuentra algun bit que se repita más de 33 veces ya sea 0 o 1.

Correlación entre valores sucesivos.

Esto significa que se pueda encontrar una relación entre cada uno de los valores, que permita, teniendo uno de los valores, calcular el siguiente de manera feasible y en tiempo polinómico o cuasi polinómico. El programa no incluye testeos para buscar correlación, entonces puede no detectar ciertos PRNG que en teoría parecen perfectos, pero en la realidad contienen graves fallas.
Prueben por ejemplo modificar el PRNG del programa por lo siguiente:

unsigned long long val = 0;
unsigned long long rnd()
{
    val++;
    if(val%255 == 0) val++;
    if(val%65024 == 0) val++;
    return val;
}

Este "PRNG" tiene un período de 2^32 y medidas estadísticas cuasi perfectas.
Sin embargo, la sucesión de valores es perfectamente predecible, ya que lo único que hace es sumarle "1" al valor anterior. Los dos "if" sirven para evitar que tenga período corto.
El generador lineal congruencial tiene el mismo problema ya que los parámetros que se utilizan para calcular el siguiente valor, están hardcodeados y varían sólo un poco, con conseguir pocos valores, se podría conseguir rápidamente el siguiente valor de la secuencia. Esto sumado a su período corto, hacen a éste PRNG como potencialmente inseguro.

---

Fuentes:
http://en.wikipedia.org/wiki/Linear_congruential_generator
http://www.csm.ornl.gov/~dunigan/fips140.txt
http://en.wikipedia.org/wiki/Mersenne_twister


Este es el fin del capítulo VI y el fin de la parte teórica del taller de criptografía asimétrica. Posteen todas las dudas que tengan y cuando estén listos, empezamos a crear.
Un abrazo
APOKLIPTICO

El código bájenlo por acá http://web.i.elhacker.net/archivos/StatisticalAnalysis.rar (Gracias Novlucker!)

Toda la información expuesta en este taller, está protegida bajo licencia Creative Commons Attribution-NonCommercial-ShareAlike 2.5.

Perdonen el abandono, estoy extremadamente ocupado con estudios, tengo todos parciales la semana que viene y la otra.
Pero bueno, como andan esas lecturas? Entendieron algo o es todo chino básico?
Pregunten lo que no entienden, ak estamos para aprender, no importa si parece extremadamente tonta o demasiado complicada la pregunta, uds háganla y se les responderá.

Un abrazo
APOKLIPTICO

El lunes me libero de todo

Hasta del foro

Buenas, yo tambien estuve estudiando y además ahora esta la navidad a la vuelta de la esquina....
A principios de enero me paso de nuevo por el foro porque ahora no tengo mucho tiempo

Saludos!

Francamente apokliptico, creo que has hecho un trabajo fenomenal. Puedo decir que habré dedicado a este taller unas 8 horas (incluyendo las búsquedas en Google sobre conceptos matemáticos que no controlaba) y debo decir que en el único apartado en el cual me he perdido un poco es en el último capítulo cuando empiezas a definir la kurtosis.
Por lo demás, he aprendido mucho y ya hay ganas de crear un algoritmo propio
Sólo una pregunta,  ¿cómo utilizaremos las medidas estadísticas nombradas en el último post?
¡Saludos!

estoy hecho un lio con los conceptos basicos de la criptografia asimetrica :S

según entiendo, si tengo 2 sujetos A y B, y el sujeto B quiere recibir información cifrada, por parte del sujeto A, el sujeto B tendrá un clave privada (que él elige) y una clave publica que según entiendo es generada por un programa como el PGP (estoy diciendo barbaridades aqui?  ) la clave pública es generada a partir de la privada.

entonces el sujeto A, usando el programa (en este caso PGP), cifra su mensaje usando la clave publica del sujeto B, y de paso le envia su clave publica, por si quiere recibir alguna respuesta.

Creo que estoy mal en mis afirmaciones por lo que agradecería las correcciones del caso.

saludos

Vaya es muy buena lección de criptografía, haber si encuentro un buen rato en que dedicarme a aprender, muchísimas gracias por el aporte.