Реализация Rsa с BigInteger не работает для больших чисел

Я пытаюсь использовать простое шифрование/дешифрование RSA, используя BigInteger. Он отлично работает для меньших чисел, но не для больших:

BigInteger messageToInt = 111098; 
BigInteger enc = BigInteger.ModPow(messageToInt, publicKey, n);
BigInteger dec = BigInteger.ModPow(enc, privateKey, n); // should be same as messageToInt
Console.WriteLine(dec);

Ключи взяты из примера из Вики - privateKey = 413, publicKey = 17, n = 3233.

  • для messageToInt = 1500: dec = 1500 (что нормально).
  • для messageToInt = 15000: dec = 2068. (какая?!).

rsa c# public-key-encryption biginteger
person Liad Sagi    schedule 30.08.2019    source источник
comment
RSA не используется для шифрования. Даже при использовании вам нужна хорошая прокладка, такая как PKCS # 1.5 или OAEP. Для подписи можно использовать RSA, на этот раз вам понадобится схема подписи RSA-PSS. Также вы можете использовать RSA для обмена ключами как RSA-KEM. Шифрование является наименее используемым среди них. См. этот хороший ответ   -  person kelalaka    schedule 31.08.2019

Ответы (1)


arrow_upward
3
arrow_downward

На самом деле это сработало идеально:

15000 mod 3233 = 2068.

Поскольку RSA опирается на модульную арифметику, вы ограничены простыми текстами, размер которых меньше n. Невозможно различить, был ли обычный текст 2068, 2068 + n, 2068 + 2n и т. д.

Решение заключается в том, чтобы либо разбить обычный текст на части, меньшие n, либо увеличивать n до тех пор, пока туда не поместится обычный текст.

person janw    schedule 30.08.2019
comment
О, интересно .. никогда не видел, чтобы этот факт упоминался раньше. Как это работает? Почему сообщения длиннее n не работают? редактировать - я понимаю, почему, когда вы говорите только о моде. Как власть вступает в игру? - person Liad Sagi; 30.08.2019
comment
Модульное возведение в степень (ModPow) выполняет многократное умножение и модульное сокращение (например, возвести в квадрат и умножить). В конце результат сводится к наименьшему возможному числу по модулю n. Это немедленно означает, что вы не можете получить число, равное или превышающее n, поскольку оно n будет многократно вычитаться, пока не будет достигнуто число меньше n. - person janw; 30.08.2019
comment
Спасибо! Я знаю, что rsa в основном используется для шифрования небольших вещей или симметричных ключей, а также большинство реализаций RSA делят сообщение на блоки. Но можно ли с уверенностью сказать, что еще одним преимуществом использования все более и более крупных ключей является возможность шифрования больших блоков данных? редактировать - по причинам выше - person Liad Sagi; 31.08.2019
comment
Основная цель увеличения размера блока состоит в том, чтобы затруднить взлом шифра (например, путем факторизации n). Хотя теоретически увеличение размера ключа позволяет увеличить размер блоков, на практике это не имеет значения, как вы уже сказали: ключ AES имеет от 128 до 256 бит, поэтому оставшиеся 1000 бит в основном используются для заполнения (например, OAEP). ). Также обратите внимание, что удвоение размера ключа сильно влияет на производительность: webmasters.stackexchange.com/a/102372. выполнение RSA-2048 дважды намного дешевле, чем однократное выполнение RSA-4096. - person janw; 31.08.2019
comment
@JanWichelmann: Massive, возможно, преувеличивает. Выполнение RSA-2048 дважды, вероятно, немногим менее чем в два раза быстрее, чем однократное выполнение RSA-4096. - person President James K. Polk; 31.08.2019