Криптосистемы и количество ключей
Вот, кстати, почему-то часто приходится слышать, что если в какой-то криптосистеме большое число возможных ключей, то уже поэтому такая криптосистема стойкая и хорошая. Такое заблуждение. Между тем, даже в популярной литературе традиционно приводится старый пример с наивной криптосистемой на перестановках букв алфавита. Вот он:
Предположим, что в качестве ключа используется конкретная перестановка всех букв алфавита (перестановка – это, думаю, понятно, что такое: было “АБВ…ЮЯ”, стало “БTА…ФК”). Шифрование производится заменой буквы открытого текста на соответствующую ей букву ключа (скажем, А->Б; Б->T и т.д. – если использовать только что упомянутый ключ).
В такой криптосистеме число ключей = 33!, то есть где-то около 8.7*1036 – перебирать и перебирать. Но при этом всякое достаточно длинное осмысленное текстовое сообщение, зашифрованное описанным выше образом, элементарно раскрывается за доли секунды, так как частотные характеристики текстов на естественном языке позволяют быстро вычислить ключ без перебора всех его вариантов.
Адрес записки: https://dxdt.ru/2008/10/31/1794/
Похожие записки:
- Превентивное удаление "цифровых следов" и художественное произведение
- Квантовые состояния в неизвестности
- Подстановки и определение понятия бита
- Кибернетический след в "Илиаде" и цветовой сдвиг
- "Лазейки" вокруг неравенства Белла
- ИИ и математические задачи, "автоматизированные" дважды
- Машинный ИИ в книгах прошлого века
- Реплика: пример про ДСЧ
- Реплика: переключение морфологических веток
- Неверная интерпретация систем ИИ как "инструмента для анализа"
- Реплика: превращение словарных имён королей - Чарльз/Карл
Кратко этот сайт характеризуется так: здесь можно узнать про технологический прогресс, Интернет, математику, криптографию, авиацию, компьютеры, авиационные компьютеры, вооружения, роботов, вооружение роботов, армии мира, астрономию, космические исследования. И иногда о чём-то ещё (
Комментарии читателей блога: 11
1. 1st November 2008, 11:19 // Читатель Taras написал:
а если сначала заZIPить, а потом перестановкой, то не так уж и явно …
2. 2nd November 2008, 23:56 // Александр Венедюхин:
В принципе, та же история – у файлов архивов, скажем, известные заголовки.
3. 15th January 2009, 14:30 // Читатель skelterer написал:
почему, почему… Да потому что в современном мире идет речь о системах, для которых статистические методы не работают, как в случае шифра простой замены, который вы описали. Есть теорема Шеннона, которая фактически дает критерий идеальной (не вскрываемой иным способом, кроме прямого перебоа ключей) криптосистемы (говоря грубо, по сути): если распределение символов шифрпоследовательнсоти строго равновероятно. Для таких систем и говорят о кол-ве ключей. Понятно, что мы говорим о математической модели шифрсистемы, а не о шифраторе или иной технической реализации, слабости которой могут быть использованы для атаки.
4. 15th January 2009, 17:28 // Александр Венедюхин:
Это Вы к чему написали?
5. 16th January 2009, 16:13 // Читатель skelterer написал:
вот к чему:
“Вот, кстати, почему-то часто приходится слышать, что если в какой-то криптосистеме большое число возможных ключей, то уже поэтому такая криптосистема стойкая и хорошая. Такое заблуждение.”
Может быть, вам не очень изнутри заметно, но фраза ваша сия выглядит как “письмо ученому соседу”. В принципе, чисто формально, придраться к фразе вроде нельзя, но общий смысл – именно как в упомянутом письме (“поп у нас с колокольни упал, а у вас люди на луне! брехня!”), и я просто объяснил, почему именно. Могу повторить в одной фразе: в наши времена шифрсистемы, не обеспечивающие статистического выравнивания зашифрованного текста, просто не рассматриваются, потому что обычно они вскрываются автоматически, практически без участия человека. Вообще вы, как я вижу, не очень разборчивы с матерьялами на вашем сайте.
6. 16th January 2009, 17:19 // Александр Венедюхин:
Да ну бросьте, Вы-то как раз и придираетесь, на пустом месте. Вот, пишете Вы, вроде бы и согласен, и придраться-то не к чему, а вот всё равно поумничаю, да поучу тут.
Добавлю: там в записке речь вообще не о “частотном анализе” и “равновероятности” – это Вы приплели из учебника, видимо, – а речь о том, что большое число ключей не является достаточным условием высокой стойкости криптосистемы. Пример приведён самый очевидный, по-моему.
7. 17th January 2009, 12:32 // Читатель arcman написал:
Заметка просто поверхностная, вот и возникают разночтения и домыслы
8. 17th January 2009, 17:21 // Александр Венедюхин:
Ну, может, она, эта элементарная заметка, кажется поверхностной тем, кто, что называется, не в теме, но про Шеннона нахватался. Это да, такое бывает.
9. 9th June 2009, 12:00 // Читатель skelterer написал:
когда от предметного разговора переходят к оскорблениям, становится скучно. Придержите язык, господин Венедюхин. На вашем сайте действительно полно, мягко говоря, не очень проверенной и “чайниковой” информации. Чем переходить на личности, лучше бы слушали, что вам говорят. Впрочем, это, похоже, бесполезно :).
10. 9th June 2009, 12:42 // Александр Венедюхин:
Либо это иной юзер пишет, угнав чужой ник, либо вообще не понятно, почему почти полгода человек обдумывал написание столь бессодержательного комментария.
На всякий случай, ещё раз напоминаю: не нужно постить сюда бессодержательные склоки и разводить флейм.
11. 13th October 2009, 12:54 // Читатель arcman написал:
“О скоростях перебора паролей на CPU и GPU”
http://golubev.com/about_cpu_and_gpu_ru.htm