RSA-kryptering

Hej!

Jag undrar om jag kan bestämma den privata nyckeln d såhär:

Dekrypterat meddelande: $x = y^{d} (m o d n)$

Krypterat meddelande: $y = x^{e} (m o d n)$

Jag vet att e=169, n=100619 (offentliga nycklar).

n = p*q , där p och q är två stora primtal. Det ger p=239 och q=421.

a: (p-1)*(q-1)= 99 960

Sedan bestäms den privata nyckeln d: e × d ≡ 1 (mod a)

Det ger den diofantiska ekvationen:

$d = \frac{99 960 \times m + 1}{169}$

Om m = 459 är d=271 489.

Detta verkar stämma.

Ex. Om meddelandet i klartext är "72", så ger det det krypterade meddelandet y= $72^{169} (m o d 100619)$ = 27565.

Det dekrypterade meddelandet blir: $x = 27565^{271489} (m o d 100619) = 72$

Men kan jag vara säker på att d verkligen är 271 489? Diofantiska ekvationen kan väl ha fler lösningar? Kan det finns fler privata nycklar? Kan d vara negativ?

Mvh KriAno

Enligt länk ska $1 < d < a$ . Därför är $d = 271489 > 99960$ större än vad vi söker. Just denna diofantiska ekvation kommer ha oändligt antal lösningar enligt Bézouts identitet och utökade Euklides algoritm. Kan förklara varför om det önskas. Enligt WolframAlpha är den generaliserade lösningen $d = 99960 n + 71569$ och $m = 169 n + 121$ för alla heltal $n$ . För att hitta detta behöver man använda utökningen av Euklides algoritm. Alltså kan $d$ vara negativt men det är inte vad vi söker.

Snerf skrev:
Enligt länk ska $1 < d < a$ . Därför är $d = 271489 > 99960$ större än vad vi söker. Just denna diofantiska ekvation kommer ha oändligt antal lösningar enligt Bézouts identitet och utökade Euklides algoritm. Kan förklara varför om det önskas. Enligt WolframAlpha är den generaliserade lösningen $d = 99960 n + 71569$ och $m = 169 n + 121$ för alla heltal $n$ . För att hitta detta behöver man använda utökningen av Euklides algoritm. Alltså kan $d$ vara negativt men det är inte vad vi söker.

Tack för svar!

Skulle vara jättesnällt om du kunde förklara!

Bézouts identitet säger att om $a x + b y = g c d (a, b)$ där $a, b$ är heltal kan man alltid hitta ett heltalspar $(x_{0}, y_{0})$ som uppfyller $a x_{0} + b y_{0} = g c d (a, b)$ . Bevis finns till detta men jag utelämnar det för enkelhetens skull. Vi kan hitta en lösning genom att använda Euklides algortim baklänges. Algoritmen förklaras mycket bra i denna video https://youtu.be/FjliV5u2IVw.

Om $(x_{0}, y_{0})$ är en lösning till $a x + b y = g c d (a, b)$ så är alla heltalslösningar på formen $x = x_{0} + n \cdot \frac{b}{g c d (a, b)}, y = y_{0} - n \cdot \frac{a}{g c d (a, b)}$ .

Bevis:

Givet lösningen $(x_{0}, y_{0})$ då är

$a x + b y = a x_{0} + b y_{0} \leftrightarrow a (x - x_{0}) = - b (y - y_{0}) \leftrightarrow \frac{a}{g c d (a, b)} (x - x_{0}) = \frac{- b}{g c d (a, b)} (y - y_{0})$

Eftersom $\frac{a}{g c d (a, b)}$ och $\frac{b}{g c d (a, b)}$ är relativt prima finns det $n$ så att $x - x_{0} = n \cdot \frac{b}{g c d (a, b)}$ och $y - y_{0} = n \cdot \frac{- a}{g c d (a, b)}$ ,

vi kan lösa för $x$ och $y$ vilket slutför beviset.

Om du vill kan du nu testa att komma fram till en allmän lösning till din diofantiska ekvation, $169 d - 99960 m = 1$ .

Hur Snerf skrev:
Enligt länk ska $1 < d < a$ . Därför är $d = 271489 > 99960$ större än vad vi söker. Just denna diofantiska ekvation kommer ha oändligt antal lösningar enligt Bézouts identitet och utökade Euklides algoritm. Kan förklara varför om det önskas. Enligt WolframAlpha är den generaliserade lösningen $d = 99960 n + 71569$ och $m = 169 n + 121$ för alla heltal $n$ . För att hitta detta behöver man använda utökningen av Euklides algoritm. Alltså kan $d$ vara negativt men det är inte vad vi söker.

Hur kommer det sig att jag får rätt när d > a? Då d=99960n+71569, betyder det att det finns flera privata nycklar och inte bara 1 som fungerar?

Svara

Visa senaste svar