RSA implementation decryption/ encryption

Question

I'm trying to implement RSA. But I've got a few problems with this. I´m trying to encrypt a String with 2 prime numbers.

p= 1606938044258990275541962092341162602522202993782792835301611
q= 3213876088517980551083924184682325205044405987565585670603103

First I do what has to be done for the RSA algorithm. After I've encrypted the String I tried to decrypt it as well. But the result is something like this: ÜŞϟʐͶz̽ć

def xgcd(a, b):
    """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
    x0, x1, y0, y1 = 0, 1, 1, 0
    while a != 0:
        q, b, a = b // a, a, b % a
        y0, y1 = y1, y0 - q * y1
        x0, x1 = x1, x0 - q * x1
    return b, x0, y0

def genKeypair(p, q):

    n = p * q
    phiN = (p - 1) * (q - 1)
    e = 65537

    d = egcd(phiN, e)
    return n, e, d


# encrypt message and return cipher
def encrypt(m, n, e):
    m1 = ""
    # Turn message string into ascii so it can be used for encryption
    for x in range(len(m)):
        m1 += '{0:03}'.format(ord(m[x]))
    # encrypt
    c = squareAndMultiply(int(m1), e, n)
    print(c)
    return c


# decrypt cipher and return message
def decrypt(c, n, d):
    # decrypt c
    m = squareAndMultiply(c, d, n) #% n
    # put decryption result into ascii format and use ascii to decode it
    m = str(m)
    tmp = ""
    message = ""
    i = 0
    if int(m[0] + m[1] + m[3]) > 255:
        m = "0" + m
    for x in range(len(m)):
        tmp = tmp + m[x]
        i += 1
        if i % 3 == 0:
            message += chr(int(tmp))
            tmp = ""
    return message

My square and multiply method looks like this:

def squareAndMultiply(x, n, m=0):

# turn exponent into binary
bin = '{0:b}'.format(n)
r = x

# loop through the string representing the binary form of the exponent while ignoring the leftmost bit and perform
# the appropriate operations on r
for i in range(1, len(bin)):
    if (bin[i] == "0"):
        r *= r % m
    else:
        r *= r % m
        r *= x % m

# check for m being greater than 0, ignore it otherwise
if (m > 0):
    return r % m
else:
    return r

Has anyone an idea what could be wrong and what has to be changed, that the decryption gives the right answer?

I've used pow and got the same result as my own implementation. I need to implement square and multiply by my own. — Kevin E.

Topaco Topaco · Accepted Answer · 2019-05-27T23:18:26

In the code, the plaintext is encoded into a string by using the corresponding decimal ASCII-code (formatted to three digits) for each character, e.g.

ABCDEF -> 065066067068069070

Then, the string is converted to an integer m which is used as message and encrypted according to

$c = m^{e} \; mod \; n$

This concept results in m becoming larger and larger with increasing plaintext length. At some point m violates the condition m < n and the algorithm fails (see RSA, Operation)!

The plaintext length at which the algorithm fails depends on n and can be determined as follows: In the example, n is a 121-digit number. Because 121/3 = 40.33..., a maximum of 40 characters can be encrypted without violating the condition m < n, i.e. from incl. 41 the encryption will generally fail. This can be verified with the following code:

p = 1606938044258990275541962092341162602522202993782792835301611
q = 3213876088517980551083924184682325205044405987565585670603103

n = p * q
phiN = (p - 1) * (q - 1)
e = 65537
d = egcd(phiN, e)[2]

encrypted = encrypt('0123456789012345678901234567890123456789', n, e);      # will succeed
#encrypted = encrypt('01234567890123456789012345678901234567890', n, e);    # will fail
decrypted = decrypt(encrypted, n, d);
print('>' + decrypted + '<')

A possible solution to this problem is to divide the plaintext into blocks with the same number of characters (the last block usually contains fewer characters). This number should correspond to the maximum possible number of characters, so that the condition m < n is not violated (= 40 in the posted example). Then each block is individually encoded and encrypted (in the same way as before).

RSA implementation decryption/ encryption

1 Answers