Практическая стойкость шифров.
Раздел практической стойкости рассматривает атаки на шифры не являющиеся совершенными.
Центровым понятием в практической стойкости по Шеннону является рабочая характеристика шифра, представляющая собой средний объем работы W(N), необходимый для определения ключа по криптограмме, состоящей из N букв, причем N>L0 (объем перехвата перевалил за расстояние единственности), измеренный в удобных элементарных операциях.
Ценность большинства данных со временем снижается, поэтому важно, чтобы рабочая характеристика шифра превышала по стоимости защищаемую информацию.
Сложность взлома алгоритмов классифицируется по категориям:
· Полное вскрытие. Криптоаналитик находит ключ k, такой, что Dk(x)=y.
· Глобальная дедукция. Криптоаналитик находит альтернативный алгоритм A, эквивалентный Dk(x) без знания k.
· Случайная (или частичная) дедукция. Криптоаналитик находит (крадет) открытый текст для перехваченного шифрованного сообщения.
· Информационная дедукция. Криптоаналитик добывает некоторую информацию о ключе или открытом тексте. Такой информацией могут быть несколько битов ключа, сведения о форме открытого текста и пр.
Алгоритм безусловно стоек, если восстановление невозможно при любом объеме шифртекста, полученного криптотаналитиком. На поверку безусловно стойки только одноразовые блокноты. Все остальные криптосистемы теоретически можно вскрыт методом грубой силы (прямой подбор ключа, лобовая атака).
Вычислительная стойкость по отношению к лобовой атаке зависит от длины ключа. Некоторые оценки стойкости см. приложение 1.
Вопросами вычислительной стойкости по отношению к другим методам криптоанализа (вероятностный, линейный, дифференциальный и пр.) занимается теория сложности вычислений. Подробное ее рассмотрение выходит за рамки данного пособия.
Таблица 1. Оценки времени лобового вскрытия для симметричных шифров.
| Стоимость | Длина ключа, бит. | |||||
| $100000 | 2 сек | 35 час | 1 год | 70000 лет | 1014 лет | 1019 лет |
| $1 млн. | 0.2 сек | 3.5 час | 37 дней | 7000 лет | 1013 лет | 1018 лет |
| $10 млн. | 0.02 сек | 21 мин | 4 дня | 700 лет | 1012 лет | 1017 лет |
| $100 млн. | 2 мсек | 2 мин | 9 час | 70 лет | 1011 лет | 1016 лет |
| $1 млрд. | 0.2 мсек | 13 сек | 31 мин | 7 лет | 1010 лет | 1015 лет |
| $10 млрд. | 0.02 мсек | 1 сек | 5.4 мин | 245 дней | 109 лет | 1014 лет |
| $100 млрд. | 2 мксек | 0.1 сек | 32 сек | 24 дня | 108 лет | 1013 лет |
| $1 трлн. | 0.2 мксек | 0.01 сек | 3 сек | 2.4 дня | 107 лет | 1012 лет |
| $10 трлн. | 0.02 мксек | 1 мсек | 0.3 сек | 6 час | 106 лет | 1011 лет |
Таблица 2. Оценки среднего времени лобового вскрытия в "Китайской лотерее".
| Страна | Население | Число телевизоров радиоприемников | Время взлома | |
| 56 бит | 64 бита | |||
| Китай | 280 сек | 20 час | ||
| США | 97 сек | 6.9 час | ||
| Ирак | 4.2 час | 44 дня | ||
| Израиль | 5.5 час | 58 дней | ||
| Вайоминг | 15 час | 160 дней | ||
| Невада | 48 дней | 34 года |
Термодинамические ограничения. Идеальный компьютер затрачивает на каждую установку и сброс бита 4.4·10-16 эрг энергии. Энергия излучаемая солнцем за год равна 1.21·1041 эрг. Этого достаточно, чтобы совершить 2.7·1056 премен бита, чего хватает для пробега 187-разрядным счетчиком всех значений.
Лобовое вскрытие 256 битового ключа невозможно пока компьютеры построены из обычной материи и работают в обычном пространстве.
Таблица 3. Длины симметричных и открытых ключей, равных по устойчивости к лобовому вскрытию.
| Длина симметричного ключа (бит) | Длина открытого ключа (бит) |
Таблица 4. Расстояние единственности по симметричному ключу
| Длина ключа (бит) | Расстояние единственности (символов) |
| 5.9 | |
| 8.2 | |
| 9.4 | |
| 11.8 | |
| 18.8 | |
| 37.6 |
Дата добавления: 2016-02-13; просмотров: 1851;