Bloom-Blum-Päls-algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 4 november 2021; kontroller kräver 4 redigeringar .

Algoritm Blum - Blum - Shub ( Eng. Algorithm Blum - Blum - Shub , BBS) är en pseudo-slumptalsgenerator som föreslagits 1986 av Lenore Blum , Manuel Blum och Michael Shub .

BBS ser ut så här:

x_{n+1}=x_n^2\;\bmod\;M,

där är produkten av två stora primtal och . Vid varje steg av algoritmen erhålls utsignalen från antingen paritetsbiten eller en eller flera minst signifikanta bitar . $M=pq$ $sid$ $q$ $x_{n}$ $x_{n}$

De två primtalen, och , måste båda vara kongruenta med 3 modulo 4 (detta garanterar att varje kvadratisk rest har en kvadratrot , som också är en kvadratisk rest ) och den största gemensamma divisorn gcd måste vara liten (detta ökar cykellängden). $sid$ $q$ $(p-1,q-1)$

En intressant egenskap hos denna algoritm är att för att erhålla det inte är nödvändigt att beräkna alla tidigare siffror om initialtillståndet för generatorn och siffrorna och är kända . -th värde kan beräknas "direkt" med hjälp av formeln: $x_{n}$ $n-1$ $x_{0}$ $sid$ $q$ $n$

x_{n}=x_{0}^{2^{n}{\bmod {\lambda }}(M)}\;{\bmod {\;}}M

var är Carmichael-funktionen : i detta fall den minsta gemensamma multipeln av talen och . $\lambda$ $\lambda (M)=\lambda (pq)=lcm(p-1,q-1)$ $p-1$ $q-1$

Tillförlitlighet

Denna generator är lämplig för kryptografi , men inte för simulering eftersom den inte är tillräckligt snabb. Den har dock en ovanligt hög hållbarhet, vilket tillhandahålls av kvaliteten på generatorn baserat på beräkningskomplexiteten i nummerfaktoriseringsproblemet . När primtalen väljs noggrant, och bitar av varje är utdata, så växer gränsen som tas så snabbt, och att beräkna utdatabitarna blir lika svårt som faktorisering . $O(\log\logM)$ $x_{n}$ $M$ $M$

Om faktorisering av heltal är så svårt (som det är tänkt att vara), så kommer en stor BBS att ha en utdata fri från alla icke-slumpmässiga mönster som kan detekteras med tillräcklig beräkning. En snabb algoritm för faktorisering är dock möjlig, och därför är BBS inte garanterat tillförlitlig. $M$

Anteckningar

Litteratur

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.
Lenore Blum, Manuel Blum och Michael Shub. "Jämförelse av två pseudo-slumptalsgeneratorer", Advances in Cryptology: Proceedings of Crypto '82 . Tillgänglig som PDF .
Pascal Junod, "Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator", augusti 1999. PDF-fil på 21 sidor
Martin Geisler, Mikkel Krøigård och Andreas Danielsen. "About Random Bits", december 2004. Tillgänglig som PDF och Gzipped Postscript .
Slumpmässighetsrekommendationer för säkerhet - RFC 1750 .