Blum Blum Shub

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

x_{i}=x_{i-1}^{2}\ (\operatorname {mod} \ M)

där utsignalen ofta presenteras som pariteten för x_i , på formen z₁, z₂, … z_i. Alla de log (log (M)) första bitarna är dock säkra att använda. Startvärdet x₀ räknas fram genom formeln x₀ = s² (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:

q\equiv p\equiv 3\ (\operatorname {mod} \ 4)

Denna egenskap gör att varje x_i (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 x_i-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 (x₀ = x_lä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 x_i för alla i via Eulers sats:

x_{i}=\left(x_{0}^{2^{i}\operatorname {mod} \lambda (M)}\right)(\operatorname {mod} \ M)

Om man känner till x₀ samt M, vilket också gör det möjligt att räkna sekvensen framåt. Genom att känna till x_i+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 x₀ till s² (mod M)
Sekvensen blir då x_i = x_i-1² (mod M), för i = 1, 2, …
Utsignalen som används blir z₁, z₂, … där z_i = paritetsbiten (x_i) (dvs 1 om z_i är udda 0 och 1 om z_i ä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 x₀ = 100² (mod 133) = 25

Vi får då sekvensen x₁ = 25² (mod 133) = 93, x₂ = 93² (mod 133) = 4, x₃ = 4² (mod 133) = 16, x₄ = 16² (mod 133) = 123.

Detta ger då z₁ = 1, z₂ = 0, z₃ = 0, z₄ = 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 x₀ 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 = 2P₁+1, P₁ = 2P₂+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 x_i+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.