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.
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
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
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
Thanks a million lads....
So to answer the question -
"Determine which of the following values for a and b yield a valid decryption function"
Basically they all do?
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