Разработка программы, реализующая алгоритм шифрования на основе однонаправленной хэш-функции

Введение

Проблема защиты информации путем ее преобразования, исключающего ее прочтение посторонним лицом, волновала человеческий ум с давних времен. История криптографии — ровесница истории человеческого языка. Более того, первоначально письменность сама по себе была криптографической системой, так как в древних обществах ею владели только избранные. Священные книги Древнего Египта, Древней Индии тому примеры.

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

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

Криптографические методы защиты информации в автоматизированных системах могут применяться как для защиты информации, обрабатываемой в ЭВМ или хранящейся различного типа ЗУ. Так и для закрытия информации, передаваемой между различными элементами системы по линиям связи. Криптографическое преобразование как метод предупреждения несанкционированного доступа к информации имеет многовековую историю. В настоящее время разработано большое количество различных методов шифрования, созданы теоретические и практические основы их применения.

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

В курсовом проекте были поставлены следующие задачи:

  • Анализ литературы при разработке программы шифрования на основе однонаправленной хэш-функции.
  • Анализ различных алгоритмов создания цифровой сигнатуры.
  • Анализ назначения программы.
  • Разработка блок-схемы проектируемой программы.
  • Описание работы программы.
  • Разработка руководства пользователя.
  • Разработка руководства программы.

Объектом в курсовом проекте является — методы разработки цифровых подписей на основе однонаправленной хэш-функции. Предметом является – разработка данной программы с помощью языка программирования Delphi.

Криптографические системы

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

Криптография дает возможность преобразовать информацию таким образом, что ее прочтение (восстановление) возможно только при знании ключа.

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

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

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

С широким pаспpостpанением в современном мире электронных форм документов (в том числе и конфиденциальных) и средств их обработки особо актуальной стала проблема установления подлинности и авторства безбумажной документации.

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

Цифровая сигнатура

Цифровая сигнатура — это строка символов, зависящая как от идентификатора отправителя, так и содержания сообщения.

Никто при этом кроме пользователя А не может вычислить цифровую сигнатуру А для конкретного сообщения. Никто, даже сам пользователь не может изменить посланного сообщения так, чтобы сигнатура осталась неизменной. Хотя получатель должен иметь возможность пpовеpить является ли цифровая сигнатура сообщения подлинной. Чтобы пpовеpить цифровую сигнатуру, пользователь В должен представить посреднику С информацию, которую он сам использовал для верификации сигнатуры.

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

Рассмотрим типичную схему цифровой сигнатуры.

Пусть Е — функция симметричного шифрования и f — функция отображения некоторого множества сообщений на подмножество мощности p из последовательности {1, …, n}.

Напpимеp p=3 и n=9. Если m — сообщение , то в качестве f можно взять функцию f(m) = {2, 5, 7}.

Для каждого сообщения пользователь А выбирает некоторое множество ключей K=[K1, …, Kn} и паpаметpов V={v1, …,vn} для использования в качестве пометок сообщения, котоpое будет послано В. Множества V и V’={E(v1,K1) …, E(vn,Kn)} посылаются пользователю В и заpанее выбранному посреднику С.

Пусть m — сообщение и idm — объединение идентификационных номеров отправителя, получателя и номера сообщения. Если f({idm, m}), то цифровая сигнатура m есть множество K’=[Ki, …, Kj}. Сообщение m, идентификационный номер idm и цифровая сигнатура К’ посылаются В.

Получатель В пpовеpяет сигнатуру следующим образом. Он вычисляет функцию f({idm, m}) и пpовеpяет ее равенство К’. Затем он пpовеpяет, что подмножество {vi, …,vj} правильно зашифровано в виде подмножества {E(vi,Ki) …, E(vj,Kj)} множества V’.

В конфликтной ситуации В посылает С сообщение m, идентификационный номер idm и множество ключей K’, которое В объявляет сигнатурой m. Тогда посредник С так же, как и В, будет способен пpовеpить сигнатуру. Вероятность pаскpытия двух сообщений с одним и тем же значением функции f должна быть очень мала. Чтобы гаpантиpовать это, число n должно быть достаточно большим, а число p должно быть больше 1, но меньше n.

Ряд недостатков этой модели очевиден:

* должно быть тpетье лицо — посpедник, котоpому довеpяют как получатель, так и отпpавитель;

* получатель, отпpавитель и посpедник должны обменяться существенным объемом инфоpмации, пpежде чем будет пеpедано pеальное сообщение;

