Изучить теоретические основы построения систем с открытым ключом (сок) и схемы распределения открытых ключей

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«УЛЬЯНОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра «Вычислительная техника»

Отчёт по лабораторной работе №3

«Использование систем шифрования с открытым ключом»

Вариант №9
Выполнил:

студент группы ИСТд-41

Корнеев А.В.

Проверил:

доцент каф. «Вычислительная техника»

к.т.н. Мартынов А.И.

Ульяновск, 2012 г.

Задание на лабораторную работу

Изучить теоретические основы построения систем с открытым ключом (СОК) и схемы распределения открытых ключей.
Изучить алгоритмы оптимизации наиболее сложных вычислительных аспектов СОК (тесты Рабина-Миллера и Лемана, алгоритм Евклида, расширенный алгоритм Евклида, алгоритмы ускоренного умножения в конечном поле).
Реализовать следующие функциональные блоки:
- Генератор ключей – модуль, предназначенный для генерации пары ключей (открытого и закрытого). Входные данные – левая граница диапазона, с которой начинается процесс поиска простых чисел. Выходные данные – файлы close_key.txt и open_key.txt, содержащие значения полученных ключей. Требования по функциональности: в процессе генерации ключей программа выдает информацию о состоянии процесса (Progress Bar или что-то подобное); пользователь должен иметь возможность прервать процесс генерации в любое время.
- Шифратор/Дешифратор – модуль, осуществляющий кодирование/декодирование текстовых файлов по схеме, указанной в Таблице 1 согласно варианту. Входные-выходные данные: файл close_key.txt или open_key.txt в зависимости от режима использования; файл pass.txt или pass.cod в зависимости от режима использования. Файл pass.txt содержит текстовый пароль, который необходимо зашифровать для последующего использования и записать в файл pass.cod. Файл pass. cod содержит зашифрованный текстовый пароль, который необходимо расшифровать для последующего использования и записать в файл pass.txt. Требования по функциональности: в процессе кодирования/декодирования программа выдает информацию о состоянии процесса (Progress Bar или что-то подобное); пользователь должен иметь возможность прервать процесс кодирования/декодирования в любое время; время обработки для текстового файла размером 10-30 символов не должно превышать 20 сек.
- Блочный шифр – берется из предыдущей лабораторной работы.
- Подсистему управления – модуль, обеспечивающий частичную автоматизацию следующего сценария (эти пункты отмечены звездочкой) разбитого на шесть этапов:
  1. Пользователь создает в текущей директории две папки Sender (имитация отправителя) и Recipient (имитация получателя), копирует в эти папки разработанную программу, а также исходные данные: в папку Sender – файл pass.txt и файл message.txt.
  2. *Запускает генератор ключей и распределяет ключи (файл close_key.txt кладет в папку Recipient, а файл open_key.txt в папку Sender).
  3. *Запускает шифратор в папке Sender, на вход которого подает файл с текстовым паролем pass.txt и файл open_key.txt и результат кодирования (файл pass.cod) сохраняет в папке и Recipient.
  4. *Запускает дешифратор в папке Recipient, на вход которого подает файл с закодированным паролем pass.cod и файл close_key.txt и результат декодирования (файл pass.txt) сохраняет в папке и Recipient.
  5. *Запускает программу блочного шифрования в режиме кодирования в папке Sender, на вход которой подается пароль (файл pass.txt) и исходное сообщение (message.txt). Результат кодирования (файл message.cod) сохраняет в папке Recipient.
  6. *Запускает программу блочного шифрования в режиме декодирования в папке Recipient, на вход которой подается пароль (файл pass.txt) и зашифрованное сообщение (message.cod). Результат декодирования (файл message.txt) сохраняет в папке Recipient.
  7. Пользователь сравнивает полученные результаты и если файлы message.txt в папках Recipient и Sender совпадают, то процесс кодирования считается успешно завершенным.

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

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

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

№ Этапа	Что добавляется в папку Sender	Что добавляется в папку Recipient
1	pass.txt, message.txt
2	open_key.txt	close_key.txt
3		pass.cod
4		pass.txt
5		message.cod
6		message.txt

Реализовать систему шифрования в соответствии с вариантами (RSA и тест Рабина-Миллера).

Тест Рабина-Миллера

Пусть — нечётное число большее 1. Число однозначно представляется в виде $m-1 = 2^s \cdot t$ , где нечётно. Целое число , , называется свидетелем простоты числа , если выполняются два условия:

не делится на ;
$a^t\equiv 1\pmod m$ или существует целое , $0\leq k<s$ , такое, что $a^{2^kt}\equiv -1\pmod m.$

Теорема Рабина утверждает, что составное нечётное число

