Enigma en VHDL

1. El contador, un rotor sin partes móviles

Un rotor de una Enigma real gira físicamente una posición por pulsación, lo que desplaza el cableado un puesto. Aquí eso es un contador módulo 10 hecho con cuatro biestables T. Su valor se le suma a la entrada, lo que produce el mismo efecto de desplazamiento sin que se mueva nada.

2. El sumador: (m + c) mod 10

Desplaza el mensaje según la posición del contador. Si la suma pasa de 9 da la vuelta, así que 8 + 5 sale 3.

3. El rotor, una mezcla fija

Un circuito combinacional que permuta los diez valores posibles. Esto es el cableado interno del tambor del rotor:

4. El reflector, que devuelve la corriente

En la máquina real el reflector rebota la señal eléctrica de vuelta por los rotores siguiendo un camino distinto. Aquí es simplemente el complemento, Ref(x) = 9 − x:

Fíjate en que ningún valor se mapea consigo mismo. Esa es la propiedad que define a un reflector de Enigma, y es también la debilidad histórica que permitió a Bletchley Park romper la máquina: una letra nunca puede cifrarse como ella misma, lo que le regala al criptoanalista una restricción en cada intento.

5. El rotor inverso, el camino de vuelta

La corriente sale de vuelta por el mismo cableado, así que este bloque deshace el rotor exactamente, Ri = R⁻¹.

6. El restador: (i − c) mod 10

Quita el desplazamiento que metió el sumador. Este es el bloque que faltaba en el diseño original de 2017, y no tenerlo es lo que rompía el cifrado para cualquier posición del contador que no fuese cero.

Llamemos g = Ri ∘ Ref ∘ R a las tres etapas del medio. La máquina entera queda así:

salida(m, c) = ( g((m + c) mod 10) − c ) mod 10

g es una involución, es decir que aplicarla dos veces te deja donde empezaste, g(g(x)) = x. Eso pasa porque el reflector es simétrico y el camino de vuelta deshace exactamente el de ida. Así que si vuelves a meter la salida:

salida(salida(m, c), c)
  = ( g( ((g((m+c)%10) − c)%10 + c) %10 ) − c ) %10
  = ( g( g((m+c)%10) ) − c ) %10        el −c y el +c se cancelan
  = ( (m+c)%10 − c ) %10                porque g es una involución
  = m                                   ✓

Las dos cancelaciones están haciendo trabajo ahí. Quita el restador y la línea del medio deja de colapsar, porque g no es lineal respecto a la suma módulo 10, así que el desplazamiento del contador se cuela por la permutación y ya no vuelve a salir. Eso es el bug 2.

Un biestable T conmuta cuando T = 1 y se queda quieto cuando T = 0, o sea Qsig = Q ⊕ T. Para diseñar el contador escribes el estado al que tiene que ir a continuación, y luego lees las conmutaciones que necesitas para llegar ahí, T = Q ⊕ Qsig.

Los estados del 10 al 15 no ocurren nunca, así que son inespecificados (X). Pueden valer lo que más convenga, y eso deja que los mapas de Karnaugh se simplifiquen mucho más de lo que se simplificarían si no.

T0 vale 1 en todas las celdas, el bit menos significativo conmuta en cada ciclo de reloj. Agrupando los unos de los otros tres mapas sale:

T3 = Q3·Q0 + Q2·Q1·Q0
T2 = Q1·Q0
T1 = Q3'·Q0
T0 = 1

En T1 = Q3'·Q0 es donde vive la vuelta decimal. El bit 1 conmutaría normalmente cada dos cuentas, pero el término Q3' lo mata en el estado 9, así que el contador salta de vuelta a 0 en lugar de seguir hasta 10.

El rotor es una tabla de consulta, pero expresada como puertas en vez de como memoria. Cada uno de los cuatro bits de salida es su propia función booleana de los cuatro bits de entrada, así que la tabla de permutación se convierte en cuatro mapas de Karnaugh separados. Escribiendo R(x) en binario:

Cuatro mapas, uno por bit de salida. Las filas son s3s2 y las columnas s1s0, las dos en código Gray para que las celdas vecinas solo se diferencien en un bit. Ese es el truco que hace que todo esto funcione: si dos celdas adyacentes valen 1 las puedes agrupar, y la variable que cambia entre ellas desaparece del término.

Agrupando cada mapa sale la forma de suma de productos que va directa al VHDL:

r3 = s2·s1'·s0 + s2'·s1·s0
r2 = s1·s0' + s2·s1 + s3·s1'·s0'
r1 = s3'·s2'·s1' + s1·s0'
r0 = s1'·s0 + s2·s1·s0' + s3·s2'

Y en el código fuente, una asignación concurrente por bit, cuatro líneas de VHDL que se sintetizan en un par de docenas de puertas:

