Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Лабораторная работа 3 / Защита_информации_3

.doc
Скачиваний:
45
Добавлен:
01.05.2014
Размер:
226.3 Кб
Скачать

Министерство образования и науки РФ

Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»

кафедра математического обеспечения ЭВМ

Отчет

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

«Асимметричное шифрование»

по дисциплине «Методы и средства защиты компьютерной информации»

Выполнили: студенты гр 3341 Рыжок М.С. Гвоздякова Е.И.

Проверил: доцент кафедры МО ЭВМ Горячев Г.А.

Санкт-Петербург 2008-05-05

Лабораторная работа №3

Асимметричное шифрование

Цель работы: Ознакомление с асимметричными криптографическими шифрами на основе алгоритма RSA.

Задание: Разработка и программная реализация алгоритма шифрования RSA

Схема алгоритма : Первый этап любого асимметричного алгоритма – создание пары ключей – состоит для схемы RSA из следующих операций.

1. Выбираются два больших простых числа р и q (простым называется число, делящееся на единицу и на само себя).

2. Вычисляется n, равное (p  q).

3. Выбирается произвольное число e (e < n), такое, что наибольший общий делитель НОД (e, (p-1)  (q-1)) = 1, т. е. должно быть взаимно простым с числом

(p-1)  (q-1).

4. Методом Евклида решается в целых числах уравнение e  d + (p-1)  (q-1)  y = 1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d, y), каждая из которых является решением уравнения в целых числах.

5. Пара чисел (e, n) – публикуется как открытый ключ. Число d хранится в строжайшем секрете – это и есть закрытый ключ, который позволит читать исе послания, зашифрованные с помощью пары ключей (e, n).

Второй этап – собственно шифрование с помощью открытого ключа.

1. Отправитель разбивает свое сообщение на блоки, равные k = [log2 (n)] , где квадратные обозначают взятие целой части от дробного числа. Подобный блок может быть интерпретирован как число из диапазона (0 : 2k – 1).

2. Для каждого такого числа (назовем его mi) вычисляется выражение ci = ((mi)e) mod n. Блоки ci и есть зашифрованное сообщение. Их можно без опасения передавать по открытому каналу, поскольку операция возведения в степень по модулю простого числа является трудноразрешимой математической задачей.

Третий этап – дешифрование послания с помощью секретного ключа. Частный случай теоремы Эйлера утверждает, что если число n может быть представлено в виде произведения двух простых чисел p и q, то для любого х имеет место равенство:

(р-1) (q-1)) mod n = 1.

Для дешифрования RSA – сообщений воспользуемся этой формулой. Возведем обе ее части в степень (-y): ((х(-y) (р-1) (q-1)) mod n = 1(-y) = x. После умножения обеих частей равенства на х получим

(-y) (р-1) (q-1)) mod n = 1  = х.

Далее вернемся к созданию открытого и закрытого ключей. Величина d была подобрана с помощью алгоритма Евклида так, что e d + (p-1)  (q-1)  y = 1, т. е.

e  d = 1 + (-y)  (p-1)  (q-1). Следовательно, в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e  d). Получаем

(x(e d)) mod n = (x (-y) (р-1) (q-1)+1) mod = mi

Контрольный пример : Если p = 47 и q = 71, то n = pq = 3337

Ключ е не должен иметь общих множителей с (p-1)*(q-1) = 3220. Выберем (случайно ) е равным 79. В этом случае d = e-1mod((p-1)*(q-1)) = 1019

Опубликуем e и n, оставив d в секрете. Отбросим p и q. Для шифрования сообщения сначала разделим его на маленькие блоки

Например m = 688232687966668003 разбивается как

m1 = 688

m2 = 232

m3 = 687

m4 = 966

m5 = 668

m6 = 003

Первый блок шифруется как 68879 mod 3337 = 1570 = c1

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

С = 1570 2756 2091 2276 2423 158

