Криптография и виды шифрования

 

3. Критерии определения естественности

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

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

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

В таком случае нам придется ввести оценку по теоретическим  возможностям попадания символов в  тексте. Для того, чтобы обеспечить принятые нами возможности ошибок первого  и второго рода, при оценивании максимально возможной правдоподобности, нужно проанализировать уже около 100 знаков, а анализ возможности встречи биграмм всего лишь немного уменьшает эту величину.

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

 

3. Симметричное шифрование

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

В настоящее время симметричные шифры — это:

• Блочные шифры. Обрабатывают информацию блоками определённой длины (обычно 64, 128 бит), применяя к блоку ключ в установленном порядке, как правило, несколькими циклами перемешивания и подстановки, называемыми раундами. Результатом повторения раундов является лавинный эффект — нарастающая потеря соответствия битов между блоками открытых и зашифрованных данных.
• Поточные шифры, в которых шифрование проводится над каждым битом либо байтом исходного (открытого) текста с использованием гаммирования. Поточный шифр может быть легко создан на основе блочного (например, ГОСТ 28147-89 в режиме гаммирования), запущенного в специальном режиме.

Большинство симметричных шифров используют сложную комбинацию большого количества подстановок и  перестановок. Многие такие шифры исполняются в несколько (иногда до 80) проходов, используя на каждом проходе «ключ прохода». Множество «ключей прохода» для всех проходов называется «расписанием ключей» (key schedule). Как правило, оно создается из ключа выполнением над ним неких операций, в том числе перестановок и подстановок.

Типичным способом построения алгоритмов симметричного  шифрования является сеть Фейстеля. Алгоритм строит схему шифрования на основе функции F(D, K), где D — порция данных, размером вдвое меньше блока шифрования, а K — «ключ прохода» для данного прохода. От функции не требуется обратимость — обратная ей функция может быть неизвестна. Достоинства сети Фейстеля — почти полное совпадение дешифровки с шифрованием (единственное отличие — обратный порядок «ключей прохода» в расписании), что сильно облегчает аппаратную реализацию.

Операция перестановки перемешивает биты сообщения по некоему  закону. В аппаратных реализациях  она тривиально реализуется как  перепутывание проводников. Именно операции перестановки дают возможность достижения «эффекта лавины». Операция перестановки линейна — f(a) xor f(b) == f(a xor b)

Операции подстановки  выполняются как замена значения некоей части сообщения (часто в 4, 6 или 8 бит) на стандартное, жестко встроенное в алгоритм иное число путем обращения к константному массиву. Операция подстановки привносит в алгоритм нелинейность.

Зачастую стойкость  алгоритма, особенно к дифференциальному  криптоанализу, зависит от выбора значений в таблицах подстановки (S-блоках). Как  минимум считается нежелательным наличие неподвижных элементов S(x) = x, а также отсутствие влияния какого-то бита входного байта на какой-то бит результата — то есть случаи, когда бит результата одинаков для всех пар входных слов, отличающихся только в данном бите.

Рисунок 1.Виды ключей

 

4. Ассиметричное шифрование

Криптографическая система с открытым ключом (или асимметричное шифрование, асимметричный шифр) — система шифрования и/или электронной цифровой подписи, при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу и используется для проверки ЭЦП и для шифрования сообщения. Для генерации ЭЦП и для расшифровки сообщения используется секретный ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH.

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

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

Понять идеи и методы криптографии с открытым ключом помогает следующий пример — хранение паролей в компьютере. Каждый пользователь в сети имеет свой пароль. При входе он указывает имя и вводит секретный пароль. Но если хранить пароль на диске компьютера, то кто-нибудь его может считать (особенно легко это сделать администратору этого компьютера) и получить доступ к секретной информации. Для решения задачи используется односторонняя функция. При создании секретного пароля в компьютере сохраняется не сам пароль, а результат вычисления функции от этого пароля и имени пользователя. Например, пользователь Алиса придумала пароль «Гладиолус». При сохранении этих данных вычисляется результат функции  (ГЛАДИОЛУС), пусть результатом будет строка РОМАШКА, которая и будет сохранена в системе. В результате файл паролей примет следующий вид:

 

Имя	(имя_пароль)
АЛИСА	РОМАШКА
БОБ	НАРЦИСС

Вход в систему теперь выглядит так:

Имя:	АЛИСА
Пароль:	ГЛАДИОЛУС

Когда Алиса  вводит «секретный» пароль, компьютер  проверяет, даёт или нет функция, применяемая к ГЛАДИОЛУС, правильный результат РОМАШКА, хранящийся на диске компьютера. Стоит изменить хотя бы одну букву в имени или в пароле, и результат функции будет совершенно другим. «Секретный» пароль не хранится в компьютере ни в каком виде. Файл паролей может быть теперь просмотрен другими пользователями без потери секретности, так как функция практически необратимая.

В предыдущем примере  используется односторонняя функция  без лазейки, поскольку не требуется  по зашифрованному сообщению получить исходное. В следующем примере  рассматривается схема с возможностью восстановить исходное сообщение с  помощью «лазейки», то есть труднодоступной информации. Для шифрования текста можно взять большой абонентский справочник, состоящий из нескольких толстых томов (по нему очень легко найти номер любого жителя города, но почти невозможно по известному номеру найти абонента). Для каждой буквы из шифруемого сообщения выбирается имя, начинающееся на ту же букву. Таким образом букве ставится в соответствие номер телефона абонента. Отправляемое сообщение, например «КОРОБКА», будет зашифровано следующим образом:

Сообщение	Выбранное имя	Криптотекст
К	Королёв	5643452
О	Орехов	3572651
Р	Рузаева	4673956
O	Осипов	3517289
Б	Батурин	7755628
К	Кирсанова	1235267
А	Арсеньева	8492746

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

Примеры таких  криптотекстов:

 

Криптотекст 1	Криптотекст 2	Криптотекст 3
1235267	5643452	1235267
3572651	3517289	3517289
4673956	4673956	4673956
3517289	3572651	3572651
7755628	7755628	7755628
5643452	1235267	5643452
8492746	8492746	8492746

Чтобы расшифровать текст, надо иметь справочник, составленный согласно возрастанию номеров. Этот справочник является лазейкой (секрет, который помогает получить начальный текст), известной только легальным пользователям. Не имея на руках копии справочника, криптоаналитик затратит очень много времени на расшифровку.

Схема шифрования с открытым ключом

Пусть   — пространство ключей, а   и   — ключи шифрования и расшифрования соответственно.   — функция шифрования для произвольного ключа  , такая что:

Здесь  , где   — пространство шифротекстов, а  , где   — пространство сообщений.

 — функция расшифрования, с помощью которой можно найти  исходное сообщение  , зная шифротекст   :

{ :  } — набор шифрования, а { :  } — соответствующий набор для расшифрования. Каждая пара   имеет свойство: зная  , невозможно решить уравнение  , то есть для данного произвольного шифротекста  , невозможно найти сообщение  . Это значит, что по данному   невозможно определить соответствующий ключ расшифрования  .   является односторонней функцией, а   — лазейкой.

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

Рисунок 2.Ассиметричное шифрование

1. Боб выбирает пару   и шлёт ключ шифрования   (открытый ключ) Алисе по открытому каналу, а ключ расшифрования   (закрытый ключ) защищён и секретен (он не должен передаваться по открытому каналу).
2. Чтобы послать сообщение   Бобу, Алиса применяет функцию шифрования, определённую открытым ключом  :  ,   — полученный шифротекст.
3. Боб расшифровывает шифротекст  , применяя обратное преобразование  , однозначно определённое значением  .