Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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.
Associated Topics:
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/