Date: 04/25/2002 at 21:38:25 From: Haz Subject: Number theory RSA The following message is ciphertext: C=983830091 Its plaintext is a string of some English letters. The plaintext was first changed to an integer by the following scheme, a -> 01, b -> 02, c -> 03, z -> 26 Then it was encrypted to ciphertext C by using RSA encryption method with the public key(e,N) as follows: e = 7 N = 2651733127 You are now asked to decrypt the encrpted message C. to find the original plaintext, a string of English letters.
Date: 04/26/2002 at 12:07:49 From: Doctor Paul Subject: Re: Number theory RSA You need to find the private exponent d. This is very hard to do (and explains why the algorithm is secure) if N is large. But here, N can easily be factored by a computer: N = 71593 * 37039 = p*q both of the factors are prime. Then M = phi(N) = (p-1) * (q-1) = 2651624496 Now we want to find d such that e*d = 1 mod M that is, 7*d = 1 mod 2651624496 Use the regular Euclidean Algorithm to find gcd(7, 2651624496). The answer had better be one - otherwise we can't be sure that a solution exists. 2651624496 = 7*378803499 + 3 7 = 3*2 + 1 3 = 1*3 + 0 The gcd is the last nonzero remainder, i.e. 1. Now write this gcd (one) as a linear combination of 2651624496 and 7 by working back up the tree that we just created: 1 = 7 - 2*3 = 7 - 2*(2651624496 - 7*378803499) = 7*757606999 - 2*2651624496 Thus we have: 7*757606999 - 2*2651624496 = 1 Now do "mod 2651624496" on both sides to obtain: 7*757606999 = 1 mod 2651624496 Thus d = 757606999 Now we compute: C^d mod N = 983830091^757606999 mod 2651733127 Of course, we use modular exponentiation so that the numbers don't get too large. The answer is 211911, which becomes USK. We check that this is the right answer by noting that if it is in fact correct, then 211911^e = C mod N Computing 211911^e = C mod N gives 983830091 which is the right answer. It seems as if the answer should be "USA" but then the plaintext would be 211901 and then C would be (211901)^7 mod N = 1009910366 and this isn't the value of C that was given to us. So maybe the person who converted the phrase USA into a plaintext number made a mistake... I hope this helps. Please write back if you'd like to talk about this some more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.