Matematik

Potensregneregler mht RSA-dekryptering

12. februar 2015 af ChemIdiot (Slettet) - Niveau: A-niveau

Jeg er i gang med at dekryptere tallene 1007 og 118 med den hemmelige nøgle d=667.

Normalt skulle jeg bare gør 1007^667 (mod 1111) og så ville jeg få den dekrypterede besked.

Problemet er at 667 er for stort et tal i potens så jeg ville gøre potensen mindre ved at sætte udenfor parantes og derved bruge modulo undervejs og bruge resten til at regne næste potens..
Altså, den regel jeg ville bruge er:
m^25=m*m^24=m*(m^12)^2 osv.
Jeg ved at for at få 667 så kan jeg bruger (3*3*2*2+1)*3*3*2+1
Jeg har prøvet at regne på det, men kan ikke få det til at gå op.
Er nået til m*m*((((((m^3)^2^)^3)^3)^2)^2)^3 men det giver mig kun m^650. Jeg har været gået i stå siden i går. Har prøvet forskellige ting, men kan bare ikke få det til at gå op.

Brugbart svar (0)

Svar #1
12. februar 2015 af peter lind

Det væsentlige er at du kan reducere modulo n efter hver mellemregning.

Antag at du skal beregne a^r mod n

Du laver rækkerne

a1 a² a³ a⁴ a⁵ a⁶ a⁷ a⁸ a⁹

a¹⁰ a²⁰ a³⁰ a⁴⁰ a⁵⁰ a⁶⁰ a⁷⁰ a⁸⁰ a⁹⁰

a¹⁰⁰ a²⁰⁰ a³⁰⁰ a⁴⁰⁰ a⁵⁰⁰ a⁶⁰⁰ a⁷⁰⁰ a⁸⁰⁰ a⁹⁰⁰

a¹⁰⁰⁰ ...

hvor der er underforstået at alle tal er reduceret modulo n.

Hvis du nu skal finde a⁸³⁷ modulo n kan det findes som a⁸⁰⁰*a³⁰*a⁷ mod n

Det ovenstående er baseret på at vi bruger 10 tals systemet, som derfor er kendt.

Det er faktisk bedre at bruge 2 tals systemet; men jeg gør det ikke af pædagogiske grunde

Ovenstående tabeller kan nemt laves i et regneark

Svar #2
12. februar 2015 af ChemIdiot (Slettet)

Hej Peter

Rigtig mange tak for dit svar! Får det lige prøvet igennem! :-)))

Brugbart svar (0)

Svar #3
12. februar 2015 af peter lind

Ser lige at jeg glemte at skrive at du finder for eks. a6 som a⁵*a a⁶⁰ som a⁵⁰*a¹⁰ a⁶⁰⁰ som a⁵⁰⁰*a¹⁰⁰

Svar #4
12. februar 2015 af ChemIdiot (Slettet)

Hej Peter

Jeg fik også en ven til at hjælpe faktisk og har fundet frem til at det kunne bare skrives som

((((((k^3)^3)^2)^2*k)^3)^3)^2*k

Mange tak for hjælpen! :-)

Skriv et svar til: Potensregneregler mht RSA-dekryptering

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.