0

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)
Improve this question
1
  • 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. Commented Feb 15, 2017 at 23:29

2 Answers 2

Reset to default
2

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

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Of course, as long as it fits, you can also take a few characters together. You first encode them to bytes (e.g. using ASCII) and then convert the resulting bytes into an integer.
But when decrypting, how would you determine what integer corresponds to which letter? eg. Would 15 be "o" or "ae"?
Neither. You would expect the same character value as in x = ord(x) #converts character into ASCII reference number (considering single characters). Of course you should not use x = chr(x) because that throws away information after encryption.
1

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.

Improve this answer

1 Comment

My professor told us that e cannot be a factor of n, so that's why I checked n%e==0. How would I go about encoding the whole string into a single number?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.