My Math Forum Discrete Math - RSA Decryption

 Applied Math Applied Math Forum

 December 23rd, 2015, 03:11 AM #1 Newbie   Joined: Dec 2015 From: malaysia Posts: 4 Thanks: 0 Discrete Math - RSA Decryption Hello. I'm new and I am also not sure where to post my question so I just clicked (i apologize in advance.). Anyway, So we're learning Cryptography in my Discrete Math class. For encryption we learned Algorithm Exponentiation for Repeated Squaring which I've got a grasp on just need more practice. But now I am stuck at decryption. I have an exercise the question : Assume that we choose primes p = 59, q = 101, n = 41. Compute z and Compute Φ and Compute s. z = pq = 59*101 = 5959 Φ = (p - 1)(q - 1) = (59 - 1)( 101 - 1) = 58(100) = 5800 I am stuck at Compute S: s = ns mod Φ = 1 41(s) mod 5800 = 1 I don't understand how to get s? the answer that is given is s = 3961 but I dont understand how to get that number. Please help and explain. Much appreciated.
 January 6th, 2016, 10:30 AM #2 Math Team   Joined: Jan 2015 From: Alabama Posts: 3,264 Thanks: 902 You can check: 41(3961)= 162401= 28(5800)+ 1 so 41(3961)= 1 (mod 5800). As for solving 41s= 1 (mod 5800), that is the same as saying that 41s= 5800k+ 1 for some k or 41s- 5800k= 1, a "Diophantine equation". 41 divides into 5800 141 times with remainder 19: 5800- 141(41)= 19. 19 divides into 41 twice with remainder 3: 41- 2(19)= 3. Finally, 3 divides into 19 6 times with remainder 1: 19- 6(3)= 1. Replace that "3" with 41- 2(19): 19- 6(41- 2(19))= 13(19)- 6(41)= 1. Replace that "19" with 5800- 141(41): 13(5800- 141(41))- 6(41)= 13(5800)- 1839(41)= 1. So one solution to the equation 41s- 5800k= 1 is s= -1839, k= -13. But it is easy to see that, for any i, s= -1839+ 5800i, k= -13+ 41i is also a solution because 41(-1839+5800i)- 5800(-13+ 41i)= 1+ 41(5800i)- 5800(41i)= 1. In particular, since this is "mod 5800", s must be between 0 and 5800 an we must take i= 1 so s= -1839+ 5800= 3961.

 Tags decryption, discrete, math, rsa

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post fatalistmk Elementary Math 5 December 6th, 2014 11:58 AM nwicole Number Theory 5 October 23rd, 2014 02:49 PM girl_withno_name Computer Science 5 February 18th, 2012 08:15 AM foo_ Number Theory 0 April 26th, 2009 02:35 AM Maniac Computer Science 9 July 29th, 2008 05:48 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top