Материал: Залания2017

Глава 10. Криптографический практикум 415 .1. Задания для практических занятий

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

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

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

1.1. Открытое распределение ключей Тема: “Система открытого распределения ключей Диффи – Хеллмана”.

Теоретическая часть. В данной криптосистеме каждый абонент выбирает случайный секретный ключ x и вырабатывает открытый ключ y в соответствии с формулой

y = ^x (mod p).

Все абоненты размещают свои открытые ключи в общедоступном справочнике, который должен быть заверен специально созданным доверительным центром, чтобы исключить возможные нападения путем подмены открытых ключей или навязывания ложных открытых ключей. Если два абонента A и B хотят установить секретную связь, то они поступают следующим образом. Абонент A берет из справочника открытый ключ абонента B и, используя свой секретный ключ, вычисляет общий секретный ключ:

Z_AB = (y_B)^xA = (^xB)^xA = ^xBxA ₍mod p),

где y_A и y_B  открытые ключи абонентов A и B; x_A и x_B  соответствующие секретные ключи. Общий секретный ключ Z_AB нет необходимости передавать по сети связи, поскольку абонент B по известному из справочника открытому ключу абонента A аналогичным способом вычисляет значение

Z_AB = (y_A)^xB = (^xA)^xB = ^xBxA ₍mod p).

Предполагается, что оппоненту (потенциальному нарушителю) могут быть известны значения y_B = ^xB ₍mod p) и y_A = ^xA ₍mod p), передаваемые по открытому каналу, но для того чтобы вычислить Z_AB, он должен решить трудную задачу дискретного логарифмирования. Общий секрет Z_AB может использоваться абонентами для шифрования сеансовых секретных ключей, а последние  для шифрования сообщений с использованием симметричных методов шифрования.

Экспериментальная часть. Сформировать достаточно большое простое число p и параметр  -- примитивный элемент по модулю p. Для предполагаемых 10 пользователей выбраьт 10 значений секретного ключа x₁, x₂, …, x₁₀. Вычисляются соответствующие им открытые ключи y₁, y₂, …, y₁₀. Для всех возможных пар значений (i,j), где i = 1, 2, …, 10 и j = 1, 2, …, 10, вычисляется общий секретный ключ Z_ij. Полученные результаты оформляются в виде таблицы. Проверяется выполнение условия Z_ij = Z_ji.

Тема: “Открытое распределения ключей с использованием криптосистемы rsa”.

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

С = K ^d mod n.

Получатель расшифровывает сеансовый ключ с использованием своего секретного ключа:

K = C ^e mod n.

Однако получатель должен получить гарантии того, что расшифрованный ключ был действительно отправлен подлинным отправителем. Аутентификация источника сообщения требует использования открытого ключа отправителя, поэтому отправитель должен подписать посланную криптограмму по своему секретному ключу d: S = H ^d mod n, где H – хэш-функция от криптограммы C. Затем присоединить подпись S к отправляемому значению C. Если модуль отправителя n больше модуля получателя, то он может отправить только значение S = С ^d mod n, поскольку получатель, проверяя «подлинность» подписи в этом случае может восстановить значение C, а затем по своему секретному ключу расшифровать C и получить значение ключа. Однако окончательная подлинность отправителя будет установлена только после того как отправитель правильно зашифрует или расшифрует некоторое случайное пробное сообщение. Отправитель может подписать и хэш-функцию, полученную от от значения ключа. (Подпись, полученная непосредственно по значению ключа, фактически раскрывает ключ, поэтому в открытом виде пересылаться по каналам связи не должна.)

Экспериментальная часть. Используя заданные значения простых чисел p и q, вычислить модуль n, затем сформировать открытый и закрытый ключи e и d. Используя открытый ключ, зашифровать 10 различных ключей и, используя закрытый ключ, осуществить процедуру их расшифрования. Проверить корректность расшифрования. Результаты оформить в виде таблицы.

1.2. Открытое шифрование Тема: “Открытое шифрование Эль-Гамаля”.

Теоретическая часть. Способ открытого шифрования Эль-Гамаля включает в себя составной частью систему открытого распределения ключей Диффи-Хеллмана. Каждый пользователь секретной сети выбирает секретный ключ x, вычисляет свой открытый ключ y=^x и помещает y в заверенный справочник. Шифрование сообщения T, отправляемого пользователю i, осуществляется с помощью следующего алгоритма:

• выбрать случайное число k взаимно простое с числом p-1;

• вычислить R =^k (mod p), которое по своей сути является разовым открытым ключом;

• используя открытый ключ i-го пользователя вычислить

С =y^kT (mod p);

• отправить блок шифртекста (R,С) пользователю i.

Расшифрование осуществляется пользователем i по следующему алгоритму:

