Reto de Navidad: Criptosistema ACYNOS

Por Agustín

El nombre coincide -por lo visto- con una variedad de tomillo silvestre, pero puede considerarse como acrónimo de Anomalous Ciphering Yielding No Obvious Solution.

Je, je, es broma; en realidad viene de: "Ahora Cryptool Ya No Os Servirá".

Bueno, eso es lo que yo creo. Al menos, en las pruebas que he hecho, Cryptool ha sido incapaz de calcular la longitud de la clave, a diferencia de lo que pasaba con los pobres Enigmas (I y II) que otrora me atreví a presentar, claro que a lo mejor es porque no lo manejo bien. Por otra parte, con la experiencia de anteriores desafíos, no descarto que de un papirotazo descalabréis el tinglado, y me digáis, burlones: “¿Y para esto nos molestas?” No me importará que lo resolváis con vuestros medios, pero mi intención es que no lo podáis hacer con herramientas estándar, como quien se prepara unas palomitas en el microondas.

Voy a contaros toda la historia: Esta vez no se trata de "Seguridad Mediante Oscuridad", sino de "Seguridad Mediante Confusión". Es un problema de los que os gustan: "Algoritmo conocido, clave desconocida" ¿Y en qué se diferencia este engendro de los anteriores Enigmas, que tan fácilmente cayeron? Pues en que ahora el cifrado incorpora una componente (pseudo)aleatoria, cuya semilla inicial es fuertemente dependiente de la clave. Es mi último intento de diseñar un sistema de cifrado de estilo clásico, pero seguro -ya veremos-. Es decir, que el algoritmo se limite a desplazar una letrita en el alfabeto, a partir de una clave -y algo más- y tratar de que el resultado no sea destripable estadísticamente, por más texto cifrado de que se disponga. Ya sé que muchos piensan que eso es imposible de conseguir, y probablemente tengan razón.

Un buen amigo, a quien le he mostrado el engendro dice que tiene demasiados números; pero os aseguro que las únicas operaciones matemáticas que utiliza, además de las cuatro reglas, son: potencias, logaritmos, redondeos y truncados. Ah, y módulo, claro...

Una pizca de Caos

"En el principio era la Clave, y la clave se hizo Alfabeto, y de la Clave y el Alfabeto, nació la Semilla del Caos"

Lo anterior parece una mala versión de cierto evangelio, pero sólo es una mala síntesis del procedimiento, que consiste en calcular cuatro números enteros para cada letra plana a cifrar:

1. La posición absoluta de la letra plana en el texto (N)
2. La posición de la letra plana en el alfabeto derivado (P)
3. La posición de la letra clave correspondiente (K) en el alfabeto derivado.
4. Un número pseudo-aleatorio (A), comprendido entre 1 y la longitud del alfabeto (L)

El resto ya es obvio. Se suman estos numeritos (módulo L) para obtener la posición de la letra cifrada, C, y chim-pum de la pandereta.

C = P + N + K + A (módulo L)

Algo de detalle

Una vez expuesto grosso modo el procedimiento, vamos a hacer un zoom sobre los detalles, que podrían cambiarse sin alterar la esencia del criptosistema:

1. La clave crea al alfabeto

Pues, como siempre. Se toman las letras de la clave sin repetición, a la derecha las pares, y a la izquierda las impares. Y luego las que falten del alfabeto base, de manera similar, las impares por la derecha.

El alfabeto base es

ABCDEFGHIJKLMNÑOPQRSTUVWXYZ_

es decir, las 27 letras y el símbolo separador "_". Total, 28 símbolos. No he querido aumentar la entropía añadiendo más signos, para poder ver mejor la robustez del algoritmo en sí.

2. La clave, con el alfabeto, crea la semilla

Obtenemos la posición de cada letra de la clave en el nuevo alfabeto, y utilizamos la serie de los números primos -eso siempre mola mucho- para hacer algunos tejemanejes numéricos, que nos produzcan un número decimal. Luego lo explicaré mejor.

