Интернет магазин китайских планшетных компьютеров


Компьютеры - Атака по времени - Атака на алгоритм быстрого возведения в степень

23 января 2011


Оглавление:
1. Атака по времени
2. Атака на алгоритм быстрого возведения в степень
3. Использование китайской теоремы об остатках
4. Маскировка временных характеристик
5. Предотвращение атак



Алгоритм быстрого возведения в степень, используемый алгоритмами Диффи Хеллмана и RSA, выполняет следующую операцию с секретным ключом R = y^x \mod{n} , где n — часть открытого ключа и y может быть подслушан. Цель атакующего — получить секретный ключ x. Жертва вычисляет y^x \mod{n} для нескольких значений y. w - битовая длина ключа x.

Let~s_{0}~=~1
For~k=0~upto~w-1:
  If~~is~1~then
     Let R_{k}=\mod{n}
  Else~
    Let~R_{k}~=~s_{k}
  Let~s_{k+1} = R_{k}^{2} \mod{n}
EndFor~
Return~

Атака позволяет, зная биты 0.., найти бит b. Чтобы получить весь показатель степени, можно начать с b=0 и продолжать до тех пор пока вся экспонента не станет известна.

Зная первые b бит числа x, атакующий может вычислить первые b итераций цикла For и найти значение sb. Следующая итерация задействует первый неизвестный бит x. Если он равен 1, будет произведено вычисление R_{b}= \mod{n}, если 0, то операция будет пропущена.



Просмотров: 4245


<<< Атака нахождения прообраза


Компьютерное аппаратное обеспечение   
Вычислительные комплексы   
Компьютерные данные   
Компьютерные журналы   
Классы компьютеров   
Компьютеры   
Программное обеспечение   
Производители компьютеров   
Профессии в ИТ   
Системное администрирование   
Компьютерный сленг   
Списки компьютерных терминов   
Человеко-компьютерное взаимодействие