Введение:
Алан Тьюринг и "Энигма"
Фильм "Игра в имитацию" (2014) - именно об этой протрясающей истории. "Энигма" совсем небольшая, по размеру сравнима с печатной машинкой. Снаружи она состоит из клавиатуры и панели, на которой расположены буквы с подсветкой
Если нажать букву на клавиатуре, скажем A, то на панели высветится другая буква, например Q. Это означает, что в шифровке в этом месте вместо А появится Q. Внутри у машины три вращающихся диска, и их положение меняется после набора каждой буквы. Диск повернулся, провода соединились по-другому, и когда мы в следующий раз нажимаем А, на панели высвечивается уже не Q, а, скажем, G. В набор «Энигмы» входят пять дисков, использовать можно любые три, в любом порядке. У каждого диска – 26 изначальных положений. И это еще не все. В военном варианте у «Энигмы» была передняя панель с буквами и 10 кабелей. Каждый кабель соединял две любые буквы между собой, и при шифровании они менялись местами. Диски можно было перебрать достаточно быстро, но количество комбинаций на панели было настолько велико, что перебрать их было невозможно. Всего у «Энигмы» было
158 962 555 217 826 360 000
возможных изначальных установок. Каждые сутки ровно в полночь они менялись. Новое изначальное положение дисков, новые пары букв на панели. Перебрать все комбинации за 24 часа было совершенно нереально. Шифр считался неуязвимым. Перехватить документ с установками хоть и было непросто, но иногда удавалось, а потом 24 часа заканчивались и разгадать шифр опять не представлялось возможным.
Алан Тьюринг и его команда совершили настоящий прорыв. Они научились разгадывать шифр каждое утро всего за 20 минут! Прежде всего в шифре было слабое место. Буква никогда не превращалась сама в себя. Это стало хоть какой-то зацепкой. Важным оказалось и предположение, что сообщения утром начинаются с чего-то однотипного, например с прогноза погоды. По-немецки wetterbericht. Теперь нужно отыскать такую изначальную установку, чтобы шифр совпал с расшифровкой. Очень важно определить, какие буквы соединены в пары, потому что здесь вариантов особенно много. Поскольку никаких сведений нет, начинать приходится наобум. Зато дальше из первой догадки следуют сразу несколько других. Для ускорения процесса Алан Тьюринг сделал две существенные вещи. Во-первых, он понял, что если пара букв оказалась неправильной, то и все другие пары, следовавшие из нее, тоже неправильные. А значит, их уже не надо проверять. Во-вторых, он построил огромную машину, которая с помощью электрического тока позволяла исключить все неправильные пары одновременно. Оставалось только повторить операцию для каждой позиции дисков, а на это уходило всего 20 минут. Интересно, что принцип решения Тьюринга заключался не в том, чтобы найти правильный вариант, а в том, чтобы исключить неправильные варианты и сделать это максимально быстро! Это была огромная работа и колоссальное достижение, сильно повлиявшее на ход Второй мировой войны.
Открытый обмен ключами
В настоящее время особенно популярны так называемые схемы шифрования с открытым ключом. Я расскажу о схеме Диффи – Хеллмана, которая датируется 1970-ми годами и активно используется на практике. Эта схема основана на глубокой математике, но саму идею понять совсем несложно.
Возьмем простое число р. В реальности оно должно быть огромным, но для примера выберем маленькое простое число 19. Теперь выберем еще одно число g, тоже целое, но необязательно простое и меньше р. Например, g = 2. Также трех человек: Боб, Алиса , Ева. Бобу нужно отправить сообщение Алисе , что бы Ева его не узнала и если ей удастся его перехватить она не смогла его расшифровать.
Числа р и g знают все: Боб, Алиса, Ева . Теперь Алиса выбирает число х, например x = 6, и хранит его в тайне. Боб выбирает число у, скажем y = 8, и тоже никому его не сообщает.
Дальше начинается шифрование. Алиса находит остаток от деления на р числа g^х:
26 = 64,
64÷19 = 3 и 7 в остатке.
Боб делает то же самое со своим задуманным числом:
28 = 256,
256÷19 = 13 и 9 в остатке.
Итак, наше преобразование выглядит следующим образом: возвести 2 в степень х и взять остаток от деления на 19. Напомню, что числа g и р известны, а число х выбрала Алиса. Здесь принципиально важно, что р простое число, а g меньше р, потому что в этом случае g^x на р не делится, то есть остаток от деления не может быть нулем. Есть и более глубокие причины, почему р должно быть простым. Кроме того, для заданного р есть набор «подходящих» g
Получив остаток от Боба, Алиса возводит его в степень х и снова берет остаток от деления на р. В нашем маленьком примере Алиса получила от Боба число 9, а Боб от Алисы число 7. Тогда у Алисы получается:
[остаток от деления 96 на 19] = 11.
Боб действует аналогично. Он получил остаток от Алисы, и у него есть известный ему одному у (даже Алиса его не знает!). Он возводит полученный от Алисы остаток в степень у и снова берет остаток от деления на р:
[остаток от деления 78 на 19] = 11.
Это то же самое число 11, что и у Алисы!
Естественно, это неслучайно. Математически нетрудно показать, что Алиса и Боб получат одинаковое число при любых р, g, x, и у
Алгоритм RSA
На практике часто используется еще одна схема открытого обмена ключами – алгоритм RSA, названный так по первым буквам имен своих авторов: Ривеста, Шамира, Адлемана (Rivest, Shamir, Adleman).
Алгоритм:
Алиса может выбрать не одно число, а сразу пару чисел р, q. Можно считать, что p и q – простые. Возьмем очень простое преобразование
n = p × q.
Это довольно быстрая операция – обычное умножение. Однако если вам дано натуральное число n и даже известно, что n = p × q с некоторыми простыми р и q, которых вы не знаете, то восстановить эти простые числа вам не удастся! Вернее, на это уйдут годы, коль скоро п достаточно велико.Обратите внимание: Цифровая диктатура в Китае. У миллионов людей слишком мало шансов иметь возможность жить нормальной жизнью.
Вот такие чудеса! Принцип здесь тот же самый. Для вычисления п используется простое умножение, это очень быстрая операция. А вот обратный процесс, операция разложения на множители, носит в математике красивое имя факторизация (от англ. factor – сомножитель) и представляет собой большую проблему с точки зрения вычислений.
Добавим, что операцию разложения на множители легко выполнить на квантовом компьютере. Но пока у таких компьютеров очень ограниченный регистр, то есть они могут работать только с относительно маленькими числами. Для шифрования на практике используются очень большие числа.
Основаная часть:
Схемы типа Диффи – Хеллмана и RSA работают довольно медленно, в отличие от так называемых симметричных криптосистем, которые гораздо быстрее. Но они пользуются ключом, который нужно хранить в тайне. В определенном смысле это аналоги «Энигмы». Они шифруют с помощью ключа и большого количества сложных преобразований, и знание ключа необходимо для расшифровки.
Итак, у нас есть быстрые схемы, для которых нужен ключ, и медленные – для обмена ключами. Поэтому обычно сессия безопасного соединения через интернет состоит из двух этапов.
Сначала происходит так называемое рукопожатие, то есть обмен сообщениями, во время которого, в частности, устанавливаются ключи. Именно на этом этапе применяются схемы с открытыми ключами, Диффи – Хеллмана или RSA. У «рукопожатия» есть еще несколько целей – например, часто используется аутентификация: сервер хочет убедиться, что он общается с тем, с кем думает, а клиент – что он общается с правильным сервером.
После того как ключи установлены, в течение всей оставшейся сессии сообщения зашифровываются с помощью симметричных криптосистем. В духе эпохи интернета всем хорошо известно, как эти системы работают. Если у Евы есть ключ от вашей сессии, то все ваши секреты у нее в кармане!
В предыдущих разделах мы говорили, что за ваши ключи можно не волноваться. На страже стоят сложные математические операции, которые никто не умеет выполнять. И это правда. Тем не менее качество шифрования зависит не только от математики, но и от имплементации.
Хорошо известно, что для надежного шифрования нужно пользоваться очень большими простыми числами. Стандартная величина 1024 бита, то есть 2^1024. Речь идет о 308-значных числах! Таких простых чисел очень много, выбор большой. Но, к сожалению, многие протоколы пользуются одними и теми же числами, снова и снова. Просто потому, что так легче. Насколько это угрожает нашей безопасности?
В 2015 году вышла статья, которая сильно всколыхнула мир криптографии. Авторы впервые назвали цену взлома наиболее распространенной имплементации схемы Диффи – Хеллмана: 100 миллионов долларов!
100 миллионов долларов за число:
Помните, как Алан Тьюринг взломал шифр «Энигмы»? Он построил большую машину, которая смогла быстро вычислить ключ. У этой истории две принципиальные составляющие: «машина» и «быстро».
По сути, до сих пор так все и осталось. Можно сказать, что подход Тьюринга – это прообраз современного подхода к взламыванию шифров. Нужно наличие машины и способ быстрого подсчета ключа. Машину строить необязательно, можно купить суперкомпьютер, были бы средства. Основная загвоздка, как вы уже поняли, именно в быстром способе подсчета.
И вот тут авторы статьи совершили прорыв. На основной конференции по компьютерной безопасности в 2015 году они представили новую атаку Logjam. Фактически это метод вычисления ключа в схеме Диффи – Хеллмана, при котором сами сообщения нужны лишь на последнем этапе. Эти последние шаги можно совершить очень быстро. Для основной части вычислений необходимо знать только простое число р. Поэтому основные – колоссальные – вычисления можно сделать заранее и держать ответы наготове. А дальше, как только начнется обмен сообщениями по открытому каналу, остается всего лишь их перехватить и с их помощью быстро завершить вычисление ключа.
Насколько колоссальны предварительные вычисления? Авторы просчитали, что если закупить оборудование стоимостью в пару сотен миллионов долларов, то за год можно взломать одно 308-значное простое число! Только одно. Предлагаем на секунду остановиться и еще раз оценить сложность задачи.
Реальна ли эта угроза? Скажем так: Logjam не для домашнего применения. Но, например, Агентству национальной безопасности США пара сотен миллионов вполне по карману. И если верить авторам, эта сумма примерно соответствует бюджету агентства на компьютерную криптографию.
Стоит ли оно того? Да. По крайней мере если большинство протоколов пользуются одними и теми же 308-значными числами, что и происходит на практике. Авторы той статьи утверждают, что взломав одно наиболее распространенное 308-значное простое число, можно пассивно прослушивать примерно две трети трафика VPN и примерно четверть SSH-серверов. А если взломать еще и второе по популярности число, то можно добраться приблизительно до 20 % от топ-миллиона HTTPS-сайтов.
По предположениям авторов, Агентство национальной безопасности в самом деле применяет подобные методы для прослушивания зашифрованного трафика. И многие верят, что так оно и есть. Вполне вероятно, что службы государственной безопасности продвинулись в криптографии гораздо дальше ученых.
Криптография окружена секретностью. Например, в 1996 году адвокат посоветовал американскому профессору не допускать к занятиям по криптографии иностранных студентов, потому что, оказывается, есть закон, запрещающий делиться алгоритмами криптографии с иностранцами, даже если эти алгоритмы описаны в учебниках и любой студент в состоянии их запрограммировать! А аспиранту Университета Беркли, который хотел опубликовать новые результаты по криптографии, пришлось четыре года судиться с американским правительством, пока очередной суд не признал, что запрет публикации противоречит Первой поправке к Конституции США, которая не позволяет создавать законы, противоречащие свободе слова.
На самом деле трудно понять, где заканчивается свободная наука и начинается государственная тайна. На конференции французский профессор криптографии Роберт Эрра с улыбкой сказал: «Один профессор, звезда в нашей области, утверждал, что редко встречал криптографа, который не пытался бы взломать RSA. Но, честно, если бы мне это удалось, я не отправил бы статью прямиком в журнал, а сначала позвонил бы министру обороны!»
Интересно, кстати, что ученые-криптографы изо всех сил пытаются взломать шифры. Зачем? Чтобы найти слабинку и придумать новые более надежные способы шифрования. Например, авторы Logjam рекомендуют пользоваться еще большими, 616-значными, простыми числами. А если это технически невозможно, то советуют по крайней мере выбирать разные простые числа. Сразу после появления статьи многие браузеры обновили протоколы, в том числе Chrome и Firefox.
Наши секреты должны оставаться в безопасности, даже если они транслируются по открытым сайтам по всему миру.
Больше интересных статей здесь: Новости науки и техники.
Источник статьи: 100 миллионов долларов за одно число!.