RSA dekryptering

Overskriften skulle hede enkryptering...

på dansk hedder det krypering og dekryptering.

Brug lommeregner: 

721^29(mod4343)= 671

tak for svaret. Men tænkte mellemregningerne?

En almindelig lommeregner kan ikke klare det direkte. 721²⁹ er et tal på 83 cifre, som ikke kan være i en lommeregner. Man skal bruger at man i mellemregninger kan reducere  modulo 4343 og dermed bringe antal cifre ned i et håndterbar størrelse. Simplest er simpelthen gange sammen de 28 gange og reducere modulo 4343 i hver mellemregning. Det kan nemt gøres i et regneark . Lidt smartere er at bruge en algoriteme, hvor man foretager gentagne kvadreringe af det fremkomne tal. Først kvadrer man de 721 og reducerer modulo 4343 så man har 721² mod 4343. Derefter kvadrerer man dette og reducerer. så har man 721⁴ modulo 4343 næste gang får man 721⁸ mod 4343 o.s.v

Hvis man skal dekryptere og siger 671^869mod4343..?

Man kan bruge den algoritme som peter lind beskriver:

definer x=671

for a, 1, 869-1                    (gentages 868 gange)

definer x=mod(x*671, 4343)

endif

disp x

... som giver svaret 721

Hvilket program tastes det ind i?

Det jeg skrev passer til TI lommeregner eller TI interactive. Definer skal dog skrives define uden r.

Du kan også bruge Excel:

skriv 671 i celle A1.

skriv =rest(A1*671;4343)  i A2

marker A2 ... træk den lille sorte prik i cellens nederste højre hjørne nedad, så den autoudfylder cellerne ned til A869.

Her er en algoritme som nemt kan bruges i et regneark. Det er en modificeret udgave af en algoritme som bruges i praksis. i det følgende vil jeg underforstå at man efter hver beregning modificerer modulo n, hvor n her er 4343

Beregn

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⁹⁰⁰

Den første række beregnes ved succesivt at gange med a og reducere modulo n

Den anden række undtagen første led findes ved succesivt at gange med a¹⁰.

Den tredje række fås ved at gange succesivt med a¹⁰⁰.

a⁸⁶⁹ kan så fås som a⁸⁶⁹ = a^{800+60 +9} = a⁸⁰⁰*a⁶⁰*a⁹.

Forskellen mellem dette her og det man bruger i praksis er talsystemet. Det ovenfor kører i 10-tals systemet. Det er bare mere effektivt at bruge 2-tal systemet; men er bare lidt sværere at forstå.

Hvad går galt i mine udregninger?? http://postimg.org/image/kl4zijfi1/

721⁴ ≡ 791 mod 4343

721⁸ ≡ 289 mod 4343

721⁹ Ξ 721* 289 mod 4343 ≡ 1378 mod 4343

721⁸⁺⁹ ≡ 281*1378 mod 4343 ≡ 3029 mod 4343

Det var bare ikke 721¹⁷ mod 4343 der blev bedt om

Er næsten helt sikker på mine beregninger er rigtige da jeg følger dem lige efter bogen. Hvordan skulle resultater være 671?

Metoden er god nok. Du bruger den bare forkert som det fremgår af #11

I #11 første trin giver: 721^4 ≡ 2561 mod 4343. det forvirrer mig da du skriver 791

Har løst det. Tak for din hjælp Peter.