Почему команда факторов порождает бессмыслицу по модулю RSA?

Хорошо, поэтому я думаю, что, возможно, нашел недостаток … что-то. Честно говоря, я не знаю. Это такой странный сценарий.

Я пытался сломать очень маленькое асимметричное (RSA) шифрование, как проект «Доказательство концепции» одному из моих друзей. Для тех из вас, кто мало знает о RSA, я подробно рассмотрю важные факты. Если вы уже знаете о RSA, пропустите следующий абзац:

RSA – это асимметричный алгоритм шифрования (также известный как криптография с открытым / закрытым ключом). Это означает, что есть два ключа: общедоступный и закрытый. Любой может быть использован для шифрования, но только другой ключ может расшифровать. Поэтому, если я зашифрую небольшой текстовый файл с помощью закрытого ключа, только открытый ключ может его расшифровать. Это полезно при обмене ключами. Это работает с использованием математического принципа, называемого Prime Factorization (тот факт, что умножение двух простых чисел легко, но факторизация исходных 2 простых чисел из произведения затруднительна). Представьте себе свой открытый ключ, который может шифровать, но только ваш закрытый ключ может расшифровать. У вашего закрытого ключа есть 2 простых числа, и ваш открытый ключ имеет продукт этих 2 простых чисел (модуль). Единственный способ, с помощью которого кто-то мог бы расшифровать данные, зашифрованные открытым ключом, состоял бы в том, чтобы вернуть модуль обратно в 2 простых числа и обработать закрытый ключ. Это было то, что я пытался сделать, но в очень небольших масштабах.

Правильно, так просто факторизация! Это то, что я делал. Я создал 128-битный ключ RSA (крошечный с точки зрения асимметричного шифрования, особенно учитывая, что мой процессор с частотой 2 ГГц в моем ноутбуке учитывал его менее чем за секунду). Я извлек модуль и, используя неправильную команду при переводе из шестнадцатеричного в десятичный (забыв выбрать ibase при использовании bc), привел к 97964999429910939982995739699617. Затем я использовал команду factor.

Это было то, что делало фанки.

Когда я произвел это, у меня было 8 ответов вместо двух ожидаемых.

97964999429910939982995739699617: 3 3 3 17 433 613 937 858164002128703934431

Думая об этом сейчас, я понимаю, почему у меня не было 2 ответов: это был не настоящий модуль для пары ключей RSA. Но это не «ошибка», которую я нашел (или вы не читали бы это).

Чтобы дважды проверить, я решил умножить числа вместе, чтобы снова получить модуль.

Я использовал команду

echo $ ((3 * 3 * 3 * 17 * 433 * 613 * 937 * 858164002128703934431))

Ну, конечно, это должно привести к стартовому номеру снова, верно? Нет причин, почему это не должно быть 97964999429910939982995739699617.

Ну, это был мой ход мыслей, пока я не получил ответ -8628928582186374751.

Я совершенно не понимаю, почему эта команда вернет столь явно неправильный ответ. Как это может быть даже отрицательно? Это глюк в собственных математических функциях? Команда коэффициента была правильной, я знаю это наверняка, потому что, когда я пытался использовать реальный физический калькулятор (TI-84), он возвращал значение, которое я первоначально учитывал.

Сначала я попытался выполнить эту команду на моем ноутбуке (запустил Kali Linux. Команда «uname -rvo» сообщает мне «4.3.0-kali1-amd64 # 1 SMP Debian 4.3.3-5kali4 (2016-01-13) GNU / Linux «). Затем я удаленно подключился к моим серверам Gentoo на highschool и выполнил ту же команду. Тот же, явно недействительный ответ. Uname говорит: «4.1.15-gentoo-r1 # 2 SMP Пт Мар 11, 15:12:48 CST 2016 GNU / Linux"

Что это?

Вы просто переполнили целочисленную арифметику оболочки:

 echo $(( 65536 * 65536 * 65536 * 32768 - 1 )) 9223372036854775807 echo $(( 65536 * 65536 * 65536 * 32768 )) -9223372036854775808 

Вы можете использовать произвольный инструмент точности, такой как bc для этого

 bc 3*3*3*17*433*613*937*858164002128703934431 97964999429910939982995739699617 

Или

 echo '3*3*3*17*433*613*937*858164002128703934431' | bc 97964999429910939982995739699617