Coppersmith-methode

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De Coppersmith methode is een factorisatie methode, voornamelijk toegepast in cryptografie. Don Coppersmith heeft meerdere bijdragen geleverd aan de cryptografie, waaronder twee stellingen in 1996 en 1997.

Inleiding[bewerken]

Factoriseren bij kleine getallen is vrij eenvoudig te doen door van alle priemgetallen, kleiner dan de wortel van het te factoriseren getal, te controleren of het een deler is (bijvoorbeeld: 12=2^23). Dat wordt meer werk als de getallen groter worden.

In de cryptografie is het gebruikelijk om te werken in een ring, namelijk we rekenen modulo een getal N.

De Coppersmith methode is een manier om nulpunten te vinden van een polynoom in een ring modulo een getal N=pq met p en q beide priem. Daarbij is het de bedoeling om een klein nulpunt te vinden, x_0 van het polynoom, daarmee wordt bedoeld dat het getal 0< x_0\ll N.

De idee achter de methode[bewerken]

Met de methode van Coppersmith willen we een wortel x_0 van een polynoom F(x) van graad n vinden modulo N. De polynoom schrijven we als F(x)=\sum{_i\ a_ix^i} modulo N, met a_i\in\mathbb{Z}/N. De wortel die we zoeken moet een geheel getal zijn, maar de polynoom is gedefinieerd over ring \mathbb{Z}/N. We willen de polynoom daarom herschrijven zodat we x_0 vinden als nulpunt van een polynoom h(x), zonder daarbij rekening te houden met modulo rekening. Daarom kiezen we een bovengrens voor x_0,\ X. Vervolgens zullen we daadwerkelijk de polynoom herschrijven.

Om de voornoemde polynoom h(x) te construeren kiezen we een getal m en vinden de set van polynomen g_{jk}:=x^j(F(x))^kN^{m-k} met k=0, 1, ..., m. Merk op dat als x_0 een wortel is van F(x), dan is dat getal ook wortel van g_{jk} modulo N^m. Wanneer we nu h(x) kiezen als een lineaire combinatie met gehele coëfficiënten van verschillende polynomen g_{jk}, vinden we dat x_0\leq X<N^m een nulpunt modulo N^m van deze polynoom is.

Met de stelling van Howgrave-Graham kunnen we met zekerheid zeggen dat h(x_0)=0 \in\mathbb{Z}, tenminste als we kunnen aantonen dat h(x_0)\equiv 0 modulo N^m en ||h(xX)||:=\sqrt{\sum{_i\ b_iX^i}}<\frac{N^m}{\sqrt{\omega}} met \omega het aantal coëfficiënten ongelijk aan nul in h(x):=\sum b_ix^i (ook wel eentermen genoemd).

Dus als we in staat zijn om h(x) zo te construeren dat hij aan de voorwaarden voldoet van de stelling van Howgrave-Graham, hoeven we slechts h(x)=0 op te lossen over de gehele getallen. Maar hoe precies vinden we een geschikte h(x). Een geschikt polynoom kunnen we vinden door het Gram-Schmidtmethode toe te passen op een bepaalde set g_{jk}(x), echter weten we dan niet zeker of de gereduceerde basis aan de voorwaarde ||h(xX)||:=\sqrt{\sum{_i\ (b_iX^i)^2}}<\frac{N^m}{\sqrt{\omega}} voldoet. Dat is de reden om het LLL-algoritme toe te passen, omdat we dan verzekerd zijn dat ||h(xX)|| klein genoeg is.[1]

Vereenvoudigde methode[bewerken]

Om een nulpunt x_0<X te vinden van een polynoom F(x) van graad n modulo N, schrijven we de uitdrukking F(x) als volgt op als een matrix: A=\begin{pmatrix}N&0&\cdots&0&0\\0&N X&\cdots&0&0\\\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&\cdots&N X^{n-1}&0\\a_0&a_1 X&\cdots&a_{n-1}X^{n-1}&X^n.\end{pmatrix}

Hierin is elke rij gelijk aan een polynoom met wortel x_0 modulo N.

Deze matrix vatten we op als een set basises waarop we het LLL-algoritme toepassen. We vinden dan vectoren waarbij de eerste rij van de volgende vorm is: \begin{pmatrix}b_0&b_1 X&\cdots&b_nX^n\end{pmatrix}. Vat deze rij op als de uitdrukking h(X) en vervang hierin de X voor de variabele x.

De nulpuntvergelijking van de nieuwe polynoom h(x) kan worden opgelost met het Newton-Raphson-algoritme. Hierbij hoeft niet modulo N gerekend te worden, maar wel modulo N^m. Maar omdat we vaststelden dat geldt voor de te vinden oplossing x_0 dat |x_0|<|X|<N^m, hoeven we hier geen rekening meer mee te houden.

De methode[bewerken]

Om te zorgen dat met het LLL-algoritme een gereduceerde basis gevonden wordt, is het soms nodig om de matrix uit te breiden. Daarbij is de laatste rij een macht van het polynoom F en alle kleinere machten van F verschijnen met geschikte machten van N.


De nieuwe matrix ziet er bijvoorbeeld als volgt uit (laatste rij is ,F^2):

A=\begin{pmatrix}N^2&0&\cdots&0&0&\cdots&0&0\\
0&N^2 X&\cdots&0&0&\cdots&0&0\\
\vdots&\vdots&\ddots&\vdots&\vdots&\cdots&\vdots&\vdots\\
0&0&\cdots&N^2 X^{n-1}&0&\cdots&0&0\\
Na_0&Na_1 X&\cdots&Na_{n-1}X^{n-1}&NX^n&\cdots&0&0\\
0&Na_0 X&\cdots&Na_{n-2}X^{n-1}&Na_{n-1}X^{n}&\cdots&0&0\\
\vdots&\vdots&\ddots&\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&\cdots&Na_0 X&Na_1 X&\cdots&Na_{n-1}X^{n}&0\\
a_0^2&2a_0a_1 X&\cdots&(\cdots)X^{n-1}&(\cdots)X^n&\cdots&2a_{n-1}X^{2n-1}&X^{2n}\end{pmatrix}

de eerste vector van de LLL gereduceerde basis is nu van de vorm \begin{pmatrix}b_0&b_1 X&\cdots&b_{2n}X^{2n}\end{pmatrix} Vervang hierin de X voor de variabele x en beschouw de uitdrukking als een polynoom h(x) van graad 2n. Wederom wordt met het Newton-Raphson-algoritme een nulpunt bepaald, zonder modulo N te hoeven rekenen.[2]

Zie ook[bewerken]

Voor Wikipedia-artikelen in het Engels waarvan nog geen Nederlandse versie is:

Externe link[bewerken]

Bronnen, noten en/of referenties