имеет не более $\varphi(m)/4$ различных свидетелей простоты, где $\varphi(m)$ — функция Эйлера.

Алгоритм Миллера — Рабина параметризуется количеством раундов . Рекомендуется брать порядка величины $\log_2(m)$ , где — проверяемое число.

Для данного находятся такие целое число и целое нечётное число , что . Выбирается случайное число . Если не является свидетелем простоты числа , то выдается ответ « составное», и алгоритм завершается. Иначе, выбирается новое случайное число и процедура проверки повторяется. После нахождения свидетелей простоты, выдается ответ «, вероятно, простое», и алгоритм завершается.

Из теоремы Рабина следует, что если случайно выбранных чисел оказались свидетелями простоты числа , то вероятность того, что составное, не превосходит $4^{-r}$ .

Алгоритм RSA

Схема, разработанная Райвестом, Шамиром и Адлеманом, основана на выражениях со степенями. Открытый текст шифруется блоками, каждый из которых содержит двоичное значение, меньшее некоторого заданного числа п. Это значит, что длина блока должна быть меньше или равна log₂(n). На практике длина блока выбирается равной 2^к битам, где 2^k < п ^ 2^к+1. Шифрование и дешифрование для блока открытого текста M и блока шифрованного текста C можно представить в виде следующих формул:

C =M^e mod n,
M =C^d mod n = (M ^e)^d mod n = M^ed mod n.

Как отправитель, так и получатель должны знать значение n. Отправитель знает значение е, и только получателю известно значение d. Таким образом, данная схема является алгоритмом шифрования с открытым ключом KU = {е, n} и личным ключом KR = {d, n}. Чтобы этот алгоритм мог использоваться для шифрования с открытым ключом, должны быть выполнены следующие требования.

Должны существовать такие значения е, d и n, что M^ed = M mod n для всех M < n.
Должны относительно легко вычисляться M^e и C^d для всех значений M < n.
Должно быть практически невозможно определить d по имеющимся е и n.

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

M^ed = M mod n.

Здесь как нельзя лучше подойдет следствие теоремы Эйлера: для таких любых двух простых чисел p и q и таких любых двух целых чисел n и m, что n = pq и 0 < m < n, и произвольного целого числа к выполняются следующие соотношения:

M^k^ф(ⁿ⁾+¹ ≡ m^k⁽^p^-1)(^q^-1)+1 ≡ m mod n,

где Ф(n) является функцией Эйлера, значение которой равно числу положительных целых чисел, меньших n и взаимно простых с n. В случае простыхp и q имеем ф(pq) = (p— l)(q — 1). Поэтому требуемое отношение получается при условии

ed = kф(n) + 1.

Это эквивалентно следующим соотношениям:

ed ≡1 mod Ф(n),

d ≡ e^-1 mod Ф(n),

т.е. e и d являются взаимно обратными по модулю Ф(n). Обратим внимание, что в соответствии с правилами арифметики в классах вычетов это может иметь место только тогда, когда d (а следовательно, и е) является взаимно простым с Ф(n). В эквивалентной записи gcd(ф (n), d) = 1.

Теперь у нас есть все, чтобы представить схему RSA. Компонентами схемы являются:

p и q — два простых числа (секретные, выбираются),
n = pq (открытое, вычисляется),
такое е, что gcd^(n), е) = 1, 1 < е, Ф(n), (открытое, выбирается),
d ≡ е^-1 mod Ф(n) (секретное, вычисляется).

Личный ключ складывается из {d, n}, а открытый — из {е, n}. Предположим, что пользователь A опубликовал свой открытый ключ и теперь пользователь B собирается переслать ему сообщение M. Тогда пользователь B вычисляет C = M^e (mod n) и пересылает C. Получив этот шифрованный текст, пользователь A дешифрует его, вычисляя M = C^d(mod n). Имеет смысл привести здесь обоснование этого алгоритма. Мы выбрали е и d такие, что

d ≡ е^-1 mod Ф(n).

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

ed ≡ 1 mod Ф(n).

Значит, ed имеет вид kф(n) + 1. Но по следствию теоремы Эйлера, для таких любых двух простых чисел p и q и целых чисел n = pq и M, что 0 < M < n, выполняются соотношения

M^k^ф⁽ⁿ⁾⁺¹ = M ^k(p-1)(q-1)+¹ ≡ M mod n.

Поэтому M^ed = M mod n. Теперь мы имеем

C =M^e mod n,

M =C^d mod n = (M ^e)^d mod n = M^ed mod n ≡ M mod n.

Выводы

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

В криптографической системе с открытым ключом каждый участник располагает как открытым ключом (англ. public key), так и закрытым ключом (англ. private key). В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме RSA образуют «согласованную пару» в том смысле, что они являются взаимно обратными, то есть:

