Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 686
  • Last Modified:

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
Asked:
jtiernan2008
  • 3
  • 3
  • 2
5 Solutions
 
ozoCommented:

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
 
jtiernan2008Author 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
 
NovaDenizenCommented:
All integers from 1 to 30 are invertible mod 31.
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
jtiernan2008Author Commented:
thank you but what exactly does this mean?
0
 
ozoCommented:
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
 
NovaDenizenCommented:
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
 
jtiernan2008Author Commented:
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?
0
 
ozoCommented:
yes, as I understand the word "valid"
0

Featured Post

Threat Trends for MSPs to Watch

See the findings.
Despite its humble beginnings, phishing has come a long way since those first crudely constructed emails. Today, phishing sites can appear and disappear in the length of a coffee break, and it takes more than a little know-how to keep your clients secure.

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