Kongurenser via RSA

[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.

[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].

[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

[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)

[Nebuchadnezzar]

Skrev bare av feil her inne, regnet riktig på papiret... Dumt av meg.

Kunne du se over en gang til ?

[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.

[Nebuchadnezzar]

Da klarte jeg og skrive det feil inn på kalkisen 4 ganger =)

[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:)

[Vektormannen]

Off topic, men hvorfor bruker du texify i stedet for den innebygde tex-funksjonen?

[Fibonacci92]

fordi jeg ikke visste om den innebygde texfunksjonen:P

[tex]\frac{a}{b}[/tex]

nice!