3. Este número será la semilla para una rutina pseudoaleatoria casera, no os riáis, por favor: Se toma el número π, se suma la semilla y se eleva al cuadrado. Se toma la parte decimal como número pseudoaleatorio, s':

s' = ( π + s)^2 – truncado( π + s)^2

4. Calculamos un número A entre 1 y la longitud del alfabeto, L, mediante una sencilla fórmula.

A = redondeo(s * (L - 1) ) +1

El número A se usará para el desplazamiento, como antes se dijo, y el decimal s servirá como semilla para obtener el siguiente número pseudoaleatorio.

Supongo que se discutirá la calidad de este generador de pseudoaleatorios, al que se le podrán pasar los tests oportunos. Yo me he limitado a ver que cumple tres requisitos: No tiende a cero, mantiene una razonable media, y una desviación típica que me parece aceptable. Los Chi-cuadrado y demás, que los pasen los entendidos, si quieren. Estoy casi seguro de que la rutina será considerada uno de los puntos débiles del sistema. Pero ya veremos.

La semilla aleatoria

Mi intención ha sido que la semilla de partida fuera fuertemente dependiente de la clave. Se podría haber calculado una función resumen, tipo HASH, o similar; pero he optado por algo más casero. Los trucos numéricos que he urdido para obtener la primera semilla a partir de la clave son otra chorrada con la que os partiréis el culo, de risa. Veamos:

1. Obtenemos tantos números primos, a partir de 2, como letras tenga la clave. Los números primos servirán para que la semilla dependa el orden de las letras de la clave, de modo que “SETA” y “ESTA” generen semillas distintas.

2. Se eleva el primer número primo, 2, al valor de la posición de la primera letra clave en el alfabeto derivado, y así sucesivamente. Si multiplicáramos todos estos factores obtendríamos el “Número Gödel” de la clave

G = Π Pri^Ki = 2^K1 * 3^K2 * 5^K3 * ...

que es totalmente unívoco con ella. Lo que pasa es que las potencias llegan a ser muy grandes, especialmente si la clave es muy larga, con lo que el número G crece brutalmente. Por ello, realizamos el paso siguiente

3. Se calcula el logaritmo decimal de G.

σ = log G = Σ Ki * log Pri = K1 * log 2 + K2 * log 3 + K3 * l og 5 + ...

Este número crece tan lentamente que podemos utilizar claves de longitud arbitraria, tan largas como el propio texto a cifrar. El número σ no será unívoco con respecto a la clave, pero será fuertemente dependiente de ésta.

4. Convertimos el número anterior en un decimal menor que la unidad, dividiéndolo por 10^n siendo n el número de cifras del mismo.

n = redondeo-por exceso (log σ)

s0 = σ/10^n

Esta será nuestra semilla primigenia.

El problema de la coma flotante

Para hacer reproducible todo el cálculo y que, en consecuencia, sea posible el descifrado, es esencial controlar el comportamiento de las cifras decimales. Como a veces la máquinas manejan más decimales de los que se muestran, y no siempre sabemos lo que hacen con ellos, conviene limitar del número de éstos. He optado por arrastrar sólo 10 cifras decimales en todas las operaciones -incluyendo el valor de π-, con una rutina tan simple como ésta:

D = número de decimales que se quiere manejar
n es el número decimal a tratar

Hacemos
n' = n * 10^D

para correr la coma hacia la derecha D posiciones. Luego quitamos los decimales, que están más allá de la posición D

n'' = redondeo de n'

Y volvemos a poner la coma a su sitio inicial.

n = n'' / 10^D

Eso nos devuelve el número decimal anterior, con sólo D -en nuestro caso 10-, cifras decimales significativas.

Conviene asegurarse de que los lenguajes de programación utilizados, o las hojas de cálculo, manejen correctamente la coma flotante, cosa que está lejos de estar garantizada. De hecho creo que he encontrado un bug en Open Office que tendré que reportar un día de estos.

