Криптология

 

Все многообразие существующих криптографических  методов можно свести к следующим  классам преобразований:

Многоалфавитная подстановка  – наиболее простой вид преобразований, заключающийся в замене символов исходного текста на другие (того же алфавита) по более или менее сложному правилу. Для обеспечения высокой криптостойкости требуется использование больших ключей.

Перестановки –  несложный метод криптографического преобразования. Используется как правило в сочетании с другими методами.

Гаммирование – этот метод заключается в наложении на исходный текст некоторой псевдослучайной последовательности, генерируемой на основе ключа.

Блочные шифры представляют собой последовательность (с возможным повторением и чередованием) основных методов преобразования, применяемую к блоку (части) шифруемого текста. Блочные шифры на практике встречаются чаще, чем “чистые” преобразования того или иного класса в силу их более высокой криптостойкости, а также потому, что этот метод позволяет шифровать тексты практически любой длины, разбивая их на блоки. Российский и американский стандарты шифрования основаны именно на этом классе шифров.

Метод Цезаря

Метод Цезаря является самым простым  вариантом шифрования.

Он назван по имени римского императора Гая Юлия Цезаря, который поручал  Марку Туллию Цицерону составлять послания с использованием 50-буквенного алфавита, сдвигая его на 3 символа вперед.

Подстановка определяется по таблице  замещения, содержащей пары соответствующих букв “исходный текст – шифрованный текст”.

Например, ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯ посредством подстановки преобразуется в еюыолхиврсеюивцнгкгрлб.

 

Аàг	Йàм	Тàх	Ыàю
Бàд	Кàн	Уàц	Ьàя
Вàе	Лàо	Фàч	Эà_
Гàж	Мàп	Хàш	Юàа
Дàз	Нàр	Цàщ	Яàб
Еàи	Оàс	Чàъ	_àв
Жàй	Пàт	Шàы
Зàк	Рàу	Щàь
Иàл	Сàф	Ъàэ

Таблица 1.1: Применение подстановки Цезвря.

При своей несложности система  легко уязвима. Если злоумышленник  имеет

1) шифрованный и соответствующий  исходный текст или

2) шифрованный текст выбранного  злоумышленником исходного текста,

то определение ключа и дешифрование исходного текста тривиальны.

Эту систему не представляет труда  взломать с помощью современной  вычислительной техники, используя простой перебор. Поэтому криптостойкость этого метода не велика.

Более эффективны обобщения подстановки  Цезаря – шифр Хилла и шифр Плэйфера. Они основаны на подстановке не отдельных символов, а 2-грамм (шифр Плэйфера) или n-грамм (шифр Хилла). При более высокой криптостойкости они значительно сложнее для реализации и требуют достаточно большого количества ключевой информации.

 

Системы шифрования Вижинера

Метод Вижинера является следствием подстановки Цезаря. В системе  Вижинера задается некая конечная последовательность ключа

k = (k₀ ,k₁ ,...,k_n),

которая называется ключом пользователя, она продолжается до бесконечной последовательности, повторяя цепочку. Таким образом, получается рабочий ключ

Например, при ключе пользователя 15 8 2 10 11 4 18 рабочий ключ будет периодической  последовательностью:

15 8 2 10 11 4 18 15 8 2 10 11 4 18 15 8 2 10 11 4 18 ...

Таким образом:

При длине  пользовательского ключа R

1) исходный  текст x делится на R фрагментов

x_i = (x_i , x_i+r , ..., x_i+r(n-1)), 0 £ i < r;

2) i-й  фрагмент исходного текста x_i шифруется при помощи подстановки Цезаря в зависимости от пользовательского ключа :

(x_i , x_i+r , ..., x_i+r(n-1)) ® (y_i , y_i+r , ..., y_i+r(n-1)),

Очень распространена плохая с точки зрения секретности практика использовать слово или фразу в качестве ключа для того, чтобы k=(k₀ ,k₁ ,...,k_к-1) было легко запомнить. В информационных системах для обеспечения безопасности информации это недопустимо. Для получения ключей должны использоваться программные или аппаратные средства случайной генерации ключей.

Пример. Преобразование текста с помощью  подстановки Вижинера (r=4)

Исходный текст (ИТ1):

НЕ_СЛЕДУЕТ_ВЫБИРАТЬ_НЕСЛУЧАЙНЫЙ_КЛЮЧ

Ключ: КЛЮЧ

Разобьем исходный текст на блоки  по 4 символа:

