Solved

simple question about an affine cipher

Posted on 2008-10-14
8
654 Views
Last Modified: 2008-10-17
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
Comment
Question by:jtiernan2008
  • 3
  • 3
  • 2
8 Comments
 
LVL 84

Assisted Solution

by:ozo
ozo earned 60 total points
ID: 22717381

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
 
LVL 1

Author Comment

by:jtiernan2008
ID: 22721246
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
 
LVL 22

Assisted Solution

by:NovaDenizen
NovaDenizen earned 65 total points
ID: 22721476
All integers from 1 to 30 are invertible mod 31.
0
Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 1

Author Comment

by:jtiernan2008
ID: 22733294
thank you but what exactly does this mean?
0
 
LVL 84

Assisted Solution

by:ozo
ozo earned 60 total points
ID: 22733511
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
 
LVL 22

Accepted Solution

by:
NovaDenizen earned 65 total points
ID: 22733898
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
 
LVL 1

Author Comment

by:jtiernan2008
ID: 22745307
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
 
LVL 84

Assisted Solution

by:ozo
ozo earned 60 total points
ID: 22745383
yes, as I understand the word "valid"
0

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Triangles - computing angles 6 50
Scanned document protection 2 50
On-premise Digitally Signed/Encrypted Secure E-mail Solutions 1 48
Oracle encryption 12 48
If you thought ransomware was bad, think again! Doxware has the potential to be even more damaging.
Lithium-ion batteries area cornerstone of today's portable electronic devices, and even though they are relied upon heavily, their chemistry and origin are not of common knowledge. This article is about a device on which every smartphone, laptop, an…
The Email Laundry PDF encryption service allows companies to send confidential encrypted  emails to anybody. The PDF document can also contain attachments that are embedded in the encrypted PDF. The password is randomly generated by The Email Laundr…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

792 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question