Пример 37.

Требуется защитить ключ К = 10.

А. Формируем множество {p, n₁, n₂}, где p = 13, n₁ = 17, n₂ = 19,

которое удовлетворяет условиям:

1) 13 > 10,

2) 17 < 19

3) числа 13, 17, 19 попарно взаимно просты, то есть НОД (13, 17) = 1, НОД (13, 19) = 1, НОД (17, 19) = 1

4) 17*19 > 13*19

Б. Выбираем число r Î [ 0, ((17*19) / 13) -1] ≈ [0, 23] так чтобы выполнялось условие K' = K + r * p попадало в интервал

[n₁* n₂ / p, (n₁n₂) – 1] т. е. 10 + 13 * r Î [24, 322].

возьмем r = 3, тогда K' = 49.

В. Распределяемыми числами будут K₁ = 49 (mod 17) = 15 K₂ = 49 (mod19)=11

Г. Убедимся в возможности восстановления исходного общего К по двум распределенным ключам К₁ и К₂.

1) N₁ = (17*19)/ 17 = 19 N₂ = (17*19)/19 = 17

Имеем (M₁ *19) ≡ 1 (mod17) → M₁ = 9

(M₂ *17) ≡ 1 (mod19) → M₂ = 9

2) вычисляем K', затем K

K' = (15*9*19 + 11*9*17) (mod323) = 49

K = 49 - 3*13 = 10, что и требовалось доказать. ▲

4.9. Вычисление сравнений вида a^b(mod m)

Алгоритм позволяет сделать это за O (ln m) арифметических операций. При этом конечно, предполагается что натуральные числа a и b не превосходят m. Последовательность шагов такова.

1. Представляем b в двоичной системе счисления:

b = b₀∙ 2^r + b₁∙ 2^r-1 +…+ b_r-1∙ 2 + b_r,

где b_i –цифры в двоичном представлении, равные 0 или 1.

2. Присваиваем a₀ = a и затем для i=1, …, r вычисляем

a_i = a_i-1² ∙ a^bi(mod m).

4. a_r есть искомый вычет.

Пример 38. Рассмотрим a^b(mod m) =15²⁶(mod 32). Имеем,

26 = 16 + 8 + 2 = 1*2⁴ + 1*2³ + 0*2² + 1*2¹ + 0*2⁰, т.е.

b₀ = 1, b₁ = 1, b₂ = 0, b₃ = 1, b₄ = 0.

Далее, полагаем a₀ = a = 15. Затем начинаем вычислять:

a₁ = a₀² ∙ a^b1(mod m) = 15² ∙ 15¹(mod 32) = 225 ∙ 15(mod 32) = 15.

a₂ = a₁² ∙ a^b2(mod m) = 15² ∙ 15⁰(mod 32) = 225 ∙ 1(mod 32) = 1.

a₃ = a₂² ∙ a^b3(mod m) = 1² ∙ 15¹(mod 32) = 1∙ 15(mod 32) = 17.

a₄ = a₃² ∙ a^b4(mod m) = 17² ∙ 15⁰(mod 32) = 289 ∙ 1(mod 32) = 1. ▲

5. Основные понятия и определения

В криптографии

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

Современная криптография включает в себя следующие основные направления:

1. Симметричные криптосистемы (одноключевые, традиционные).

2. Криптосистемы с открытым ключом (асимметричные, двухключевые).

3. Системы электронной цифровой подписи.

4. Управление ключами.

5. Прочие криптографические алгоритмы.

Существуют два типа симметричных криптосистем – блочные и потоковые.

1. В блочных шифрах исходная информация разбивается на блоки одного (постоянного) размера, которые последовательно подвергаются обработке по алгоритму зашифрования С_i = E(M_i).

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

5.1. Понятие шифра

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

E = {E_k}, k Î K,

где K – конечное множество допустимых значений ключа (ключевое множество). Выбранный ключ k однозначно определяет отображение E_k из семейства шифра E.

Практическое использование ключа определяется его жизненным циклом, который содержит следующие операции:

· генерация ключа;

· распределение (рассылка абонентам);

· хранение;

· применение при зашифровании информации;

· смена;

· уничтожение.

Информацию, подвергающуюся отображениям шифра, называют открытымтекстом.

Зашифрование – преобразование по криптографическому алгоритму открытого текста или данных к виду, не позволяющему осуществить несанкционированное ознакомление с ними без знания секретной переменной алгоритма – криптографического ключа. Результат шифрования открытого текста называется криптограммой. Если обозначить через X множество открытых текстов, через Y – множество зашифрованных текстов, то шифр можно рассматривать как семейство Е отображений множества X ´ K в множество Y.

Обратимость отображений шифра обеспечивает возможность восстановления открытого текста по криптограмме.

Расшифрование – преобразование по криптографическому алгоритму зашифрованного текста в открытый с использованием известного криптографического ключа.

Шифрование – процесс зашифровывания или расшифровывания.

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

Криптостойкость – характеристика шифра, определяющая его стойкость к дешифрованию.

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

