n, e Help Deciphering It
Date: 06/21/2012 at 16:49:50 From: Randy Subject: ciphers My friend gave me this sequence of numbers and told me to decipher them: 443-448-581-481-450-231-401-88-397-247-529-466- 169-443-324-355-450-544-466-274-684-345-167-529 He did not mention what type of cipher he used, only that he wanted me to try to decipher it. He also told me that n is 703, and that e is 17. But I can't figure out what type of cipher it is. I have tried a Caeser cipher, using modular arithmetic: "[number](mod 26) is congruent to...." I converted all 24 numbers to letters and then applied all 25 different shifts using a shift calculator online. Then I thought there might be more then one Caeser cipher, so I broke the sequence down into alternating groups of 2 and checked the letter frequency. He said something about "e" not being in the answer, so I shifted whatever came up most to "A." I then did that with triples, and plugged those answers into another Caeser cipher calculator. Finally, I tried seeing if the numbers were part of some function, or even polynomial function. I found out that, if it was, it would have to be a 16- or 17-degree polynomial. I decided that nobody would make you solve for the coefficients of a polynomial by making a 17- or 18-variable system -- and gave up. I have tried everything I could think of, so now I seek the advice of an expert. Thank you.
Date: 06/21/2012 at 20:23:15 From: Doctor Vogler Subject: Re: ciphers Hi Randy, Thanks for writing to Dr. Math. The "numbers" your friend gave you suggest that he is using an RSA cipher, where n and e refer not to letters, but variables. http://en.wikipedia.org/wiki/RSA_algorithm That means that he encrypted each of his original (message) numbers x by computing ... y = x^e (mod n) ... or y = x^17 (mod 703). To break RSA encryption, you should first factor n. Normally, this is the hard part, but since n is so small, it is easy to factor: n = 703 = 19 * 37. Next, you need to compute the decryption exponent: d = 1/e (mod phi(n)) = 1/17 (mod 18 * 36) = 305 (mod 648). Finally, decode the message by computing this for each of the encrypted numbers y: x = y^305 (mod 703) You can do this using the modular exponentiation algorithm (or "powermod"). For example, take your number y, and then square it 8 times, reducing mod 703 each time (that means to divide by 703 and only keep the remainder). 443^2 = 112 (mod 703) 443^4 = 112^2 = 593 (mod 703) 443^8 = 593^2 = 149 (mod 703) 443^16 = 149^2 = 408 (mod 703) 443^32 = 408^2 = 556 (mod 703) 443^64 = 556^2 = 519 (mod 703) 443^128 = 519^2 = 112 (mod 703) 443^256 = 112^2 = 593 (mod 703) Now, since 305 = 256 + 32 + 16 + 1, you compute 443^305 = 443^256 * 443^32 * 443^16 * 443 = 593 * 556 * 408 * 443 = 73 (mod 703) This is the decrypted value of the first number. It is likely that this is intended as an ASCII number, where the capital letters are 65 = A, 66 = B, 67 = C, etc. The lowercase letters are 97 = a, 98 = b, 99 = c, etc. I'll let you work out the rest of the code. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Date: 06/21/2012 at 21:20:53 From: Randy Subject: Thank you (ciphers) Thank you. Well, in the end his message turned out to be "If you figure this out tell me." Thank you so much! I worked on this a long time and had never even heard about RSA ciphers. Thank you, thank you, thank you.
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.