Solved

# simple question about an affine cipher

Posted on 2008-10-14
660 Views
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
Question by:jtiernan2008
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 3
• 3
• 2

LVL 84

Assisted Solution

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

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

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

LVL 1

Author Comment

ID: 22733294
thank you but what exactly does this mean?
0

LVL 84

Assisted Solution

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

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

ID: 22745307
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

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

## Featured Post

Question has a verified solution.

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

### Suggested Solutions

mysql Encryption with PHP 8 117
Meaning of e^x sin(x) 2 57
Pre-Linear Regression Tests 2 61
MCAT Verbal Reasoning 2 19
Healthcare providers, insurance companies and other covered entities trust eFax Corporate to transmit their most sensitive documents. eFax Corporate can help your organization implement a HIPAA compliant cloud faxing solution.
Worried about if Apple can protect your documents, photos, and everything else that gets stored in iCloud? Read on to find out what Apple really uses to make things secure.
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â€¦
With Secure Portal Encryption, the recipient is sent a link to their email address directing them to the email laundry delivery page. From there, the recipient will be required to enter a user name and password to enter the page. Once the recipient â€¦
###### Suggested Courses
Course of the Month8 days, 9 hours left to enroll