Время Python для модульного возведения в степень ⇐ Python

[Anonymous]

Мы узнали, что модульное возведение в степень потенциально может привести к утечке конфиденциальных данных. Например, рассмотрим следующую реализацию алгоритма умножения слева направо:

Код: Выделить всё

def square_and_multiply(base, exponent, modulus):
result = 1
base = base % modulus
exponent_bits = bin(exponent)[2:]

for i in range(len(exponent_bits) - 1, -1, -1):
result = (result * result) % modulus
if exponent_bits[i] == '1':
result = (result * base) % modulus

return result

В этой реализации, когда текущий бит экспоненты равен 1, выполняется дополнительное умножение, которое требует больше вычислительных затрат. Такое изменение во времени выполнения может привести к утечке информации о частном показателе через анализ побочных каналов.
Чтобы решить эту проблему, мой профессор предложил изменить алгоритм, включив в него фиктивное умножение, обеспечивая постоянство времени независимо от значения бита. Обновленный код выглядит следующим образом:

Код: Выделить всё

def square_and_multiply_dummy(base, exponent, modulus):
result = [1, 1]
base = base % modulus
exponent_bits = bin(exponent)[2:]

for i in range(len(exponent_bits) - 1, -1, -1):
result[0] = (result[0] * result[0]) % modulus
result[1 - int(exponent_bits[i])] = (result[0] * base) % modulus

return result[0]

Однако, когда я тестирую эту обновленную реализацию с 2048-битным вводом[/b] и изменяю вес Хэмминга показателя степени, я все равно обратите внимание на существенные различия во времени между экспонентой с весом Хэмминга 1 (например, один бит 1, а остальное равно 0) и экспонентой с весом Хэмминга 2048 (все биты 1).
Почему?
Обратите внимание, что если я изменю эту строку:

Код: Выделить всё

result[1 - int(exponent_bits[i])] = (result[0] * base) % modulus

на это: result[1 - int(expent_bits)] = 1, тогда я получаю такое же время...

Подробнее здесь: https://stackoverflow.com/questions/792 ... nentiation