[Translation may be, some day]
На днях я написал свою реализацию алгоритма шифрования с открытым ключом RSA. Также сделал простейший взлом этого алгоритма, поэтому хотел написать небольшую заметку на эту тему. Стойкость ко взлому RSA основывается на задаче факторизации. Факторизация… Какое страшное слово…
Не все так страшно
На самом деле на первом этапе создания ключей мы берем два случайных числа, но числа должны делиться только на себя и единицу – простые числа.
Назовем их p и q. Далее мы должны получить число n = p *q. Оно будет использоваться для дальнейшей генерации ключей, ключи в свою очередь будут использоваться для шифрования, дешифровки сообщений. В итоговом варианте приватного и публичного ключа число n будет передано без изменений.
Допустим у нас на руках один из ключей RSA и зашифрованное сообщение. Вытаскиваем из ключа число n и начинаем его хакать.
Факторизуем n
Факторизация – разложение числа на простые множители. Сначала вытаскиваем из ключа число n (на настоящих ключах можно сделать с помощью openssl), допустим n = 35. Тогда раскладываем на простые множители n = 35 = 5 * 7, это и есть наши p и q. Теперь можно перегенерить ключи с помощью полученных p, q, дешифровать сообщение и шифровать обеспечивая видимость оригинального автора.
С кубитами не все так просто
Неужели можно поломать любой RSA так просто? На самом деле нет, числа p, q берут заведомо большими, чтобы задача факторизации на классических компьютерах заняла очень продолжительное время (10 лет в какой-то там степени)
Однако, используя квантовый алгоритм Шора, факторизовать число можно за очень малое время. На данный момент в статьях на эту тему заявлено время перемножения данного числа, тоесть фактически моментально. Для работы алгоритма Шора необходимо реализовать квантовые компьютеры, с большим количеством кубит. В 2001 году IBM разложили на простые множители число 15 с помощью 7 кубит. Так что этого момента придется ждать еще долго, к тому времени мы перейдем на пост-квантовые алгоритмы шифрования.
Потрогать Шора
Питер Шор рассказывает про свой алгоритм факторизации
Чтобы опробовать алгоритм Шора на квантовом симуляторе, вы можете установить ProjectQ, в его примеры входит реализация shor.py, позволяющая факторизовать число вводимое пользователем. На симуляторе время выполнения удручает, но вроде весело и задорно симулирует работу квантового компьютера.
Статьи:
http://www.pagedon.com/rsa-explained-simply/my_programming/
http://southernpacificreview.com/2014/01/06/rsa-key-generation-example/
https://0day.work/how-i-recovered-your-private-key-or-why-small-keys-are-bad/
Реализация RSA на Python:
https://github.com/demensdeum/RSA-Python
