Coppersmith-methode

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

Inleiding

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 erdoor is te delen, bijvoorbeeld: $12=2^{2}3$. Dat wordt meer werk als de getallen groter worden.

In de cryptografie is het vaak nodig om modulair rekenen te gebruiken, rekenen modulo een getal N.

De Coppersmith methode is een manier om nulpunten te vinden van een polynoom modulo een getal $N=pq$ met p en q beide priem. Daarbij is het de bedoeling om een klein nulpunt $x_{0}$ van de polynoom te vinden. Daarmee wordt bedoeld dat het getal $0<x_{0}\ll N$.

De idee achter de methode

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_{i}x^{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))^{k}N^{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_{i}X^{i}}}}<{\frac {N^{m}}{\sqrt {\omega }}}$ met $\omega$ het aantal coëfficiënten ongelijk aan nul in $h(x):=\sum b_{i}x^{i}$.

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 geschikte 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_{i}X^{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.

Vereenvoudigde methode

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&NX&\cdots &0&0\\\vdots &\vdots &\ddots &\vdots &\vdots \\0&0&\cdots &NX^{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 verzameling 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_{n}X^{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

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 de 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_{0}a_{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.

Externe link

• (en) Algorithmic Cryptanalysis Blog, "Coppersmith’s small root algorithm and factoring related problems".