View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

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

8 replies to this topic

### #1jdub  Members

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.

### #2frob  Moderators

Posted 03 March 2013 - 07:34 PM

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 occasionally write about assorted stuff.

### #3Bacterius  Members

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

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

“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”

### #4DanielKruyt  Members

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  Members

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

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

### #7Bacterius  Members

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.

“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”

### #8Álvaro  Members

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

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.