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.

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

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search