## Inverse Modulo

This is the place for queries that don't fit in any of the other categories.

### Inverse Modulo

Hello, I am trying to make an encryption program. So far, I have the encryption done, but since the encryption includes a modulus in it, I can't seem to figure out how to do the inverse modulo.

Encryption:
Code: Select all
`alpha = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890-+,./_!@#\$%^&*()"message = "hello"messList = [8, 5, 12, 12, 15] # the positions of each letter in message in the 'alpha' variablefor each of the numbers: this is basically my main encryption algo..for the first letter 'h' or '8'(8 * 2 ** 2)%79 # the second two is the first prime number and 79 is the length of the 'alpha' variablefor the second letter 'e' or '5'(5 * 2 ** 3)%70 # the three is the second prime numberafter this pattern occurs for the rest of the numbers:I get: [32, 40, 68, 35, 68]then I put these values into 'alpha' and the encryption is complete:hello = FN_I_`

I can't seem to figure out how to reverse this, like going from [32, 40, 68, 35, 68] to [8, 5, 12, 12, 15]

Snaek

Posts: 6
Joined: Thu Mar 14, 2013 1:15 am

### Re: Inverse Modulo

(1) There is no inverse of modulo. It is a one-way function.
(2) I have no idea what is going on in your code. It's not Python. There is no indentation, and there is English outside of a comment.
(3) I have no idea what you're trying to get when you talk about going from one list to the other. I have no idea what operation you mean to perform.
Join the #python-forum IRC channel on irc.freenode.net for off-topic chat!

Please prefer not to PM members. The point of the forum is so that anyone can benefit. We don't want to help you over PMs/emails/Skype chats that others can't benefit from

micseydel

Posts: 2026
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

### Re: Inverse Modulo

Snaek wrote:Hello, I am trying to make an encryption program. So far, I have the encryption done, but since the encryption includes a modulus in it, I can't seem to figure out how to do the inverse modulo.

Encryption:
Code: Select all
`alpha = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890-+,./_!@#\$%^&*()"message = "hello"messList = [8, 5, 12, 12, 15] # the positions of each letter in message in the 'alpha' variablefor each of the numbers: this is basically my main encryption algo..for the first letter 'h' or '8'(8 * 2 ** 2)%79 # the second two is the first prime number and 79 is the length of the 'alpha' variablefor the second letter 'e' or '5'(5 * 2 ** 3)%70 # the three is the second prime numberafter this pattern occurs for the rest of the numbers:I get: [32, 40, 68, 35, 68]then I put these values into 'alpha' and the encryption is complete:hello = FN_I_`

I can't seem to figure out how to reverse this, like going from [32, 40, 68, 35, 68] to [8, 5, 12, 12, 15]

Your algorithm maps a character from one position to another in your list of characters using a simple formula:

b_k = (a_k * 2 ** p_k) mod 79

where a_k is the position of the k-th character of the plaintext in your list of characters, p_k is the k-th prime number, and b_k is the position of the encrypted character in your list of characters. 79 is the length of your list.

Code: Select all
`>>> (8 * 2**2) % 7932>>> (5 * 2**3) % 7940>>> (12 * 2**5) % 7968>>> (12 * 2**7) % 7935>>> (15 * 2**11) % 7968`

It is possible to invert a modulo operation with some constraints. Since 79 happens to be prime, and the original value you want to recovers is less than 79, it is possible. The algorithm to calculate the inverse is known as the extended GCD (or extended Euclidean) algorithm. I'll let you do some research on that algorithm and then you can post your code and we'll help you with it.

Hint: you want to calculate the inverse of 2**p_k mod 79.

I'll let you work on writing some code....

casevh
casevh

Posts: 95
Joined: Sat Feb 09, 2013 7:35 am

### Re: Inverse Modulo

This was just a side project from my main encryption program, which was using RSA Encryption.

I have successfully completed the encryption part, but I don't like how the same letter gets encrypted into the same number. Is that what's supposed to happen with RSA Encryption?

That's why I started the little side project, so even if I type the same letters, they will all have different numbers.
Snaek

Posts: 6
Joined: Thu Mar 14, 2013 1:15 am

### Re: Inverse Modulo

Most encryption algorithms are designed to encrypt blocks. The block size may be 64 bits, 128 bits, or larger. The direct implementation of an encryption algorithm will (usually) always map the same input block to the same output block. I interpret your previous post to imply that you are encrypting one character at a time. The RSA algorithm is designed to encrypt large blocks, say 1024 bits or larger. The will decrease the odds of encrypting the same block but a graphics file might have enough repetition to create repeated blocks.

For serious implementations, block chaining is performed. In block chaining, each encrypted block depends in some way on the all the previous blocks. This will prevent the same plaintext block from always getting encrypted to the same ciphertext.

casevh
casevh

Posts: 95
Joined: Sat Feb 09, 2013 7:35 am