Отрицательное возведение в степень для шифрования / дешифрования с использованием быстрого возведения в степень

Question

All

Я кодировал алгоритм быстрого возведения в степень, чтобы проверить, равно ли зашифрованное значение исходному значению для данного показателя степени (e) и по модулю base (n). Когда у меня отрицательный показатель, значения не совпадают. Вот что я делаю:

1> Любое значение base
2> Закрытый ключ prKey
3> Открытый ключ puKey
4> Основание по модулю modN

Расшифруйте, используя base ^ prKey мод modN, чтобы получить decryptVal
затем зашифруйте decryptVal ^ puKey мод modN, чтобы получить encryptVal

Теперь encryptVal должно быть равно base. В моем коде это условие выполняется для положительных значений закрытого ключа prKey только . Для отрицательных значений prKey условие никогда не выполняется.

Пример (из моего кода запускается для различных случайных значений):

1> base: 4092
2> modN = 6499
3> puKey = 5
4> prKey = -1267

даст decryptVal = 4092 и encryptVal = 5537! = base

тогда как,

1> base: 249
2> modN = 6059
3> puKey = 5
4> prKey = 1181

дает мне decryptVal = 4067 и encryptVal = 249 = base

Является ли это условие ожидаемым поведением или в моем коде имеется ошибка, основанная на приведенных выше результатах выполнения? [Примечание]: prKey и puKey вычисляются с использованием расширенного евклидова алгоритма

Answer 1

Я прочитал ваш пост дважды и не совсем понимаю, в чем проблема. Вы спрашиваете, есть ли недостаток в вашем коде, но вы не показали никакого кода. В любом случае, обычное определение возведения в степень ax mod n для отрицательного x требует, чтобы gcd (a, n) = 1. Если gcd(a,n) = 1, то a ^x mod n == (a-1) -x mod n. Поэтому, если x отрицательно, сначала вычислите обратное a, а затем увеличьте его до степени -x, все mod n.