Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Blum-Blum-Shub aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Blum-Blum-Shub-Generator

Der Blum-Blum-Shub-Generator (BBS-Generator) (auch "s² mod n"-Generator) ist ein Pseudozufallszahlengenerator entwickelt 1986 von Lenore Blum, Manuel Blum und Michael Shub. Anwendung findet das System u. a. in der Kryptologie im Entwurf komplexitätstheoretisch sicherer Kryptosysteme.

Prinzip

Der BBS-Generator ist definiert als Folge

:s₀ = s² mod n
:s_i+1 = (s_i)² mod n

wobei n=pq (n wird auch Blum-Zahl genannt) das Produkt zweier Einschränkungen unterworfener Primzahlen ist.
* p und q sollten groß, ungleich und etwa gleichdimensioniert sein, d.h. etwa mindestens 100 Dezimalstellen
* p ? q ? 3 mod 4
* (p-1), (p+1), (q-1) und (q+1) sollten mindestens einen großen Primfaktor haben.
Kommt man den Forderungen nicht nach, dann gibt es Algorithmen, die n verhältnismäßig schnell und damit zu leicht in seine Primfaktoren p und q zerlegen, was im Anwendungsfall (z. B. als Kryptosystem) dann einem Brechen entspricht.

Für den Startwert s (englisch: seed) des BBS-Generators gilt:

Anwendung

Symmetrisches Kryptosystem

Zunächst wird der BBS-Generator zur Umsetzung eines symmetrischen_Kryptosystems verwendet. Als geheimer Schlüssel zwischen Sender und Empfänger dienen n und der Startwert s des Generators.

Z. B. generiert der Sender aus n=7$\backslash cdot$11=77 und s=64 nach der oben angegebenen Vorschrift die Folge der s_i. Die zugehörige Pseudozufallszahl b_i ergibt sich aus dem letzten Bit (äquivalent zu mod 2) des jeweiligen Wertes von s_i,d. h. b_i=s_i mod 2. Um den Schlüsseltext zu bestimmen wird der Klartext (im Beispiel: 0011) XOR mit der Pseudozufallszahlenfolge verknüpft.
generierte Folge 15 71 36 64 ...
Pseudozufallszahlenfolge 1 1 0 0 ...
Klartext 0 0 1 1
Schlüsseltext 1 1 1 1

Der Empfänger bestimmt seinerseits aus den geheimen Werten n und s die Folgen s_i und b_i. Mihilfe des übersendeten Schlüsseltextes wird wiederum mittels XOR der Klartext berechnet.
generierte Folge 15 71 36 64 ...
Pseudozufallszahlenfolge 1 1 0 0 ...
Schlüsseltext 1 1 1 1
Klartext 0 0 1 1

Asymmetrisches Kryptosystem

Zur Umsetzung eines asymmetrischen_Kryptosystems eignet sich der BBS-Generator ebenfalls. Dieses Verfahren wurde 1984 von Manuel Blum und Shafi_Goldwasser vorgeschlagen und auch als Blum-Goldwasser-Kryptosystem bezeichnet.
Der geheime Schlüssel auf Seiten des Empfängers sind die Primfaktoren p und q.

Senderseitig läufen die Berechnungen analog zum obigen symmetrischen Fall ab. Zusätzlich zum Schlüsseltext $x\_0\; \backslash oplus\; b\_0,\; \backslash ldots,\; x\_i\; \backslash oplus\; b\_i$ wird aber noch s_i+1 gesendet. Da der Empfänger den Startwert nicht kennt, bildet er mithilfe der geheimen Primzahlen p und q die Folge der Pseudozufallszahlen ausgehend vom versendeten s_i+1 bis zum Startwert s zurück. Für das Beispiel bedeutet das, der Empfänger erhält 1111 sowie s₄=15.

:s_i-1 = (up$\backslash cdot$s_i^(q+1)/4 mod q + vq$\backslash cdot$s_i^(p+1)/4 mod p) mod n

Der Ansatz bedient sich des Chinesischen Restealgorithmus, einem Spezialfall des _chinesischen_Restsatzes. Die beiden Unbekannten u und v sind von den Primfaktoren p und q abhängig und werden zu Beginn mithilfe des _erweiterten_Euklidischen_Algorithmus bestimmt. Dabei gilt up+vq=1, also 2$\backslash cdot$11-3$\backslash cdot$7=1 im Beispiel. Damit ergibt sich die folgende Abarbeitung.