Для дешифрования нужно выполнить такое же возведение в степень, используя ключ дешифрования 1019

15701019 mod 3337 = 688 = m1

Аналогично восстанавливается остальная часть сообщения

Реализация алгоритма: при выполнении лабораторной работы с помощью пакета инженерных вычислений MATLAB 7.5.0 было создано приложение с графическим интерфейсом, позволяющее пользователю зашифровать любое текстовое сообщение, загруженным из файла ‘text.txt’. Ключ шифрования генерируется нажатием кнопки KeyGen Интерфейс приложения представлен на рисунке 2.

Результат шифрования/дешифрования сохраняется в файле out.txt

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

1. Открытый текст: 324 354 641 427 111 541 467 242 141

Ключ N = 6493, E = 1079

Шифротекст: 5384 6166 5156 5486 3050 3007 1942 3596 5103

2. Открытый текст: 324 354 641 427 111 541 467 242 141

Ключ N = 8093 E= 2717

Шифротекст: 4587 2935 3570 2080 952 7211 5085 3679

Ответы на контрольные вопросы:

1. Какая процедура является более производительной – асимметричное шифрование/ дешифрование или симметричное шифрование/дешифрование?

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

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

  2. Какая трудноразрешимая математическая задача лежит в основе стойкости алгоритма RSA? Ответ : В основе RSA положена проблема разложения числа на простые множители. Пока что не найдено алгоритмов, решающих ее за полиномиальное время

  3. Какая трудноразрешимая математическая задача лежит в основе стойкости алгоритма Эль Гамаль? Ответ: В основе стойкости алгоритма Эль Гамаля лежит проблема нахождения дискретного логарифма в конечном поле.

  4. В чем заключается проблема дискретного логарифма? Ответ: невозможно кроме как перебором определить показатель x такой, что ax = m(mod n)

  5. В чем заключаются проблемы разложения больших чисел на простые множители и вычисления корней алгебраических уравнений? Ответ: Невозможно кроме как перебором разложить число на простые множители. Невозможно непосредственно вычислить корни алгебраического уравнения в конечном поле

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

Приложение 1

Текст программы на языке среды инженерных разработок MATLAB

function varargout = RSA(varargin)

% RSA M-file for RSA.fig

% RSA, by itself, creates a new RSA or raises the existing

% singleton*.

%

% H = RSA returns the handle to a new RSA or the handle to

% the existing singleton*.

%

% RSA('CALLBACK',hObject,eventData,handles,...) calls the local

% function named CALLBACK in RSA.M with the given input arguments.

%

% RSA('Property','Value',...) creates a new RSA or raises the

% existing singleton*. Starting from the left, property value pairs are

% applied to the GUI before RSA_OpeningFcn gets called. An

% unrecognized property name or invalid value makes property application

% stop. All inputs are passed to RSA_OpeningFcn via varargin.

%

% *See GUI Options on GUIDE's Tools menu. Choose "GUI allows only one

% instance to run (singleton)".

%

% See also: GUIDE, GUIDATA, GUIHANDLES

% Edit the above text to modify the response to help RSA

% Last Modified by GUIDE v2.5 06-May-2008 12:12:22

% Begin initialization code - DO NOT EDIT

gui_Singleton = 1;

gui_State = struct('gui_Name', mfilename, ...

'gui_Singleton', gui_Singleton, ...

'gui_OpeningFcn', @RSA_OpeningFcn, ...

'gui_OutputFcn', @RSA_OutputFcn, ...

'gui_LayoutFcn', [] , ...

'gui_Callback', []);

if nargin && ischar(varargin{1})

gui_State.gui_Callback = str2func(varargin{1});

end

if nargout

[varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:});

else

gui_mainfcn(gui_State, varargin{:});

end

% End initialization code - DO NOT EDIT

% --- Executes just before RSA is made visible.

function RSA_OpeningFcn(hObject, eventdata, handles, varargin)

% This function has no output args, see OutputFcn.

