Терминология
Сложность криптоаналитической атаки
Сложность криптоаналитической атаки на алгоритм шифрования может быть охарактеризована с помощью трех величин:
- Сложность по данным. Количество входных данных, необходимое для успешной криптоаналитической атаки на алгоритм шифрования.
- Вычислительная сложность. Время, требуемое для успешной криптоаналитической атаки на алгоритм шифрования.
- Сложность по памяти. Объем памяти, которая нужна для успешной криптоаналитической атаки на алгоритм шифрования.
Часто под сложностью криптоаналитической атаки понимается максимальная среди этих величин. А для некоторых атак приходится искать компромисс между сложностью по данным, вычислительной сложностью и сложностью по памяти. Например, для реализации более быстрой атаки может потребоваться дополнительная память.
Сложность криптоаналитической атаки, как правило, выражается в виде экспоненциальной функции. К примеру, если атака имеет сложность 2128, то это значит, что для взлома шифра требуется выполнить 2128 операций.
При оценке сложности атаки часто приходится оперировать очень большими числами. Чтобы было понятно, насколько они велики, в табл. 5.1 для них приведены некоторые физические аналогии.
Таблица 5.1. Физические аналогии для очень больших чисел.
| Физическая аналогия | Число |
|---|---|
| Время, оставшееся до наступления следующего ледникового периода | 16ּ103 (214) лет |
| Время, оставшееся до превращения Солнца в новую звезду | 109 (230)лет |
| Возраст Земли | 109 (230)лет |
| Возраст Вселенной | 1010 (232)лет |
| Количество атомов, из которых состоит Земля | 1051 (2170) |
| Количество атомов, из которых состоит Солнце | 1057 (2190) |
| Количество атомов, из которых состоит наша Галактика | 1067 (2223) |
| Количество атомов, из которых состоит Вселенная | 1077 (2265) |
| Объем Вселенной | 1084 (2280)см3 |
В то время как сложность атаки на данный алгоритм шифрования является постоянной величиной (по крайней мере, до тех пор, пока криптоаналитик не придумает более эффективный метод взлома), вычислительная мощь современных компьютеров растет буквально не по дням, а по часам. Такой феноменальный рост наблюдается в течение последних пятидесяти лет, и есть все основания полагать, что в ближайшее время данная тенденция сохранится. Большинство криптоаналитических атак идеально подходят для реализации на параллельных компьютерах: полномасштабная атака на шифр разбивается на миллионы крошечных атак, которые ведутся независимо друг от друга и, следовательно, не требуют организации взаимодействия между процессорами. Поэтому в корне неверно заявлять о достаточной вычислительной стойкости алгоритма шифрования только потому, что его невозможно взломать при современном уровне развития технологии. Хорошая криптосистема всегда проектируется с достаточным запасом на будущее. При этом необходимо принимать во внимание прогнозируемый рост компьютерной производительности, чтобы алгоритм шифрования оставался вычислительно стойким в течение многих лет.