Алгоритм шифрования RSA

Размещено на http://www.allbest.ru/

ЗАДАНИЕ НА КУРСОВОЙ ПРОЕКТ

По курсу: Математические основы криптологии

Тема работы: Алгоритм шифрования RSA



Исходные данные

Построить таблицы Кэли для чисел p и q (p=13, q=31). Составить программу на языке программирования MatLab, которая вычисляет степенные последовательности для умножения по модулю n=p*q. Найти группы, подгруппы и факторгруппы. Реализовать алгоритм RSA.

Рекомендуемая литература

1) Ростовцев А.Г. Теоретическая криптография / А.Г. Ростовцев, Е.Б. Маховенко - НПО «Профессионал», Санкт-Петербург, 2004. - 479 с.

2) С.Б Гашков Криптогафические методы защиты информации / С.Б Гашков, З.А. Применко, М.А. Черепнев. - М.: Академия, 2010г.-304с.



Содержание

Введение

1. Модульная арифметика

2. Таблица Кэли

3. Теория групп

4. Алгоритм RSA

Заключение

Список использованных источников



Введение

RSA относится к так называемым асимметричным алгоритмам, у которых ключ шифрования не совпадает с ключом дешифровки. Один из ключей доступен всем (так делается специально) и называется открытым ключом, другой хранится только у его хозяина и неизвестен никому другому. С помощью одного ключа можно производить операции только в одну сторону. Если сообщение зашифровано с помощью одного ключа, то расшифровать его можно только с помощью другого. Имея один из ключей невозможно (очень сложно) найти другой ключ, если разрядность ключа высока. Криптосистема RSA разработана в 1977 году и названа в честь ее разработчиков Рональда Ривеста (Rivest), Ади Шамира (Shamir) и Леонарда Адлемана (Aldeman) [1].

Безопасность передачи данных в современных компьютерных сетях и по каналам связи является актуальной проблемой XXI века.

Целью курсового проекта является изучить алгоритм шифрования RSA.



1. Модульная арифметика

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

Модульная арифметика часто изучается в школе как "арифметика часов". Если отсчитать 14 часов от 3 часов после полудня, то получится 5 часов утра следующего дня:

Это арифметика по модулю 12.

Обычная запись в модульной арифметике

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

,

где - некоторое целое число

Если то называют вычетом числа по модулю .

Операцию , для нахождения вычета числа по модулю называют приведением числа по модулю или приведением по модулю.

В нашем примере или , число 5 является вычетом числа 17 по модулю 12.

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

где - целое число.

Например, для полный набор вычетов:

Модулярная арифметика аналогична во многом обычной арифметике: она коммутативна, ассоциативна и дистрибутивна. Точнее говоря, целые числа по модулю с использованием операций сложения и умножения образуют коммутативное кольцо при соблюдении законов ассоциативности, коммутативности и дистрибутивности [2].

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

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

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

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

Например, если нужно вычислить

Не следует применять примитивный подход с выполнением семи перемножений и одного приведения по модулю громадного числа:

Вместо этого выполняют три малых умножения и три малых приведения по модулю:

Тем же способом вычисляют

Вычисление



где не является степенью 2, лишь немного сложнее. Двоичная запись числа позволяет представить число как сумму степеней 2:

или , поэтому 25 = 2⁴+ 2³ + 2⁰

Тогда

При разумном накоплении промежуточных результатов потребуется только шесть умножений:

Этот метод уменьшает трудоемкость вычислений до операций в среднем, где - длина числа в битах.

Поскольку многие алгоритмы шифрования основаны на возведении в степень по модулю n, целесообразно использовать алгоритмы быстрого возведения в степень [3].



2. Таблица Кэли

Таблица Кэли -- в общей алгебре, таблица, которая описывает структуру конечных алгебраических систем с одной бинарной операцией. Названа в честь английского математика Артура Кэли. Имеет важное значение в дискретной математике, в частности, в теории групп, в которой в качестве операций рассматриваются умножение и сложение. Таблица позволяет определить, является ли группа абелевой, найти центр группы и обратные элементы по отношению к другим элементам в этой группе [4].

В высшей алгебре таблицы Кэли могут также использоваться для определения бинарных операций в полях, кольцах и других алгебраических структурах. Также они удобны при проведении действий в данных структурах[4]

Рассмотрим программу для построения таблицы Кэли в пакете прикладных программ для решения задач технических вычислений MATLAB для 7 элементов.

k=7, n=0; m=magic(k); %высчитываем элементы матрицы

for i=1:k

for j=1:k

m(i,j)=mod(((i-1)*(j-1)),k);

end

% удаляем нулевые столбцы и строки

m(1,:)=[];

m(:,1)=[];

% проверяем мультипликативная или не мультипликативная группа

for i=1:k-1

for j=1:k-1

if m(i,j)==1

n=n+1;

end

end

disp(m)

if n==k-1 disp ('Мультипликативная группа')

