Studieretningsprojekt/-opgave (SRP/SRO)
Bevis for RSA
Hej!
Jeg sidder med SRP og skriver om krypteringen.
Jeg har forsøgt, at bevise RSA-koden, men ville høre om der evt. var en der gad og tjekke om det er rigtigt, det jeg har skrevet, da jeg er meget i tvivl.
Det gælder for alle hele vilkårlige tal, at (m (mod n))(mod n)=m (mod n).
Derfor må der for alle 0<m<n gælde, at
m→me (mod n)→[me (mod n) ]d (mod n)= med (mod n)= m
Det vil sige, at: med (mod n)= m, hvor e og d er beregnet som tidligere i rapporten (afsnit: kryptering vha. RSA).
Det antages, at (m,n)=1. Ifølge Eulers sætning gælder der da, at med (mod n)≡med(mod φ(n)) (mod n), men da ed (mod φ(n)) giver 1 fås:
m(ed (mod φ(n)) (mod n)=m1 (mod n)=m (mod n)
Fra Eulers sætning vides det, at hvis (m,n)=1 så gælder, at m(φ(n))≡1 (mod n).
Dermed fås, at
med (mod n)=m (mod n)
Svar #1
03. december 2011 af peter lind
Jeg kender RSA rimelig godt; men det du skriver kan jeg ikke få hoved eller hale på. I bedste fald skal du ændre formuleringen drastisk.
Svar #2
04. december 2011 af Micha1 (Slettet)
Okay, tak!
Jeg har forsøgt at omformulere det. Er det her bedre?
Vi ønsker nu at bevise RSA-kryptosystemet, hvor det for alle 0<m<n gælder, at:
m → me (mod n) → [me (mod n) ]d (mod n) = med (mod n) = m
m → me (mod n) ; opskriver formlen for enkryptering
→ [me (mod n) ]d (mod n) ; skriver formlen for dekryptering, hvor c=m^e (mod n)
→ med (mod n)=m ; ganger d ind i parentesen
Det vil sige, at m^ed (mod n)=m, hvor d og e er beregnet som tidligere beskrevet i rapporten (afsnit: kryptring vha. RSA).
Vi antager, at (m,n)=1. Da gælder der ifølge Eulers sætning (sætning 4.37), at:
med (mod n)≡m(ed (mod φ(n)) (mod n)
Da det gælder, at ed≡1 (mod φ(n)) får vi, at med (mod n)=m er opfyldt, hvis (m,n)=1
Svar #3
04. december 2011 af peter lind
Nej. Du skal have meget mere beskrivelse af hvad du gør og hvilken sætninger du bruger. Og hvad betyder → ?
Svar #5
04. december 2011 af peter lind
Forestil at du skal skrive det til en rimelig god elev i din klasse, som aldrig har hørt om RSA
Skriv et svar til: Bevis for RSA
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.