Большие целочисленные операции в Python
Я пытаюсь решить задачу криптографии CTF, которая включает в себя использование строительных блоков пары ключей RSA (два больших простых числа) и зашифрованного номера шифра сообщения. Чтобы расшифровать это сообщение, мне нужно выполнить операции, которые, как я полагаю, не поддерживаются стандартными криптографическими библиотеками, поскольку используемый открытый показатель степени неизвестен, но у меня есть значения dp и dq, то есть я должен выполнить следующие операции:
По сути, я возвожу очень большие целые числа в степень очень больших целых чисел, и стандартная опция pow(x,y) заставляет Python зависать, казалось бы, на неопределенный срок. Тогда как без использования криптобиблиотек я могу выполнять эти операции в Python?
Редактировать: Вот конкретный код и значения, вызывающие зависание Python.
p = 7901324502264899236349230781143813838831920474669364339844939631481665770635584819958931021644265960578585153616742963330195946431321644921572803658406281
dp = 5540655028622021934429306287937775291955623308965208384582009857376053583575510784169616065113641391169613969813652523507421157045377898542386933198269451
c = 62078086677416686867183857957350338314446280912673392448065026850212685326551183962056495964579782325302082054393933682265772802750887293602432512967994805549965020916953644635965916607925335639027579187435180607475963322465417758959002385451863122106487834784688029167720175128082066670945625067803812970871
m1 = pow(c,dp)%p
Возможный дубликат Модульная мощность больших чисел
Ответы 1
pow принимает необязательный третий аргумент z, который выполняет операцию модуля, но намного быстрее, чем использование оператора %:
>>> pow(c, dp, p)
49437413074993986257824490238275931180994249527518860068137626874351971280859988288289074
Что именно висит?
pow(2790, 53) % 61на моей машине занимает около 1 микросекунды, аpow(2790, 53, 61)(вероятно, это то, что вы хотите использовать) примерно на 20% быстрее.