Solved

simple question about an affine cipher

Posted on 2008-10-14
8
639 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
 
LVL 1

Author Comment

by:jtiernan2008
ID: 22733294
thank you but what exactly does this mean?
0
How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

 
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

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Cybersecurity has become the buzzword of recent years and years to come. The inventions of cloud infrastructure and the Internet of Things has made us question our online safety. Let us explore how cloud- enabled cybersecurity can help us with our b…
As a financial services provider, your business is impacted by two of the strictest federal regulations on record: the Sarbanes-Oxley Act and the Gramm-Leach-Bliley Act. Correctly implementing faxing into your organization to provide secure, real-ti…
Get a first impression of how PRTG looks and learn how it works.   This video is a short introduction to PRTG, as an initial overview or as a quick start for new PRTG users.
This video shows how to remove a single email address from the Outlook 2010 Auto Suggestion memory. NOTE: For Outlook 2016 and 2013 perform the exact same steps. Open a new email: Click the New email button in Outlook. Start typing the address: …

743 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

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now