Matematik
RSA kryptering
Jeg skal kryptere en besked som har tallet:
152419172311
som jeg har brudt op i 4 til med hver 3 cifre. (Tallet m=5963 har 4 cifre)
a_1:=152
a_2:=419
a_3:=172
a_4:=311
Jeg skal beregne
k
b__k := a__i
mod m
for i=1...4
Hvordan gør jeg det? og hvilken metode bruger jeg.
Svar #1
15. december 2014 af peter lind
Det er jo totalt ulæseligt hvad du skriver efter sætningen "Jeg skal beregne"
Da det drejer sig om RSA gætter jeg på at der menes at du skal beregne
ae mod n
Her skal du bruge at du i alle mellemregninger kan reducere modulo n altså
a2 mod n = m2
a3 mod n = (a2*a )mod n = (m2*a) mod n = m3 o.s.v
Hvis potenserne ikke er for høje kan det nemt udregnes i et regneark
Hvis arbejdet bliver for stort for et regneark findes der en metode til at accellerere beregningerne. Har du brug for dette kan du vende tilbage
Svar #2
17. december 2014 af martin122 (Slettet)
Nu har jeg fundet ud af det.
Jeg skal så dekryptere min meddelse igen.
b_1=2291
b_2=1312
b_3=909
b:4=5301
Den private nøgle er: 5808
Den offentlige nøgle er (e,m): 103, 5963
Jeg skal bestemme u og v:
k*u-phi(m)*v=1
Kan nogen hjælpe?
Svar #3
17. december 2014 af peter lind
Hvis den offentlige nogle er e, den private nøgle e og n, meddelesen der skal kodes er x og den kodede værdi y gælder
xe mod n = y
yd mod n = x
dine nøgler stemmer ikke, så du har lavet et eller andet galt da du lavede dem. Hvad har du gjort ?
Svar #4
17. december 2014 af martin122 (Slettet)
m=p*q=5963
phi(pq)=(p-1)(q-1)=5808
e=103
Jeg fandt b_1 ved at skrive:
a_1=a^103 mod 5808 osv.
Svar #6
17. december 2014 af peter lind
(p-1)(q-1) kan aldrig blive den offentlige nøgle. Du må ikke under nogen omstændigheder offentliggøre dette tal. Så er koden nemlig brudt.
Den offentlige nøgle skal være d og n hvor d findes af e*d= k*(p-1)(q-1) +1 hvor k er et naturligt tal. Sagt med andre ord. Du skal finde d så e og d er hinandens inverse mod (p-1)(q-1). Dertil bruger man Euklids udvidede algoritme. Den findes i maple
Svar #7
18. december 2014 af martin122 (Slettet)
Jeg har vedhæftet hvad jeg har lavet indtil videre. Jegk an ikke komme videre herfra og jeg mangler hjælp til dette stykke. Nye tal, men jeg skal bare have forstået det.
Svar #9
18. december 2014 af martin122 (Slettet)
Jeg skrev heller ikke at (p-1)(q-1) var den offentlige nøgle. det er den private nøgle.
Den offentlige nøgle er m=p*q og tallet e=103 som jeg har fået udleveret af min vejleder. Er e=103 ikke en af de offentlige nøgler så?
Svar #10
18. december 2014 af peter lind
De 1013088 er ikke din hemmelige nøgle. Den har du slet ikke fundet.
Du skal finde d så k*d er hinandens inverse modulo 1013088. Det finder du ved at bruge Euklids udvidede algoritme altså hvis dit k er invertibel
Svar #11
18. december 2014 af martin122 (Slettet)
men i alle mine noter står der at phi(m)=(p-1)(q-1) er den hemmelige nøgle/private nøgle.
kan du give et udførligt eksempel på hvordan man gør det?
Svar #12
18. december 2014 af peter lind
Svar #14
19. december 2014 af peter lind
Ja. Jeg kender ikke maple; men jeg har særdeles gode grunde til at mene det er der. Søg efter greatest common devisor eller gcd
Svar #15
19. december 2014 af martin122 (Slettet)
Min hjerne forstod endelig Euklids udvidede algoritme, endelig
Jeg prøver at kigge efter noget i maple
Svar #16
19. december 2014 af martin122 (Slettet)
Hvis jeg skriver gcd(3276,1901) giver det 1, Er dette korrekt?
Svar #17
19. december 2014 af martin122 (Slettet)
3276 = +(1901, 1375)
1901 = +(1375, 526)
1375 = *(2, 526) + 323
526 = +(323, 203)
323 = +(203, 120)
203 = +(120, 83)
120 = +(83, 37)
83 = *(2, 37) + 9
37 = *(4, 9) + 1
9 = +(9, 0)
sfd(9, 1) = sfd(1, 0) and sfd(1, 0) = 1
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.