Por tokamak

Bueno, pues en este reto tendréis que romper la clave de un criptosistema basado en un generador de números aleatorios. Estos generadores suelen estar basados en funciones recurrentes del tipo:

f x(n+1)=(ax(n) + b) mod m

Las series generadas por estas funciones siempre caen en ciclos, pero es posible ajustar los parámetros para que estos ciclos sean de amplitud máxima. Podéis consultar Wikipedia para ver los detalles. Por ejemplo con a=3, b=5 y m=32 se obtiene un ciclo de amplitud máxima, como máximo m, sin repetirse ningún valor.

Lo interesante son las congruencias con ciclos amplísimos, de las que he encontrado algunos ejemplos aquí o aquí

Al final me he quedado con la siguiente:

a = 2862933555777941757
b = 3037000493
m = 2^64

Esa función tiene un período de 2^64, lo que nos servirá para implementar nuestro algoritmo de esta forma:

El alfabeto base es el estándar de Kriptópolis, con valores entre 0 y 31:

ABCDEFGHIJKLMNÑOPQRSTUVWXYZ_.,:;

0-) Ponemos la clave en el "bloque anterior"
1-) Tomamos un bloque de 8 bytes del texto claro.
2-) Tomamos el bloque anterior, del texto en claro
2-) Convertimos el bloque anterior en una cadena de números, con los valores numéricos de sus carácteres.
3-) Utilizamos ese valor para generar un número "aleatorio" con la función propuesta
4-) Tomamos los 16 valores más significativos de ese número. Si hay menos, anteponemos ceros hasta completar 16 bytes
4-) Repasamos ese número, cogiendo cifras de dos en dos y haciendo módulo 32
5-) Hacemos Xor con esos valores y con cada uno de los valores del bloque actual y generamos el bloque cifrado
6-) Así hasta el final del cifrado

Os pongo un ejemplo
Clave

SANCHO_P

Claro

EN_UN_LUGAR_DE_LA_MANCHA

Traza

Bloque anterior   Bloque actual  Cadena numérica         Aleatorio      Aleatorio mod 32     Cifrado
 
SANCHO_P          EN_UN_LU       1900130207152716      8144192868236447  1712192804230015     UBIJJMLZ
EN_UN_LU          GAR_DE_L       0413272113271121      1284083070662115  1220083006022115     UBIJJMLZKTZFFGÑE
GAR_DE_L          A_MANCHA       0600182703042711      9560860986001016  3128220922001016     UBIJJMLZKTZFFGÑE;HZJ_CNP

Ya se ve que que es un proceso sencillísimo, poco más que un Vigenère con autoclave; además como es difícil que cada secuencia de 8 bytes se repita en el texto y como cada una de ellas nos genera un número distinto que sumar al bloque, resulta que estamos incrementando mucho el nivel de dificultad. Sobre todo teniendo en cuenta que no es fácil compilar una lista exhaustiva de las permutaciones posibles de cada bloque, a causa del gran número (32^8) de ellas, lista con la que podríamos conocer las asignaciones "aleatorias" que corresponderían a cada bloque.

La única complicación técnica de este proceso es la dificultad para hacer cálculos con precisión de 16 dígitos pero, mira por donde, ya había salido el tema en otro post, y yo había localizado unas funciones muy útiles para ese propósito en esta monografía. Sqrmatryx también nos contó como se puee hacer en Java, por lo que creo que no va a ser ningún problema.

Lo he llamado EL GRIAL, por la maravillosa simplicidad de los algoritmos para cifrados basados en generadores aleatorios, que se acercan a mi ideal de criptosistema. Ahora bien: seguro que existe una metodología para atacar estos cifrados, porque si no...apaga y vámonos. Además, finalmente lo he hecho más simple de lo que inicialmente había pergueñado, para dar alguna oportunidad. Por ejemplo no hago un segundo Xor con la clave anterior, lo que ofuscaría más el texto. Hay una vulnerabilidad evidente que podéis explotar.

Bueno que lo disfrutéis, el reto está en un fichero que se puede bajar de aquí

Y este es el código fuente, utilizable como siempre desde Excel.

