Jag fick en fråga om kryptorelaterade algoritmer som skulle kunna vara lämpliga att köra som exempel i en kurs om system-modellering. Tanken som jag förstod det var att på TLM-nivå simulera SW-funktioner som sedan flyttas till HW.
Intressanta algoritmer behöver både vara enkla att begripa och kunna ge stor skillnad i prestanda, genomströmning etc när funktionen flyttas från SW till HW. Utifrån detta var mitt förslag RC4 (som är enkel, men inte skalar speciellt bra i HW), XTEA, SHA-1 och SHA-2 (256).
Några andra algoritmer man borde kunna sätta i händerna på studenter är eSTREAM-kryptona Grain och Trivium. Båda dessa krypton är relativt enkla att förstå, har intressanta explicita skalbarhetsegenskaper och är välspecificerade med testvektorer, referensmodeller etc.
Sedan slog det mig att en annan, något annorlunda algoritm som skulle kunna användas är Stephen Wolframs cellautomat Rule 30.
Rule 30 är en endimensionell cellautomat som ger upphov till ett slumpmässigt (PRNG) mönster. Rule 30 används som slumptalsgenerator i Wolfram Research Mathematica. En fördel med att använda en endimensionell cellautomat är att den enkelt går att rita upp och grafiskt verifiera.
De första iterationerna av regel 30 samt de styrande tillståndskombinationerna.
En annan kul egenskap är att algoritmen är trivialt parallelliserbar, detta då alla celler kan uppdateras samtidigt. Antagligen går det att göra bra SW-implementationer, inte minst om man tar till SSE-instruktioner alt GPU-acceleration, men en ren HW-implementation blir väldigt enkel.
Jag blev så inspirerad av Rule 30 att jag satte mig ned och hackade ihop ett par implementationer. Först en version i Python (naturligtvis) för att få koll på att jag tänkte rätt. Det blev inte speciellt många rader kod, ca 20 inkl kommentarer. Och jag är säker på att om man är en riktig Pythonista går algoritmen att stampa ner till ett fåtal rader kod, ex med lite list comprehensions.
Sedan hackade jag ihop en RTL-generator (i Python) som kan generera Verilogkod för en Rule30-automat med godtyckligt antal bitar. Den genererade konstruktionen består väsentligen av ett tillståndsregister med en bit för varje cell. För varje cell finns det sedan en enbitars 8-till-1-MUX som implemeterar uppdateringsregeln.
En sak man behöver fundera på är vad som händer för första resp sista biten i arrayen. Jag har valt att göra en ring av arrayen. Detta innebär att vid uppdatering av den högsta biten tittar vi på bit 0 och tvärs om. Implementationsmässigt innebär detta två separata ledningar som går från kant till kant, inte bara lokalt mellan ett cellregisters närmaste grannar.
Jag genererade några stycken versioner av min Rule 30-konstruktion och använde sedan Alteras verktyg Quartus II för att implementera konstruktionen i en Cyclone II-FPGA. Lite resultat:
256 bitar: 687 LEs, 263 MHz
128 bitar: 344 LEs, 358 MHz
64 bitar: 128 LEs, 420 MHz
32 bitar: 64 LEs, 420 MHz
16 bitar: 32 LEs, 420 MHz
8 bitar: 16 LEs, 420 MHz
(Notera att implementationen kräver lika många register som bitar, jag redovisar dock inte det här.)
En snabb analys ger att varje MUX (samt logik för att ladda in ett användarstyrt initialvärde) implementeras med två logikelement (LE). Mellan 64 och 128 bitar ser det ut som att någon form av replikering behöver införas.
Vad gäller klockfrekvensen är 420 MHz max som Cyclone II är specad för. I en annan FPGA, ex Stratix III går det antagligen att få upp klockfrekvensen ytterliggare en bit. Eftersom uppdateringsfunktionen för resp bit består av en 8-1-MUX med ett grinddjup motsvarande ungefär tre NAND2-grindar eller en LE, blir det transportfördröjningen genom FPGA:ns switchnät som sätter gränsen för klockfrekvensen.
Nu är Rule 30 inte en kryptografiskt säker PRNG, men för att vara en PRNG som ger så bra slumpserier så att den duger för Mathematica förbrukar den väldigt lite resurser. Och med 256 PRNG-bitar varje cykel i 263 MHz får vi 67 Gbit/s! (Vilket skulle vara hopplöst att få ut på ett kort och använda utanför FPGA:n.)
Jag tänker slänga upp en version av Verilogkoden, antigen här eller hos InformAsic. Återkommer med det. Nästa steg är att att bygga ut generatorn med stöd för resursdelning, men det gör jag inte i kväll i alla fall.
Att cellautomater har försökt användas i kryptosammanhang finns det flera artiklar som vittnar om. Jag hittade en färsk sådan med titeln LCASE: Lightweight Cellular Automata-based
Symmetric-key Encryption som just tar upp Rule 30. Värd att läsa om du vill veta mer.
