Inverse Modulo

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

Inverse Modulo

Postby Snaek » Thu Mar 14, 2013 1:22 am

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' variable
for 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' variable
for the second letter 'e' or '5'
(5 * 2 ** 3)%70 # the three is the second prime number
after 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]

Can someone please help me with this?
Image
Snaek
 
Posts: 6
Joined: Thu Mar 14, 2013 1:15 am

Re: Inverse Modulo

Postby micseydel » Thu Mar 14, 2013 4:01 am

(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!

Please do not PM members regarding questions which are meant to be discussed publicly. The point of the forum is so that others can benefit from it. We don't want to help you over PMs or emails.
User avatar
micseydel
 
Posts: 1258
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

Re: Inverse Modulo

Postby casevh » Thu Mar 14, 2013 7:02 am

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' variable
for 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' variable
for the second letter 'e' or '5'
(5 * 2 ** 3)%70 # the three is the second prime number
after 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]

Can someone please help me with this?


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.

Your examples:

Code: Select all
>>> (8 * 2**2) % 79
32
>>> (5 * 2**3) % 79
40
>>> (12 * 2**5) % 79
68
>>> (12 * 2**7) % 79
35
>>> (15 * 2**11) % 79
68


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: 70
Joined: Sat Feb 09, 2013 7:35 am

Re: Inverse Modulo

Postby Snaek » Thu Mar 14, 2013 8:16 pm

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.
Image
Snaek
 
Posts: 6
Joined: Thu Mar 14, 2013 1:15 am

Re: Inverse Modulo

Postby casevh » Fri Mar 15, 2013 3:51 am

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: 70
Joined: Sat Feb 09, 2013 7:35 am


Return to General Coding Help

Who is online

Users browsing this forum: Google [Bot] and 7 guests