Machtsgenerator

Een machtsgenerator is een pseudotoevalsgenerator, een algoritme dat pseudotoevalsgetallen produceert. Dat zijn getallen die deterministisch worden voortgebracht en dus niet echt willekeurig zijn, maar veel eigenschappen van toevalsgetallen hebben.

Definitie

Een machtsgenerator is een algoritme voor het berekenen van de rij $(u_n)$ via de recursieve relatie:

$u_n=u_{n-1}^e(\mathrm{mod}m)$;

Daarin zijn $u_0$ (de startwaarde), $m$ en $e$ gehele getallen zodanig dat ggd$(u_0,m)=1$.

Voor de gegenereerde getallen geldt: $0\le u_n\le m-1$.

De machtsgenerator heeft veel toepassingen op het gebied van cryptografie. Daarnaast zijn pseudotoevalsgetallen ook van belang voor numerieke simulaties van Monte Carlo-methoden, numerieke analyse, het testen van computerchips voor gebreken en de programmering van speelautomaten. Verschillende toepassingen vereisen verschillende eigenschappen van de getallen.

Complexiteit

Voor een machtsgenerator met $m$ een priemgetal en periode $T$ kan de lineaire complexititeit L afgeschat worden door:

$L\ge \frac{T^2}{m-1}$.

RSA-generator

Een bijzonder geval van een machtsgenerator is de RSA-generator. Als $d$ zodanig gekozen wordt dat $\mathrm{ggd}(e,\phi (m))=1$, met $\phi (m)$ de Eulerfunctie, wordt de generator RSA-generator genoemd. Het is aangetoond dat als de periode $T$ van de rij $(u_n)$ voldoet aan de ongelijkheid $T\le m^{3/4+\epsilon }$ voor een gegeven $e>0$, dan zijn de fracties $(u_n/m{)}_{n=1}^T$ uniform verdeeld op het interval [0,1].

Blum-Blum-Shub generator

Een ander speciall geval is de Blum-Blum-Shub-generator, Als $e=2$, wordt de generator Blum-Blum-Shub-generator genoemd, bedacht door Lenore Blum, Manuel Blum and Michael Shub in 1986. Deze generator is van de vorm $u_n\equiv u_{n-1}^2(\mathrm{mod}m)$, met $m=pq$ het product van twee grote priemgetallen $p$ en $q$. Bij elke stap van het algoritme wordt een uitkomst verkregen uit het berekende getal $u_n$. Die uitkomst is meestal de pariteitsbit van $u_n$ of een of meer van de minst significante bits van $u_n$.

De beginwaarde $u_0$ moet een geheel getal zijn ongelijk aan 1 en $\mathrm{ggd}(u_0,m)=1$. De priemgetallen $p$ en $q$ moeten beide modulo 4 congruent zijn met 3 (dit garandeert dat elk kwadratisch residu een wortel heeft die ook een kwadratisch residu is) en $\mathrm{ggd}(\phi (p-1),\phi (q-1))$ moet klein zijn (dit maakt de cycluslengte groot).

Een interessant kenmerk van de Blum-Blum-Shub-generator is de mogelijkheid om elke $u_i$ rechtstreeks te berekenen (via de stelling van Euler).

Beveiliging

De Blum-Blum-Shub-generator is niet geschikt voor gebruik in simulaties, alleen voor cryptografie, omdat het algoritme erg traag is. Het heeft wel een ongewoon sterke beveiliging; de kwaliteit van de generator hangt af van de rekentechnische moeilijkheid van het ontbinden in priemfactoren.

Als factorisatie in priemfactoren moeilijk is (zoals wordt vermoed), zou de Blum-Blum-Shub-generator met grote $m$ een output moeten hebben vrij van niet-willekeurige patronen die kunnen worden ontdekt met niet te veel berekeningen. Zo lijkt het net zo veilig als andere encryptietechnologieën gebonden aan de factorisatieprobleem, zoals RSA-encryptie.

Lineaire complexiteit

Neem aan dat de rij $(u_n)$ periodiek is met periode $T$. Dan geldt voor de lineaire complexiteit $L$ van de Blum-Blum-Shub-generator de afschatting:

$L\ge T\phi (m{)}^{-1/2}$.

Met behulp van van de Chinese reststelling kan men zien dat de lineaire complexiteit modulo een samengesteld getal $m$ gelijk is aan de grootste lineaire complexiteit modulo alle priem machtsdelers van $m$. Dit geldt inderdaad als $m=m_1{m}_2$, met $m_1,m_2\ge 2$ relatief priem en als een zekere oneindige rij $(s_n)$ voor $n=1,2,\dots$ voldoet aan de congruenties:

$S_{n+L_1}\equiv a_{L_1-1}{s}_{n+L_1-1}+\dots +a_0{S}_n(\mathrm{mod}{m}_1)$

en

$S_{n+L_2}\equiv b_{L_2-1}{s}_{n+L_2-1}+...+b_0{S}_n{(\mathrm{mod}m)}_2$

We zetten $b_k=a_k=0$ voor $k<0$ en definiëren vervolgens integers

$0\le c_0,\dots ,c_{L-1}\le m-1,$ met $L=\mathrm{m}\mathrm{a}\mathrm{x}\{L_1,L_2\}$

vanuit de congruenties:

$c_{L-j}\equiv a_{L1-j}(\mathrm{mod}{m}_1)$ en $c_{L-j}\equiv b_{L2-j}(\mathrm{mod}{m}_2)$.

Dan geldt dat $S_{n+L}\equiv c_{L-1}{s}_{n+L-1}+\dots +c_0{S}_n(\mathrm{mod}m),n=1,2,\dots$

Daarom geldt dat voor een Blum-integer $m=pq$ met $p\equiv q\equiv m^{1/2}$ dat de lineaire complexiteit $L$ de volgende formule niet overschrijdt:

$L=\mathrm{m}\mathrm{a}\mathrm{x}\{L_p,L_q\}\le \mathrm{m}\mathrm{a}\mathrm{x}\{T_p,T_q\}\le \mathrm{m}\mathrm{a}\mathrm{x}\{p,q\}=(1+o(1))m^{1/2},$

met $L_p$ en $T_p$ de lineaire complexiteit en de periode modulo $p$ en $L_q$ en $T_q$ de lineaire complexiteit en de periode modulo $q$.

In het meest interessante geval voor toepassing, namelijk als de periode $T$ van orde $m$ is, geven bovenstaande formules dat $L$ van grootst mogelijke orde $\sqrt{m}$ is.

Referenties

Cusick, T.W., C. Ding, and A. Renvall, Stream ciphers and number theory, Elsevier (2004)

Shparlinski, I., On the linear complexity of the power generator, School of MPCE (2001)