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  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
discrete Math  fatalistmk  Elementary Math  5  December 6th, 2014 11:58 AM 
Discrete math again :(  nwicole  Number Theory  5  October 23rd, 2014 02:49 PM 
DES Decryption  girl_withno_name  Computer Science  5  February 18th, 2012 08:15 AM 
RSA decryption using CRT  foo_  Number Theory  0  April 26th, 2009 02:35 AM 
Encryption / Decryption  Maniac  Computer Science  9  July 29th, 2008 05:48 AM 