Лабораторная работа 3 / Защита_информации_3
.docМинистерство образования и науки РФ
Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»
кафедра математического обеспечения ЭВМ
Отчет
по лабораторной работе №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 раз, т.к все алгоритмы асимметричного шифрования используют медленные операции возведения в степень по модулю, нахождение обратных элементов и.т.п.
-
К какому типу криптоалгоритма (с точки зрения его устойчивости к взлому) и почему относится алгоритм RSA? Ответ : шифр RSA обладает практической стойкостью, т.к при его взломе методом полного перебора ключей требуется неоправданно большое количество времени и вычислительных ресурсов, тем не менее существует вероятность нахождения ключа за конечное время.
-
Какая трудноразрешимая математическая задача лежит в основе стойкости алгоритма RSA? Ответ : В основе RSA положена проблема разложения числа на простые множители. Пока что не найдено алгоритмов, решающих ее за полиномиальное время
-
Какая трудноразрешимая математическая задача лежит в основе стойкости алгоритма Эль Гамаль? Ответ: В основе стойкости алгоритма Эль Гамаля лежит проблема нахождения дискретного логарифма в конечном поле.
-
В чем заключается проблема дискретного логарифма? Ответ: невозможно кроме как перебором определить показатель x такой, что ax = m(mod n)
-
В чем заключаются проблемы разложения больших чисел на простые множители и вычисления корней алгебраических уравнений? Ответ: Невозможно кроме как перебором разложить число на простые множители. Невозможно непосредственно вычислить корни алгебраического уравнения в конечном поле
Выводы: при выполнении лабораторной работы были получены навыки в использовании асимметричных шифров.
Приложение 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)