• Advertisement
Sign in to follow this  

affine decryption?

This topic is 1784 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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).

Share this post


Link to post
Share on other sites

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...

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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) [...]

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement