Generator Blum-Blum-Shub (BBS) nosi nazwę od nazwisk trzech jego wynalazców. Niekiedy bywa on też nazywany generatorem reszt kwadratowych. Podstawą teoretyczną jego działania jest obliczanie reszt kwadratowych modulo n. Generator ten działa w taki sposób, że należy wziąć dwie liczby pierwsze p i q, które są kongruentne względem 3 modulo 4. Iloczyn tych liczb n=p^.q jest liczbą całkowitą Bluma. Następnie należy wybrać inną losową liczbę całkowitą x, względnie pierwszą z n, i obliczyć:

x₀=x² mod n

Liczba ta jest wartością początkową dla generatora. Rozpoczyna się proces wytwarzania binarnego ciągu losowego. Elementem o numerze i w ciągu pseudolosowym jest najmniej znaczący bit liczby x_i, przy czym

x_i=x²_i-1 mod n

Jeżeli są znane wartości p i q, to bit i może być obliczony bezpośrednio ze wzoru

x_i=x₀^{(2i) mod ((p-1)(q-1))} mod n

Właściwość ta oznacza, że można wykorzystać ten silny kryptograficznie generator pseudolosowego ciągu bitów jako strumieniowy system kryptograficzny dla plików o dostępie bezpośrednim.

Bezpieczeństwo tego algorytmu opiera się na trudności faktoryzacji liczby n. Dla danego ciągu wytworzonego przez BBS kryptoanalitycy nie mogą przewidzieć wartości kolejnego bitu w ciągu lub wartości bitu poprzedniego.

Generator BBS jest względnie powolny i w związku z tym niezbyt użyteczny dla szyfrów strumieniowych, jednak przy zastosowaniach wymagających silnego zabezpieczenia, takich jak wytwarzanie kluczy, jest on najlepszy.

Blum Blum Shub to generator liczb pseudolosowych (PRNG) postaci:

gdzie x_n to kolejne stany, zaś M to iloczyn dwóch dużych liczb pierwszych dających w dzieleniu przez 4 resztę 3, i mających możliwie mały
, a φ jest funkcją Eulera (co zapewnia długi cykl). Wynikiem generatora jest kilka ostatnich bitów x_n.

Funkcja φ Eulera (inaczej tocjent) - funkcja matematyczna, która każdej liczbie naturalnej n przypisuje liczbę tych liczb względnie pierwszych z n, które są mniejsze od n. Na przykład, φ(6)=2, bo spośród liczb naturalnych mniejszych od 6 tylko liczby 1 i 5 są względnie pierwsze z 6.

Wzór ogólny

Można udowodnić, że dla każdej liczby naturalnej n prawdziwy jest wzór:

gdzie
są wszystkimi dzielnikami pierwszymi n.

Wartość dla liczb pierwszych

Jeżeli p jest liczbą pierwszą to każda z liczb 1,2,...p-1 jest względnie pierwsza z p, więc:

Wartość dla liczb względnie pierwszych

Jeżeli liczby całkowite m i n są względnie pierwsze, to

---