Mod n криптоанализ

Атака применима к блочным и потоковым шифрам

В криптографии криптоанализ по модулю n — это атака, применимая к блочным и потоковым шифрам . Это форма криптоанализа с разделением , которая использует неравномерность работы шифра над классами эквивалентности (классами конгруэнтности) по модулю n . Метод был впервые предложен в 1999 году Джоном Келси , Брюсом Шнайером и Дэвидом Вагнером и применен к RC5P (вариант RC5 ) и M6 (семейство блочных шифров, используемых в стандарте FireWire ). Эти атаки использовали свойства двоичного сложения и вращения битов по модулю простого числа Ферма .

Анализ RC5P по Mod 3

Для RC5P анализ проводился по модулю 3. Было отмечено, что операции в шифре (поворот и сложение, обе на 32-битных словах) были несколько смещены относительно классов конгруэнтности по модулю 3. Чтобы проиллюстрировать подход, рассмотрим левый поворот на один бит:

${\displaystyle X\lll 1=\left\{{\begin{matrix}2X,&{\mbox{if }}X<2^{31}\\2X+1-2^{32},&{\mbox{if }}X\geq 2^{31}\end{matrix}}\right.}$

Тогда, потому что

${\displaystyle 2^{32}\equiv 1{\pmod {3}},\,}$

следует, что

${\displaystyle X\lll 1\equiv 2X{\pmod {3}}.}$

Таким образом, левое вращение на один бит имеет простое описание по модулю 3. Анализ других операций (зависимое от данных вращение и модульное сложение) выявляет схожие, заметные смещения. Хотя существуют некоторые теоретические проблемы при анализе операций в сочетании, смещение может быть обнаружено экспериментально для всего шифра. В (Kelsey et al., 1999) эксперименты проводились до семи раундов, и на основании этого они предполагают, что с помощью этой атаки можно отличить от случайных до 19 или 20 раундов RC5P . Существует также соответствующий метод восстановления секретного ключа .

Против M6 есть атаки mod 5 и mod 257, которые еще более эффективны.

Ссылки

• Джон Келси , Брюс Шнайер , Дэвид Вагнер (март 1999 г.). Современный криптоанализ с приложениями против RC5P и M6 ( PDF / PostScript ) . Быстрое программное шифрование , материалы шестого международного семинара. Рим : Springer-Verlag . стр. 139–155 . Получено 12.02.2007 .{{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка )
• Винсент Реймен (01.12.2003). ""mod n" Криптоанализ Rabbit" (PDF) . Белая книга , версия 1.0. Cryptico . Получено 12.02.2007 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
• Тошио Токита; Цутому Мацумото. «О применимости дифференциального криптоанализа, линейного криптоанализа и Mod n криптоанализа к алгоритму шифрования M8 (ISO9979-20)». Журнал Ipsj . 42 (8).