Un ejemplo

Para facilitar la comprensión de este galimatías, os presento el cifrado, paso a paso, de un fragmento de unos cuantos caracteres de un texto, concretamente de la Regenta de Clarín.

Alfabeto base:
ABCDEFGHIJKLMNÑOPQRSTUVWXYZ_
(28 caracteres)

Clave:
VALE
(4 caracteres, bien sencillita)

Si hubiera espacios en la clave, deberían sustituirse por el separador "_" Los programas que se adjuntan realizan automáticamente esa operación.

Alfabeto derivado: (con las viejas reglas de Enigma II)
_YWUSQONJHFDBLVAECGIKMÑPRTXZ

Primos: (Pri)
2 3 5 7

Posiciones de las letras de la clave (en el alfabeto derivado): (Ki)
15 16 14 17

Logaritmos de las potencias Li = log(PRi^Ki)
4.5154499350 7.6339400755 9.7855800607 14.3666666802

Sumatorio:
σ = Σ Li = L1 + L2 + L3 +L4
36.3016367514

Semilla inicial
S0 = Π /10^nde
0.3630163675

Valor de π
3.1415926536

Texto en claro

LA_HEROICA_CIUDAD_DORMIA_LA_SIESTA_EL_VIENTO_SUR_CALIENTEY_PEREZOSO_EMPUJABA_LAS_NUBES_BLANQUECINAS_QUE_SE_RASGABAN

(115 caracteres)

Posiciones de las letras del texto en el alfabeto derivado: (Pi)

14 16 01 10 17 25 07 20 18 16 01 18 20 04 12 16 12 01 12 07 25 22 20 16 01 14 16 01 05 20 17 05 26 16 01 17 14 01 15 20 17 08 26 07 01 05 04 25 01 18 16 14 20 17 08 26 17 02 01 24 17 25 17 28 07 05 07 01 17 22 24 04 09 16 13 16 01 14 16 05 01 08 04 13 17 05 01 13 14 16 08 06 04 17 18 20 08 16 05 01 06 04 17 01 05 17 01 25 16 05 19 16 13 16 08

Números de orden (Ni)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115

Números de la clave (hasta 115 ocurrencias)

15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14 17 15 16 14

Semillas aleatorias

S' = parte decimal de (π + S)^2 (partiendo de s = 0.3630163675)

0.2822843908 0.7229340152 0.9345663739 0.6150724175 0.1125324564 0.5893302315 0.9197855746 0.4947931125 0.2233014399 0.3225122605 0.0000228559 0.8697480095 0.0908539154 0.4487108214 0.8902790426 0.2559893746 0.5435636383 0.5803768957 0.8530573259 0.9572284587 0.8003345106 0.5387897679 0.5452147685 0.5925489677 0.9438136479 0.6905446483 0.6852763006 0.6449259926 0.3377234580 0.1056406044 0.5445238319 0.5874547447 0.9057944988 0.3813427614 0.4110739383 0.6214399132 0.1604140988 0.9032485929 0.3607407094 0.2663389856 0.6139980575 0.1044615893 0.5368681478 0.5310738674 0.4884793745 0.1774229292 0.0158644389 0.9695352910 0.9013729769 0.3455710894 0.1603109705 0.9025675428 0.3552316941 0.2277805187 0.3526755742 0.2099104478 0.2325730387 0.3849941191 0.4368142654 0.8049960779 0.5755626156 0.8172432953 0.6723820703 0.5464031945 0.6013133756 0.0093455434 0.9284115213 0.5649339837 0.7383397130 0.0538751694 0.2110146078 0.2399754492 0.4350028339 0.7920352812 0.4734287294 0.0683795995 0.3039218657 0.8715703027 0.1054769138 0.5434607755 0.5796187753 0.8474144986 0.9121780603 0.4330570009 0.7781201524 0.3641484815 0.2902209063 0.7773443099 0.3580669239 0.2476171584 0.4867431498 0.1648207022 0.9323692794 0.5971658315 0.9783150099 0.9736391558 0.9351328451 0.6196907918 0.1472531566 0.8165067633 0.6665509941 0.5019580415 0.2754616678 0.6762602354 0.5760006820 0.8205002089 0.6981798511 0.7438528879 0.0966870560 0.4864554776 0.1627332423 0.9185696263 0.4849177391 0.1515776284 0.8449705062

