Matematik

RSA kryptering

15. december 2014 af martin122 (Slettet) - Niveau: A-niveau

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. 


Brugbart svar (0)

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?


Brugbart svar (0)

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 #5
17. december 2014 af martin122 (Slettet)

Det skal siges at MOD er en funktion i maple


Brugbart svar (0)

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 #8
18. december 2014 af martin122 (Slettet)

Hov, her kom det

Vedhæftet fil:RSA 2.pdf

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å? 


Brugbart svar (0)

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 #13
18. december 2014 af martin122 (Slettet)

Kan man regne det ud i maple? ¨


Brugbart svar (0)

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


Brugbart svar (0)

Svar #18
19. december 2014 af peter lind

ja


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.