# Пример использования алгоритма Шора для взлома RSA с помощью IBM-Q ## Описание Пример использования алгоритма Шора для взлома системы RSA на 16-битной квантовой машине IBM-Q. Результат:  ### Как запустить? 1. Создайте среду выполнения Python 3. 2. Установите зависимости командой `$ pip3 install -r requirements.txt`. 3. Выполните скрипт `test.py` или откройте ноутбук `Breaking_RSA.ipynb` в Jupyter Notebook. ``` $ python test.py ``` или ``` $ jupyter notebook Breaking_RSA.ipynb ```4. Введите количество битов для факторов (например, 4), введите сообщение произвольной длины, получите шифротекст, расшифруйте его с использованием приватного ключа и используйте алгоритм Шора для расшифровки на IBM-Q. Замечание: Поскольку квантовый компьютер предоставляет только 16 бит, максимальное количество битов для факторов составляет корень из 16, то есть 4 бита. Однако это не означает, что RSA имеет размер ключа 4 бита. Размер ключа RSA зависит от двух случайных простых чисел, поэтому он может поддерживать до RSA-17. Для более длинных ключей RSA, таких как RSA-2048, требуется около 617 десятичных цифр, а размер факторов составляет примерно 309 бит. Это требует квантового компьютера с количеством битов порядка 90 тысяч для одного вычисления. Однако использование многократных вычислений или распределенного квантового компьютера (например, метод разделенного луча из лаборатории Oak Ridge National Laboratory) позволяет существенно угрожать современным системам публичных ключей даже с меньшими квантовыми компьютерами.Алгоритм Шора был разработан Peter Shor в 1994 году. Он значительно снижает временные затраты на факторизацию целых чисел до O(log N). Дополнительные детали можно найти в подробных руководствах по квантовым вычислениям: [Понимание алгоритма Шора](https://www.bilibili.com/video/BV1a4411M7cU)