% hObject handle to figure

% eventdata reserved - to be defined in a future version of MATLAB

% handles structure with handles and user data (see GUIDATA)

% varargin command line arguments to RSA (see VARARGIN)

% Choose default command line output for RSA

handles.output = hObject;

set(handles.loadbutton, 'Enable', 'off');

set(handles.encryptbutton, 'Enable', 'off');

set(handles.loadbutton, 'Enable', 'off');

set(handles.decryptbutton, 'Enable', 'off');

% Update handles structure

guidata(hObject, handles);

% UIWAIT makes RSA wait for user response (see UIRESUME)

% uiwait(handles.figure1);

% --- Outputs from this function are returned to the command line.

function varargout = RSA_OutputFcn(hObject, eventdata, handles)

% varargout cell array for returning output args (see VARARGOUT);

% hObject handle to figure

% eventdata reserved - to be defined in a future version of MATLAB

% handles structure with handles and user data (see GUIDATA)

% Get default command line output from handles structure

varargout{1} = handles.output;

% --- Executes on button press in keygenbutton.

function keygenbutton_Callback(hObject, eventdata, handles)

K = keygenerate();

textstring = strvcat(['N = ', num2str(K.basic)], ['E = ', num2str(K.open)]);

handles.basic = K.basic;

handles.open = K.open;

handles.close = K.close;

set(handles.keytext, 'String', textstring);

set(handles.loadbutton, 'Enable', 'on');

set(handles.encryptbutton, 'Enable', 'off');

set(handles.decryptbutton, 'Enable', 'off');

set(handles.opentext, 'String', '');

set(handles.cyphertext, 'String', '');

set(handles.decrypttext, 'String', '');

guidata(hObject, handles);

% hObject handle to keygenbutton (see GCBO)

% eventdata reserved - to be defined in a future version of MATLAB

% handles structure with handles and user data (see GUIDATA)

% --- Executes on button press in loadbutton.

function loadbutton_Callback(hObject, eventdata, handles)

k = fopen('in.txt');

data = fscanf(k, '%3d');

fclose(k);

textstring = num2str(data');

handles.Data = data';

set(handles.opentext, 'String', textstring);

set(handles.encryptbutton, 'Enable', 'on');

set(handles.decryptbutton, 'Enable', 'off');

set(handles.cyphertext, 'String', '');

set(handles.decrypttext, 'String', '');

guidata(hObject, handles);

% hObject handle to loadbutton (see GCBO)

% eventdata reserved - to be defined in a future version of MATLAB

% handles structure with handles and user data (see GUIDATA)

% --- Executes on button press in encryptbutton.

function encryptbutton_Callback(hObject, eventdata, handles)

Data = handles.Data;

Cypher = zeros(1, length(Data));

Uncypher = zeros(1, length(Data));

n = handles.basic;

e = handles.open;

for i = 1:length(Data)

Cypher(i) = quickpower(Data(i), e, n);

end

handles.cypher = Cypher;

set(handles.cyphertext, 'String', num2str(Cypher));

set(handles.decryptbutton, 'Enable', 'on');

set(handles.decrypttext, 'String', '');

guidata(hObject, handles);

% hObject handle to encryptbutton (see GCBO)

% eventdata reserved - to be defined in a future version of MATLAB

% handles structure with handles and user data (see GUIDATA)

% --- Executes on button press in decryptbutton.

function decryptbutton_Callback(hObject, eventdata, handles)

f = handles.close;

n = handles.basic;

Cypher = handles.cypher;

Uncypher = zeros(1, length(Cypher));

for i = 1:length(Cypher)

Uncypher(i) = quickpower(Cypher(i), f, n);

end

set(handles.decrypttext, 'String', num2str(Uncypher));

% hObject handle to decryptbutton (see GCBO)

% eventdata reserved - to be defined in a future version of MATLAB

% handles structure with handles and user data (see GUIDATA)