matematikk.net

Heisann, jeg har et problem med å finne Hidden Key S, og lurer på om noen kan lære meg det!

"Konstruksjonen av nøkkler"

1. Velg to primtall p og q .
2. Regn ut z = p × q og Ø = ( p -1) × (q -1)
3. Velg et tall n slik at gcd(n,f ) =1
4. Beregn det unike tallet s som er slik at n * s mod f =1 og (0 < s <f) .
5. Offentlig nøkkel: (z,n) . Skjult nøkkel: (z, s) .

Man får oppgitt tallene p og q. det må være 2 primtall. Deretter finner man lett Z og Ø ved å følge formellen! "n", får man som oftest valgt for seg.

p = 7 , q = 11.

Z = 77
Ø = 60
n = 13 .. gcd(13,60) = 1.

Hvordan finne Public key og hidden key?

Her er et bilde av forelesnings notatene til faglærer, men jeg forstår ikke hvordan han kom fram til Hidden Key S. Det jeg trenger er public key, og Hidden key, kan dere hjelpe meg å finne de to? Forklar hva dere gjør også.

http://bildr.no/view/306488

Du har [tex]13s\equiv 1 mod(60)[/tex] og skal finne [tex]s[/tex].

Da er [tex]13s+60t=1[/tex] og man skal finne et heltallspar [tex](s,t)[/tex] som løser denne diofantiske ligningen. Siden [tex]gcd(13,60)=1[/tex] har ligningen løsning.

60=4*13+8
13=8+5
8=5+3
5=3+2
3=2+1

Dette er Euklids algoritme. Les mer om den på wikipedia. Målet er at du kan gå baklengs og starte med 1 og skrive 1 på formen til den ligningen du skal finne heltallsløsning på. Når du har funnet ett bestemt løsningspar har du nemlig funnet alle. Man kan generere alle andre på en lettvint måte...

Start med 1 og den siste linja i algoritmen.
Da er 1=3-2. Videre er 3=8-5 og 2=5-3, så 1=8-5-(5-3) etc.

Da komme du frem til at 1=5*60+(-23)*13. Sammelign med den opprinnelige ligninga. Da ser du at s= -23, og siden vi regner i mod(60) er -23= -23+60= 37. Så s=37

Ser ut som om foreleser går veien om euklids algoritme og euklids omvendte algoritme. En enklere måte er vel å løse den diofantiske likninga direkte, og finne hidden key, s.
DVS

n = 13 og [tex]\,\,\phi=60[/tex]

[tex]nx\equiv 1 \text (mod\,\phi)[/tex]

[tex]13x\equiv 1 \text (mod\,60)[/tex]

[tex]13x\equiv 1 \text\,+\,8\cdot 60 (mod\,60)\equiv 481 (mod 60)[/tex]

[tex]x\equiv 37 \text (mod\,60)[/tex]

s = 37

Janhaa skrev:Ser ut som om foreleser går veien om euklids algoritme og euklids omvendte algoritme. En enklere måte er vel å løse den diofantiske likninga direkte, og finne hidden key, s.

I dette tilfellet går jo dette greit fordi talla er så små, vanligvis når man holder på med dette er det med tall av en helt annen størrelsesorden.