0
votes

I am doing a project for one of my classes. The professor is having us make an RSA encryption/decryption program without using the crypto libraries (all done from scratch). So I get my p, q, n, phi, e, and d and everything is fine. The problem I run into is trying to encrypt it. I take the ASCII ordinance of each character and encrypt using my e and n. However, the number I get back is far out of range to change back into an ASCII character. How can I change that number into a character and still be able to decrypt it using my private key later? Here is my rough code so far:

import random

def generatePrimes():
    prime = False
    while prime == False:
        n = random.randint(10000, 100000) #generates random integer between 10,000 and 100,000
        if n % 2 != 0: #checks if integer is divisible by 2
            for x in range(3, int(n ** 0.5), 2): #starts at 3, increments by 2 to check if integer is divisible by anything
                if n % x == 0:
                    break #if integer divides a number x and  has no remainder, it isn't prime and the loop breaks
                else:
                    prime = True #a prime number is found

    return n #returns prime number



def  findE(n, pn):
    factor = True
    while factor == True:
        e = random.randint(3, 35) #creates random integer from 2 to p(n), but keeps it small for ease of use
        if n % e != 0: #checks if integer is divisible by n
            factor = False #if remainder is not 0, the integer isn't divisible by n. if remainer is 0, the loop restarts to choose another number

     return e



def findD(e, pn):
    d = pow(e, pn - 2, pn) #calculates d

    return d



def encryption():
    p = generatePrimes() #creates random prime number for p
    q = generatePrimes() #creates random prime number for q
    n = p * q #finds n by multiplying p and q
    pn = (p - 1) * (q - 1) #finds p(n)
    e = findE(n, pn) #creates e such that 1 < e < p(n)
    d = findD(e, pn) #creates d

    print('n =', n)
    print('e =', e)
    print('d =', d)

    print('Keys have been created.')
    message = input('Enter the message you wish to encrypt:')

    newMessage = '' #creates new string that the encrypted message will be put into
    for x in message:
        x = ord(x) #converts character into ASCII reference number
        x = (x ** e) % n #encrypts using rsa algorithm
        x = chr(x)
        newMessage += x #places new character into the encrypted string

    print('Here is your encrypted message:')
    print(newMessage) 


def decryption():
    n = int(input('Enter in a value for n:'))
    d = int(input('Enter in a value for d:'))

    newMessage = []
    message = input('Enter the message you wish to decrypt:')
    for x in message:
        x = ord(x)
        x = (x ** d) % n
        x = chr(x)
    newMessage += x

    print('Here is your decrypted message:')
    print(newMessage)
2
On a side note, writing your own encryption algorithm is horrible practice in real world application. Not relevant to answering the question, but I just want to help with the understanding of good principles within the programmatic world. - the_constant

2 Answers

2
votes

Generally, for this kind of toy RSA implementations, each character is encrypted separately. Now encryption will result in a value between zero and N, the modulus.

Probably the easiest way to encode this value is to always make sure it is dLen decimals in size where dLen is the number of decimals required to display the modulus N. You can do this by prefixing zero digits until the value is of the right size. Then, to decrypt, read dLen characters, convert it into a number, and perform the modular exponentiation with the private key.

The same thing happens for actual RSA encryption (e.g. RSA-OAEP). Here the result of the encryption is converted to the same number of bytes required to hold the modulus. This function is called I2OSP. Implementing above will let you practice implementing such function.


Tamas is of course correct when he explains that - in real life - this is not how to encrypt strings. You'd use a hybrid cryptosystem instead where a block cipher encrypts the plaintext (converted to bytes).

1
votes

You must not encrypt every character in the string separately. You must encode the whole string in a single number, and execute the rsa encryption on that number. The same must be done in reverse while decoding. RSA has standards how long the character sequence can be, how it should be encoded and padded. (see PKCS1 or OAEP)

Btw your findE function is flawed. No one cares if n%e==0, but e and pn must be coprime. Simplest is to choose a not-too-small prime for e like e==65537. It doesn't have to be random.