else disp('Не мультипликативная группа')

end

С помощью функции m=magic(k) формируем специальную квадратную матрицу порядка k, элементами которой являются целые числа, суммы элементов которой по строкам и столбцам равны.

В первом цикле высчитываем элементы матрицы от 1 до k по модулю k. Но цикл задаем от i-1 до k, так как нужно элементы таблицы брать от 0. Далее удаляем полученные нулевые строки и столбцы.

Во втором цикле проверяем мультипликативная или не мультипликативная группа. Для этого проверяем каждую строку на наличие 1 и считаем их количество. Если количество полученных 1 равно количеству строк, т.е. k-1, так как мы удалили одну нулевую строку, то группа элементов является мультипликативной, иначе не является мультипликативной группой.

Результат программы

k=7

1 2 3 4 5 6

2 4 6 1 3 5

3 6 2 5 1 4

4 1 5 2 6 3

5 3 1 6 4 2

6 5 4 3 2 1

Мультипликативная группа



3. Теория групп

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

- Замкнутость по умножению: для любых, выполняется .

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

- Для любого существует обратный элемент такой, что

Группа называется абелевой, или коммутативной, если операция умножения коммутативна .

В определении групп операция (умножение, для мультипликативных групп) не конкретизируется. Групповой операцией может служить и сложение, например, сложение целых чисел. Если операция называется сложением, то группа является аддитивной. В этом случае единичный элемент называется нулем, а вместо обратного элемента используется противоположный элемент . Аддитивная абелева группа называется модулем [5].

Группа обладает следующими свойствами.

- Уравнение и в группе G всегда имеют единственные решения, а именно и . Поэтому последние два условия можно заменить условием однозначной разрешимости уравнений и . Для доказательства достаточно подставить эти решения в уравнения:



- Предположим, что есть два решения и уравнения . Умножив равенства и слева на , получим отсюда

- Однозначность деления. Если то , если , то Для доказательства умножим равенства ax=ay слева на , равенство справа на . Получим , следовательно, Во втором случае получим .

- В группе существует единственный единичный элемент. Доказательство следует из единственного решения уравнения .

- Каждый элемент группы имеет единственный обратный элемент. Доказательство следует из единственного решения уравнения

- Обращение произведения: Для доказательства достаточно умножить обе части равенства справа или слева на [6].

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

Если рассматриваемое множество замкнуто по отношению к операции умножения и каждое из уравнений имеет единственное решение при любых a, b, то это множество называется квазигруппой [5].

Признак подгруппы:

Непустое подмножество в группе будет подгруппой этой группы тогда и только тогда, когда:

Например, целые числа с операцией сложения образуют подгруппу в группе , которая, в свою очередь является подгруппой группы [5]. Пусть некоторый фиксированный элемент группы , а - любая ее подгруппа.

Множество называется левым, а - правым смежным классом группы по подгруппе.

Например, очевидно, что , так что подгруппа Н сама является одним из смежных классов.

Свойства смежных классов.

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

- Каждый элемент входит в смежный класс .

- Если y входит в смежный класс , то

- Если y не входит в смежный класс , то [7]

Рассмотрим программу в MATLAB для нахождения циклической группы, подгруппы, смежных классов и факторгруппы:

a=11

p=13

q=31

n=p*q

u=0;

h=0;

v=0;

t=1;

m=0;

w=0;

z=0;

g=0;

x=0;

xx=0;

c=0;

Вычисляем элементы множества while m~=1 u=u+1; %

Считаем количество элементов множества m(u)=mod(t*a,n); % полученное число t=m(u); if u==500 %

Цикл длится до 500 элементов, иначе выходит

break;

end

end

m %

Выводим полученное множество чисел на экран %

Перемножаем элементы множества для выяснения является ли группа циклической for i=1:u

for j=1:u

if i~=j

s(i,j)=mod(m(i)*m(j),n);

h=h+1; % считает количество полученных элементов

end

end

end

%

Проверяем является ли множество циклической группой for i=1:u

for j=1:u

for l=1:u

if s(i,j)==m(l);

v=v+1; % считаем совпадения

end

end

end

end

if h==v

disp('Множество является циклической группой')

else

disp ('Множество не является циклической группой')

end

%

Ищем подгруппу

e=6; %

Порядковый номер элемента для которого берется подгруппа

while z~=1

w=w+1; %

Считаем количество элементов множества

z(w)=mod(t*m(e),n);

t=z(w);

if w==500

break;

end

end

disp ('Подгруппа');

z

%

Смежный класс

for i=1:e-1

for j=1:w

g(i,j)=mod(m(i)*z(j),n);

end

end

disp('Cмежные классы')

g

%

Фактор группа

for i=1:w

x(i)=g(2,i); %

Берем любой смежный класс

for j=1:w

xx(i,j)=mod(z(j)*x(i),n);

end

if xx(i,j)==x(i)

c=c+1; %

