My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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.
nobbydoods is offline  
 
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.
Country Boy is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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





Copyright © 2019 My Math Forum. All rights reserved.