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

Компьютеры - Атака по времени - Использование китайской теоремы об остатках

Для оптимизации операций с секретным ключом в RSA часто используется Китайская теорема об остатках. Сначала вычисляются и , где y - сообщение. Простейшая атака заключается в выборе y близких к p или q. Если y меньше p, не сделает ничего, а если y > p, потребуется вычесть p из y хотя бы один раз. Также, если y незначительно больше p, будет иметь старшие биты равными нулю, что может сократить время первого умножения. Специфические временные характеристики зависят от реализации.

Примеры атак на RSA: Timing attacks on RSA и Атака по времени выполнения на RSA

Временной криптоанализ DSS

Алгоритм Digital Signature Standard вычисляет , где p и q известны атакующему, а k вычислено заранее, H - хэш сообщения, x -секретный ключ. На практике сначала вычисляется а затем домножается на . Атакующий может вычислить H и сделать соответсвтующую поправку. Так как H примерно такого же размера как и q, сложение оказывает незначительное влияние на операцию редуцирования в методе возведения в степень Монтгомери. Наибольшее значение будут иметь старшие биты . Значение r известно. Между старшими битами x и временем выполнения операции редуцирования Монтгомери существует взаимосвязь. Если k вычислено заранее, подпись сообщения требует только двух операций модульного умножения, таким образом количество дополнительно вносимого шума становится относительно небольшим.