RSA opgave, kursusgang 10 

Spørgsmål 1. 

Skal undersøge om p og q er primtal og om gcd(e,(p-1)(q-1))=1 

(1)

 

(2)

 

(3)

 

Spørgsmål 2. Find invers til e. Brug Euklids udvidede algoritme. 

(4)

 

(5)

 

(6)

 

Spørgsmål 3. Bob sender til Alice: 

(7)

 

(8)

 

Spørgsmål 4. 

(9)

 

(10)

 

Spørgsmål 5. 

(11)

 

Alternativ metode: 

Bob kan eventuelt udregne  og . 

Da 

(12)

 

og  ifølge Fermat Sætning (da 73 ikke går op i C) kan beregnes som 

(13)

 

Tilsvarende, da 

(14)

 

kan beregnes som 

(15)

 

kan nu beregnes ved hjælp af den kinesiske restsætning: 

(16)