$\forall$ сообщения $m \in m$ , где  — множество допустимых сообщений

$\forall$ допустимых открытого и закрытого ключей  и

$\exist\,$ соответствующие функции шифрования  и расшифрования , такие что

Ассиметричное шифрование предназначено для шифрования небольшого объема данных, т.к оно очень ресурсоемко.
Листинг программы

Простые в реализации функции и код графического интерфейса опущен.

Класс RabinMiller: проверка числа на простоту.

public static class RabinMiller

{

public static bool[] prime;

static RabinMiller()

{

prime = new bool[2000];

for(int i = 0; i < prime.Length; prime[i++] = true);

for (int i = 2; i < 1000; ++i )

{

if (!prime[i]) continue;

for (int j = 2*i; j < prime.Length; j+=i)

{

prime[j] = false;

}

public static bool simpleTest(int n)

{

for (int i = 2; i < prime.Length; ++i)

{

if (prime[i] && ((n % i) == 0))

{

return false;

}

return true;

}
public static bool IsPrime(int n, int k)

{

if (n < 2) {

return false;

}

if (n != 2 && n % 2 == 0) {

return false;

}

if (!simpleTest(n)) return false;

int s = n - 1;

while (s % 2 == 0) {

s >>= 1;

}

Random r = new Random();

for (int i = 0; i < k; i++) {

double a = r.Next((int)n - 1) + 1;

int temp = s;

int mod = (int)Math.Pow(a, (double)temp) % n;

while (temp != n - 1 && mod != 1 && mod != n - 1) {

mod = (mod * mod) % n;

temp = temp * 2;

}

if (mod != n - 1 && temp % 2 == 0) {

return false;

}

return true;

}

Здесь отдельно хочется отметить статический конструктор, который единожды вычисляет простые число от 0 до 2000. Затем перед тестом Рабина-Миллера выполняется проверка на делимость на все простые числа от 0 до 2000. А затем запускается тест, алгоритм которого был подробно описан в первом разделе.

Класс RSA: функции ассиметричного шифрования.

class RSA

{

public void InitKeyData()

{

Random random = new Random();

this.p = getPrimeNumber(15);

this.q = getPrimeNumber(12);

this.n = (ulong)((ulong)this.p * (ulong)this.q);

this.phi = (ulong)((ulong)(p - 1) * (ulong)(q - 1));

List possibleE = GetAllPossibleE(this.phi);
do {

this.e = possibleE[random.Next(0, possibleE.Count)];

this.d = ExtendedEuclide(this.e % this.phi, this.phi).u1;

} while (this.d < 0);

}
public string encode(string text)

{

InitKeyData();

instr = text;

var outStr = "";

System.Text.UTF8Encoding enc = new System.Text.UTF8Encoding();

byte[] strBytes = enc.GetBytes(text);

foreach (byte value in strBytes) {

ulong encryptedValue = ModuloPow(value, this.e, this.n);

outStr += encryptedValue + "|";

}
return outStr;

}
public string decode(string text, string n_s, string d_s)

{

string outStr = "";

ulong n = ulong.Parse(n_s);

ulong d = ulong.Parse(d_s);

ulong[] arr = GetDecArrayFromText(text);

byte[] bytes = new byte[arr.Length];

System.Text.UTF8Encoding enc = new System.Text.UTF8Encoding();

int j = 0;

foreach (int i in arr) {

byte decryptedValue = (byte)ModuloPow((ulong)i, d, n);

bytes[j] = decryptedValue;

j++;
}

outStr += enc.GetString(bytes);

return outStr;

}
}

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

public static int getRandomNumber(int bits)

{

return (int) ( (rnd.Next() | 0x1 | (1 << bits)) & ((1 << (bits + 1)) - 1) );

}
public static ulong ModuloPow(ulong value, ulong pow, ulong modulo)

{

BigInteger result = value;

while (pow != 0) {

if ((pow & 1) == 1) {

result *= result;

--pow;

}

pow >>= 1;

result *= value;

result %= modulo;

}

return (ulong)result;

}
private static ExtendedEuclideanResult ExtendedEuclide(ulong a, ulong b)

{

ulong u1 = 1;

ulong u3 = a;

ulong v1 = 0;

ulong v3 = b;
while (v3 > 0) {

ulong q0 = u3 / v3;

ulong q1 = u3 % v3;
ulong tmp = v1 * q0;

ulong tn = u1 - tmp;

u1 = v1;

v1 = tn;
u3 = v3;

v3 = q1;

}
ulong tmp2 = u1 * (a);

tmp2 = u3 - (tmp2);

ulong res = tmp2 / (b);

return new ExtendedEuclideanResult() {

u1 = u1,

u2 = res,

gcd = u3

};

}