C = f(М), или C = f(М, S). Криптография решает указанную задачу посредством шифрования защищаемых данных, что предполагает использование двух следующих взаимно обратных преобразований:

· перед отправлением данных по линии связи или перед помещением на хранение они подвергаются зашифрованию;

· для восстановления исходных данных из зашифрованных к ним применяется процедура расшифрования.

Рисунок 5.1. Схема преобразования данных при шифровании

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

Алфавит – конечное множество используемых знаков.

Текст – упорядоченный набор из элементов алфавита.

В качестве примеров алфавитов, используемых в современных информационных системах (ИС) можно привести следующие:

• алфавит Z33 – 32 буквы русского алфавита и пробел;

• алфавит Z44 – буквы русского алфавита, знаки препинания и пробела;

• алфавит Z256 – символы, входящие в стандартные коды ASCII и КОИ-8;

• бинарный алфавит – Z2 = {0, 1};

• восьмеричный алфавит – Z8 = {0, 1, 2, 3, 4, 5, 6, 7};

• шестнадцатеричный алфавит – Z16 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F};

Каким же условиям должен удовлетворять шифр? Прежде всего, процедура расшифрования должна всегда восстанавливать открытое сообщение в его исходном виде. Иными словами, для каждого допустимого сообщения М преобразования за – и расшифрования должны удовлетворять следующему свойству:

М = D(E(М)).

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

Каким же условиям должен удовлетворять стойкий шифр? Эти условия сформулировал Шеннон в ряде своих основополагающих работ по теории шифрования: такой шифр должен обладать свойствами перемешивания и рассеивания:

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

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

Если шифр обладает обоими указанными свойствами в достаточной степени, то любые изменения в блоке открытых данных приводят к тому, что с точки зрения наблюдателя все символы (биты) в зашифрованном блоке получат новые значения, равновероятные в области их определения и независимые друг от друга. Так, если шифр оперирует информацией, представленной в двоичной форме, то инвертирование даже одного бита в блоке исходных данных приведет к тому, что все биты в соответствующем блоке шифрованных данных с вероятностью 1/2 независимо друг от друга так же поменяют свое значение. Такой шифр невозможно вскрыть способом, менее затратным с точки зрения количества необходимых операций, чем полный перебор по множеству возможных значений ключа. Данное условие является обязательным для шифра, претендующего на то, чтобы считаться хорошим. Как же создать надежный шифр, соответствующий всем приведенным выше условиям надежности? Шеннон предложил строить его из простых шифров, как большой дом строится из отдельных кирпичиков. Каждый из использованных простых шифров может не обладать рассмотренными выше свойствами, но все вместе они образуют вполне стойкий шифр.

Поэтому всё многообразие существующих традиционных кpиптогpафических методов можно свести к следующим классам простых пpеобpазований:

1. Подстановка (замена)

2. Перестановка

3. Аналитические преобразования

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

5. Комбинированные способы.

5.2. Симметричные криптоалгоритмы

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

Обмен информацией осуществляется в 3 этапа:

1. Отправитель передает получателю ключ (в случае сети с несколькими абонентами у каждой пары абонентов должен быть свой ключ, отличный от ключей других пар);

2. Отправитель, используя ключ, зашифровывает сообщение, которое пересылается получателю;

3. Получатель получает сообщение и расшифровывает его.

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

5.2.1. Моно - и многоалфавитные подстановки

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

Подстановкой π на алфавите Z_n называется автоморфизм, при котором буквы исходного текста t замещены буквами шифрованного текста

π (t): Z_n → Z_n; π: t → π (t).

Набор всех подстановок из Z_n с операцией умножения является симметрической группой. Для доказательства этого утверждения необходимо выполнение всех свойств группы:

1. Замкнутость: произведение подстановок π ₁∙ π ₂ является подстановкой:

π: t→ π ₁∙ (π ₂(t)).

2. Ассоциативность: результат произведения π ₁ ∙ π ₂ ∙ π ₃ не зависит от порядка расстановки скобок: (π ₁ ∙ π ₂) ∙ π ₃ = π ₁ ∙ (π ₂ ∙ π ₃)

3. Существование единичного элемента: постановка е, определяемая как е (t) = t, 0 ≤ t < m, является нейтральным элементом S(Z_n) по операции умножения: е ∙ π = π ∙ е для " π Î S(Z_n).

4. Существование обратного элемента: для любой подстановки π существует единственная обратная подстановка π ^-1, удовлетворяющая условию:

π ∙ π ^-1 = π ^-1∙ π = е.

Ключом подстановки k для Z_n называется последовательность элементов симметрической группы S(Z_n):

k = (p₀, p₁,..., p_n-1,...), p_i Î S(Z_n), 0 ≤ n < ∞.

Подстановка, определяемая ключом k, является криптографическим преобразованием T_k, при помощи которого осуществляется преобразование n -граммы исходного текста (x₀, x₁,.., x_n-1) в n -грамму зашифрованного текста (y₀, y₁,..., y_n-1): y_i = p(x_i), 0 ≤ i < n