User Name Remember Me? Password

 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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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

Copyright © 2019 My Math Forum. All rights reserved.      