Den digitale signatur - anvendt talteori og kryptologi



Opgave 8

Elliptiske kurver modulo p

At to tal a og b har samme rest ved division med p skrives

a = b (mod p )

1.

Bestem samtlige løsninger (x,y ) modulo 5 til ligningen

y 2 = x 3 - x + 1

Når en meddelelse skal repræsenteres som et punkt på kurven, omsættes meddelelsen til at tal, og der vælges et punkt, hvis x -koordinat er lig med eller tæt på dette tal. For at finde y -koordinaten indsættes i højresiden af kurveligningen og regnes modulo p, hvilket giver en ligning af typen

y 2 = c (mod p ) (12)

Resultatet i den følgende opgave kan bruges til at afgøre om (12) har en løsning:

2.

Benyt Fermats lille sætning til at vise at

(13)

hvis c = k 2 (mod p ).

Hvis (12) har løsninger kan en løsning bestemmes ved brug af resultatet i den følgende opgave, når p har rest 3 ved division med 4.

3.

Benyt Fermats lille sætning til at vise at

c (p+1)/4 (14)

er løsning til (12) hvis (13) er opfyldt. Bemærk at eksponenten i (14) kun er et helt tal når p har rest 3 ved division med 4.

4.

Vis at ligningen

y 2 = 6 (mod 23)

har en løsning og bestem en løsning.

Ud fra den geometriske beskrivelse af addition af punkter kan man udlede følgende koordinatudtryk. Lad P (x 1 , y 1) og Q (x 2 , y 2) og P + Q = (x 3 , y 3) så er

(x 3 , y 3) = (s 2 -x 1 - x 2 , - y 1 + s(x 1 - x 3)) (15)

Her er s hældningskoefficienten til linjen, og formlen for s afhænger af om er sekantline (P ≠ Q ) eller tangentlinie (P =Q ):

sekantlinie: tangentlinie:

Når der regnes modulo et tal p, skal p være et primtal for at division kommer til at fungere fornuftigt.

5.

Bestem , som er løsningen til ligningen 5 ·x = 1 modulo 17. Udregn dernæst .