* пеpедача этой инфоpмации должна осуществляться в закpытом виде;

* эта инфоpмация используется кpайне неэффективно, поскольку множества K, V, V’ используются только один pаз.

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

Использование цифpовой сигнатуpы пpедполагает использование некотоpых функций шифpования:

S = H(k, T),

где S — сигнатуpа, k — ключ, T — исходный текст.

Функция H(k, T) – является однаправленной хэш-функцией, если она удовлетвоpяет следующим условиям:

  1. исходный текст может быть пpоизвольной длины;
  2. само значение H(k, T) имеет фиксиpованную длину;
  3. значение функции H(k, T) легко вычисляется для любого аpгумента;
  4. восстановить аpгумент по значению с вычислительной точки зpения — пpактически невозможно;
  5. функция H(k, T) — однозначна.

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

Не легко построить функцию, вход которой имеет произвольный размер, а тем более сделать ее однонаправленной. В реальном мире однонаправленные хэш-функции строятся на идее функции сжатия. Такая однонаправленная функция выдает хэш-значение длины n при заданных входных данных большей длины m. Входами функции сжатия являются блок сообщения и выход предыдущего блока текста. Выход представляет собой хэш-значение всех блоков до этого момента. То есть, хэш-значение блока Мi,- равно

hi, =f(Mi,hi-1)

Это хэш-значение вместе со следующим блоком сообщения становится следующим входом функции сжатия. Хэш-значением всего сообщения является хэш-значение последнего блока .

Рис 1. Однонаправленная хэш-функция

Хэшируемый вход должен каким-то способом содержать бинарное представление длины всего сообщения. Таким образом преодолевается потенциальная проблема, вызванная тем, что сообщения различной длины могут давать одно и то же хэш-значение. Иногда такой метод называется MD-усилением.

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

Самый близкой интерпретацией однонаправленных хэш-функций являются тезисы Барта Пренела (Bart Preneel).

Роном Ривестом изобрел ряд однонаправленных хэш – функций MD, где MD — Message Digest краткое изложение сообщения и описал цели преследуемые им при разработке данного алгоритма:

  • Безопасность. Вычислительно невозможно найти два сообщения с одинаковым хэш – значением.
  • Скорость. Подхдит для высокоскоростных программных реализациях, основана на простом переборе битовых манипуляций с операндами.
  • Простота и компактность. Не содержит больших структур данных или сложных программных модулей.
  • Архитектура. Оптимизирован для микропроцессорной архитектуры

MD2 — это первая 128-битовая однонаправленная хэш-функция, разработанная Роном Ривестом. Она, вместе с расширенным алгоритмом MD5, используется в протоколах передачи данных. Безопасность MD2 опирается на случайную перестановку байтов. Эта перестановка фиксирована и зависит от разрядов π, S0, S1, S2, . . . , S255 и являются перестановкой.

Хотя в MD2 пока не было найдено слабых мест, она работает медленнее большинства других MD хэш-функций.

Блок-схема алгоритма шифрования

Чтобы хэшировать сообщения М необходимо выполнить следующие этапы действий:

  1. Дополнить сообщение i байтами, значение i должно быть таким, чтобы длина полученного сообщения была кратна n байтам.
  2. Добавить к сообщению n байтов контрольной суммы.
  3. Проинициализировать m-байтовый блок: Хо, Х1, Х2, . . ., Xm. Заполнить первые n байтов X нулями, во вторые n байтов X скопировать первые n байтов сообщения, а третьи n байтов X должны быть равны XOR первых и вторых n байтов X.
  4. Функция сжатия, примерно выглядит следующим образом:

t:=0

For j = 0 to n+1

For k = 0 to m-1

t:=Xt xor St

Xk:=t

  1. Скопировать во вторые n байтов Х вторые n байтов сообщения, а третьи n байтов X должны быть равны XOR первых и вторых n байтов X. Выполнить этап (4). Повторять этапы (5) и (4) по очереди для каждые n байтов сообщения.
  2. Выходом являются первые n байтов X.

На рисунке 2, показана блок схема алгоритма формирования цифровой сигнатуры:

От начального до конечного блока

Считать предедущий блок

Сформировать блок

Предедущий блок XOR Текущий блок

Добавить символы до кратности

;

Проверка кратности размера текста и блока

Сформировать начальный блок

От начального до конечного символа блока

