Page 1 of 1
Kongurenser via RSA
Posted: 04/12-2011 15:25
by Nebuchadnezzar
Forstår enda ikke helt hvordan jeg skal løse kongurenser ved hjelp av RSA, mistet litt notater og så her sitter jeg.
[tex]x^65 \equiv 6 \pmod{133} [/tex]
Hvor hintet er RSA [tex]7 \cdot 19[/tex]
Utifra det lille jeg husker, representerer likningen ovenfor hvordan en dekrypterer en melding?
Husker også noe vagt om å finne phi, som gir en ny likning
[tex]\phi{133} = (7-1)(19-1) = 6\cdot 18 = 60+48 = 108[/tex]
Her er [tex]e=65[/tex]
[tex]de = 1 \pmod{\phi(n)}[/tex]
[tex]65d = 1 \pmod{133}[/tex]
Men forstår egentlig ikke så mye hva som foregår her, så om noen kunne forklart hadde det vært supert.
Posted: 04/12-2011 15:30
by Vektormannen
Som hintet sier så kan du se på [tex]x^{65} \equiv 6[/tex] som at vi har kryptert medlingen x, og den krypterte meldingen ble 6. Så for å finne meldingen x kan vi dekryptere den krypterte meldingen 6. For å dekryptere så trenger vi den hemmelige nøkkelen d. Da vil [tex]x \equiv 6^d \ (\text{mod} \ 133)[/tex].
For å finne d så må du bruke den kongruensen du nevner. Så du ender opp med [tex]65d \equiv 1 \ (\text{mod} \ 108)[/tex].
Posted: 04/12-2011 16:05
by Nebuchadnezzar
Løser jeg den via euler kommer jeg frem til at
[tex]5 \cdot 65 - 3 \cdot 108 = 1[/tex]
Altså er [tex]d = 5[/tex]
[tex]x \equiv 6^5 \pmod{133}[/tex]
[tex]x \equiv 2 \pmod{133}[/tex]
Tror kanskje dette ble feil, mmm
Posted: 04/12-2011 16:08
by Vektormannen
Du har feil modulus. Det er kun når man bestemmer e og d at man bruker [tex]\phi(n)[/tex]. Når man krypterer og dekrypterer så bruker man n. ([tex]\phi(n)[/tex] skal jo ikke være kjent for alle heller, for da er det lett å finne dekrpyteringsnøkkelen)
Posted: 04/12-2011 16:10
by Nebuchadnezzar
Skrev bare av feil her inne, regnet riktig på papiret... Dumt av meg.
Kunne du se over en gang til ?
Posted: 04/12-2011 16:13
by Vektormannen
Det meste ser jo rett ut, men det skal vel bli 62, ikke 2? [tex]6^5 - 58 \cdot 133 = 62[/tex] i følge kalkisen.
Posted: 04/12-2011 16:16
by Nebuchadnezzar
Da klarte jeg og skrive det feil inn på kalkisen 4 ganger =)
Posted: 04/12-2011 16:26
by Fibonacci92
Løser først ligningen:
Finner at d = 5, og dermed at:
Som vil si at:
Er slik jeg tenker på denne oppgaven i alle fall:)
Posted: 04/12-2011 16:30
by Vektormannen
Off topic, men hvorfor bruker du texify i stedet for den innebygde tex-funksjonen?
Posted: 04/12-2011 16:34
by Fibonacci92
fordi jeg ikke visste om den innebygde texfunksjonen:P
[tex]\frac{a}{b}[/tex]
nice!