Gilberto Rios

Postulado de Golomb

Existen cuatro requerimientos generales para que una secuencia de unos y ceros se considere segura para utilizarla como clave en Criptografía:

1. Período: la longitud de la secuencia de unos y ceros es decir de la clave debe ser al menos la longitud del mensaje en claro.

2. Distribución de unos y ceros: si se toman varias muestras de cierta longitud de una secuencia dichas muestras están uniformemente distribuidas a lo largo de toda la secuencia.

3. Imprevisibilidad: si consideramos una muestra de la secuencia, un criptoanalista no debería poder predecir el dígito siguiente con una probabilidad de acierto mayor a 0.5.

4. Facilidad de implementación: la velocidad de generación, costo, tamaño, consumo y otros factores no deben ser impedimentos para generar las secuencias pseudoaleatorias con medios electrónicos.

Golomb estableció tres postulados que debe cumplir una secuencia binaria para considerarse pseudoaleatoria, a continuación se exponen concretamente cada uno de dichos postulados:

1. G1: la probabilidad de aparecer a lo largo de la secuencia es igual para unos y ceros, es decir que el número de unos debe ser igual al número de ceros o bien la diferencia debe ser de uno.

2. G2: un cero tiene la misma probabilidad que un uno de aparecer después de un cierto n-grama (muestra de n dígitos consecutivos).

3. G3: el cómputo de coincidencias entre una secuencia y su versión desplazada no debe aportar ninguna información sobre el período de la secuencia.

Los postulados de Golomb son condiciones necesarias pero no suficientes para que secuencias pseudoaleatorias parezcan aleatorias. Fueron enunciados por el ingeniero y matemático estadounidense Solomon W. Golomb.

Sea

s=s^0,s^1,...,s^n

una secuencia de período

n

, los postulados plantean que:¹ ²

En el ciclo $s^n$ de $s$ , la cantidad de elementos '1' difiere de la cantidad de elementos '0' como máximo en 1.
En el ciclo $s^n$ , las diversas rachas son de longitud $\frac{1}{2^n}$ , esto es: Al menos la mitad de las rachas tienen longitud 1, al menos la cuarta parte, longitud 2, al menos un octavo longitud 3, etc. Además para cada una de esas rachas hay la misma cantidad de huecos y de bloques.
La función de autocorrelación tiene sólo 2 valores racionales: