2.3. Шифрование с помощью аналитических преобразований Краткие теоретические сведения

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

.

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

Задание 5. Шифрование и расшифрование с помощью аналитических преобразований

1. Научитесь шифровать и расшифровывать тексты, используя аналитические преобразования.

Технология работы

1. Необходимо зашифровать слово СЕКРЕТ, используя в качестве ключа квадратную матрицу:

.

2. Заменим буквы алфавита цифрами, соответствующими их порядковому номеру в алфавите, начиная с нуля (А – 0, Б – 1, …, Я – 31). В этом случае слову СЕКРЕТ будет соответствовать следующая числовая последовательность 17, 5, 10, 16, 5, 18.

3. Разобьем эту последовательность на группы, число элементов в которых равно размерности матрицы ключа (в данном случае в каждую группу входит по три числа): (17, 5, 10) и (16, 5, 18).

4. Запустите программу MathCAD и выполните умножение матрицы ключа на полученные вектора в предыдущем пункте:

5. Зашифрованный текст будет выглядеть следующим образом: 281, 163, 62, 318, 189, 76.

6. Дешифрование осуществляется с использованием того же правила умножения матрицы на вектор, только в качестве основы берется матрица, обратная той, с помощью которой осуществлялось закрытие, а в качестве вектора-сомножителя – соответствующее количество символов шифртекста. Результатом будут цифровые эквиваленты знаков открытого текста. С помощью программы MathCAD вычислите обратную матрицу к ключевой:

.

7. С помощью программы MathCAD осуществите перемножение обратной ключевой матрицы на векторы шифртекста:

.

8. В результате получаем открытый текст 17, 5, 10, 16, 5, 18 в виде эквивалентной числовой последовательности кодов.

9. Самостоятельно с помощью указанной выше ключевой матрицы выполните шифрование и расшифрование слова КРИПТОЛОГИЯ – ЭТО КРИПТОГРАФИЯ И КРИПТОАНАЛИЗ.

2.4. Криптосистемы с открытым ключом Краткие теоретические сведения

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

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

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

• Алфавит А, в котором записывается сообщение (открытый текст), и алфавит В, в котором записывается шифртекст.

• Пространство ключей К (множество слов в некотором алфавите).

• Алгоритм генерирования ключей - полиномиальный вероятностный алгоритм, выдающий случайную пару (К,К)К: К - открытый ключ, используемый в шифровании, а К - секретный ключ, используемый для дешифрования.

• Полиномиальный детерминированный алгоритм шифрования Е, который получает на входе сообщение М и открытый ключ К, а выдает криптограмму С=Е_К(М).

• Полиномиальный детерминированный алгоритм дешифрования D, получающий на входе криптотекст С и секретный ключ К, и выдающий открытый текст М: М=D_К(С).

Криптосистемы с открытым ключом должны удовлетворять следующим условиям:

1. если пара ключей (К,К) порождена алгоритмом генерирования ключей, то из С=Е_К(М) вытекает М=D_К(С) для любого открытого текста М;

2. нет (или, по крайней мере, неизвестно) ни одного эффективного алгоритма, который по известным С=Е_К(М) и К мог бы найти М.

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

Центральным понятием «новой криптографии» является понятие односторонней функции.

Односторонняя функция F: XY – это функция, обладающая двумя свойствами:

• существует полиномиальный алгоритм вычисления значений y = F(x);

• не существует полиномиального алгоритма обратного вычисления значения x = F^-1(y).

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

Существование полиномиального алгоритма вычисления односторонней функции означает следующее. Пусть шифруемое (дешифруемое) сообщение включает n букв. Если время на шифрование (дешифрование) этого сообщения удовлетворяет неравенству t(n)  cn^c для некоторой константы с>0, то говорят, что алгоритм решает задачу шифрования (дешифрования) за полиномиальное время. Такие алгоритмы относятся к классу эффективных, так как реализуют решаемые задачи за реальное время.

Алгоритм, время реализации которого для некоторой константы с>0, называется экспоненциальным. Такой алгоритм является неэффективным, так как он не может быть реализован за разумное время. Примером такого алгоритма является полный перебор возможных ключей в задаче криптоанализа («лобовая атака»).

Еще одним новым понятием является понятие функции с «лазейкой».

Функция с «лазейкой» F_К: XY – это функция, зависящая от некоторого параметра К и обладающая свойствами:

• при любом К существует полиномиальный алгоритм вычисления значений y = F_К(x);

• при неизвестном К не существует полиномиального алгоритма обратного вычисления значения x = F_К^-1(y);

• при известном К существует полиномиальный алгоритм обратного вычисления значения x = F_К^-1(y).

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

Для практических целей криптографии было построено несколько функций, которые гипотетически считаются односторонними:

1) функция умножения: MULT(x, y) = xy, определенная на парах натуральных чисел x и y с одинаковым количеством значащих цифр;

2) RSA функция: RSA(x, e, m) = x^e mod m, e, m, определенная для произведения m = pq двух разных простых чисел и такого е, что НОД(е,(m)) = 1, xZ_m.

3) функция Рабина (квадратичная функция): SQUARE(x,m) = x² mod m, m, определенная для произведения m = pq двух разных простых чисел и xZ_m.

4) экспоненциальная функция: EXP(x, g, p) = g^x mod p, g, p, определенная для произвольного простого р, первичного корня g по модулю р и xZ_p^*.

В чем же заключаются преимущества новой криптографической схемы над классической? Рассмотрим коммуникационную сеть, которой пользуются n абонентов. Каждый из них хочет установить конфиденциальную связь с каждым. Если использовать классическую криптосистему, то потребуется n(n1)/2 ключей, которые должны быть переданы по такому же количеству закрытых каналов связи. В случае применения криптосистемы с открытым ключом каждый из абонентов самостоятельно генерирует свою пару ключей (K_i,K_i), i = 1, 2, ... n, причем только n ключей (K_i) поступают в общее пользование и при этом из них не делают секрета.

Применение функций с «лазейкой» в криптографии позволяет:

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

2. включить в задачу криптоанализа («взлома» шифра) трудную математическую задачу и тем самым повысить обоснованность стойкости шифра;

3. решать новые криптографические задачи, отличные от шифрования (цифровая подпись, распределение ключей и др.).

Рассмотрим некоторые алгоритмы криптосистем с открытым ключом, предложенные в последние годы.

Система RSA. Одной из наиболее популярных криптосистем с открытым ключом является система RSA, предложенная в 1977 г. Рональдом Райвеста, Ади Шамиром и Леонардом Адлеманом (название системы состоит из первых букв фамилий ее авторов).

1. Генерирование ключей:

• выбираются два достаточно больших простых числа p и q, и находится их произведение n=pq;

• находится функция Эйлера (n)=(p1)(q1)=npq+1;

• случайным образом выбирается число е, не превышающее (n) и являющееся взаимно простым с ним;

• с помощью алгоритма Эвклида для е находится число d, обратное к нему и такое, что d<(n) и ed  1 (mod (n));

• как результат полагают:

открытый ключ: e, n;

секретный ключ: d.

2. Шифрование осуществляется блоками. Для этого исходное сообщение кодируется в цифровом коде (обычно двоичном) и разбивается на блоки таким образом, чтобы каждый блок обозначал целое число, не превышающее n. Например, если блок записан в двоичном коде длины m, то должно выполняться неравенство 2^m<n.

Блок М шифруется путем возведения его в степень е:

C = E_e,n(M) = M^e mod n.

В результате получается блок криптотекста С той же длины, что и блок открытого текста М.

3. Дешифрование осуществляется также поблочно возведением криптотекста С в степень d (секретный ключ):

М = D_d(C) = C^d mod n.

4. Корректность. Возможность дешифрования криптотекста D_d(E_e,n(M)) = М вытекает из следующего доказанного утверждения: если n = pq является произведением двух простых числе и ed  1 (mod (n)), то для всех x  Z_n выполняется:

x^ed  x (mod n).

5. Эффективность. Алгоритм генерирования ключей использует процедуру нахождения простых чисел и расширенный алгоритм Эвклида для вычисления НОД(е,(n)) и d = e^-1 mod (n), которые являются полиномиальными, т.е. эффективными. В алгоритмах шифрования и дешифрования возведение в степень осуществляется с помощью бинарного метода, который также является эффективным.

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

Задано: e, n, y (перехваченный криптотекст), где n = pq и НОД(е,(n))=1.

Найти: х (открытый текст) такое, что х^е  y (mod n).

Таким образом, задача вскрытия RSA является задачей получения из заданного целого числа y корня е-ой степени по модулю n=pq. На сегодняшний день для этой задачи неизвестно ни одного эффективного алгоритма.

Можно попытаться вскрыть RSA путем определения секретного ключа d из открытого е:

Задано: e, n (открытый ключ), где n=pq и НОД(е,(n))=1.

Найти: d (секретный ключ) такой, что х^еd  x (mod n) для всех х.

Эта задача сводится к вычислению значения функции Эйлера (n), которая, в свою очередь, эквивалентна задаче нахождения сомножителей p и q числа n (так называемая задача факторизации). На сегодняшний день решить подобную задачу – безнадежное дело для n порядка 10²⁰⁰. Поэтому при генерировании ключей p и q рекомендуется выбирать приблизительно с сотней десятичных цифр каждое.