Blum Blum Shub

Blum Blum Shub (B.B.S.) är en pseudoslumptalsgenerator (PSTG) och är även kryptologiskt säker. 
B.B.S. har formen:

.

där utsignalen ofta presenteras som pariteten för xi , på formen z1, z2, … zi. Alla de log (log (M)) första bitarna är dock säkra att använda. Startvärdet x0 räknas fram genom formeln x0 = s2 (mod M), där s ska vara ett tal mellan 1 och M-1, tillhöra de naturliga talen och p och q ska inte vara en faktor i s. 

M är produkten mellan två unika tillräckligt stora Blumprimtal p och q (M = pq), där p och q uppfyller:

.

Denna egenskap gör att varje xi (som är en kvadratisk rest) enbart har en rot som är en kvadratisk rest, vilket gör det möjligt (om man känner till p och q) att ta fram xi-1 entydigt.

För att få en så lång cykellängd som möjligt så ska SGD(φ(p-1), φ(q-1)) vara så liten som möjligt (där φ(n) är Eulers fi-funktion). För att räkna ut cykellängden, d.v.s. hur många iterationer som måste köras innan dess att talen upprepar sig (x0 = xlängd), använder man formeln λ(λ (M)) = längd, där lambda är Carmichaelfunktionen. Detta gäller oftast men endast med säkerhet då ytterligare ett krav ställs på valet av p och q, samt att s måste väljas mer specifikt.

En intressant egenskap hos B.B.S. är att det är möjligt att räkna fram xi för alla i via Eulers sats:

.

Om man känner till x0 samt M, vilket också gör det möjligt att räkna sekvensen framåt. Genom att känna till xi+1 och faktorerna i M d.v.s. p och q kan man även räkna sekvensen baklänges.

Algoritm
Nedan följer en kort beskrivning över algoritmen för att skapa en Blum Blum Shub-slumptalsgenerator.
 Generera två stycken stora Blumprimtal p och q som uppfyller p ≠ q och sätt M = pq
 Välj ett tal s som ligger mellan 1 och M-1, så att SGD(s, M) = 1
 Sätt x0 till s2 (mod M)
 Sekvensen blir då xi = xi-12 (mod M), för i = 1, 2, …
 Utsignalen som används blir z1, z2, … där zi = paritetsbiten (xi) (dvs 1 om zi är udda 0 och 1 om zi är jämn)

Exempel
Vi använder instruktionerna ovan och sätter p = 7 och q = 19, dvs. M = 133.

Sätter vi s = 100 får vi x0 = 1002 (mod 133) = 25

Vi får då sekvensen x1 = 252 (mod 133) = 93, x2 = 932 (mod 133) = 4, x3 = 42 (mod 133) = 16, x4 = 162 (mod 133) = 123. 

Detta ger då z1 = 1, z2 = 0, z3 = 0, z4 = 1.

Säkerhet
Säkerheten i B.B.S. bygger på att det är svårt att lösa ut den kvadratiska resten till ett tal samt svårigheten i att faktorisera primtal. Det är bevisat att förutsäga en sekvens av bitar genererade av B.B.S. är lika svårt som att bestämma den kvadratiska resten, som i sin tur är bevisat lika svårt som att faktorisera stora tal.

Eftersom B.B.S. är ganska långsam jämfört med andra PSTG:er som inte är kryptologiskt säkra så lämpar denna sig inte för exempelvis simulationer. Däremot så är den relativt snabb då man jämför med andra säkra PSTG:er. Problemet med B.B.S. är att p, q och x0 behövs väljas på ett omständligt sätt för att garantera att cykellängden blir en viss längd. Exempelvis så ska både p och q (förutom tidigare nämnda krav) vara ”speciella” primtal. Dessa ”speciella” primtal ska uppfylla P = 2P1+1, P1 = 2P2+1.

Egenskaperna för B.B.S. och hur det är möjligt att skapa sekvensen framåt och bakåt genom att känna till M eller p och q kan användas för kryptering och dekryptering av meddelanden, där M då är den publika nyckeln som används för att kryptera ett meddelande som sedan skickas tillsammans med xi+1. Det kan sedan användas, tillsammans hjälp av p och q, för att dekryptera meddelandet.

Publicerad
Blum Blum Shub föreslogs av Lenore Blum, Manuel Blum och Michael Shub. B.B.S presenterades offentligt i sin helhet för första gången i: L. Blum, M. Blum och M. Shub. A Simple Unpredictable Pseudo-Random Number Generator. SIAM Journal on Computing, volym 15, sidorna 364-383, maj 1986.

Källor
 Lenore Blum, Manuel Blum och Michael Shub. "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing, volym 15, sidorna 364–383, maj 1986.

 Pascal Junod. “Cryptographic Secure Pseudo-Random Bits Generation: The Blum Blum Shub Generator”, augusti 1999 PDF

 Martin Geisler, Mikkel Krøigård och Andreas Danielsen. "About Random Bits", december 2004. PDF

 http://www.ciphersbyritter.com/NEWS2/TESTSBBS.HTM

Artikelursprung

Kryptologi
Algoritmer