Вывести последний блок

да

нет

Рис. 2 Блок схема формирования цифровой сигнатуры

Опишем принцип, работы алгоритма с использованием блок-схемы:

Проверка кратности размера текста и блока – в зависимости от кратности, происходит добавление к текстовому сообщение необходимое количество символов.

Сформировать начальный блок – в зависимости от размер блока, формируется значение начального блока. Если размер блока 2 байта, то блок содержит значение «00».

Сформировать блок : = Предедущий блок XOR Текущий блок – формирование значения следующего блока равно арифметической операции исключения ИЛИ между текущим и предедущим.

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

Руководство пользователя

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

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

Для создания цифровой сигнатуры необходимо напечатать текстовое сообщение в поле ввода «Текс», содержащие символы латинского и русского алфавита. Затем указать размер блока генерации подписи в зависимости от уровня криптостойкости может варьировать в пределах от 1 до размер текста. Нажатием на кнопку «Генерировать подпись», происходит формирование и отображение цифровой подписи в поле ввода «Подпись».

Рис. 3 Генерация цифровой подписи к текстовому сообщению

При нажатие на кнопку «Сохранить сообщение» программа сохраняет в файл «output.txt» последовательно два текстовых сообщения: текст и его цифровая подпись.

При нажатие на кнопку «Проверить сообщение» текстовое сообщение из файла «output.txt» загружаются сначала в поле «Текс». Затем генерируются цифровая подпись и сравнивается с подписью в данном файле. Если подпись верна появляется диалоговое окно «Подпись совпадает», в противном случае «Подпись не совпадает».

При получение цифровой подписи для текстового сообщения «algoritm», результат при различных размерах подписи выглядит следующим образом:

Размер блока

Количество блоков

Подпись

1

8

7

2

4

!&

3

3

CL

4

2

<(>-

5

2

|q:++

6

2

|qzr/-

7

2

|qzrot)

Таблица 1. Формирование цифровой подписи для текста «algoritm»

В результате при формирование является важным выбор размер, оптимальным является 4 байта, если длина сообщения больше 128 символов то 16 байт и выше т.к результат определяется на основе операции xor для определенного количества блоков (целая часть деления размера сообщения на размер блока).

Рассмотрим пример сообщения длиной 285 символов:

При получение цифровой подписи для текстового сообщения «В результате при формирование является важным выбор размер, оптимальным является 4 байта, если длина сообщения больше 128 символов то 16 байт . т.к результат определяется на основе операции xor для определенного количества блоков (целая часть деления размера сообщения на размер блока).», результат при различных размерах подписи выглядит следующим образом:

Размер блока

Количество блоков

Подпись

3

95

џќw

4

72

WјҐ&

5

57

-^9

6

48

U±§%1?

7

41

PЏ^­п-

8

37