НЕ_С ЛЕДУ ЕТ_В ЫБИР АТЬ_ НЕСЛ УЧАЙ НЫЙ_ КЛЮЧ

и наложим на них ключ (используя  таблицу Вижинера):

H+К=Ч, Е+Л=Р и т.д.

Получаем зашифрованный (ЗТ1) текст:

ЧРЭЗ ХРБЙ ПЭЭЩ ДМЕЖ КЭЩЦ ЧРОБ ЭБЮ_ ЧЕЖЦ ФЦЫН

Криптостойкость метода резко убывает с уменьшением длины ключа.

Тем не менее такая система как шифр Вижинера допускает несложную аппаратную или программную реализацию и при достаточно большой длине ключа может быть использован в современных ИС.

Гаммирование

Гаммирование является также широко применяемым криптографическим преобразованием. На самом деле граница между гаммированием и использованием бесконечных ключей и шифров Вижинера, о которых речь шла выше, весьма условная.

Принцип шифрования гаммированием заключается в генерации гаммы шифра с помощью датчика псевдослучайных чисел и наложении полученной гаммы на открытые данные обратимым образом.

Процесс дешифрования данных сводится к повторной генерации гаммы шифра при известном ключе и наложении такой гаммы на зашифрованные данные.

Полученный зашифрованный текст  является достаточно трудным для  раскрытия в том случае, если гамма шифра не содержит повторяющихся битовых последовательностей. По сути дела гамма шифра должна изменяться случайным образом для каждого шифруемого слова. Фактически же, если период гаммы превышает длину всего зашифрованного текста и неизвестна никакая часть исходного текста, то шифр можно раскрыть только прямым перебором (пробой на ключ). Криптостойкость в этом случае определяется размером ключа.

Метод гаммирования становится бессильным, если злоумышленнику становится известен фрагмент исходного текста и соответствующая ему шифрограмма. Простым вычитанием по модулю получается отрезок ПСП и по нему восстанавливается вся последовательность. Злоумышленники может сделать это на основе догадок о содержании исходного текста. Так, если большинство посылаемых сообщений начинается со слов “СОВ.СЕКРЕТНО”, то криптоанализ всего текста значительно облегчается. Это следует учитывать при создании реальных систем информационной безопасности.

 

 

Криптосистемы с открытым ключом

В 1976 г. У.Диффи и М.Хеллманом  был предложен новый тип криптографической системы – система с открытым ключом [public keycryptosystem]. В схеме с открытым ключом имеется два ключа, открытый [public] и секретный [private, secret], выбранные таким образом, что их последовательное применение к массиву данных оставляет этот массив без изменений. Шифрующая процедура использует открытый ключ, дешифрующая – секретный. Дешифрование кода без знания секретного ключа практически неосуществимо; в частности, практически неразрешима задача вычисления секретного ключа по известному открытому ключу. Основное преимущество криптографии с открытым ключом – упрощенный механизм обмена ключами. При осуществлении коммуникации по каналу связи передается только открытый ключ, что делает возможным использование для этой цели обычного канала и устраняет потребность в специальном защищенном канале для передачи ключа.

С появлением систем с открытым ключом понятие о защите информации, а  вместе с ним функции криптографии значительно расширились. Если раньше основной задачей криптографических систем считалось надежное шифрование информации, в настоящее время область применения криптографии включает также цифровую подпись(аутентификацию), лицензирование, нотаризацию (свидетельствование), распределенное управление, схемы голосования, электронные деньги и многое другое . Наиболее распространенные функции криптографических систем с открытым ключом – шифрование и цифровая подпись, причем роль цифровой подписи в последнее время возросла по сравнению с традиционным шифрованием: некоторые из систем с открытым ключом поддерживают цифровую подпись, но не поддерживают шифрование.

Цифровая подпись используется для аутентификации текстов, передаваемых по телекоммуникационным каналам. Она  аналогична обычной рукописной подписи  и обладает ее основными свойствами: удостоверяет, что подписанный текст  исходит именно от лица, поставившего подпись, и не дает самому этому лицу возможности отказаться от обязательств, связанных с подписанным текстом. Цифровая подпись представляет собой небольшое количество дополнительной информации, передаваемой вместе с подписываемым текстом. В отличие от шифрования, при формировании подписи используется секретный ключ, а при проверке – открытый.

