Matematik
SRP: RSA Kryptering - under 24 timer igen
Hej.
Jeg skal aflevere om 24 timer og mangler stadig at vise mit eget eksempel på RSA. Her er et eksempel på, hvad jeg har prøvet. Here goes:
Jeg vælger to primtal:
p=163
q=109
n=pq=163•109≈17767
φ(n)=(p-1)(q-1)=(163-1)(109-1)≈17496
Jeg vælger e=5, som er indbyrdes primisk med φ(n)
de≡1 (mod n)
d=e^(-1) (mod φ(n))=5^(-1)/17496≈1,1431184270690443•?10?^(-5)
r=0,1431184270690443•17496≈2504
offentlig nøgle: n og e
17496 og 5
Hemmelig nøgle d
2504
Klartekst: DANIEL
Teksten skal deles ind i blokke m, 0<m<n
0401 1409 0511
Hver blok krypteres m→m^e (mod n)=c
?0401?^5/17767≈583589891,48426855
0,48426855•17767≈8603,9993278500006=8604
Disse sendes til modtageren.
Dekrypteringen foregår c→c^d (mod n)
?8604?^5/17767≈2653920482259549
r=0 ?????
Hvor går det galt?
Jeg håber nogen kan hjælpe - opgaven skal afleveres i morgen kl 10.
På forhånd tak,
Daniel
Svar #1
20. december 2012 af PeterValberg
Det ser ud at du har beregnet d forkert (jeg skulle mene, at d = 13997)
du skal jo "bare" løse ligningen:
e·d ≡ 1 (mod φ(n))
5·d ≡ 1 (mod 17496)
hvilket ved anvendelse af Euklids udvidede algoritme giver: d = -3499
hvilket svarer til 13997 mod 17496
Svar #2
20. december 2012 af danielhansen13 (Slettet)
Tak for svaret, Peter Valberg.
Desværre kan hverken programmet Wordmat eller TI-NSpire regner med så store tal.
Svar #3
20. december 2012 af PeterValberg
Så lav et eksempel med mindre tal, - fx:
p = 17 og q = 11
vælg e = 7
Svar #4
20. december 2012 af PeterValberg
du skriver i #0
d=e^(-1) (mod φ(n))=5^(-1)/17496≈1,1431184270690443•?10?^(-5)
det har du misforstået lidt, e-1 er ikke 1/e
Det er den multiplikative inverse modulo φ(n) til e
Denne kan være lidt besværlig at beregne.
Du skal benytte dig af Euklids udvidede algoritme, - se denne tråd [ LINK ]
Svar #5
20. december 2012 af danielhansen13 (Slettet)
Det prøver jeg, men kan du hjælpe mig med udregning af d?
ed ≡ 1 (mod φ(n)) <=>
7d ≡ 1 (mod 160) <=>
7d=-159
Er det forkert? Min lommeregner kan i hvert fald ikke regne det.
Svar #6
20. december 2012 af danielhansen13 (Slettet)
#4
du skriver i #0
d=e^(-1) (mod φ(n))=5^(-1)/17496≈1,1431184270690443•?10?^(-5)
det har du misforstået lidt, e-1 er ikke 1/e
Det er den multiplikative inverse modulo φ(n) til e
Denne kan være lidt besværlig at beregne.
Du skal benytte dig af Euklids udvidede algoritme, - se denne tråd [ LINK ]
Jeg kan godt regne med Euklids udvidede algoritme, men hvilken værdi er så d?
Ved (187,7) får jeg -7*187+187*7
Svar #7
20. december 2012 af danielhansen13 (Slettet)
Eller har jeg misforstået noget, så det er (160,7)=1 -> -1*160+23*7=1 ? Hvordan hjælper dette mig med at finde d?
Svar #8
20. december 2012 af danielhansen13 (Slettet)
Hej Peter.
Jeg har fået problemet løst nu - efter at have rodet med det i 48 timer - tak for hjælpen.
Mange hilsner
Daniel
Skriv et svar til: SRP: RSA Kryptering - under 24 timer igen
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.