• вычислить значение (R)^x =(^k) ^x= ^kx (mod p), которое по своей сути является разовым общим секретом (Z_AB) получателя и отправителя;

• вычислить значение Z^-1 = (^kx)^-1 (mod p);

• расшифровать криптограмму С: T = СZ^-1 (mod p).

Экспериментальная часть. Сформировать достаточно большое простое число p и параметр  -- примитивный элемент по модулю p. Сгенерировать секретный ключ x. Используя заданные значения p и , вычисляется открытый ключ y. Используя открытый ключ осуществляется зашифрование 10 различных сообщений, фиксируя для каждого из них значения k, k^-1, R, С, Z, Z^-1. Проверяется правильность расшифрования сообщений. Полученные результаты оформляются в виде таблицы.

Тема: “Открытое шифрование по Рабину”.

Теоретическая часть.

В схеме открытого шифрования Рабина используется RSA модуль n = pq, в которомчисла p и q сравнимы с числом 3 по модулю 4: p = 3 mod 4 и q = 3 mod 4, что обеспечивает при знании разложения модуля (числа p и q являются секретным ключом) возможность выполнения операции извлечения квадратного корня из квадратичных вычетов по модулю n.

Открытым ключом является значение n, с помощью которого сообщение M < n зашифровывается путем возведении числа M в квадрат по модулю n:

c = M ² mod n.

Процедура расшифрования  состоит в извлечении квадратного корня из криптограммы c (очевидно, что она является квадратичным вычетом) по модулю n. Предварительно вычисляют корни c из по модулям p и q:

; ;

; .

Из этих четырех значений вычисляются четыре возможных корня из c по модулю n:

;

;

;

;

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

Экспериментальная часть. По указанию преподавателя обучающимся индивидуально задаются значения модуля n. Задание состоит в осуществлении зашифрования и расшифрования некоторой совокупности сообщений. Значения m_p1, m_p2, m_q1, m_q2, M₁, M₂, M₃ и M₄ записываются в таблицу результатов вычислений.

Тема: “Вычисление мультипликативно обратных элементов в поле вычетов”.

Теоретическая часть. Для вычисления обратных элементов в поле вычетов используется расширенный алгоритм Евклида. Известно, что если числа n и x являются взаимно простыми и x < n, то для x существует единственное значение x – такое, что x < n и xx = 1 (mod n). Это число называется мультипликативно обратным элементом в поле вычетов по модулю n и обозначается как x ^1  (mod n). Используя теорему Эйлера, можно записать

x^(n) 1x = x ^1x = 1  (mod n),

откуда получаем

x^(n) 1= x ^1  (mod n),

т.е. мультипликативно обратный элемент можно вычислить по значению функции Эйлера.

Экспериментальная часть. Выполняется вычисление мультипликативно обратных элементов для ряда чисел x_i , i = 1, 2, …10, для трех простых модулей p₁, p₂, p₃ и трех составных модулей n₁, n₂  и n₃. Вычисления выполняются двумя способами: 1) с использованием расширенного алгоритма Евклида и 2) с использованием формулы x^{(n)  1}= x^1  (mod n). Составляется сопоставительная таблица, показывающаяся идентичность результатов вычисления по двум способам.

1.3. Схемы эцп Тема: “Электронная цифровая подпись Эль-Гамаля”.

Теоретическая часть. Пусть для абонента A имеем секретный ключ x_A и открытый ключ y_A = ^xA. Подписью абонента A под документом M, где M < p служит пара чисел (r,s), где 0  r < p  1 и 0  s < p  1, которая удовлетворяет уравнению

^M = y_A^rr^s  (mod p).

Это уравнение проверки подписи абонента A. Данная система ЭЦП основана на том, что только действительный владелец секретного ключа a может выработать пару чисел (r, s), удовлетворяющую уравнению проверки подписи, по следующему алгоритму:

1. Сгенерировать случайное число k, удовлетворяющее условию: 0 < k < p  1 и НОД(k, p  1) = 1.

2. Вычислить r = ^k (mod p).

3. Вычислить s из уравнения M = x_Ar + ks  (mod (p  1)).

Из теории чисел известно, что последнее уравнение имеет решение для s, если НОД(k, p  1) = 1. Это уравнение легко получить путем подстановки в уравнение проверки подписи значения r = ^k  mod p:

^M = ^xAr^ks = y_A^rr^s  (mod p).

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

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

Экспериментальная часть. Используя заданные значения простого числа p и параметра , сформировать секретный ключ x_A, вычислить соответствующий ему открытый ключ y_A и вычислить значение электронной подписи для 10 различных сообщений, фиксируя получаемые значения параметров k, r = ^k, s, ^M, y_A^r, r^s, y_A^rr^s (mod p). Осуществить проверку подписи по открытому ключу. Результаты оформить в виде таблицы.