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: ${\displaystyle 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 ${\displaystyle N=pq}$ met p en q beide priem. Daarbij is het de bedoeling om een klein nulpunt ${\displaystyle x_{0}}$ van de polynoom te vinden. Daarmee wordt bedoeld dat het getal ${\displaystyle 0<x_{0}\ll N}$.

De idee achter de methode

Met de methode van Coppersmith willen we een wortel ${\displaystyle x_{0}}$ van een polynoom ${\displaystyle F(x)}$ van graad n vinden modulo N. De polynoom schrijven we als ${\displaystyle F(x)=\sum {_{i}\ a_{i}x^{i}}}$ modulo N, met ${\displaystyle a_{i}\in \mathbb {Z} /N}$. De wortel die we zoeken moet een geheel getal zijn, maar de polynoom is gedefinieerd over ring ${\displaystyle \mathbb {Z} /N}$. We willen de polynoom daarom herschrijven zodat we ${\displaystyle x_{0}}$ vinden als nulpunt van een polynoom h(x), zonder daarbij rekening te houden met modulo rekening. Daarom kiezen we een bovengrens voor ${\displaystyle 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 ${\displaystyle g_{jk}:=x^{j}(F(x))^{k}N^{m-k}}$ met k=0, 1, ..., m. Merk op dat als ${\displaystyle x_{0}}$ een wortel is van F(x), dan is dat getal ook wortel van ${\displaystyle g_{jk}}$ modulo ${\displaystyle N^{m}}$. Wanneer we nu h(x) kiezen als een lineaire combinatie met gehele coëfficiënten van verschillende polynomen ${\displaystyle g_{jk}}$, vinden we dat ${\displaystyle x_{0}\leq X<N^{m}}$ een nulpunt modulo ${\displaystyle N^{m}}$ van deze polynoom is.

Met de stelling van Howgrave-Graham kunnen we met zekerheid zeggen dat ${\displaystyle h(x_{0})=0\in \mathbb {Z} }$, tenminste als we kunnen aantonen dat ${\displaystyle h(x_{0})\equiv 0}$ modulo ${\displaystyle N^{m}}$ en ${\displaystyle ||h(xX)||:={\sqrt {\sum {_{i}\ b_{i}X^{i}}}}<{\frac {N^{m}}{\sqrt {\omega }}}}$ met ${\displaystyle \omega }$ het aantal coëfficiënten ongelijk aan nul in ${\displaystyle 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 ${\displaystyle g_{jk}(x)}$, echter weten we dan niet zeker of de gereduceerde basis aan de voorwaarde ${\displaystyle ||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.^[1]

Vereenvoudigde methode

Om een nulpunt ${\displaystyle 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:

${\displaystyle 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 ${\displaystyle x_{0}}$ modulo ${\displaystyle 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: ${\displaystyle {\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 ${\displaystyle N^{m}}$. Maar omdat we vaststelden dat geldt voor de te vinden oplossing ${\displaystyle x_{0}}$ dat ${\displaystyle |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 ,${\displaystyle F^{2}}$):

${\displaystyle 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 ${\displaystyle {\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".

1. (en) TU/e, Ellen Jochemsz, "Cryptanalysis of RSA variants using small roots of polynomials" (pdf), 4 oktober 2007. Gearchiveerd op 25 maart 2023.