Solved

simple question about an affine cipher

Posted on 2008-10-14
8
660 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
[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
  • Learn & ask questions
  • 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
2017 Webroot Threat Report

MSPs: Get the facts you need to protect your clients.
The 2017 Webroot Threat Report provides a uniquely insightful global view into the analysis and discoveries made by the Webroot® Threat Intelligence Platform to provide insights on key trends and risks as seen by our users.

 
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

Put Machine Learning to Work--Protect Your Clients

Machine learning means Smarter Cybersecurity™ Solutions.
As technology continues to advance, managing and analyzing massive data sets just can’t be accomplished by humans alone. It requires huge amounts of memory and storage, as well as the high-speed power of the cloud.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
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 …

738 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