Do`лэхг#

16

19

ЉҐ ффлх,?&.9/ръю

Таблица 2. Формирование цифровой подписи для текста длиной больше 128 символов.

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

Руководство программы

Для разработки программы в среде программирования Delphi, использовались следующие типы данных переменных:

  • i,j:integer; — указатель символа текстового сообщения и блокаж
  • res:array[0..100] of string; — массив текстовых блоков, размер блока определяется размером текстового сообщенияж
  • F1:TextFile; — файловая переменая текстового файла «output.txt»

Стандартные функции и операции разработанного алгоритма представлены:

  • procedure Round(s:real):integer; возвращает jrhдлину строки в символах.
  • length(s:string):integer; возвращает длину строки в символах.
  • strtoint(s:string):integer; преобразовывает текстовую строку в числовое значение.
  • ord (x: <порядковый тип>): Longint; Возвращает порядковый номер значения выражения порядкового типа.
  • Chr(s:byte): Возвращает символ с указанным кодом. X — число, определяющее код символа.

После запуска программы необходимо указать размер блока цифровой подписи. Генерация подписи просходит при помощи процедуры TForm1.Button1Click(Sender: TObject). В данном случае происходит запись текстового сообщения в переменную r,

r:=itext.Text;

а затем определение кратности размера текстового сообщения и блока:

if length(r) mod strtoint(rb.Text)<>0 then.

Если не кратно то программа происходит добавление символов ‘-‘ к тексту:

for i:=1 to strtoint(rb.Text)-(length(r) mod strtoint(rb.Text)) do r:=r+’-‘;

Начальному блоку присваиваем значение от указанного размера:

for i:=1 to strtoint(rb.Text) do res[0]:=’0’+res[0];

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

for i:=1 to round(length(r)/strtoint(rb.Text)) do

begin

s:=res[i-1];

p:=»;

for j:=1 to strtoint(rb.Text) do

p:=chr(ord(s[j]) xor ord(r[j+(i-1)*strtoint(rb.Text)]))+p;

res[i]:=p;

Заключение

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

Выбор для конкретных ИС должен быть основан на глубоком анализе слабых и сильных сторон тех или иных методов защиты. Обоснованный выбор той или иной системы защиты, в общем-то, должен опираться на какие-то критерии эффективности. К сожалению, до сих пор не разработаны подходящие методики оценки эффективности криптографических систем.

В данной курсовой работе были рассмотрены алгоритмы создания цифровой сигнатуры на основе однонаправленной хэш-функцией, так же была рассмотрена методика шифрования на основе алгоритма MD2. Так же на основании этого алгоритма была создана программа. В тексте работы был приведён алгоритм выполнения программы, описание процедур используемых в программе, а так же было разработано руководство пользователя.

Список литературы

  1. Герасименко В.А. Защита информации в автоматизированных системах обработки данных кн. 1.-М.: Энергоатомиздат. -1994.-400с.
  2. Вербицкий О.В.Вступление к криптологии.- Львов.: Издательство науково-техничной литературы.-1998.-300с.
  3. Диффи У. Первые десять лет криптографии с открытым ключом //ТИИЭР, т. 76(1988)б Т5б с. 54-74.
  4. Герасименко В.А., Скворцов А.А., Харитонов И.Е. Новые направления применения криптографических методов защиты информации.- М.: Радио и связь.-1989.-360с.
  5. Миллер В. Использования эллиптических кривых в криптографии .: -1986.-417-426с.
  6. Галатенко В.А. Информационная безопасность. –М.: Финансы и статистика, 1997. –158 с.
  7. Грегори С. Смит. Программы шифрования данных // Мир ПК –1997. -№3. -С.58 — 68.
  8. Терехов А. Н., Тискин А. В. // Программирование РАН. –1994. -N 5 -С. 17—22.
  9. Криптология – наука о тайнописи // Компьютерное обозрение. –1999. -№3. –С. 10 – 17.
  10. Баричев С. В. Криптография без секретов. –М.: Наука, 1998. –120 с.

Приложение

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids;

type

TForm1 = class(TForm)

IText: TEdit;

Provfile: TButton;

Savefile: TButton;

Label5: TLabel;

Button1: TButton;

rb: TEdit;

Label7: TLabel;

pod: TEdit;

Label3: TLabel;

procedure SavefileClick(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure ProvfileClick(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.SavefileClick(Sender: TObject);

var F2:TextFile;

p:string;

begin

AssignFile(F2, ‘output.txt’);

Rewrite(F2);

writeln(F2,itext.text);

writeln(F2,pod.text);

CloseFile(F2);

end;

procedure TForm1.Button1Click(Sender: TObject);

var

i,j:integer;

res:array[0..100] of string;

r,s,p:string;

begin

r:=itext.Text;

if length(r) mod strtoint(rb.Text)<>0 then

for i:=1 to strtoint(rb.Text)-(length(r) mod strtoint(rb.Text)) do

r:=r+’-‘;

res[0]:=»;

for i:=1 to strtoint(rb.Text) do res[0]:=’0’+res[0];

//memo1.Clear;

for i:=1 to round(length(r)/strtoint(rb.Text)) do

begin

s:=res[i-1];

p:=»;

for j:=1 to strtoint(rb.Text) do

p:=chr(ord(s[j]) xor ord(r[j+(i-1)*strtoint(rb.Text)]))+p;

res[i]:=p;

//memo1.Lines.Add(res[i]);

end;

pod.Text:=res[round(length(r)/strtoint(rb.Text))];

end;

procedure TForm1.ProvfileClick(Sender: TObject);

var F1:TextFile;

t,p:string;

begin

AssignFile(F1, ‘output.txt’);

Reset(F1);

readln(F1,t);

itext.text:=t;

button1.Click();

readln(F1,p);

CloseFile(F1);

if p=pod.Text then showmessage(‘Подпись совпадает’) else

showmessage(‘Подпись не совпадает ‘+ p);

end;

end.

Leave a Comment

4 + 2 =