Followers 0

# affine decryption?

## 8 posts in this topic

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

0

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

Edited by Bacterius
0

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

0

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

0

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

0

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

0

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

0

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

0

## Create an account

Register a new account