El cifrado lo componen sólo las 4 primeras funciones, un código minimalista. El resto es la "biblioteca" para cálculos largos.

Public Function CoD(ByRef mensaje As Variant, clave As Variant, cd As Variant) As String
 
 Dim bloque_ant, bloque_8, letra, letra_clave, semilla, nuevo, suma
 Dim i, j, cifra, k, l
 
 CoD = ""
 bloque_ant = clave
 
 For i = 1 To Len(mensaje) Step 8
   bloque_8 = Mid$(mensaje, i, 8)
   semilla = ""
   For j = 1 To 8
     letra_clave = Mid(bloque_ant, j, 1)
     semilla = semilla & Format$(inv_caracter(letra_clave), "00")
   Next j
 
   nuevo = aleatorio(semilla) 'Convierte bloque anterior en nº "aleatorio"
 
   aux = "": k = 0
    For j = 1 To 16 Step 2
     k = k + 1
     cifra = CInt(Mid(nuevo, j, 2)) Mod 32
          '  nº aleatorio   letra bloque
     cifra = cifra Xor inv_caracter(Mid(bloque_8, k, 1))
     CoD = CoD & caracter(cifra)
     aux = aux & caracter(cifra)
   Next j
  If cd = "C" Then bloque_ant = bloque_8 Else bloque_ant = aux
 Next i
 
End Function
Public Function inv_caracter(caracter)
  Dim i, caracteres
  caracteres = "ABCDEFGHIJKLMNÑOPQRSTUVWXYZ_.,:;"
  i = InStr(caracteres, caracter)
  inv_caracter = i - 1
End Function
Public Function caracter(numero)
  Dim caracteres()
  caracteres = Array("A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", _
  "Ñ", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "_", ".", ",", ":", ";")
  caracter = caracteres(numero)
End Function
 
Public Function aleatorio(semilla) As String
 
Dim x(2) As String
Dim y(2) As String
Dim z(2) As String
 
Dim CR() As String
 
'X = (2862933555777941757 * X + 3037000493) mod 2^64
Dim n As Integer, test As Double
 
Dim Potencia, producto, suma As String
 
n = Len(test) - 1
 
Potencia = "18446744073709551616" ' 2^64
 
y(1) = semilla
y(2) = "2862933555777941757"
producto = Multiplicar(y(), n)
 
x(1) = producto
x(2) = "3037000493"
suma = Sumar(x(), n)
 
z(1) = suma
z(2) = Potencia
 
CR() = DivisionEuclidea(z(), n)
 
aleatorio = CR(2)
 
If Len(aleatorio) > 16 Then aleatorio = Left(aleatorio, 16)
diferencia = 16 - Len(aleatorio)
If diferencia > 0 Then   aleatorio = String(diferencia, "0") & aleatorio
 
End Function

Aquí se puede enlazar al texto completo. Funciones de cálculos largos incluídas

Descargar código completo con biblioteca de cálculos largos

Post scríptum
EL GRIAL (FORTE)

Existe la posibilidad de incrementar poderosamente la seguridad de este cifrado, añadiendo un generador adicional pseudoaleatorio que inicializaremos también con el valor de clave, y que se irá alimentando recursivamente con los valores que vaya produciendo. Cada valor generado lo Xoreamos con el bloque actual, y después seguimos el mismo procedimiento que con EL GRIAL.

Como generador adicional podemos usar, por ejemplo:

a = 6364136223846793005
b = 1442695040888963407
m = 2^64

Y ésta sería la traza para cifrar el mismo texto:

 Cadena numérica  Aleatorio        Aleatorio mod 32 Semilla adicional Aleatorio adicional Adicional mod 32 Bloque cifra  
 1900130207152716 8144192868236447 1712192804230015 1900130207152716    1427708576476394 1427062112153130 _ZÑ.FDTE
 0413272113271121 1284083070662115 1220083006022115 1427708576476394    1781493185490403 1717173121170403 _FLZPWKH
 0600182703042711 9560860986001016 3128220922001016 1781493185490403    1813710054170517 1813070022170517 NK,JNSIB

No voy a publicar el fuente para no interferir con el reto. Quien quiera el código sólo tiene que pedirmelo.