close

Вход

Забыли?

вход по аккаунту

?

Лаб2

код для вставкиСкачать
 МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
Учреждение образование "Белорусский государственный технологический университет"
Кафедра информационных систем и технологий Лабораторная работа № 2
по теме:
"Алгоритм шифрования RSA"
Выполнила:
студентка 5 курса,
9 группы
Иванашко О.В
Минск 2013
Содержание
Введение3
1. Теоретические сведения4
2. Постановка задачи и решение задачи6
Вывод9
Введение
RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) - криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел.
Криптосистема RSA стала первой системой, пригодной и для шифрования, и для цифровой подписи. Алгоритм используется в большом числе криптографических приложений, включая PGP, S/MIME, TLS/SSL, IPSEC/IKE и других.
1. Теоретические сведения
Первой реально действующей асимметричной схемой шифрования стал алгоритм RSA, разработанный тремя учеными-математиками: Рональдом Ривестом (Ronald Rivest), Ади Шамиром (Adi Shamir) и Леонардом Адльманом (Leonard Adleman), и названный по их именам. Они воспользовались тем фактом, что нахождение больших простых чисел в вычислительном отношении осуществляется легко, но разложение на множители произведения двух таких чисел практически невыполнимо. Доказано, что раскрытие шифра RSA эквивалентно такому разложению. Поэтому для любой длины ключа можно дать нижнюю оценку числа операций для раскрытия шифра, а с учетом производительности современных компьютеров возможно и оценить необходимое на это время.
Схема реализации алгоритма RSA приведена на рисунке ниже.
Процесс передачи-получения зашифрованного сообщения можно разделить на три этапа.
Первый этап - создание пары ключей - состоит из следующих действий.
1. Выбираются два больших простых числа p и q.
2. Вычисляется число n как n = pq.
3. Выбирается произвольное число e (e<n), такое, что наибольший общий делитель (НОД) пары чисел (e, (p -1)(q -1))=1, т.е. число e должно быть взаимно простым с числом (p -1)(q -1).
4. Методом Евклида решается в целых числах уравнение ed+(p-1)(q-1)y=1, где неизвестными являются переменные d и y1. 5. Пара чисел (e, n) публикуется в качестве открытого ключа. В свою очередь, число d хранится в секрете, так как это и есть секретный ключ, позволяющий читать все сообщения, зашифрованные с помощью пары чисел (e, n). Второй этап - шифрование открытым ключом. Отправитель разбивает свое сообщение на блоки, равные k = [log2n] бит, где квадратные скобки означают взятие целой части от возможного дробного числа. Такой блок интерпретируется как число из диапазона (0 ... 2k-1).
2. Для каждого такого числа (условно обозначаемого как mi) вычисляется выражение ci=((mi)e)modn. Блоки ci представляют собой зашифрованное сообщение. Их можно передавать по открытому каналу, поскольку операция возведения в степень простого числа и есть трудноразрешимая математическая задача.
Третий этап - дешифрование сообщения с помощью закрытого ключа.
Частный случай теоремы Эйлера утверждает, что если число n представляется в виде произведения двух простых чисел p и q, то для любого x выполняется равенство (x(p-1)(q-1)) modn =1.
Для дешифрования сообщений целесообразно воспользоваться приведенным соотношением. После возведения в степень (-y) обеих его частей соотношение выглядит следующим образом:
(x(-y)p-1)(q-1)) modn =1(-y)=1.
Умножение левой и правой частей этого равенства на x трансформирует его к виду:
(x(-y)p-1)(q-1)+1) mod n =1x= x.
Здесь необходимо вспомнить, как создавалась пара ключей (открытый и закрытый). Величина d была подобрана с помощью алгоритма Евклида так, что
ed+(p-1)(q-1)y=1,
то есть ed =1+(-y)(p-1)(q-1).
Тогда в выражении (x(-y)p-1)(q-1)+1) mod n =1x= x показатель степени можно заменить числом (ed), после чего получается:
(x(ed)) mod n = (x(-y)p-1)(q-1)+1) mod n =1x= x.
Таким образом, для прочтения сообщения ci=((mi)e) mod n достаточно возвести его в степень d по модулю n:
((ci)d) mod n = ((mi)(ed)) mod n = mi.
В итоге сообщение дешифровано.
2. Постановка задачи и решение задачи
В данной лабораторной работе требуется разработать программу для шифрования и дешифрования исходного сообщения методом шифрования RSA.Для выполнения работы использовался язык программирования С#. Пример работы программы представлен на рисунке 3.1.
Рисунок 3.1. Пример работы программы.
Для начала вводим сообщение. Генерируем случайные простые числа p и q. Находим модуль n как произведение этих чисел. Находим значение функции Эйлера f(n) как произведение без единицы p и q. Далее генерируем открытую экспоненту e таким образом, чтобы она была взаимнопростой со значением функции Эйлера. Вычисляем секретную экспоненту d, которое мультипликативно обратное к числу e по модулю f(n). Формируем публичный ключ, представленной парой (e, n) и тайный ключ (d, n). Далее зашифровываем сообщение по формуле Ci =memod n. Расшифровываем сообщение по формуле Mi =Cdmod n.
int[] pmas = new int[10000];
int tt = 0;
for (int i = 0; i < 1000; i++)
{
if (isPrime(i) == true)
{
pmas[tt] = i;
tt++;
}
}
string str = textBox1.Text;
Random rnd = new Random();
int gp = rnd.Next(0, tt);
p = pmas[gp];
label14.Text = Convert.ToString(p);
int gq = rnd.Next(0, tt);
q = pmas[gq];
label15.Text = Convert.ToString(q);
n = p * q;
w = raz(n);
label5.Text = Convert.ToString(w);
label6.Text = Convert.ToString(n);
fi = (p - 1) * (q - 1);
for(int i=0; i<tt;i++)
{
if (BigInteger.GreatestCommonDivisor(pmas[i], fi) == 1)
{ e1 = pmas[i]; break; }
}
label16.Text = Convert.ToString(e1);
label8.Text = Convert.ToString(fi);
d = Convert.ToInt32(Inverse((int)fi, (int)e1));
label10.Text = Convert.ToString(d);
label22.Text = "(" + e1 + "," + n + ")";
label23.Text = "(" + d + "," + n + ")";
chis = "";
for (int i = 0; i < str.Length; i++)
{
int ci = Convert.ToInt32(str[i]);
chis += Convert.ToString(ci).PadLeft(4, '0');
}
os1 = chis.Length % (w - 1);
int l = 0;
sh = new BigInteger[chis.Length];
for (int i = 0; i < chis.Length; i += (int)(w - 1))
{
string per = "";
for (int j = i; j < i + w - 1; j++)
{
if (j == chis.Length) { break; }
per += chis[j];
}
sh[l] = Convert.ToInt32(per);
l++;
}
if (os1 != 0)
{
string vor = Convert.ToString(sh[l - 1]);
vor.PadLeft((int)w - 1, '0');
sh[l - 1] = Convert.ToInt32(vor);
}
for (int i = 0; i < l; i++)
{
label18.Text += Convert.ToString(sh[i] + " ");
}
label17.Text = chis;
Random rd = new Random();
str1 = "";
for (int i = 0; i < l; i++)
{
BigInteger c = BigInteger.Pow(sh[i], e1);
BigInteger s;
if (c < n) { s = c; }
s = c % n;
label12.Text += s + "| ";
str1 += s;
BigInteger c1 = BigInteger.Pow(s, d);
BigInteger k = c1 % n;
str2 += Convert.ToString(k).PadLeft((int)w-1, '0');
label13.Text += k + "| ";
}
BigInteger os2 = str2.Length % 4;
l = 0;
for (int i = 0; i < str2.Length; i += 4)
{
string per = "";
for (int j = i; j < i + 4; j++)
{
if (j == str2.Length) { break; }
per += str2[j];
}
sh[l] = Convert.ToInt32(per);
l++;
}
if (os1 != 0)
{
string vor = Convert.ToString(sh[l - 1]);
vor.PadLeft(4, '0');
sh[l - 1] = Convert.ToInt32(vor);
}
for (int i = 0; i < l; i++)
{
char ii = (char)sh[i];
label19.Text += Convert.ToString(ii);} Вывод
В результате выполнения данной лабораторной работы была разработана программа, позволяющая зашифровывать и расшифровывать сообщение методом шифрования RSA.
Рисунок 1.1 - Схема реализации алгоритма RSA
---------------
------------------------------------------------------------
---------------
------------------------------------------------------------
Документ
Категория
Рефераты
Просмотров
77
Размер файла
228 Кб
Теги
лабораторная работа, лаб2, лаба, лабораторная
1/--страниц
Пожаловаться на содержимое документа