Matematik
RSA kryptering
Hej jeg har fået til opgave at Konstruer et nøglesæt ud fra primtallene 37 og 89 samt enkrypteringnøglen e=41. krypter teksten Lærke og dekrypter kodetekseten ”1021-2520-1922-2195-0858”
indtil vidre har jeg fået
Offentlig nøgle: (n,e)=(3293,41)
Hemmelig nøgle: d=2009
og Lærke til at være ”1176-0560-1835” (jeg tror det er forkert)
men jeg kan ikke se hvordan jeg skal dekryptere, da talene er for store til lommeregneren og da det vil blive et for stort arbejde at bruge samme teknik som i delen hvor man kryptere fra klartekst til kryptotekst.
er der nogen der kunne hjælpe?
Svar #1
08. december 2011 af peter lind
Det undrer mig at du ikke rendt ind i det problem ved kodningen. Du skal gøre dig klart at efter enhver regneoperation i en restklasse modulo n, kan du reducere modulo n uden at det ændrer på resultatet. Hvis du kan prgramere er det let nok idet du kan bruge at ai+1 = a*ai mod n. I det praktiske duer den metode ikke fordi den er for langsom. Man har derfor en algoritme, der kan nedsætte antal beregninger ganske drastisk. Den nedenfor er ændret noget af pædagogiske grunde:
Lav rækkerne
a a2 a3 a4 a5 a6 a7 a8 a9
a10 a20 a30 a40 a50 a60 a70 a80 a90
a100 a200 a300 a400 a500 a600 a700 a800 a900
Her er første reække fremkommet ved a2 = a*a mod n, a3 =a*a2 mod n ...
anden række fremkommet som a20 = a10*a10 mod n, a30 = a10*a20 mod n ...
tredje række fremkommet som a200 = a100*a100 mod n, a300 = a100*a200 mod n ...
Hvis du nu vil finde a686 kan det findes som a600*a80*a6 mod n
Hvis du tæller efter kan du se at det kræver mindre en 10*antallet af cifre i potensen at regne det ud. Selv med flere hundrede cifre er det nemt for en datamaskine at udregne det.
Når jeg har skrevet som jeg gjorde er det fordi regning i titalssysemet kender du. Det er bare ikke det bedste. Professionelle bruger algoritmen med potensen i 2 tals systemet. Det er både enklere og hurtigere; men kræver lidt ekstra i forståelsen.
Skriv et svar til: RSA kryptering
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.