Números aleatorios (entre 1 y 28 (longitud del alfabeto)

Ai = redondeo(Si*(L-1))+1

09 21 26 18 04 17 26 14 07 10 01 24 03 13 25 08 16 17 24 27 23 16 16 17 26 20 20 18 10 04 16 17 25 11 12 18 05 25 11 08 18 04 15 15 14 06 01 27 25 10 05 25 11 07 11 07 07 11 13 23 17 23 19 16 17 01 26 16 21 02 07 07 13 22 14 03 09 25 04 16 17 24 26 13 22 11 09 22 11 08 14 05 26 17 27 27 26 18 05 23 19 15 08 19 17 23 20 21 04 14 05 26 14 05 24

Posición de las letras cifradas en el alfabeto derivado:

Ci = (Pi + Ni + Ki + Ai) módulo 28

11 27 16 21 13 08 26 03 21 24 27 15 23 19 10 01 04 24 13 15 28 20 17 18 11 20 21 08 03 14 22 15 15 21 06 04 15 24 23 01 07 14 14 27 19 17 10 05 06 10 02 24 15 10 04 22 12 03 03 12 26 14 01 13 20 04 02 18 10 26 04 16 26 16 04 28 18 21 01 06 02 18 15 15 27 06 27 28 17 18 15 08 26 04 14 20 06 08 11 01 01 25 02 01 02 22 02 03 04 05 09 03 15 11 21

Texto cifrado

FXAKB NTWKP XVÑGH _UPBV ZIECF IKNWL MVVKQ UVPÑ_ OLLXG EHSQH YPVHU MDWWD TL_BI UYCHT UATAU ZCK_Q 

(Las disposición en grupos de 5 caracteres, it's just a tradition. Los espacios entre grupos no son significativos)

El fichero original, y el cifrado, con la misma clave "VALE" los tenéis aquí, por si queréis jugar con ellos y con los programas que pongo más abajo.

Regenta

Regenta cifrada

He aquí el problema

Aquí os pongo unos cuantos grupos cifrados, con clave secreta.

GLERC K_PDN ARTN_ SFQHB JDÑMO QOCLZ WIDOJ V_EEQ WÑANE HBFGW ÑPFMT WIQAR DBYJC JLHXN YFQGS __FXT KMIAK UAUQN AXYGA LMXSX CWBRN WQXFP UJOHK HÑ_QO NPÑNK HTASK ZÑ_QS DKWUE

El fichero completo cifrado está en:
Secreto que tiene 56160 caracteres.

También os pongo un programa hecho en Logo para descifrar un fichero, siempre y cuando se conozca la clave, claro está:
DESCIFRADO LOGO

Y este otro, para cifrar:
Cifrado LOGO

El MSWLogo lo podéis obtener de:
http://www.softronix.com/download/mswlogo65.exe

Para manejar los ficheros de entrada y de salida, hay que colocarlos en el mismo directorio en el que esté el programa.

Los programas arrancan pidiendo la clave (con espacios normales), y los nombre de los ficheros a cifrar o descifrar, así como el fichero de salida. Pero no le he dedicado mucho tiempo a pulirlos ni a documentarlos, así que deberéis tomarlos "tal cual".

Disclaimer

Yo me voy unos días fuera del país, huyendo del Doctor Romerales y de su diabólica enfermera.

Saludos cordiales.

Agustín.