считаем количество совпадений

end

end

if c==w

disp('Подгруппа и смежный класс образуют фактор группу')

end

Задаем простые числа p и q. Вычисляем n. Зануляем переменные, использующиеся в программе.

В первом цикле вычисляем элементы множества m, возводя число a в степень по модулю n до тех пор, пока не появится единица. Для легкости вычисления присваиваем полученное число и далее его умножаем на число a. Цикл длится до 500 элементов.

Во втором цикле для выяснения является ли множество циклическим, перемножаем каждый элемент множества на элементы из этого же множества и считаем количество полученных элементов.

В третьем цикле проверяем, является ли множество циклической группой, для этого полученные элементы сравниваем с элементами начального множества и считаем их совпадения. Если количество полученных элементов равно совпадениям, то множество является циклической группой, иначе не является циклической группой.

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

В пятом цикле ищем смежные классы g. Умножаем элементы подгруппы на элементы циклической группы.

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

Результат программы:

a = 11

p = 13

q = 31

n = 403

m = Columns 1 through 23

11 121 122 133 254 376 106 360 333 36 396 326 362 355 278 237 189 64 301 87 151 49 136

Columns 24 through 46

287 336 69 356 289 358 311 197 152 60 257 6 66 323 329 395 315 241 233 145 386 216 361

Columns 47 through 60

344 157 115 56 213 328 384 194 119 100 294 10 110 1

Множество является циклической группой

Подгруппа

z = 376 326 64 287 311 66 233 157 194 1

Смежные классы

g₁= 106 362 301 336 197 323 145 115 119 11

g₂= 360 355 87 69 152 329 386 56 100 121

g₃= 333 278 151 356 60 395 216 213 294 122

g₄= 36 237 49 289 257 315 361 328 10 133

g₅= 396 189 136 358 6 241 344 384 110 254

Подгруппа и смежный класс образуют фактор группу

4. Алгоритм RSA

RSA - ключи генерируются следующим образом.

- Выбираются два различных случайных простых числа p и q.

- Вычисляется их произведение n=p*q, которое называется модулем.

- Вычисляется значение функции Эйлера от числа n:

- Выберем случайное число, которое назовем (закрытая экспонента). Это число должно быть взаимно простым (не иметь общего делителя, кроме ) с результатом .

- Определим такое число (открытая экспонента) для которого является истинным следующее соотношение:

(.

Слишком малые значения e, например 3, потенциально могут ослабить безопасность схемы RSA.

- Пара {e, n} публикуется в качестве открытого ключа.

- Пара {d, n} играет роль закрытого ключа и держится в секрете [8].

Следующий пример наглядно демонстрирует алгоритм шифрования RSA, зашифруем и расшифруем сообщение "ИРГТУ".

- Выберем .

- Определим

- Найдём .

- Следовательно, будет равно, например,

- Выберем число по следующей формуле (,

( Значит е будет равно, например, .

- открытый ключ и {103,403} закрытый ключ.

- Представим шифруемое сообщение как последовательность чисел в диапазоне от 0 до 402 (кончается на n-1). Буква И=6, Р=2, Г=3, Т=4, У=5.

- Теперь зашифруем сообщение, используя открытый ключ

Теперь расшифруем данные, используя закрытый ключ {103,403}.

Данные расшифрованы.



Заключение

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



Список использованных источников

асимметричный алгоритм шифр бинарный

1. Венбо Мао. Современная криптография. Теория и практика / Венбо Мао. - М.: Вильямс, 2005. - 768 с.

2. Черемушкин А.В. Лекции по арифметическим алгоритмам в криптографии / А.В. Черемушкин-- М.: МЦНМО, 2003. - 670 с.

3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест - М.: МЦНМО, 1999. - 511 с.

4. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си/ Б. Шнайер - М.: Триумф, 2002. - 816 с.

5. Ростовцев А.Г. Теоретическая криптография / А.Г. Ростовцев, Е.Б. Маховенко - НПО «Профессионал», Санкт-Петербург, 2004. - 479 с.

6. Курош А.Г. Теория групп / А. Г. Курош - М.: Наука, 1967. - 648 с.

7. Каргаполов М.И. Основы теории групп / М.И. Каргаполов, Ю.И. Мерзляков - "Наука", 1972. - 445с.

8. Менез А. Руководство по практической криптографии / А. Менез, С. Ванстон. - М.: Диалектика 1996. - 816 с.

9. Фергюсон Н. Практическая криптография / Н. Фергюсон, Б. Шнайер. - М.: Диалектика, 2004. - 432 с.

10. Виноградов И.М. Основы теории чисел / И. М. Виноградов - М.: Гос. изд. технико-теоретической литературы, 1992. -180 с.

11. Гашков С.Б. Криптогафические методы защиты информации / С.Б Гашков, З.А. Применко, М.А. Черепнев. - М.: Академия, 2010г.-304с.

Размещено на Allbest.ru

...