Matematik

Hjælp

19. december 2005 af BaggerTheMan (Slettet)

Jeg har problemer med at løse følgende opgeve:

e=11
e*d er kongurent med 1(mod 3956)

jeg skal finde d!

Jeg er kommet så langt:
11d+3956c=1

Herfra bruger jeg så euklids algoritme, men er gået i stå under den linearekombination! Nogen der måske ville hjælpe?

Svar #1
19. december 2005 af BaggerTheMan (Slettet)

Så langt er jeg nået nu:
(1) 3956 = 359*11 + 7 (rest 7)
(2) 11 = 1*7 + 4 (rest 4)
(3) 7 = 1*4 + 3 (rest 3)
(4) 4 = 1*3 + 1 (rest 1)
(5) 1 = 1*1 + 0 (rest 0)

omskrivning vha. linearkombinationer af 3956, 11 og resterne:

7 = 3956 – 359*11
4 = 11-7*1 = 11- (3956-359*11)*1
3 = 7-4*1 = 3956 – 359*11-(11- (3956-359*11)*1)
1 = 4-3*1 =11- (3956-359*11)*1- (3956 – 359*11-(11- (3956-359*11)*1) =

Brugbart svar (0)

Svar #2
19. december 2005 af Rasmus1234 (Slettet)

Kan ikke lige overskue det selv... hehe

Men prøv at kigge på Euklids Udvided Algoritme

http://en.wikipedia.org/wiki/Extended_Euclidean_Algorithm

og evt dette eksempel fra "Kryptologi - fra viden til videnskab"

http://pastebin.com/469647

Svar #3
19. december 2005 af BaggerTheMan (Slettet)

Nej...

det er lige meget... jeg har fundet ud af det hele, undskyld ulejligheden!!

Svar #4
19. december 2005 af BaggerTheMan (Slettet)

Ok... har faktisk lige en spørgsmål alligevel! Jeg har nu regnet færdig, og jeg for d=1079 og c=-3 d er helt rigtig, men hvad kan jeg bruge a til??

Brugbart svar (0)

Svar #5
19. december 2005 af Rasmus1234 (Slettet)

d er så din hemmelige nøgle.

Di skal enkryptere ved at sige m^e mod n = c

m^11 mod 3956 = c

og dekryptere med c^d mod n = m

c^1079 mod 3956 = m

jeg tror dog der er en fejl et sted, idet

3^11 mod 3956 = 3083 og
3083^1079 mod 3956 = 3359

Hvad er din p og q værdi?

Brugbart svar (0)

Svar #6
19. december 2005 af Rasmus1234 (Slettet)

Hmmm kan se at e og d værdien faktisk passer, men kan ikke lige gennemskue hvorfor det ikke går op... Må blive på et andet tidspunkt.

Brugbart svar (0)

Svar #7
20. december 2005 af Rasmus1234 (Slettet)

Jeg tror evt fejlen ligger i din n værdi. 3956/43 = 92 og 3956/23 = 172 hvilket er de eneste 2 primtal under 150 der går op i 3956, og begge resultater er sammensatte tal.

Kunne det tænkes du måske har brugt phi(n) og ikke n til at regne d?

Svar #8
20. december 2005 af BaggerTheMan (Slettet)

hmm... men det er da vel phi(n) jeg skal bruge?? sådan som jeg læser det i min bog, så står det da sådan! hmm...

Brugbart svar (0)

Svar #9
20. december 2005 af Rasmus1234 (Slettet)

når du skal finde d skal du bruge phi(n) men når du skal enkryptere skal du bruge n,e

Det virker ihvertfald for mig.

Hvilken bog tænker du på?

Svar #10
20. december 2005 af BaggerTheMan (Slettet)

Hmm.... jeg har på fornemmelsen at vi snakker forbi hinanden, jeg har kun lavet de foregående, inden enkryptering og dekryptering! Skal først igang med det andet nu her!
Men det kan være at jeg for brug for lidt hjælp med det, men så skriver jeg bare lige!

Jeg bruger bogen "Kryptologi"

Skriv et svar til: Hjælp

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.