RSA расчет C ^ D мод N

Question

В алгоритме шифрования RSA как можно вычислить c^d mod n, когда c и d являются большими числами?

Answer 1

GMP - это программная библиотека C / C ++, которая делает это за вас: mpz_powm, mpz_powm_ui в документации.Используемый метод (в значительной степени) объяснен на странице википедии , и вы можете попробовать прочитать исходный код для GMP, если вы чувствуете, что до этого ...

Answer 2

Простой ответ: используйте язык и / или библиотеку, которая реализует арифметику для «больших целых чисел» и включает соответствующую функцию для возведения в модуляр.В Java это означает использование java.lang.BigInteger, в частности, метод modPow().

, поскольку базовые компьютеры не могут реально обрабатывать «целые числа», но имеют ограниченную эмуляцию (например, «32-разрядные целые числа», которые ведут себя как целые числа)за исключением того, что старшие биты после 32-й отбрасываются), такие реализации «большого целого» должны применять некоторые конкретные алгоритмы, которые подробно описаны в Справочнике по прикладной криптографии (глава 14).

Answer 3

Операция powMod может быть переведена в меньший шаг.

Например, 5 ^ 3 % 6 равно ((5 * 5) % 6) * 5 % 6, а 5 ^ 4 % 6 равно (((5 * 5) % 6) * 5 % 6) * 5 % 6). Как вы можете видеть, вы можете применить операцию по модулю в подчиненном результате показателя степени, чтобы всегда работать с меньшим числом и, таким образом, облегчить вычисление c ^ d % n, даже когда c и d имеют высокое значение.

Для получения дополнительной информации: http://en.wikipedia.org/wiki/Modular_exponentiation