[Webinar] Streamline your web hosting managementRegister Today

x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 692

# simple question about an affine cipher

I have a question from college. Simple one as I am new to the subject.

2.      An affine cipher with a modulus m=31 is used. Given the encryption function

E(x) = (ax+b) mod 31

Determine which of the following values for a and b yield a valid decryption function
------------------------
a      B
20      4
21      5
13      7
1      5
------------------------
I have found that the invertible integers mod31 are {1,3,5,7,9,11,15,17,19,21,23,25}
so must utilize one of the invertible integers for a.
any value of b is acceptable, however since everything is mod31 so need to use a
number between 0 and 25.

So I would take it that the answer is 21, 5 i.e. the second one?

I just want to make sure that I am correct and that I am understanding the question correctly.
0
jtiernan2008
• 3
• 3
• 2
5 Solutions

Commented:

E(x) = (20x+4) mod 31
is decrypted by x=(14E+23) mod 31

E(x) = (21x+5) mod 31
is decrypted by x=(3E+16) mod 31

E(x)=(13x+7)  mod 31
is decrypted by (12E+9)%31

E(x)=(1x+5)  mod 31
is decrypted by (1E+26)%31
0

Author Commented:
Hi ozo,

I am a newbie and am really looking to understand the question better.
When he says "Determine which of the following values for a and b yield a valid decryption function" from what you say above does this mean that they all yield a valid function since you have calculated out each one?
How do you come to for example;
E(x) = (20x+4) mod 31
is decrypted by x=(14E+23) mod 31

thanks a million

0

Commented:
All integers from 1 to 30 are invertible mod 31.
0

Author Commented:
thank you but what exactly does this mean?
0

Commented:
E(x) = (20x+4) mod 31
x=(14E+6) mod 31
= (14 ( (20x+4) mod 31) +6 ) mod 31
= (( (280x+56) mod 31) +6 ) mod 31
= (( (280 mod 31 )x+(56 mod 31)) mod 31) +6 ) mod 31
= (((1)x+25) mod 31) + 6) mod 31
= (x +25+6) mod 31
= (x + (25+6) mod 31) mod 31
= (x + (31) mod 31) mod 31
= (x +0) mod 31
= x mod 31
0

Commented:
For any prime p, to get the multiplicative inverse of n modulo p you just calculate n^(p-2) mod p
For instance, when n=2 and p=31
(everything here is mod 31)
2^1 = 2
2^2 = 4
2^4 = 4*4 = 16
2^8 = 16*16 = 256 = 8
2^16 = 8*8 = 64 = 2
2^29 = 2^16 * 2^8 * 2^4 * 2^1
= 2 * 8 * 16 * 2
= 16 * 32
= 16*1
= 16
and 2*16 = 32 = 1, so 2 and 16 are inverses.

If
E = a*x + b
and a and c are inverses, that is
a*c = c*a = 1
then
(E - b)*c =
= E*c - b*c
= (a*x + b)*c - b*c
= a*x*c + b*c - b*c
= a*c*x
since a*c=1,
= x
So when you are presented with an encryption function like
E = a*x + b
then you can calculate c, the inverse of a, and say that
x = E*c - b*c
0

Author Commented:
So to answer the question -
"Determine which of the following values for a and b yield a valid decryption function"
Basically they all do?
0

Commented:
yes, as I understand the word "valid"
0

## Featured Post

• 3
• 3
• 2
Tackle projects and never again get stuck behind a technical roadblock.