rot3 <= (sum2 and not sum1 and sum0) or (not sum2 and sum1 and sum0);
rot2 <= (sum1 and not sum0) or (sum2 and sum1) or (sum3 and not sum1 and not sum0);
rot1 <= (not sum3 and not sum2 and not sum1) or (sum1 and not sum0);
rot0 <= (not sum1 and sum0) or (sum2 and sum1 and not sum0) or (sum3 and not sum2);

El reflector y el rotor inverso salen exactamente del mismo proceso. El reflector se simplifica bien porque 9 − x es muy regular:

ref3 = r3'·r2'·r1'
ref2 = r3'·r2'·r1 + r3'·r2·r1'
ref1 = r3'·r1
ref0 = r3'·r0' + r2'·r1'·r0

Haz todo esto a mano para doce bits de salida y tienes alrededor de cien términos que agrupar y transcribir sin equivocarte ni una vez. De ahí salió el bug 1.

El test 1 pasó a la primera, el reflector no tiene puntos fijos en los 100 casos. El test 2 falló estrepitosamente, 80 de 100 combinaciones rompían la propiedad autoinversa. Las veinte que pasaban estaban todas en la posición 0 del contador, que es justo donde estaban mis casos de prueba manuales de 2017.

Bug 1: ocho entradas mal en el sumador

El sumador módulo 10 tenía 8 entradas mal de 100 en sus ecuaciones SOP hechas a mano, tres en el bit 3, cinco en el bit 2, ninguna en los bits 1 y 0. Los mapas de Karnaugh son una técnica visual, y con unos cien términos que agrupar repartidos en cuatro mapas, leer mal alguna celda es casi inevitable. Lo que lo hizo invisible es que los errores solo aparecen cuando el contador no es cero, y con el contador a 0 el sumador es simplemente la identidad, que es el único caso que había mirado nadie.

Bug 2: faltaba un restador

El contador se sumaba a la entrada antes del rotor pero no se restaba nunca de la salida. Una Enigma real desplaza la permutación entera según la posición del rotor, y sumar una constante a la ida no es la misma operación, así que la diferencia no se cancela. Incluso con un sumador perfectamente correcto la máquina no podía ser autoinversa para ningún contador que no fuese cero. El arreglo es un restador módulo 10 después del rotor inverso.

Los dos están arreglados. El sumador y el restador usan procesos compactos con ieee.numeric_std en lugar de ecuaciones deducidas a mano, mientras que el rotor, el reflector y el rotor inverso siguen siendo lógica a nivel de puertas, que es la parte de la que iba el ejercicio en realidad.

La suite comprueba propiedades en vez de vectores fijos, así que dice algo sobre el diseño en lugar de limitarse a congelar lo que hace hoy:

Los tests 3 al 5 vinieron después, y el 3 se justificó solo enseguida. Comprobé la suite rompiendo el diseño a propósito de tres maneras distintas, y un biestable del contador corrupto se coló tranquilamente por delante de los tests 1 y 2. Los dos configuran el mismo contador roto en la pasada de cifrado y en la de descifrado, así que la simetría se sigue cumpliendo perfectamente, solo que se cumple alrededor del valor equivocado. Eso solo lo caza una comprobación independiente de la secuencia de estados del propio contador. Un test de ida y vuelta que es autoconsistente tiene un punto ciego justo donde los dos sentidos comparten un componente, y es algo en lo que no me había parado a pensar.

Metodología

La suite corre en GHDL. El proceso de estímulos pulsa el reloj él mismo, un pulso cada vez, en lugar de usar un generador libre, porque si no un flanco puede caer en mitad de una ventana de medida y el contador avanza a tus espaldas, lo que hacía que los resultados no fuesen deterministas. Las lecturas de bus rechazan 'U' y 'X' directamente en vez de tomarlos como cero sin decir nada, así que un test no puede pasar sobre basura sin inicializar. Aprobar o suspender lo deciden sentencias assert, y la ejecución sale con código distinto de cero si salta alguna.

Test 1: PASSED (100 cases, no fixed points)
Test 2: PASSED (100 cases, all symmetric)
Test 3: PASSED (11 states, 0-9 then wrap to 0)
Test 4: PASSED (20 checks, rotor and reflector are bijections)
Test 5: PASSED (10 values, R(Ri(y)) == y)

  ALL TESTS PASSED

Todo esto son dos archivos VHDL y un script de PowerShell. GHDL es la única dependencia obligatoria, el visor de formas de onda es opcional.

.\simulate.ps1          # compila y simula -> enigma.vcd
.\simulate.ps1 -test    # ejecuta las cinco suites de tests
.\simulate.ps1 -view    # abre la forma de onda en Surfer o GTKWave
.\simulate.ps1 -clean   # borra los archivos generados