Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


affine decryption?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
8 replies to this topic

#1 jdub   Members   -  Reputation: 419

Like
0Likes
Like

Posted 03 March 2013 - 06:35 PM

I have an assignment in CS class to create an affine cipher where the equation for encrypting a character is ax+b.  I have created the encryption  function.  However, I am not sure how to create a decryption function because the inverse of the affine transform ((y-b)/x) won't work because there is division involved.  I have seen the wikipedia page on affine encryption/decryption however I do not understand the decryption section.  Could someone explain this to me and perhaps give a little pseudo-code to show me how i might go about creating a decryption function?

 

Thanks


J.W.

Sponsor:

#2 frob   Moderators   -  Reputation: 22255

Like
3Likes
Like

Posted 03 March 2013 - 07:34 PM

Ask your teacher.

If you don't understand the material it is likely that other students also don't understand the material. It also lets the instructor know what areas he needs to cover in more depth.

As for the algorithm itself, the Wikipedia page does an excellent job of describing it. Considering they include a careful walk through I'm not sure what you'd be missing. It looks like you wrote down the wrong function, but that is easily remedied by carefully reading the description of the decryption algorithm.

Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I write about assorted stuff.


#3 Bacterius   Crossbones+   -  Reputation: 9068

Like
0Likes
Like

Posted 04 March 2013 - 01:14 AM

Check out the modular multiplicative inverse. This is the equivalent of division modulo some number. Implementing it using the EEA can be tricky, though there is a shortcut.

 

Also, as Frob says, you have the wrong decryption function. You're trying to get "x" back, not "a". Look through it again.

 

Also, for bonus points, implement a message decryption function without using "a" nor "b". wink.png


Edited by Bacterius, 04 March 2013 - 01:20 AM.

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#4 DanielKruyt   Members   -  Reputation: 265

Like
0Likes
Like

Posted 04 March 2013 - 08:52 AM

Hi there, ( first post here :) )

Provided that 'a' is an odd number ( ie lowest bit is one ), the division will give you a valid 'x' in return. You will see a lot of PRNGs that use multiplication, but all will use odd factors.

 

Regards,
Daniel Kruyt



#5 Álvaro   Crossbones+   -  Reputation: 13662

Like
0Likes
Like

Posted 04 March 2013 - 12:08 PM

Just so I know what we are talking about here, the encryption method is simply to take the message character by character and encoding each character x as (a*x+b)%256. Is that right?

 

If that's the case and a is odd (which it should be), you can divide by a just fine, understanding the division as multiplying by a's inverse modulo 256. There are several methods you can use to find a multiplicative inverse, but 256 is such a small number that everything works (including looping over all odd numbers and checking if the product with a is 1 mod 256).



#6 Paradigm Shifter   Crossbones+   -  Reputation: 5410

Like
0Likes
Like

Posted 05 March 2013 - 04:32 AM

There are multiple inverses of elements mod 256 though.

 

Modulo arithmetic mod p only forms a field (i.e. all non-zero elements have unique inverses with respect to multiplication) if and only if p is prime...


"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#7 Bacterius   Crossbones+   -  Reputation: 9068

Like
0Likes
Like

Posted 05 March 2013 - 04:34 AM

There are multiple inverses of elements mod 256 though.
 
Modulo arithmetic mod p only forms a field (i.e. all non-zero elements have unique inverses with respect to multiplication) if and only if p is prime...

 

"a" is always chosen to be invertible modulo 26 (or 256, depending on the alphabet). Otherwise, decryption is indeed not possible.


The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#8 Álvaro   Crossbones+   -  Reputation: 13662

Like
0Likes
Like

Posted 05 March 2013 - 10:57 AM

There are multiple inverses of elements mod 256 though.

 

I think you missed this:

If that's the case and a is odd (which it should be) [...]



#9 Paradigm Shifter   Crossbones+   -  Reputation: 5410

Like
0Likes
Like

Posted 05 March 2013 - 12:42 PM

I guess so ;)

 

Then the rule is

 

a (mod n) has a unique inverse if and only if a and n are coprime (i.e. their greatest common divisor is 1). So that works if a is odd with n = 256 since n is a power of 2 hence coprime to any odd number.


"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS