Blum Blum Shub

Från Wikipedia
Hoppa till: navigering, sök

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 xi , på formen z1, z2, … zi. Men alla de log (log (M)) första bitarna är 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 Blum primtal p och q (M = pq). Det vill säga primtal som uppfyller:

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

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 Carmichael funktionen. 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:

x_i = \left( x_0^{2^i \operatorname{mod} \lambda(M)} \right)(\operatorname{mod}\ M).

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[redigera | redigera wikitext]

Nedan följer en kort beskrivning över algoritmen för att skapa en Blum Blum Shub slumptalsgenerator.

  1. Generera två stycken stora Blum primtal p och q som uppfyller pq och sätt M = pq
  2. Välj ett tal s som ligger mellan 1 och M-1, så att SGD(s, M) = 1
  3. Sätt x0 till s2 (mod M)
  4. Sekvensen blir då xi = xi-12 (mod M), för i = 1, 2, …
  5. 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[redigera | redigera wikitext]

Använder vi 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.

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

Säkerhet[redigera | redigera wikitext]

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 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 PSTGs. 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[redigera | redigera wikitext]

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 and M.Shub

A Simple Unpredictable Pseudo-Random Number Generator

SIAM Journal on Computing, volym 15, sidorna 364-383, Maj 1986.


Källor[redigera | redigera wikitext]

  • Lenore Blum, Manuel Blum, and 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, and Andreas Danielsen. "About Random Bits", December 2004. PDF