А для крутых парней барабаны - часть 5
Первая часть.
Вторая часть.
Третья часть.
Четвертая часть.
Итак, в прошлый раз мы остановились на случайных числах. Их связь с криптографией неразрывна, как у капитала с империалистической войной(С). С вашего позволения я уделю этой теме пару абзацев.
Кстати, серьезно заинтересовавшимся историей шифров, очень рекомендую понятную даже без малейшего математического образования книгу Саймона Сингха - там очень много интересного. Я ее вообще взахлеб читал, как художественную литературу. А для нашей дальнейшей дискуссии просто отмечу, что на протяжении многих веков криптоаналитики пытались (обычно весьма успешно) прочесть зашифрованные сообщения путем так называемого частотного анализа.
Если вы читали в детстве «Пляшущих Человечеков» Артура Конан-Дойля или «Золотой Жук» Эдгара Аллана По, то должны помнить, что и там и там сыщики брали текст, состоящий из кракозябр, предполагали, что он написан на английском языке, а дальше проверяли какая кракозябра встречается чаще всего. Кстати, вот таблица популярности букв английского языка:
Плюс к этому существуют еще дополнительные достаточно простые ухищрения - например двойная E в английском встречается очень часто. Ну и так далее, и тому подобное. Это все еще было до компьютеров, так - развлечение холодными зимними вечерами. Когда рука набита - то можно и десяток разных кодов за день взломать, тренировки ради.С тех пор много воды утекло в Темзе, и на данный момент хорошим тоном в шифровании стало использование стандартных алгоритмов.
Таким образом, я отлично знаю по каким правилам из исходного текста будет составлен текст секретный. Чего я не знаю, и не должен знать ни в коем случае - так это ключ шифрования. Исходный текст, как мы только что говорили, очень предсказуемая вещь, даже если буквы заменять одна на другую по более сложной схеме, а на одна в одну. Поэтому нам нужен очень-очень-очень случайный ключ шифрования. И это на самом деле экстремально важно, потому что практически во всех алгоритмах ключ короче самого сообщения, а значит нам нужно много-много-много случайности в нем, так чтобы хватило максимально «растворить» изначальную неслучайность нашего секретного письма.
Даже в годы второй мировой войны можно было предвидеть, что в зашифрованных сообщениях будут основные слова немецкого языка, цифры, названия населенных пунктов и т.д. Самое время кстати отдать должное Алану Тюрингу, которого вчера помиловали задним числом. Шестьдесят лет прошло, герой войны, великий математик, построил машину, автоматически взламывающую немецкие военные коды («Энигма», ага), провинился в гомосексуализме. Ладно, это уже другая тема.
Кстати, секундный экивок в сторону - если вы мечтаете изобрести совершенно невзламываемый код, то не торопитесь - его уже изобрели до вас. Прошу любить и жаловать - Шифр Вернама.
Он элементарно прост - берете абсолютно случайный ключ(он же одноразовый шифроблокнот), и осуществляете некую математическую операцию между каждой буквой вашего секретного сообщения и каждой буквой ключа. После использования шифроблокнот уничтожаете - на то он и одноразовый. Схема абсолютно безопасна как раз из-за того, что ключ совершенно случаен, и не повторяется. В принципе, несложно догадаться почему - риск начинается когда у вас есть больше смысла, чем шума. А если шум совершенно случаен, и смешан со смыслом в соотношении 1:1, то искать в этой смеси абсолютно нечего - вам не помогут ни квантовый компьютер, ни бесконечное время на анализ сообщений.
Серьезные ребята (ЦРУ, ГРУ) вовсю использовали (и, думаю, продолжают использовать) одноразовые шифроблокноты. Правильно делают, у них риски уж больно серьезные. Однако же, бывают промашки - советские разведчики с непонятного переполоху с 1942го по 1948й год несколько раз использовали одни и те же ключи. Всем спасибо, всем привет - у американцев появился проект Венона, имевший крайне неприятные, а местами фатальные последствия для советской разведывательной сети.
У Стивенсона в «Криптономиконе» жена викария тянула шарики с буквами из корзинки, а потом делала из них шифроблокноты. Если предположить, что она отдавала предпочтение «нормальным» буквам E,T,A, то мы снова оказываемся в ситуации недостаточной случайности ключа шифрования, а там уже и до электрического стула недалеко.
Кроме того, получение по-настоящему случайных чисел на компьютере - само по себе очень непростое мероприятие, ведь вся идея компьютера в его предсказуемости - давая ему определенные команды мы ожидаем всегда получить один и тот же результат. Поэтому принято собирать случайные данные из разных внешних для компьютера источников (микрофон, скорость печатания по клавишам, движения мышки), а потом уже использовать эти данные для создания случайных чисел. Псевдослучайных, вернее.
Это все - очень тонкая материя, вот две отличные цитаты выдающихся математиков: «генерация случайных чисел слишком важна, чтобы оставлять её на волю случая», и «всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений»
Возвращаемся к NSA. Допустим, американские разведчики хотят попортить реализацию широко известного алгоритма шифрования. Скажем, RSA. Они не могут просто заставить программистов написать неправильный код. Этому две причины. Первая и главная - совместимость. Есть другие реализации того же самого RSA или там IPSEC, и если они не будут друг с другом нормально работать, то весь мир полезет разбираться почему. Так дела не делаются.
Вторая - слишком много людей участвуют в процессе: кто-то этот код пишет, другой человек потом просматривает, проверяет на соответствие стандартам - и так далее, и тому подобное. Очень сложно, до непрактичности.
Гораздо проще максимально корректно реализовать алгоритм, но внести поправки в некие «тонкие» места. Уже понимаете, к чему была вся длинная преамбула про ключи шифрования и случайность? Именно так - если мы сможем выбирать раз за разом плохие, или просто недостаточно случайные ключи шифрования, то самый лучший патентованный алгоритм не предотвратит прочтения наших секретных писем врагами. Методов это сделать есть миллион и маленькая тележка, но самый красивый - реализовать генератор случайных чисел, который будет выдавать не совсем случайные числа. В идеале они должны выглядеть случайными, но при этом быть хорошо предсказуемыми - причем предсказуемыми именно NSA, чтобы враги не пронюхали, а криптофанатики не заподозрили.
На этом я заканчиваю краткий экскурс в современную криптографию, искренне надеюсь, что вас не потерял.
В следующей части я постараюсь минимизировать теоретические рассуждения, а вместо этого изложить грустную судьбу генератора случайных чисел Dual EC_DRBG, и прочих уважаемых товарищей, павших вместе с ним.
ПРОДОЛЖЕНИЕ СЛЕДУЕТ
Вторая часть.
Третья часть.
Четвертая часть.
Итак, в прошлый раз мы остановились на случайных числах. Их связь с криптографией неразрывна, как у капитала с империалистической войной(С). С вашего позволения я уделю этой теме пару абзацев.
Кстати, серьезно заинтересовавшимся историей шифров, очень рекомендую понятную даже без малейшего математического образования книгу Саймона Сингха - там очень много интересного. Я ее вообще взахлеб читал, как художественную литературу. А для нашей дальнейшей дискуссии просто отмечу, что на протяжении многих веков криптоаналитики пытались (обычно весьма успешно) прочесть зашифрованные сообщения путем так называемого частотного анализа.
Если вы читали в детстве «Пляшущих Человечеков» Артура Конан-Дойля или «Золотой Жук» Эдгара Аллана По, то должны помнить, что и там и там сыщики брали текст, состоящий из кракозябр, предполагали, что он написан на английском языке, а дальше проверяли какая кракозябра встречается чаще всего. Кстати, вот таблица популярности букв английского языка:
Плюс к этому существуют еще дополнительные достаточно простые ухищрения - например двойная E в английском встречается очень часто. Ну и так далее, и тому подобное. Это все еще было до компьютеров, так - развлечение холодными зимними вечерами. Когда рука набита - то можно и десяток разных кодов за день взломать, тренировки ради.С тех пор много воды утекло в Темзе, и на данный момент хорошим тоном в шифровании стало использование стандартных алгоритмов.
Таким образом, я отлично знаю по каким правилам из исходного текста будет составлен текст секретный. Чего я не знаю, и не должен знать ни в коем случае - так это ключ шифрования. Исходный текст, как мы только что говорили, очень предсказуемая вещь, даже если буквы заменять одна на другую по более сложной схеме, а на одна в одну. Поэтому нам нужен очень-очень-очень случайный ключ шифрования. И это на самом деле экстремально важно, потому что практически во всех алгоритмах ключ короче самого сообщения, а значит нам нужно много-много-много случайности в нем, так чтобы хватило максимально «растворить» изначальную неслучайность нашего секретного письма.
Даже в годы второй мировой войны можно было предвидеть, что в зашифрованных сообщениях будут основные слова немецкого языка, цифры, названия населенных пунктов и т.д. Самое время кстати отдать должное Алану Тюрингу, которого вчера помиловали задним числом. Шестьдесят лет прошло, герой войны, великий математик, построил машину, автоматически взламывающую немецкие военные коды («Энигма», ага), провинился в гомосексуализме. Ладно, это уже другая тема.
Кстати, секундный экивок в сторону - если вы мечтаете изобрести совершенно невзламываемый код, то не торопитесь - его уже изобрели до вас. Прошу любить и жаловать - Шифр Вернама.
Он элементарно прост - берете абсолютно случайный ключ(он же одноразовый шифроблокнот), и осуществляете некую математическую операцию между каждой буквой вашего секретного сообщения и каждой буквой ключа. После использования шифроблокнот уничтожаете - на то он и одноразовый. Схема абсолютно безопасна как раз из-за того, что ключ совершенно случаен, и не повторяется. В принципе, несложно догадаться почему - риск начинается когда у вас есть больше смысла, чем шума. А если шум совершенно случаен, и смешан со смыслом в соотношении 1:1, то искать в этой смеси абсолютно нечего - вам не помогут ни квантовый компьютер, ни бесконечное время на анализ сообщений.
Серьезные ребята (ЦРУ, ГРУ) вовсю использовали (и, думаю, продолжают использовать) одноразовые шифроблокноты. Правильно делают, у них риски уж больно серьезные. Однако же, бывают промашки - советские разведчики с непонятного переполоху с 1942го по 1948й год несколько раз использовали одни и те же ключи. Всем спасибо, всем привет - у американцев появился проект Венона, имевший крайне неприятные, а местами фатальные последствия для советской разведывательной сети.
У Стивенсона в «Криптономиконе» жена викария тянула шарики с буквами из корзинки, а потом делала из них шифроблокноты. Если предположить, что она отдавала предпочтение «нормальным» буквам E,T,A, то мы снова оказываемся в ситуации недостаточной случайности ключа шифрования, а там уже и до электрического стула недалеко.
Кроме того, получение по-настоящему случайных чисел на компьютере - само по себе очень непростое мероприятие, ведь вся идея компьютера в его предсказуемости - давая ему определенные команды мы ожидаем всегда получить один и тот же результат. Поэтому принято собирать случайные данные из разных внешних для компьютера источников (микрофон, скорость печатания по клавишам, движения мышки), а потом уже использовать эти данные для создания случайных чисел. Псевдослучайных, вернее.
Это все - очень тонкая материя, вот две отличные цитаты выдающихся математиков: «генерация случайных чисел слишком важна, чтобы оставлять её на волю случая», и «всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений»
Возвращаемся к NSA. Допустим, американские разведчики хотят попортить реализацию широко известного алгоритма шифрования. Скажем, RSA. Они не могут просто заставить программистов написать неправильный код. Этому две причины. Первая и главная - совместимость. Есть другие реализации того же самого RSA или там IPSEC, и если они не будут друг с другом нормально работать, то весь мир полезет разбираться почему. Так дела не делаются.
Вторая - слишком много людей участвуют в процессе: кто-то этот код пишет, другой человек потом просматривает, проверяет на соответствие стандартам - и так далее, и тому подобное. Очень сложно, до непрактичности.
Гораздо проще максимально корректно реализовать алгоритм, но внести поправки в некие «тонкие» места. Уже понимаете, к чему была вся длинная преамбула про ключи шифрования и случайность? Именно так - если мы сможем выбирать раз за разом плохие, или просто недостаточно случайные ключи шифрования, то самый лучший патентованный алгоритм не предотвратит прочтения наших секретных писем врагами. Методов это сделать есть миллион и маленькая тележка, но самый красивый - реализовать генератор случайных чисел, который будет выдавать не совсем случайные числа. В идеале они должны выглядеть случайными, но при этом быть хорошо предсказуемыми - причем предсказуемыми именно NSA, чтобы враги не пронюхали, а криптофанатики не заподозрили.
На этом я заканчиваю краткий экскурс в современную криптографию, искренне надеюсь, что вас не потерял.
В следующей части я постараюсь минимизировать теоретические рассуждения, а вместо этого изложить грустную судьбу генератора случайных чисел Dual EC_DRBG, и прочих уважаемых товарищей, павших вместе с ним.
ПРОДОЛЖЕНИЕ СЛЕДУЕТ