Расшифровка / шифрование реализации RSA - PullRequest
Новая
       14

Расшифровка / шифрование реализации RSA

0 голосов
/ 27 мая 2019

Я пытаюсь реализовать RSA. Но у меня есть несколько проблем с этим. Я пытаюсь зашифровать строку с двумя простыми числами. 

p= 1606938044258990275541962092341162602522202993782792835301611
q= 3213876088517980551083924184682325205044405987565585670603103

Сначала я делаю то, что должно быть сделано для алгоритма RSA. После того, как я зашифровал строку, я тоже попытался ее расшифровать. Но результат примерно такой: ÜŞϟʐͶ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

Мой метод квадрата и умножения выглядит следующим образом: 

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

Кто-нибудь знает, что может быть не так и что нужно изменить, что расшифровка дает правильный ответ?

1 Ответ

0 голосов
/ 28 мая 2019

В коде открытый текст кодируется в строку с использованием соответствующего десятичного ASCII-кода (отформатированного до трех цифр) для каждого символа, например, 

ABCDEF -> 065066067068069070

Затем,строка преобразуется в целое число m, которое используется в качестве сообщения и шифруется в соответствии с

. Эта концепция приводит к увеличению и увеличению m с увеличением длины открытого текста.В какой-то момент m нарушает условие m < n, и алгоритм терпит неудачу (см. RSA, Операция )!

Длина открытого текста, при котором происходит сбой алгоритма, зависитна n и может быть определено следующим образом: В этом примере n - это 121 -значное число.Поскольку 121/3 = 40.33..., может быть зашифровано максимум 40 символов без нарушения условия m < n, то есть от вкл.41 шифрование обычно не выполняется.Это можно проверить с помощью следующего кода: 

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 + '<')

Возможное решение этой проблемы - разделить открытый текст на блоки с одинаковым количеством символов (последний блок обычно содержит меньше символов).Это число должно соответствовать максимально возможному количеству символов, чтобы условие m < n не нарушалось (= 40 в опубликованном примере).Затем каждый блок кодируется и шифруется индивидуально (так же, как и раньше).

...