Matematik
Brug for hjælp til RSA-kryptering
Jeg er i gang emd min Studieretningsopgave, og er løbet ind i nogle uventede problemer - så håber at nogen kan hjælpe mig med noget RSA-kryptering!
Jeg skal oprette et nøglepar, f.eks. med primtallene 51 og 61. Jeg har fundet n = pq, og ø(n) = 3000. e (0<e<ø(n), (e,ø(n))=1) har jeg valgt til at være 7. Jeg skal nu beregne d, via ed = (3 streger) 1 (mod ø(n)), men da jeg ikke har super meget styr på hvordan jeg gør det med denne formel, har jeg brugt følgende: e = d^ø(n)-1 $ k dvs. e = 7^3000-1 $ 3000 (altså 7^3000-1 (mod 3000)).
Mit problem er, at jeg ved ikke rigtig hvad jeg skal gøre ved potensen 7^2999, som jo er sindsyg stor. Jeg skal have den skrevet om på en eller anden måde så jeg kan finde resten (altså e). Jeg har en idé om at den skal reduceres ved hjælp af nogle 2-potenser, men jeg kan ikke finde ud af hvordan det skal gøres!
Håber nogle kan hjælpe mig!
Svar #1
14. december 2007 af peter lind
Jeg går ud fra, at der skal beregnes a^e mod n
0) Initialisering
Inddata a,e,n. y := 1
1) c := e mod 2
e := heltal(e/2)
Hvis c = 1 så y := y*a nod n
2) hvis e > 0 gå til 1 ellers stop y = a^e mod n.
:= betyder beregn højre side og sæt resultatet ind i variablen på venstre side.
Bortset fra at stoppe kan koden nemt implementeres i et regneark. Hvis der ikke stoppes fortsættes bare med at levere facit, så det gør ikke så meget.
Svar #2
14. december 2007 af David E (Slettet)
Jeg må indrømme, at jeg har absolut ikke særlig meget styr på kryptologi, og jeg ved kun lidt om det aller væsentligste i RSA-kryptering (Jeg har kun arbejdet med det i en uge!) Så jeg må indrømme, at jeg ikke forstod noget af det du har skrevet!
For lige at gøre det helt klart; så skal jeg kryptere noget tekst, og har nogenlunde styr på hvordan det skal gøres. Jeg er som sagt i gang med at oprette det her nøglepar, men er løbet ind i problemet med at finde
e = 7^(3000-1) (mod 3000). Og da min Ti 89'er ikke kan klare så store tal som 7^2999 er, så er jeg usikker på, hvordan jeg skal gribe regnestykket an!
Håber at du vil skære det lidt mere ud i pap!
Svar #3
14. december 2007 af peter lind
Jeg kan prøve med et lille eksempel jeg vælger a = 4, e = 9, n=10
0) initialiserin a = 4, e = 9, n=10, y = 1
1) c = 9 mod 2 = 1
e = heltal(7/2) = 4
y = (1*4) mod 10 = 4
a= 4*4 mod 10 = 6
2) e = 3 > 0. gå til 1)
1) c = 4 mod 2 = 0
e = heltal(4/2) = 2
c = 0 så y uændret 4
a = 6*6 mod 10 = 6
2) e =2 > 0 så gå til 1
1) c=2 mod 2 = 0
e = heltal(2/2) = 1
c = 0 så y uændret 4
a = 6*6 mod 10 = 6
2) e= 1 > så gå til 1
1) c = 1 mod 2 = 1
e = heltal(1/2) = 0
c = 1 så y = 4*6 mod 10 = 4
a = 6*6 mod 10
2) e = 0 så stop
y = 4 = 4^9 mod 10
4^9 er så stort et tal, at jeg nok ikke havde lyst til at udregne det med håndkraft.
c er iøvrigt cifrene af e i 2-talssystemet.
Svar #4
15. december 2007 af peter lind
a^2999 mod n = a^(2000+900+90+9) mod n = (a^2000*a^900*a^90*a^9) mod n =
(a^2000 mod n)* (a^900 mod n)*(a^90 mod n)*(a^9 mod n) =
[(a^1000)^2 mod n]*[(a^100)^9 mod n]*[(a^10)^9 mod n]*[a^9 mod n]=
[(a^1000 mod n)^2 mod n]*[(a^100 mod n)^9 mod n]*[(a^10 mod n)^9 mod n]*[a^9 mod n]
Fidusen er at man kan reducere modulo n efter hver mellemregning og dermed hold værdierne nede. Dette skal også benyttes til udregning af a^1000 mod n, a^100 mod n, a^10 mod n. Der gælder for eks. a^1000 mod n = (a^100)^10 mod n = (a^100 mod n)*10
Svar #5
17. december 2007 af Stina007 (Slettet)
a^395 (mod n) =
a^(300+90+5) (mod n) =
(a^300 · a^90 · a^5) (mod n) =
(a^300 (mod n)) · (a^90 (mod n)) · (a^5 (mod n)) =
((a^100)^3 (mod n)) · ((a^10)^9 (mod n)) · (a^5 (mod n)) =
((a^100 (mod n))^3 (mod n)) · ((a^10 (mod n)^9 (mod n)) · (a^5 (mod n))
Men kan ikke se hvordan jeg nu skal få tallene mindre, mit e = 7, f(n)= 396 og n = 437, så tallene er for store til udregning på TI-89
Håber at der er nogen som kan hjælpe??
Svar #6
16. december 2008 af Llamas (Slettet)
Hej
Jeg har et lille problem med min RSA-kryptering. jeg skal kryptere ordet KRYPTOGRAM med primtallene p=11 og q=19
jeg har regnet
pq= 209
φ(n) = 180
e=7
d=103
m1 = 11 m2 = 18 m3 = 24 m4 = 16 m5 = 20 m6 = 15 m7 = 07 m8 = 18 m9 = 01 m10 = 13 og Klarteksten er nu 11182416201507180113
så har jeg enkrypteret:
K: 11 11
R: 18 94
Y: 24 73
P: 16 36
T: 20 191
O: 15 203
G: 7 83
R: 18 94
A: 1 1
M: 13 29
nu skal jeg så dekryptere. og det er så mit problem. ville høre om der var nogen som kunne hjælpe ?
Svar #7
16. december 2008 af peter lind
Det skal jo gøres på samme måde som at kryptere blot med e erstattet af d, så hvad er problemet egentlig?.
Skriv et svar til: Brug for hjælp 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.