Из-за особенностей алгоритмов, лежащих  в основе систем с открытым ключом, их быстродействие при обработке  единичного блока информации обычно в десятки раз меньше, чем быстродействие систем с симметричным ключом на блоке той же длины. Для повышения эффективности систем с открытым ключом часто применяются смешанные методы, реализующие криптографические алгоритмы обоих типов. При шифровании информации выбирается случайный симметричный ключ, вызывается алгоритм с симметричным ключом для шифрования исходного текста. а затем алгоритм с открытым ключом для шифрования симметричного ключа. По коммуникационному каналу передается текст, зашифрованный симметричным ключом, и симметричный ключ, зашифрованный открытым ключом. Для расшифровки действия производятся в обратном порядке: сначала при помощи секретного ключа получателя расшифровывается симметричный ключ, а затем при помощи симметричного ключа -полученный по каналу зашифрованный текст. Для формирования электронной подписи по подписываемому тексту вычисляется его однонаправленная хэш-функция(дайджест) [one-way hash function, digest], представляющая собой один короткий блок информации, характеризующий весь текст в целом; задача восстановления текста по его хэш-функции или подбора другого текста, имеющего ту же хэш-функцию, практически неразрешима. При непосредственном формировании подписи, вместо шифрования секретным ключом каждого блока текста секретный ключ применяется только к хэш-функции; по каналу передается сам текст и сформированная подпись хэш-функции. Для проверки подписи снова вычисляется хэш-функция от полученного по каналу текста, после чего при помощи открытого ключа проверяется, что подпись соответствует именно данному значению хэш-функции. Алгоритмы вычисления однонаправленных хэш-функций, как правило, логически тесно связаны с алгоритмами шифрования с симметричным ключом.

Описанные гибридные методы шифрования и цифровой подписи сочетают в себе эффективность алгоритмов с симметричным ключом и свойство независимости от дополнительных секретных каналов для передачи ключей, присущее алгоритмам с открытым ключом. Криптографическая стойкость конкретного гибридного метода определяется стойкостью слабейшего звена в цепи, состоящей из алгоритмов с симметричным и с открытым ключом, выбранных для его реализации.

Система RSA

Самым распространенным алгоритмом ассиметричного шифрования является алгоритм RSA. Он был  предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest) , Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах. Разработчикам данного алгоритма удалось эффективно воплотить идею односторонних функций с секретом. Стойкость RSA базируется на сложности факторизации больших целых чисел. Современное состояние алгоритмов факторизации (разложения на множители) позволяет решать эту задачу для чисел длиной до 430 бит; исходя из этого, ключ длиной в 512 бит считается надежным для защиты данных на срок до 10 лет, а в 1024 бита – безусловно надежным. Несмотря на то, что отсутствует математически доказанное сведение задачи раскрытия RSA к задаче разложения на множители, система выдержала испытание практикой и является признанным стандартом de-facto в промышленной криптографии, а также официальным стандартом ряда международных организаций. С другой стороны, свободное распространение программного обеспечения, основанного на RSA, ограничено тем, что алгоритм RSA защищен в США рядом патентов. RSA можно применять как для шифрования/расшифровывания, так и для генерации/проверки электронно-цифровой подписи.

Генерация ключа

Первым этапом любого асимметричного алгоритма является создание пары ключей : открытого и закрытого и распространение открытого ключа «по всему миру». Для алгоритма RSA этап создания ключей состоит из следующих операций :

Выбираются два простых (!) числа p и q

Вычисляется их произведение n(=p*q)

Выбирается произвольное число e (e<n), такое, что НОД(e,(p-1)(q-1))=1, то есть e должно быть взаимно простым с числом (p-1)(q-1).

Методом Евклида решается в целых  числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь  неизвестными являются переменные d и y – метод Евклида как раз  и находит множество пар (d,y), каждая из которых является решением уравнения  в целых числах. Два числа (e,n) – публикуются как открытый ключ.

Число d хранится в строжайшем секрете  – это и есть закрытый ключ, который  позволит читать все послания, зашифрованные  с помощью пары чисел (e,n).

Шифрование/расшифровывание

Отправитель разбивает свое сообщение  на блоки, равные k=[log₂(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа.

Подобный блок, как Вы знаете, может  быть интерпретирован как число  из диапазона (0;2^k-1). Для каждого такого числа (m_i) вычисляется выражение c_i=((m_i)^e)mod n. Блоки c_i и есть зашифрованное сообщение, и их можно спокойно передавать по открытому каналу, поскольку операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название «логарифмирование в конечном поле» и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по c_i прочесть исходные сообщения m_i он не может никак, кроме как полным перебором m_i.