:s₃ = (22$\backslash cdot$15² mod 7 - 21$\backslash cdot$15³ mod 11) mod 77
:s₃ = (22$\backslash cdot$1 - 21$\backslash cdot$9) mod 77 = 64

:s₂ = (22$\backslash cdot$64² mod 7 - 21$\backslash cdot$64³ mod 11) mod 77
:s₂ = (22$\backslash cdot$1 - 21$\backslash cdot$3) mod 77 = 36

:s₁ = (22$\backslash cdot$36² mod 7 - 21$\backslash cdot$36³ mod 11) mod 77
:s₁ = (22$\backslash cdot$1 - 21$\backslash cdot$5) mod 77 = 71

:s₀ = (22$\backslash cdot$71² mod 7 - 21$\backslash cdot$71³ mod 11) mod 77
:s₀ = (22$\backslash cdot$1 - 21$\backslash cdot$4) mod 77 = 15

:s = (22$\backslash cdot$15² mod 7 - 21$\backslash cdot$15³ mod 11) mod 77
:s = (22$\backslash cdot$1 - 21$\backslash cdot$5) mod 77 = 64

Empfängerseitig wird nun analog zum symmetrischen Fall aus der eben rückwärts berechneten BBS-Generatorfolge die Folge der Pseudozufallszahlen bestimmt und letztendlich durch XOR-Verknüpfung mit dem Schlüsseltext der Klartext generiert.

Ein so konstruiertes asymmetrisches Kryptosystem ist jedoch nicht sicher gegen aktive Angreifer, z. B. durch einen gewählter_Schlüsseltext-Klartext-Angriff (englisch: chosen-ciphertext attack).

Sicherheit

Zur Zeit kann keine Aussage getroffen werden, wie schwer Faktorisierung ist. Mit anderen Worten, die Frage nach einem Algorithmus, der in annehmbarer Zeit bei Eingabe beliebiger n die Primfaktorzerlegung in p und q durchführt, bleibt unbeantwortet. Somit kann die Problematik lediglich mithilfe einer Annahme abgegrenzt werden.

Faktorisierungsannahme (FA): Die Wahrscheinlichkeit, dass ein schnelles Faktorisierungsverfahren eine ganze Zahl n=pq mit Erfolg faktorisiert, sinkt rapide mit Länge der Faktoren p und q.

Für konkrete praktische Anwendungen fordert man dann, dass bei gegebener Länge der Primfaktoren nur ein bestimmter Teil in einer bestimmten Zeit mit maximal verfügbarer Rechnerkapazität faktorisiert werden kann, also z. B. bei einer Länge von 1024 Bit werden 2^-50% aller n in einem Jahr faktorisiert.

Die Sicherheit des BBS-Generators kann über die Faktorisierungsannahme bewiesen werden. Einen anderen auf der Funktionalität beruhenden Nachweis bietet die Quadratische-Reste-Annahme (QRA) (englisch: quadratic residuosity assumption). Diese resultiert aus der (wiederum nicht bewiesenen) Schwere (im Sinne von aufwändig) des Quadrattests in einem Restklassenring. Mit anderen Worten, ist eine Zahl das Quadrat einer anderen bzgl. des gegebenen Restklassenrings. Zwei Punkte erschweren diesen Test. Erstens gibt es in einem Restklassenring mehrere Wurzeln zu einer gegebenen Zahl. So haben z. B. im $\backslash mathbb\{Z\}/4\backslash mathbb\{Z\}$ 0 und 2 sowie 1 und 3 die gleichen Quadrate. Zweitens interessiert man sich nur für solche Quadrate, die selbst Quadrate sind. Diesen Umstand kann man sich mithilfe der Definition der BBS-Generatorfolge verdeutlichen.

Zusammenfassend gilt daher: Der Generator ist sicher, weil die Umkehrung des Quadrierens in einem Restklassenring
$\backslash mathbb\{Z\}/n\backslash mathbb\{Z\}$ mit zusammengesetztem Modul n genauso schwierig ist wie die
Faktorisierung von n.

       VIDEO-NEWS UND ANGEBOTE