# Math Help - Trivial cryptography

1. ## Trivial cryptography

I'm trying to solve the task 3.13.2 (b) from the book "Introduction to Cryptography" by Wade Trappe & Lawrence Washington:

Suppose you write a message as a number m (mod 31). Encrypt m as m^7 (mod 31). How would you decrypt? (Hint: Decryption is done by raising the ciphertext to a power mod 31. Fermat's theorem will be useful.)

Any ideas?

2. Hello,
Originally Posted by posix_memalign
I'm trying to solve the task 3.13.2 (b) from the book "Introduction to Cryptography" by Wade Trappe & Lawrence Washington:

Suppose you write a message as a number m (mod 31). Encrypt m as m^7 (mod 31). How would you decrypt? (Hint: Decryption is done by raising the ciphertext to a power mod 31. Fermat's theorem will be useful.)

Any ideas?
Fermat's theorem says that if p is a prime, $m^p=m (\bmod p)$

So $m^{31}=m (\bmod 31)$
And $m^{30}=1 (\bmod 31)$

My thought is that you find a number in the form 30k+1 that is divisible by 7.
For example 91=7x13.

$N^{13}=(m^7)^{13}=m^{91}=m^{30\times 3+1}=(m^{30})^3 \cdot m=m (\bmod 31)$
where N is the message you want to decrypt

Not too sure if it's correct though

3. Originally Posted by Moo
Hello,

Fermat's theorem says that if p is a prime, $m^p=m (\bmod p)$

So $m^{31}=m (\bmod 31)$
And $m^{30}=1 (\bmod 31)$

My thought is that you find a number in the form 30k+1 that is divisible by 7.
For example 91=7x13.

$N^{13}=(m^7)^{13}=m^{91}=m^{30\times 3+1}=(m^{30})^3 \cdot m=m (\bmod 31)$
where N is the message you want to decrypt

Not too sure if it's correct though
Thanks for the help, but I don't quite follow.

So based on this then:

e(m) = m^7 (mod 31)
d(m) = m^13 (mod 31)

Where e() is the encryption function and d() is the decryption function.
If tested with m = 2 this seems to encrypt to 4 and then decrypt back to 2, ok.
However I don't understand how you determined that it should be raised to the power of 13?

4. Originally Posted by posix_memalign
Thanks for the help, but I don't quite follow.

So based on this then:

e(m) = m^7 (mod 31)
d(m) = m^13 (mod 31)

Where e() is the encryption function and d() is the decryption function.
If tested with m = 2 this seems to encrypt to 4 and then decrypt back to 2, ok.
However I don't understand how you determined that it should be raised to the power of 13?
The purpose is to find k such that $(m^7)^k=m (\bmod 31)$

That is $m^{7k}=m (\bmod 31)$

We know that $m^{30}=1 (\bmod 31)$, thanks to Fermat's theorem.

Hence for any integer j, we have $(m^{30})^j=m^{30j}=1^j=1 (\bmod 31)$

Therefore, $m^{30j+1}=m (\bmod 31)$

So it is sufficient that $7k=30j+1$

Find by trial and error that if j=3, then k=13.
And this k is your decryption key.