Matematik
Hvordan finder man d i et RSA-system?
Hej.
Jeg er ved at lave et eksempel på et simpelt rsa-system, hvor jeg har:
to primtal: p=7 og q=13 =>n=91
phi(n)=72
e=5
Jeg har derfor denne ligning jeg skal løse:
e*d=1 mod(phi(n))
Jeg har opstilt det i et regne ark med kolonnerne d, d*e, rest(72;e*d). Jeg ved bare ikke hvordan jeg finder det hele tal 1 i den sidste kolonne.
Håber det er forståeligt og at der er en der kan hjælpe.
Svar #1
06. december 2010 af peter lind
d er den inverse til e i restklassen modulo φ(n). Den udvidede Euklids algoritme kan finde den inverse, hvis den eksisterer. Jeg ved ikke om du må bruge et CAS værktøj til det.
Det drejer sig om små tal, så du kan også blot regne e*d mod φ(n) ud for alle relevante værdier af d i et regneark. Det er meget hurtigt gjort.
Svar #2
08. december 2010 af Holmelin (Slettet)
Jeg må lige bryde ind og sige, at p og q skal være primtal med mere end 100 cifre og n skal derfor være ret så stor :-)
Svar #3
08. december 2010 af peter lind
#2 Hvis du ser i #0 vil du opdage at der spørges om små tal. At det så ikke dur i den praktiske anvendelse er en anden sag. I gymnasiet går det først og fremmest ud på at forstå metoden.
Skriv et svar til: Hvordan finder man d i et RSA-system?
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.