Alice and Bob encrypt their messages using the RSA method. Bobs (a) Alice would

Question

Alice and Bob encrypt their messages using the RSA method. Bobs (a) Alice would like to send Bob the plaintext m 183. What cyphertext (b) Bob knows that (n) 24300 but has forgotten his private key d. (c) Bob has received the cyphertext 16935 from Casey. Find the original public key is (n, e) = (24613, 1003). should she send? Find d and the prime factorisation of n. plaintext For parts (a) and (b) you are allowed to use a computer for basic arithmetic modulo a given natural number, but you should do all other calculations by hand. For part (b) you will need a table of prime numbers which can be easily find online. In (c) you may use anything which speeds up the computation

Explanation / Answer

n = 24613 e = 1003

(a) m = 183

c = me mod n

c = 1831003 mod 24613

=> c = 17315817488068303643732618659570549707673303931318640505132153445884333795273634888203153874879058647032788620164104019856111874937343393468038881496766232774617435572388415053108439288629901205465592301639826930036340236476042971187603341636625102848018857085992500635891764199531137053174877219527912893159996577204640019319378486836863715107008488389893405702324752937434319814111683172388533226051759811282031211158473814102142307085036048861437992034491157188758492101939152998958435115826222340 mod 24613

= 33.

(b) (n) = 150 * 162 = (151 - 1) * (163 - 1) = 24300

n = 151 * 163  

de = 1 mod (n)

=> 1003d = 1 mod 24300

Using Euclid's algorithm,

24300 = 24*1003 + 228

1003 = 4*228 + 91

228 = 2*91 + 46

91 = 46 + 45

46 = 45 + 1

45 = 45*1 + 0

gcd(1003,24300) = 1

Using Euclid's extended algorithm,

1 = (46 - 45)

1 = (46 - (91 - 46))

1 = ((228 - 2*91) - (91 - (228 - 2*91)))

1 = ((228 - 2*(1003 - 4*228)) - ((1003 - 4*228) - (228 - 2*(1003 - 4*228))))

1 = (((24300 - 24*1003) - 2*((1003 - 4*(24300 - 24*1003))) - ((1003 - 4*(24300 - 24*1003) - ((24300 - 24*1003) - 2*(1003 - 4*(24300 - 24*1003)))))

1 = 24300 - 24*1003 - 2*1003 + 8*24300 - 192*1003 - 1003 + 4*24300 - 96*1003 + 24300 - 24*1003 - 2*1003 + 8*24300 - 192*1003

1 = 22*24300 - 533*1003

=> -533*1003 = 1 mod 24300

=> d = 24300 - 533 = 23767.

(c) m = cd mod n

= 1693523767 mod 24613

= 1689 * 354911883 mod 24613

= 1689 * 3549 * 181585941 mod 24613

= 1689 * 3549 * 18158 * 218292970 mod 24613

= 1689 * 3549 * 18158 * 221741485 mod 24613

= 1689 * 3549 * 18158 * 22174 * 16988742 mod 24613

= 1689 * 3549 * 18158 * 22174 * 4719371 mod 24613

= 1689 * 3549 * 18158 * 22174 * 4719 * 18809185 mod 24613

= 1689 * 3549 * 18158 * 22174 * 4719 * 18809 * 1583292 mod 24613

= 1689 * 3549 * 18158 * 22174 * 4719 * 18809 * 1804546 mod 24613

= 1689 * 3549 * 18158 * 22174 * 4719 * 18809 * 1664823 mod 24613

= 1689 * 3549 * 18158 * 22174 * 4719 * 18809 * 16648 * 1352411 mod 24613

= 1689 * 3549 * 18158 * 22174 * 4719 * 18809 * 16648 * 13524 * 239865 mod 24613

= 1689 * 3549 * 18158 * 22174 * 4719 * 18809 * 16648 * 13524 * 23986 * 239342 mod 24613

= 1689 * 3549 * 18158 * 22174 * 4719 * 18809 * 16648 * 13524 * 23986 * 18007 mod 24613

= 20831944549122000000000000000000000000000 mod 24613

= 11451

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.