Беглое введение в криптологию
Принятие Закона Республики Беларусь об электронном документе не может не вызвать вспышки интереса к технологии электронной подписи. Методы наложения электронных (цифровых) подписей и оценка их устойчивости к атакам злоумышленников являются частью криптологии. Так что вполне уместно кратко познакомиться с криптологией как таковой.
Когда родилась наука о сокрытии и восстановлении информации никто точно сказать не сумеет. Можно, например, начать с Древнего Рима, где Юлий Цезарь, посылавший письма своим поверенным, не доверял посыльным. Поэтому он заменял в письмах каждую букву A на D, B на E и так далее.
Прочесть письма могли только избранные, знавшие о правиле "сдвига на три", с помощью которого шифровались и расшифровывались сообщения. Вот несколько определений. Криптосистемой или шифросистемой называется способ изменения сообщений так, чтобы прочесть их могли только посвященные люди. Криптография - искусство создания и применения криптосистем. Криптоанализ - искусство раскрытия (взлома) криптосистем. Криптология изучает криптографию и криптоанализ.
Исходный текст сообщения называется простым текстом. После обработки криптосистемой, то есть после шифрования, простой текст превращается в шифротекст. Обратная операция преобразования шифротекста в простой текст называется дешифровкой или расшифровкой.
На деле криптосистема обычно включает в себя сразу несколько алгоритмов (де)шифрования. Но и это еще не все: работа этих алгоритмов зависит от значения определенного параметра, называемого ключом. Поэтому для обозначения конкретной процедуры шифрования наряду с названием алгоритма указывается ключ. Алгоритм является постоянной частью процедуры, а ключ, который может принимать разные значения, - переменной частью. Вполне вероятно, что Цезарь использовал алгоритм "сдвиг на N" для разных значений N. Иными словами, N - ключ.
Классический криптоанализ представляет собой занятную смесь аналитических рассуждений, приложений математического аппарата, распознавания комбинаций, терпения, настойчивости и удачи. Профессионализм в криптоанализе вырабатывается, главным образом, путем практических попыток вскрытия существующих криптосистем. Подобный опыт считается столь ценным, что некоторые примеры криптоанализа, проведенного Союзниками против фашистской Германии во время Второй Мировой войны, до сих пор засекречены.
В настоящее время в криптоанализе все большую роль начинает играть применение теории чисел и вычислительная (читай - компьютерная) математика. Со времен Цезаря изменился и подход к созданию криптосистем. Теперь не считается необходимым держать в секрете алгоритм шифрования. Любой современный алгоритм должен обеспечивать защиту информации даже в том случае, когда противник знает все детали алгоритма, включая способ передачи ключа, а неизвестным остается только его значение.
Это положение подводит нас к очень интересному вопросу о способах раскрытия криптосистем. Появление компьютеров и невероятный рост их производительности сделал возможным применение грубой силы, когда задача решается "в лоб". Вот пример такого подхода. Дано: f(x) = y. Вы знаете y и знаете, как вычисляется f(x). После этого вы пытаетесь обнаружить х, который дает y путем вычисления f для всех возможных значений х.
А вот более реалистичный пример. Предположим, что криптоаналитик обнаружил простой текст и соответствующий ему шифротекст, знает алгоритм, но не располагает ключом. (Кстати, говорят, что в противном случае ни один криптоаналитик вообще не станет браться за работу.) Итак, можно попробовать просто шифровать текст, перебирая все возможные ключи, в надежде, что один из них подойдет и даст совпадение с известным шифротекстом. А можно поступить наоборот - расшифровывать текст всеми возможными ключами.
Хорошо разработанная криптосистема предполагает существование такого количества ключей, что найти среди них искомый простым перебором практически невозможно. Но граница "практически возможного" не стоит на месте. Скажем, DES, система используемая властями США уже более 10 лет, имеет 2 в 56-й степени (примерно 10 в 17-й) ключей. В середине 70-х взлом DES грубой силой был невозможен. Сегодня - возможен, что и является причиной поисков замены DES.
С современной точки зрения надежные криптосистемы должны обладать рядом характерных признаков. Во-первых, как уже упоминалось, надежность криптосистемы в меньшей степени определяется секретностью алгоритма, чем количеством возможных ключей. Во-вторых, шифротекст, выдаваемый системой, должен казаться случайным набором символов даже после обработки стандартными статистическими методами.
Впрочем, наличие у криптосистемы указанных характеристик еще не означает, что она принадлежит к числу надежных. Эти свойства необходимы, но не достаточны. Помните, что криптография определялась как искусство? Так оно и есть, поскольку лишь некоторые из криптосистем обладают математической основой, которая позволяет доказать их надежность. В подавляющем большинстве случаев это не так.
Ну а в случае математически доказанной надежности криптосистемы можно быть уверенным, что ее никто не взломает? Как ни странно, нет! Дело в том, что криптоанализ также является искусством. Не обладающий исходным текстом сообщения аналитик может предположить, что в нем встречается определенное слово и на основе одного этого предположения (если оно верно) вскрыть код. А еще он может обработать предполагаемый текст несколькими ключами и алгоритмами и одолеть задачу даже вопреки теории.
Кроме всего сказанного, следует учитывать тот факт, что криптосистемы могут неправильно применяться или быть дефектными сами по себе. Удивительно, но люди часто используют относительно слабые системы. Объяснений несколько: одни не знают других систем, другие разрабатывают собственные любительские схемы, даже не догадываясь, на что способен профессиональный криптоаналитик. Но причина беспечности одна: секреты этих людей не нужны никому из тех, кто обладает возможностями вскрыть их криптосистемы.
Какие же методы применяются криптоаналитиками, атакующими вражеские криптосистемы? Элементы стандартного подхода уже упоминались. Он состоит в том, что аналитик имеет фрагмент простого текста или предполагает его. Затем, он шифрует этот фрагмент, перебирая возможные алгоритмы и ключи, в надежде обнаружить соответствие какому-либо фрагменту шифротекста. Такие совпадения наводят на след верного ключа и алгоритма и дают почву для следующих предположений.
Если перечислить основные типы атак на криптосистемы в порядке убывания их трудоемкости и сложности, получится примерно следующее.
А) Только шифротекст: аналитик располагает лишь шифротекстом, по которому должен восстановить исходное сообщение. Успех такой атаки обычно считается возможным. Устойчивость к ней является главной мерой надежности криптосистемы.
Б) Известный текст: аналитик имеет в своем распоряжении простой текст и соответствующий ему шифротекст. Это называется "скомпрометированным" сообщением. В некоторых криптосистемах одно единственное скомпрометированное сообщение раскрывает содержание всех прочих возможных сообщений. Устойчивость к "компромату" также является важной характеристикой надежности криптосистемы.
В) Произвольный фрагмент текста: аналитик отыскивает фрагмент шифротекста, соответствующий произвольному предполагаемому фрагменту исходного текста.
Г) Произвольный фрагмент шифротекста: аналитик выбирает фрагмент шифротекста и отыскивает соответствующий ему фрагмент простого текста.
Д) Адаптивный выбор: аналитик выводит шифротекст, основываясь на технике произвольного фрагмента текста, причем последующий выбор производится с учетом анализа результатов, полученных на предыдущем шаге. Этот метод также известен под названием дифференциального криптоанализа.
И пусть вас не удивляет пристальное внимание к методам взлома криптосистем. В действительности это единственный реальный путь подтверждения их надежности. И пусть этим лучше занимаются профессионалы, отвечающие за то, чтобы в свет не вышла криптосистема, не способная хранить тайну.
Но что это мы все за упокой? Широко известный стандарт RSA, точнее, RSA-155 (512 бит), недавно подвергся профессиональному криптоанализу. Результатом стал взлом системы и рекомендация к увеличению длины ключа. Познакомьтесь с некоторыми сведениями о процедуре взлома, которая завершилась 22 августа 1999 года. Это более чем любопытно.
В ходе работы сначала нужно было определить все возможные простые числа, произведение которых не превосходит 512 бит. Множители подбирались методом просеивания, хорошо известным аналогом которого служит решето Эратосфена. В общем и целом на просеивание ушло примерно 36 CPU-лет. Парк техники был такой (см. таблицу).
Вычислительная мощность всей использованной техники приблизительно эквивалентна 8000 MIPS-годам. MIPS - это миллионы целочисленных операций в секунду. Календарное время расчетов составило 3.7 месяца. Всего было проверено 124722179 вариантов, а результирующая таблица содержала 6699191 строк, 6711336 столбцов и 417132631 чисел (62.27 отличных от нуля чисел на строку). На этом закончился первый этап.
Таблица оказалась в полтора раза больше и вдвое более насыщенной, чем для RSA-140. А потом в работу был запущен, ни много ни мало, суперкомпьютер CRAY C916 Амстердамского научного вычислительного центра. Расчеты заняли 224 часа работы процессора и потребовали около 32 ГБ памяти.
К слову сказать, если для вскрытия RSA-155 потребовалось 35.7 CPU-лет, то для RSA-140 хватило "всего" 8.9 CPU-лет. RSA-155 была взломана в общем и целом за 7.4 календарных месяца, а для RSA-140 хватило девяти недель.
Считаете ли вы этот взлом демонстрацией ненадежности?
Вы все еще не доверяете надежности современных криптосистем с широко известными алгоритмами? Или, чего доброго, считаете, что в нашем отечестве найдутся самодеятельные хакеры, способные проделать работу не хуже, чем профессионалы?
Евгений Щербатюк
Когда родилась наука о сокрытии и восстановлении информации никто точно сказать не сумеет. Можно, например, начать с Древнего Рима, где Юлий Цезарь, посылавший письма своим поверенным, не доверял посыльным. Поэтому он заменял в письмах каждую букву A на D, B на E и так далее.
Прочесть письма могли только избранные, знавшие о правиле "сдвига на три", с помощью которого шифровались и расшифровывались сообщения. Вот несколько определений. Криптосистемой или шифросистемой называется способ изменения сообщений так, чтобы прочесть их могли только посвященные люди. Криптография - искусство создания и применения криптосистем. Криптоанализ - искусство раскрытия (взлома) криптосистем. Криптология изучает криптографию и криптоанализ.
Исходный текст сообщения называется простым текстом. После обработки криптосистемой, то есть после шифрования, простой текст превращается в шифротекст. Обратная операция преобразования шифротекста в простой текст называется дешифровкой или расшифровкой.
На деле криптосистема обычно включает в себя сразу несколько алгоритмов (де)шифрования. Но и это еще не все: работа этих алгоритмов зависит от значения определенного параметра, называемого ключом. Поэтому для обозначения конкретной процедуры шифрования наряду с названием алгоритма указывается ключ. Алгоритм является постоянной частью процедуры, а ключ, который может принимать разные значения, - переменной частью. Вполне вероятно, что Цезарь использовал алгоритм "сдвиг на N" для разных значений N. Иными словами, N - ключ.
Классический криптоанализ представляет собой занятную смесь аналитических рассуждений, приложений математического аппарата, распознавания комбинаций, терпения, настойчивости и удачи. Профессионализм в криптоанализе вырабатывается, главным образом, путем практических попыток вскрытия существующих криптосистем. Подобный опыт считается столь ценным, что некоторые примеры криптоанализа, проведенного Союзниками против фашистской Германии во время Второй Мировой войны, до сих пор засекречены.
В настоящее время в криптоанализе все большую роль начинает играть применение теории чисел и вычислительная (читай - компьютерная) математика. Со времен Цезаря изменился и подход к созданию криптосистем. Теперь не считается необходимым держать в секрете алгоритм шифрования. Любой современный алгоритм должен обеспечивать защиту информации даже в том случае, когда противник знает все детали алгоритма, включая способ передачи ключа, а неизвестным остается только его значение.
Это положение подводит нас к очень интересному вопросу о способах раскрытия криптосистем. Появление компьютеров и невероятный рост их производительности сделал возможным применение грубой силы, когда задача решается "в лоб". Вот пример такого подхода. Дано: f(x) = y. Вы знаете y и знаете, как вычисляется f(x). После этого вы пытаетесь обнаружить х, который дает y путем вычисления f для всех возможных значений х.
А вот более реалистичный пример. Предположим, что криптоаналитик обнаружил простой текст и соответствующий ему шифротекст, знает алгоритм, но не располагает ключом. (Кстати, говорят, что в противном случае ни один криптоаналитик вообще не станет браться за работу.) Итак, можно попробовать просто шифровать текст, перебирая все возможные ключи, в надежде, что один из них подойдет и даст совпадение с известным шифротекстом. А можно поступить наоборот - расшифровывать текст всеми возможными ключами.
Хорошо разработанная криптосистема предполагает существование такого количества ключей, что найти среди них искомый простым перебором практически невозможно. Но граница "практически возможного" не стоит на месте. Скажем, DES, система используемая властями США уже более 10 лет, имеет 2 в 56-й степени (примерно 10 в 17-й) ключей. В середине 70-х взлом DES грубой силой был невозможен. Сегодня - возможен, что и является причиной поисков замены DES.
С современной точки зрения надежные криптосистемы должны обладать рядом характерных признаков. Во-первых, как уже упоминалось, надежность криптосистемы в меньшей степени определяется секретностью алгоритма, чем количеством возможных ключей. Во-вторых, шифротекст, выдаваемый системой, должен казаться случайным набором символов даже после обработки стандартными статистическими методами.
Впрочем, наличие у криптосистемы указанных характеристик еще не означает, что она принадлежит к числу надежных. Эти свойства необходимы, но не достаточны. Помните, что криптография определялась как искусство? Так оно и есть, поскольку лишь некоторые из криптосистем обладают математической основой, которая позволяет доказать их надежность. В подавляющем большинстве случаев это не так.
Ну а в случае математически доказанной надежности криптосистемы можно быть уверенным, что ее никто не взломает? Как ни странно, нет! Дело в том, что криптоанализ также является искусством. Не обладающий исходным текстом сообщения аналитик может предположить, что в нем встречается определенное слово и на основе одного этого предположения (если оно верно) вскрыть код. А еще он может обработать предполагаемый текст несколькими ключами и алгоритмами и одолеть задачу даже вопреки теории.
Кроме всего сказанного, следует учитывать тот факт, что криптосистемы могут неправильно применяться или быть дефектными сами по себе. Удивительно, но люди часто используют относительно слабые системы. Объяснений несколько: одни не знают других систем, другие разрабатывают собственные любительские схемы, даже не догадываясь, на что способен профессиональный криптоаналитик. Но причина беспечности одна: секреты этих людей не нужны никому из тех, кто обладает возможностями вскрыть их криптосистемы.
Какие же методы применяются криптоаналитиками, атакующими вражеские криптосистемы? Элементы стандартного подхода уже упоминались. Он состоит в том, что аналитик имеет фрагмент простого текста или предполагает его. Затем, он шифрует этот фрагмент, перебирая возможные алгоритмы и ключи, в надежде обнаружить соответствие какому-либо фрагменту шифротекста. Такие совпадения наводят на след верного ключа и алгоритма и дают почву для следующих предположений.
Если перечислить основные типы атак на криптосистемы в порядке убывания их трудоемкости и сложности, получится примерно следующее.
А) Только шифротекст: аналитик располагает лишь шифротекстом, по которому должен восстановить исходное сообщение. Успех такой атаки обычно считается возможным. Устойчивость к ней является главной мерой надежности криптосистемы.
Б) Известный текст: аналитик имеет в своем распоряжении простой текст и соответствующий ему шифротекст. Это называется "скомпрометированным" сообщением. В некоторых криптосистемах одно единственное скомпрометированное сообщение раскрывает содержание всех прочих возможных сообщений. Устойчивость к "компромату" также является важной характеристикой надежности криптосистемы.
В) Произвольный фрагмент текста: аналитик отыскивает фрагмент шифротекста, соответствующий произвольному предполагаемому фрагменту исходного текста.
Г) Произвольный фрагмент шифротекста: аналитик выбирает фрагмент шифротекста и отыскивает соответствующий ему фрагмент простого текста.
Д) Адаптивный выбор: аналитик выводит шифротекст, основываясь на технике произвольного фрагмента текста, причем последующий выбор производится с учетом анализа результатов, полученных на предыдущем шаге. Этот метод также известен под названием дифференциального криптоанализа.
И пусть вас не удивляет пристальное внимание к методам взлома криптосистем. В действительности это единственный реальный путь подтверждения их надежности. И пусть этим лучше занимаются профессионалы, отвечающие за то, чтобы в свет не вышла криптосистема, не способная хранить тайну.
Но что это мы все за упокой? Широко известный стандарт RSA, точнее, RSA-155 (512 бит), недавно подвергся профессиональному криптоанализу. Результатом стал взлом системы и рекомендация к увеличению длины ключа. Познакомьтесь с некоторыми сведениями о процедуре взлома, которая завершилась 22 августа 1999 года. Это более чем любопытно.
В ходе работы сначала нужно было определить все возможные простые числа, произведение которых не превосходит 512 бит. Множители подбирались методом просеивания, хорошо известным аналогом которого служит решето Эратосфена. В общем и целом на просеивание ушло примерно 36 CPU-лет. Парк техники был такой (см. таблицу).
Вычислительная мощность всей использованной техники приблизительно эквивалентна 8000 MIPS-годам. MIPS - это миллионы целочисленных операций в секунду. Календарное время расчетов составило 3.7 месяца. Всего было проверено 124722179 вариантов, а результирующая таблица содержала 6699191 строк, 6711336 столбцов и 417132631 чисел (62.27 отличных от нуля чисел на строку). На этом закончился первый этап.
Таблица оказалась в полтора раза больше и вдвое более насыщенной, чем для RSA-140. А потом в работу был запущен, ни много ни мало, суперкомпьютер CRAY C916 Амстердамского научного вычислительного центра. Расчеты заняли 224 часа работы процессора и потребовали около 32 ГБ памяти.
К слову сказать, если для вскрытия RSA-155 потребовалось 35.7 CPU-лет, то для RSA-140 хватило "всего" 8.9 CPU-лет. RSA-155 была взломана в общем и целом за 7.4 календарных месяца, а для RSA-140 хватило девяти недель.
Считаете ли вы этот взлом демонстрацией ненадежности?
Вы все еще не доверяете надежности современных криптосистем с широко известными алгоритмами? Или, чего доброго, считаете, что в нашем отечестве найдутся самодеятельные хакеры, способные проделать работу не хуже, чем профессионалы?
Евгений Щербатюк
Компьютерная газета. Статья была опубликована в номере 10 за 2000 год в рубрике разное :: мелочи жизни
