Демо (html) Методы и средства защиты компьютерной информации

1. Внесите изменения в программу. Подключите библиотеку GraphABC. Опишите переменные, необходимые для построения диаграммы.

Program statistics;

uses GraphABC;

Var i,j,l : integer;

simv : array[0..25] of char;

kol___sim : array[0..25] of integer;

otn___sim : array[0..25] of real;

f : text;

str : string;

x,y,w,h : integer;

2. В конце программы добавьте следующие операторы:

w:=WindowWidth;

h:=WindowHeight-1;

MoveTo(20,20);

LineTo(20,h-20);

MoveTo(20,round(h/2));

LineTo(w-20,round(h/2));

x:=20;

for i:=0 to 25 do

begin

x:=x+20;

SetBrushColor(clBlue);

FillRect(x-5,round(h/2),x+5,round(h/2)-round(otn___sim[i])*20);

ClearBrushPicture;

TextOut(x-4,round(h/2)+10,simv[i]);

end;

3. Проверьте работу приложения:

4. Сохраните приложение.

1. Составить программу нахождения частоты встречаемости букв русского алфавита. Множество букв текста на русском языке состоит из 32 символов от А до Я (без буквы Ё).

2. Определить частоты встречаемости букв русского алфавита в файле v1.txt.

1. Составить программу нахождения частоты встречаемости букв русского алфавита. Множество букв текста на русском языке состоит из 32 символов от А до Я (без буквы Ё).

2. Определить частоты встречаемости букв русского алфавита в файле v2.txt.

1. Составить программу нахождения частоты встречаемости букв русского алфавита. Множество букв текста на русском языке состоит из 32 символов от А до Я (без буквы Ё).

2. Определить частоты встречаемости букв русского алфавита в файле v3.txt.

1. Составить программу нахождения частоты встречаемости букв русского алфавита. Множество букв текста на русском языке состоит из 32 символов от А до Я (без буквы Ё).

2. Определить частоты встречаемости букв русского алфавита в файле v4.txt.

1. Составить программу нахождения частоты встречаемости букв русского алфавита. Множество букв текста на русском языке состоит из 32 символов от А до Я (без буквы Ё).

2. Определить частоты встречаемости букв русского алфавита в файле v5.txt.

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

Для наиболее простых шифров, например, подстановок и перестановок, при криптоанализе применяют статистическое распределение символов в алфавите. Так, в шифре моноалфавитной замены количество возможных перестановок букв алфавита (для английского языка) равно 26!. Однако данный шифр не является криптостойким по следующим причинам:

ü в шифротексте сохраняются статистические зависимости символов и сочетаний символов исходного текста

ü перемешанный алфавит может быть установлен постепенным подбором.

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

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

Частота встречаемости букв: а — английского и немецкого алфавитов;

б — русского алфавита

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

Цель:

знакомство с методами криптоанализа информации.

Результаты обучения:

После успешного завершения занятия пользователь должен:

· знать основные понятия криптоанализа;

· знать характеристики криптографических средств защиты;

· уметь проводить криптоанализ простых шифров замены и перестановки.

Список рекомендуемой литературы:

1. Шаньгин В.Ф. Информационная безопасность компьютерных систем и сетей. Учебное пособие. – М.: ИД «ФОРУМ»: ИНФРА-М, 2008.

2. Осипян В.О., Осипян К.В. Криптография в задачах и упражнениях. – М.: Гелиос АРВ, 2004.

3. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. – М.: Гелиос АРВ, 2002.

Используемые программы:

PascalABC

Система Pascal ABC предназначена для обучения программированию на языке Паскаль, позволяет осуществить плавный переход от простейших программ к модульному, объектно-ориентированному, событийному и компонентному программированию.

Используемые файлы:

Cryptography.txt, v1.txt, v2.txt, v3.txt, v4.txt, v5.txt

1. Зашифровать текст методом RSA с заданными значениями открытого и секретного ключей.

2. Расшифровать текст методом RSA с заданными значениями открытого и секретного ключей.

1. Зашифровать текст методом RSA с заданными значениями открытого и секретного ключей.

2. Расшифровать текст методом RSA с заданными значениями открытого и секретного ключей.

1. Зашифровать текст методом RSA с заданными значениями открытого и секретного ключей.

2. Расшифровать текст методом RSA с заданными значениями открытого и секретного ключей.

1. Зашифровать текст методом RSA с заданными значениями открытого и секретного ключей.

2. Расшифровать текст методом RSA с заданными значениями открытого и секретного ключей.

1. Зашифровать текст методом RSA с заданными значениями открытого и секретного ключей.

2. Расшифровать текст методом RSA с заданными значениями открытого и секретного ключей.

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

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

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

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

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

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

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

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

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

Составим программу, реализующую алгоритм RSA для английского алфавита

1. Запустите PascalABC.

2. С помощью команды Сервис – Создать форму сформируйте форму:

3. Введите событийную процедуру, вызываемую при изменении полей ввода. Для этого выделите верхнее поле ввода Edit1, выберите вкладку События и дважды щелкните левой кнопкой мыши в поле OnChange:

4. Введите текст событийной процедуры Edit1OnChange:

procedure Edit1OnChange;

begin

If (edit1.text<>'') and (edit2.text<>'') then

begin

p:=StrToInt(edit1.text);

q:=StrToInt(edit2.text);

n:=p*q;

k:=(p-1)*(q-1);

textlabel4.caption:='n=' + IntToStr(n);

textlabel5.caption:='k=' + IntToStr(k);

end;

end;

5. Для поля Edit2 также укажите событийную процедуру OnChange - Edit1OnChange:

6. Опишите используемы переменные:

//$VCLDESIGN+

var

Form1: Form;

…

//$VCLDESIGN-

p,q,n,k: integer;

7. Проверьте работу приложения:

8. Сохраните приложение.

9. Добавьте на форму элементы управления в соответствии с рисунком:

10. Введите событийную процедуру, вызываемую при изменении поля ввода Edit3. Для этого выделите верхнее поле ввода Edit3, выберите вкладку События и дважды щелкните левой кнопкой мыши в поле OnChange:

11. Введите текст событийной процедуры Edit3OnChange:

procedure Edit3OnChange;

begin

If (edit1.text<>'') and (edit2.text<>'') and (edit3.text<>'') then

begin

e:=StrToInt(edit3.text);

for d:=1 to k do

begin {Îïðåäåëÿåì ÷èñëî d}

ost:=(e*d) mod k; {äëÿ êîòîðîãî (e*d) mod k=1}

if ost=1 then break;

end;

If ost=1 Then

begin

textlabel9.caption:='d=' + IntToStr(d);

textlabel13.caption:='{' + IntToStr(e) + ',' + IntToStr(n) + '}';

textlabel14.caption:='{' + IntToStr(d) + ',' + IntToStr(n) + '}';

end

Else

begin

e:=0;

d:=0;

textlabel9.caption:='';

textlabel13.caption:='';

textlabel14.caption:='';

end;

end;

end;

12. Внесите изменения в событийную процедуру Edit1OnChange:

procedure Edit1OnChange;

begin

If (edit1.text<>'') and (edit2.text<>'') then

begin

p:=StrToInt(edit1.text);

q:=StrToInt(edit2.text);

n:=p*q;

k:=(p-1)*(q-1);

textlabel4.caption:='n=' + IntToStr(n);

textlabel5.caption:='k=' + IntToStr(k);

edit3.text:='';

e:=0;

d:=0;

textlabel9.caption:='';

textlabel13.caption:='';

textlabel14.caption:='';

end;

end;

13. Опишите используемы переменные:

//$VCLDESIGN+

var

Form1: Form;

…

//$VCLDESIGN-

p,q,n,k,e,d,ost: integer;

14. Проверьте работу приложения:

15. Сохраните приложение.

16. Добавьте на форму элементы управления в соответствии с рисунком:

17. Введите событийную процедуру для кнопки «Зашифровать»:

procedure Button1OnClick;

begin

If edit4.text<>'' then

begin

edit5.text:='';

edit4.text:=UpperCase(edit4.text);

soob:=edit4.text;

sh___soob:='';

l:=ord(soob[0]); {l-длина сообщения}

for i:=1 to l do

begin

kod___soob:=ord(soob[i])-65; {Определяем код}

st:=kod___soob; {очередного символа}

for j:=1 to e-1 do {Шифруем этот код,}

begin {возводя его в степень e}

st:=st*kod___soob; {и применяя операцию mod n}

st:=st mod n;

end;

kod___sh___soob:=st+65; {Находим ASCII-символ, соответствующий}

sh___soob:=sh___soob + char(kod___sh___soob); {зашифрованному коду}

end;

edit5.text:=sh___soob;

end;

end;

18. Введите событийную процедуру для кнопки «Расшифровать»:

procedure Button2OnClick;

begin

If edit5.text<>'' then

begin

edit4.text:='';

sh___soob:=edit5.text;

soob:='';

l:=ord(sh___soob[0]);

for i:=1 to l do

begin

kod___sh___soob:=ord(sh___soob[i])-65; {Определяем код символа}

st:=kod___sh___soob; {зашифрованного сообщения}

for j:=1 to d-1 do

begin {Расшифровываем этот код,}

st:=st*kod___sh___soob; {возводя его в степень d}

st:=st mod n; {и применяя операцию mod n}

end;

kod___soob:=st+65; {Находим ASCII-символ, исходного сообщения,}

soob:=soob + char(kod___soob); {соответствующий расшифрованному коду}

end;

edit4.text:=soob;

end;

end;

19. Введите событийные процедуры для кнопок «Очистить»:

procedure Button3OnClick;

begin

edit4.text:='';

end;

procedure Button4OnClick;

begin

edit5.text:='';

end;

20. Опишите используемы переменные:

//$VCLDESIGN+

var

Form1: Form;

…

//$VCLDESIGN-

i,j,p,q,n,k,e,d,ost,l,st,kod___soob,kod___sh___soob: integer;

soob,sh___soob: string;

21. Проверьте работу приложения:

22. Сохраните приложение.

Цель:

знакомство с криптографическими методами защиты информации в системах с открытым ключом.

Результаты обучения:

После успешного завершения занятия пользователь должен:

· знать принципы работы асимметричных криптосистем шифрования;

· знать процедуры зашифровывания и расшифровывания данных в криптосистемах RSA;

· уметь зашифровывать и расшифровывать с помощью алгоритма RSA.

Список рекомендуемой литературы:

1. Шаньгин В.Ф. Информационная безопасность компьютерных систем и сетей. Учебное пособие. – М.: ИД «ФОРУМ»: ИНФРА-М, 2008.

2. Осипян В.О., Осипян К.В. Криптография в задачах и упражнениях. – М.: Гелиос АРВ, 2004.

3. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. – М.: Гелиос АРВ, 2002.

Используемые программы:

PascalABC

Система Pascal ABC предназначена для обучения программированию на языке Паскаль, позволяет осуществить плавный переход от простейших программ к модульному, объектно-ориентированному, событийному и компонентному программированию.

1. С помощью метода распределения ключей Диффи-Хеллмана определить открытые ключи отправителя и получателя при заданных значениях a, n, x, y.

2. С помощью метода распределения ключей Диффи-Хеллмана определить общий секретный (сессионный) ключ при заданных значениях a, n, x, y.

1. С помощью метода распределения ключей Диффи-Хеллмана определить открытые ключи отправителя и получателя при заданных значениях a, n, x, y.

2. С помощью метода распределения ключей Диффи-Хеллмана определить общий секретный (сессионный) ключ при заданных значениях a, n, x, y.

1. С помощью метода распределения ключей Диффи-Хеллмана определить открытые ключи отправителя и получателя при заданных значениях a, n, x, y.

2. С помощью метода распределения ключей Диффи-Хеллмана определить общий секретный (сессионный) ключ при заданных значениях a, n, x, y.

1. С помощью метода распределения ключей Диффи-Хеллмана определить открытые ключи отправителя и получателя при заданных значениях a, n, x, y.

2. С помощью метода распределения ключей Диффи-Хеллмана определить общий секретный (сессионный) ключ при заданных значениях a, n, x, y.

1. С помощью метода распределения ключей Диффи-Хеллмана определить открытые ключи отправителя и получателя при заданных значениях a, n, x, y.

2. С помощью метода распределения ключей Диффи-Хеллмана определить общий секретный (сессионный) ключ при заданных значениях a, n, x, y.

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

К распределению ключей предъявляются следующие требования:

q оперативность и точность распределения;

q конфиденциальность и целостность распределяемых ключей.

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

1) использование одного или нескольких центров распределения ключей;

2) прямой обмен ключами между пользователями сети.

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

Задача распределения ключей сводится к построению такого протокола распределения ключей, который обеспечивает:

q взаимное подтверждение подлинности участников сеанса;

q подтверждение достоверности сеанса;

q использование минимального числа сообщений при обмене ключами.

Характерным примером реализации первого подхода является система аутентификации и распределения ключей Kerberos.

Остановимся подробнее на втором подходе.

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

Для решения этой проблемы возможно:

1) использование асимметричной криптосистемы с открытым ключом для защиты секретного ключа симметричной криптосистемы;

2) использование системы открытого распределения ключей Диффи — Хеллмана.

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

Второй способ основан на применении алгоритма открытого распределения ключей Диффи — Хеллмана, позволяющего пользователям обмениваться ключами по незащищенным каналам связи.

Распределение ключей по методу Диффи-Хеллмана осуществляется в следующей последовательности:

1) Задать основание a и модуль n.

2) С помощью генератора случайных чисел получить случайное число x (1<x<n) – секретный ключ отправителя. Вычислить значение - открытый ключ отправителя. Послать l получателю.

3) С помощью генератора случайных чисел получить случайное число y (1<y<n) – секретный ключ получателя. Вычислить значение - открытый ключ получателя. Послать m отправителю.

4) Вычислить секретный ключ отправителя (общий сессионный ключ) .

5) Вычислить секретный ключ получателя (общий сессионный ключ) .

Цель:

знакомство с методами управления криптоключами.

Результаты обучения:

После успешного завершения занятия пользователь должен:

· знать принципы процесса управления криптоключами;

· знать метод распределения ключей Диффи-Хеллмана;

· уметь генерировать криптоключи .

Список рекомендуемой литературы:

1. Шаньгин В.Ф. Информационная безопасность компьютерных систем и сетей. Учебное пособие. – М.: ИД «ФОРУМ»: ИНФРА-М, 2008.

2. Осипян В.О., Осипян К.В. Криптография в задачах и упражнениях. – М.: Гелиос АРВ, 2004.

3. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. – М.: Гелиос АРВ, 2002.

Используемые программы:

PascalABC

Система Pascal ABC предназначена для обучения программированию на языке Паскаль, позволяет осуществить плавный переход от простейших программ к модульному, объектно-ориентированному, событийному и компонентному программированию.

1. Напомним, что c, отличное от нуля, делит a, если a = m ´ c для некоторого m, где c, a и m являются целыми числами.

Таким образом, c делит a, если деление выполняется без остатка. Это пишется так: c|a.

Если c|a, то c называют делителем a.

2. Целое число p>1 называется простым, если его делителями являются только числа
± 1 и ± p.

3. Запись gcd (a, b) будет обозначать наибольший общий делитель чисел (НОД) a и b.

4. Положительное целое число c является наибольшим общим делителем чисел a и b, если:

· c является делителем a и b;

· любой делитель a и b является делителем c.

gcd (a, b) = max [k таких, что k|a и k|b].

Пример: gcd (60, 24) = gcd (60, -24) = 12.

5. Любое целое число a > 1 может быть разложено на множители и единственным способом представлено в виде

,

где p1< p2< …< pt являются простыми числами, и где каждая ai > 0.

Пример: 3600 = 24 ´ 32 ´ 52.

6. Целые числа a и b являются взаимно простыми, если они не имеют общих простых делителей, т.е. если их единственным общим делителем является 1. Другими словами числа a и b являются взаимно простыми, если gcd (a, b) = 1.

7. Если a является целым, а z - положительным целым, то a mod z определяется как остаток от деления a на z. Тогда для любого целого числа a можно написать

a = ëa/zû ´ z + (a mod z),

где ëa/zû означает наибольшее целое число, не превышающее (a/z).

Пример: 11 mod 7 = 4.

11 = ë11/7û ´ 7 + 4 = 1 ´ 7 + 4.

8. Говорят, что два целых числа a и b являются сравнимыми по модулю n, если
(a mod n) = (b mod n). Это записывается так: a º b mod n.

Пример: 73 º 4 mod 23, так как остатки от деления чисел 73 и 4 на 23 совпадают (4).

Алгоритм Евклида нахождения наибольшего общего делителя основывается на следующей теореме (приводим без доказательства).

Для любого неотрицательного числа X и любого положительного числа Y справедливо следующее:

gcd (X, Y) = gcd (Y, X mod Y),

где X>Y>0.

Чтобы определить наибольший общий делитель, приведенное выше равенство необходимо использовать многократно (до получения значения Y = 0). Ниже приводится раскрытая запись

gcd (X, Y) = gcd (Y, X mod Y) = gcd (Y, X – (ëX/Yû - целое частное) ´ Y)).

Пример: gcd (18, 12) = gcd (12, 18 mod 12) = gcd (12, 18 – 1 ´ 12) = gcd (12, 6).

gcd (12, 6) = gcd (6, 12 mod 6) = gcd (6, 12 – 2 ´ 6) = gcd (6, 0).

Ответ: gcd (18, 12) = 6.

1. С помощью алгоритма Евклида вычислить наибольший общий делитель чисел 42 и 24.

2. С помощью расширенного алгоритма Евклида вычислить мультипликативное обратное числа 13 по модулю 89.

3. Вычислить 3420 mod 14.

1. С помощью алгоритма Евклида вычислить наибольший общий делитель чисел 57 и 18.

2. С помощью расширенного алгоритма Евклида вычислить мультипликативное обратное числа 11 по модулю 62.

3. Вычислить 3220 mod 24.

1. С помощью алгоритма Евклида вычислить наибольший общий делитель чисел 58 и 8.

2. С помощью расширенного алгоритма Евклида вычислить мультипликативное обратное числа 25 по модулю 33.

3. Вычислить 3112 mod 18.

1. С помощью алгоритма Евклида вычислить наибольший общий делитель чисел 82 и 27.

2. С помощью расширенного алгоритма Евклида вычислить мультипликативное обратное числа 6 по модулю 83.

3. Вычислить 3112 mod 11.

1. С помощью алгоритма Евклида вычислить наибольший общий делитель чисел 96 и 38.

2. С помощью расширенного алгоритма Евклида вычислить мультипликативное обратное числа 22 по модулю 47.

3. Вычислить 3515 mod 30.

Пример 1: Вычислить ab mod n, где a = 19, b = 5 и n = 119. Иначе, 195 mod 119 = ?

b = 510 = 101, k = 2, c = 0, d = 1, a = 19, n = 119.

1. k > 0, k = 2;

c = 2 ´ c = 2 ´ 0 = 0;

d = (d ´ d) mod n = (1 ´ 1) mod 119 = 1 mod 119 = 1;

bk = b2 = 1;

c = c + 1 = 0 + 1 = 1;

d = (d ´ a) mod n = (1 ´ 19) mod 119 = 19 mod 119 = 19 - ë19 / 119û ´ 119 = 19 – 0 ´119 = 19.

k = k – 1 = 2 – 1 = 1.

2. k > 0, k = 1;

c = 2 ´ c = 2 ´ 1 = 2;

d = (d ´ d) mod n = (19 ´ 19) mod 119 = 361 mod 119 = 361 - ë361 / 119û ´ 119 = 361 – 3 ´ 119 =
= 361 – 357 = 4;

bk = b1 = 0;

k = k – 1 = 1 – 1 = 0.

3. k > 0, k = 0;

c = 2 ´ c = 2 ´ 2 = 4;

d = (d ´ d) mod n = (4 ´ 4) mod 119 = 16 mod 119 = 16 - ë16 / 119û ´ 119 = 16 – 0 ´ 119 = 16;

bk = b0= 1;

c = c + 1 = 4 + 1 = 5;

d = (d ´ a) mod n = (16 ´ 19) mod 119 = 304 mod 119 = 304 - ë304 / 119û ´ 119 = 304 – 2 ´119 = =66.

k = k – 1 = 0 – 1 = -1.

Ответ: 195 mod 119 = 66.

Пример 2: Вычислить ab mod n, где a = 66, b = 77 и n = 119. Иначе, 6677 mod 119 = ?

b = 7710 = 10011012, k = 6, c = 0, d = 1, a = 66, n = 119.

1. k > 0, k = 6;

c = 2 ´ c = 2 ´ 0 = 0;

d = (d ´ d) mod n = (1 ´ 1) mod 119 = 1 mod 119 = 1;

bk = b6 = 1;

c = c + 1 = 0 + 1 = 1;

d = (d ´ a) mod n = (1 ´ 66) mod 119 = 66 mod 119 = 66 - ë66 / 119û ´ 119 = 66 – 0 ´119 = 66.

k = k – 1 = 6 – 1 = 5.

2. k > 0, k = 5; b5 = 0;

c = 2 ´ c = 2 ´ 1 = 2;

d = (d ´ d) mod n = (66 ´ 66) mod 119 = 4356 mod 119 = 4356 - ë4356 /119û ´ 119 = 4356 – (36´ ´ 119) = 4356 – 4284 = 72;

k = k – 1 = 4;

bk = b4 = 0;

c = c ´ 1 = 2 ´ 2 = 4;

d = (d ´ d) mod n = (72 ´ 72) mod 119 = 5184 mod 119 = 5184 - ë5184 / 119û ´ 119 = 5184 – (43´
´119) = 5184 – 5117 = 67.

k = k – 1 = 4 – 1 = 3.

3. k > 0, k = 3; b3 = 1;

c = 2 ´ c = 2 ´ 4 = 8;

d = (d ´ d) mod n = (67 ´ 67) mod 119 = 4489 mod 119 = 4489 - ë4489 /119û ´ 119 = 4489 – (37 ´ ´119) = 4489 – 4403 = 86;

c = c + 1 = 8 + 1 = 9;

d = (d ´ a) mod n = (86 ´ 66) mod 119 = 5676 mod 119 = 5676 - ë5676 / 119û ´ 119 = 5676 – (47´ ´119) = 5676 – 5593 = 83.

k = k – 1 = 3 – 1 = 2; b2 = 1.

4. k > 0, k = 2; b2 = 1;

c = 2 ´ c = 2 ´ 9 = 18;

d = (d ´ d) mod n = (83 ´ 83) mod 119 = 6889 mod 119 = 6889 - ë6889 /119û ´ 119 = 6889 – (57 ´ ´ 119) = 6889 – 6783 = 106;

c = c + 1 = 18 + 1 = 19;

d = (d ´ a) mod n = (106 ´ 66) mod 119 = 6996 mod 119 = 6996 - ë6996 / 119û ´ 119 = 6996 – (58 ´119) = 6996 – 6902 = 94.

k = k – 1 = 2 – 1 = 1; b1 = 0.

5. k > 0, k = 1; b1 = 0;

c = 2 ´ c = 2 ´ 19 = 38;

d = (d ´ d) mod n = (94 ´ 94) mod 119 = 8836 mod 119 = 8836 - ë8836 /119û ´ 119 = 8836 – (74 ´ ´119) = 8836 – 8806 = 30;

b1 = 0;

6. k > 0, k = 0; b0 = 1;

c = 2 ´ c = 2 ´ 38 = 76;

d = (d ´ d) mod n = (30 ´ 30) mod 119 = 900 mod 119 = 900 - ë900 /119û ´ 119 = 900 – (7 ´ 119 = = 900 – 833 = 67;

c = c + 1 = 76 + 1 = 77;

d = (d ´ a) mod n = (67 ´ 66) mod 119 = 4422 mod 119 = 4422 - ë4422 / 119û ´ 119 = 4422 – (37´ ´119) = 4422 – 4403 = 19.

k = k – 1 = 0 – 1 = -1.

Так как k < 0, то получен следующий ответ.

Ответ: 6677 mod 119 = 19.

Цель:

освоение основных методов и алгоритмов криптографии с открытым ключом.

Результаты обучения:

После успешного завершения занятия пользователь должен:

· уметь находить наибольший общий делитель чисел с помощью алгоритма Евклида;

· уметь находить мультипликативное обратное числа по заданному модулю с помощью расширенного алгоритма Евклида;

· уметь вычислять ab mod n при больших значениях b.

Список рекомендуемой литературы:

1. Шаньгин В.Ф. Информационная безопасность компьютерных систем и сетей. Учебное пособие. – М.: ИД «ФОРУМ»: ИНФРА-М, 2008.

2. Осипян В.О., Осипян К.В. Криптография в задачах и упражнениях. – М.: Гелиос АРВ, 2004.

3. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. – М.: Гелиос АРВ, 2002.

Используемые программы:

Pascal ABC

1. Вычислить степени числа 2 по модулю 5.

2. Используя метод Диффи-Хеллмана, определить открытые ключи пользователей и общий секретный ключ при p =5, a=4, Xa=12, Xb=17.

1. Вычислить степени числа 2 по модулю 7.

2. Используя метод Диффи-Хеллмана, определить открытые ключи пользователей и общий секретный ключ при p =5, a=4, Xa=14, Xb=13.

1. Вычислить степени числа 3 по модулю 5.

2. Используя метод Диффи-Хеллмана, определить открытые ключи пользователей и общий секретный ключ при p =7, a=10, Xa=1, Xb=4.

1. Вычислить степени числа 3 по модулю 7.

2. Используя метод Диффи-Хеллмана, определить открытые ключи пользователей и общий секретный ключ при p =5, a=13, Xa=17, Xb=17.

1. Вычислить степени числа 5 по модулю 7.

2. Используя метод Диффи-Хеллмана, определить открытые ключи пользователей и общий секретный ключ при p =7, a=3, Xa=16, Xb=7.

Пример ДХ 1: Произвести обмен ключами между двумя пользователями А и В и сгенерировать общий сеансовый секретный ключ по схеме Диффи-Хеллмана.

Примечание. Описание примера дается для процесса информационного обмена между двумя абонентами. Это сделано для удобства выполнения лабораторной работы автономно одним студентом на одном рабочем месте.

1. Определение общих открытых элементов (в начале данный пункт задания выполняется пользователем А (условно) и полученные результаты в открытом виде передаются (условно) пользователю В). Для экономии времени одновременно пользователь В аналогичную работу выполняет с другими значениями p и a.

Это простое число p и его первообразный корень a.

Рекомендуется в качестве p выбрать двухразрядное число, равное или меньшее по значению 97. Для рассматриваемого примера, ради обеспечения простоты, мы выберем p=19.

Первообразный корень для выбранного p может быть определен двояко.

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

Во втором случае первообразный корень для выбранного p подбирается из условия, что целыми числами с первообразными корнями могут быть только числа 2, 4, na и 2na (где n - любое нечетное простое число). Естественно, выбранный в данном случае первообразный корень a < p.

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

Для нашего примера p=19 и a=10 (см. таблицу примера СТЕП 1).

2. Выбор секретных ключей пользователей А и В (соответственно XA и XB).

В соответствии с выбранным значением p определяются секретные ключи по условиям XA < p и XB < p. Выбираем

XA=5 и XB=7.

3. Вычисление в соответствии с найденным a и выбранному p открытых ключей YA и YB (соответственно пользователями А и В) для пользователей А и В на основе XA и XB (при этом используется алгоритм «Быстрое возведение в степень для ab mod n при больших значениях b»):

YA = aXA mod p = 105 mod 19.

YB = aXB mod p = 107 mod 19.

В действительности целые числа, используемые в приведенных соотношениях очень большие и выполнить данные расчеты не так легко. Поэтому необходимо эти расчеты производить в соответствии с алгоритмом «Быстрое возведение в степень для ab mod n при больших значениях b» (см. лабораторную работу 6 - «Алогритм быстрого возведения в степень для ab mod n при больших значениях b», примеры БВОЗ 1 и БВОЗ 2, и задание 3, не путать p с n; в алгоритме n выбранное простое число).

В нашем примере YA = aXA mod p = 105 mod 19 = 3, то есть . YA = 3.

YB = aXB mod p = 107 mod 19 = 15, то есть, YB = 15.

4. Выполнение процесса обмена открытыми ключами (условно).

Пользователь А получает в свое распоряжение открытый ключ пользователя В - YB.

Пользователь B получает в свое распоряжение открытый ключ пользователя A - YA.

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

Пользователь A вычисляет свой сеансовый секретный ключ K ―

K = (YB)XA mod p.

Пользователь B вычисляет свой сеансовый секретный ключ K ―

K = (YA)XB mod p.

При этом обе стороны используют алгоритм «Быстрое возведение в степень для ab mod n при больших значениях b».

Для нашего примера

Пользователь A: K = (YB)XA mod p = 155mod19 = 2; K= 2.

Пользователь B: K = (YA)XB mod p = 37mod19 = 2; K= 2.

6. Посылка (условно) определенного сообщения пользователем A пользователю B.

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

Сообщение (А) -....З В Е З Д А

Шестнадцатиричный

код 866 (A).…... 87 82 85 87 84 80

Двоичный код.1000 0111 1000 0010 1000 0101 1000 0111 1000 0100 1000 0000

Гамма K (A).…1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010

Å mod 2………0010 1101 0010 1000 0010 1111 0010 1101 0010 1110 0010 1010

Гамма К (B).....1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010

Двоичный код 1000 0111 1000 0010 1000 0101 1000 0111 1000 0100 1000 0000

Шестнадцатиричный

код 866 (B)…..……87 82 85 87 84 80

Сообщение (B) -.... З В Е З Д А

7. С целью проверки совместной работы пользователей необходимо расшифрованное пользователем В сообщение переслать (условно) в открытом виде пользователю А.

8. Необходимо такую же работу, одновременно с пользователем А, произвести и пользователю В (условно) согласно п. 1 для передачи другого слова пользователем В
пользователю А.

Цель:

освоение основных методов и алгоритмов криптографии с открытым ключом.

Результаты обучения:

После успешного завершения занятия пользователь должен:

· уметь вычислять степени целого числа am по модулю p и целых чисел, принадлежащих показателю f(p) - первообразные корни по модулю p;

· уметь генерировать секретные ключи по схеме Диффи-Хеллмана.

Список рекомендуемой литературы:

1. Шаньгин В.Ф. Информационная безопасность компьютерных систем и сетей. Учебное пособие. – М.: ИД «ФОРУМ»: ИНФРА-М, 2008.

2. Осипян В.О., Осипян К.В. Криптография в задачах и упражнениях. – М.: Гелиос АРВ, 2004.

3. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. – М.: Гелиос АРВ, 2002.

Число положительных целых значений, которые меньше n и являются взаимно простыми с n, обозначается через f(n) и называется функцией Эйлера. Для простого числа p

f(p) = p – 1.

Если имеется два простых числа p и q, тогда для n = pq получим

f(n) = f(pq) = f(p) ´ f(q) = (p-1) ´ (q-1).

Теорема Эйлера утверждает, что для любых взаимно простых чисел a и n

af(n) º 1 mod n.

Пример: a = 3, n = 10, f(n) = f(pq) = f(p) ´ f(q) = (p-1) ´ (q-1) = (5-1) ´ (2-1) = 4. Следовательно, 34 = 81 º 1 mod 10.

Важным является следующее.

Если a и n являются взаимно простыми, то существует, по крайней мере, одно целое число m, удовлетворяющее соотношению am º 1 mod n, где m = f(n).

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

¨ порядок числа a по модулю n;

¨ показатель, которому принадлежит a по модулю n;

¨ длина периода последовательности, генерируемой степенями a.

Общая блок-схема алгоритма определения степеней целых чисел (am) по конкретно заданному модулю p и одновременно его первообразных корней:

Если существует, по крайней мере, одно целое число m, удовлетворяющее соотношению

am º 1 mod n, где m = f(n), то a и n являются взаимно

1. Вычислить значение секретного ключа d, мультипликативного обратного для e по модулю f(n) = (p-1) ´ (q-1) при p=11 , q=5 и e=7.

2. C помощью алгоритма RSA зашифровать сообщение a=M=9 открытым ключом b = e = 7 при n=p*q=55.

3. C помощью алгоритма RSA расшифровать сообщение a=C=4 секретным ключом b = d = 23 при n=p*q=55.

1. Вычислить значение секретного ключа d, мультипликативного обратного для e по модулю f(n) = (p-1) ´ (q-1) при p=13 , q=11 и e=7.

2. C помощью алгоритма RSA зашифровать сообщение a=M=9 открытым ключом b = e = 7 при n=p*q=143.

3. C помощью алгоритма RSA расшифровать сообщение a=C=48 секретным ключом b = d = 103 при n=p*q=143.

1. Вычислить значение секретного ключа d, мультипликативного обратного для e по модулю f(n) = (p-1) ´ (q-1) при p=13 , q=7 и e=7.

2. C помощью алгоритма RSA зашифровать сообщение a=M=9 открытым ключом b = e = 7 при n=p*q=91.

3. C помощью алгоритма RSA расшифровать сообщение a=C=9 секретным ключом b = d = 31 при n=p*q=91.

1. Вычислить значение секретного ключа d, мультипликативного обратного для e по модулю f(n) = (p-1) ´ (q-1) при p=3 , q=11 и e=7.

2. C помощью алгоритма RSA зашифровать сообщение a=M=9 открытым ключом b = e = 7 при n=p*q=33.

3. C помощью алгоритма RSA расшифровать сообщение a=C=15 секретным ключом b = d = 3 при n=p*q=33.

1. Вычислить значение секретного ключа d, мультипликативного обратного для e по модулю f(n) = (p-1) ´ (q-1) при p=7 , q=11 и e=7.

2. C помощью алгоритма RSA зашифровать сообщение a=M=9 открытым ключом b = e = 7 при n=p*q=77.

3. C помощью алгоритма RSA расшифровать сообщение a=C=37 секретным ключом b = d = 43 при n=p*q=77.

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

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

Пример RSA-0. Выбор целого e, взаимно простого с f(n) и меньшего, чем f(n). А также определение такого d, что de = 1 mod f(n) и d < f(n).

Это подготовительный этап для выполнения алгоритма RSA.

Выбираем два простых числа p = 7 и q = 17.

Вычисляем n = p ´ q = 7 ´ 17 = 119.

Вычисляем f(n) = (p-1) ´ (q-1) = 6 ´16 = 96.

Выбираем e по условию, что gcd (e, f(n)) = 1 и 1<e<f(n) Для этого будем пользоваться расширенным алгоритмом Евклида для нахождения наибольшего общего делителя двух чисел, который при определении и уточнении, что таким делителем является 1, выдает и мультипликативное обратное для e по модулю f(n).

gcd (d, f) = gcd (e =5, f(n) = 96) = 1.

Общая блок-схема расширенного алгоритма Евклида для вычисления мультипликативного обратного:

Выполняем алгоритм:

X1 = 1, X2 = 0, X3 = 96.

Y1 = 0, Y2 = 1, Y3 = 5.

Y3 ¹ 0,

Y3 ¹ 1.

Q = ëX3/Y3û = ë96/5û = 19.

T1 = X1 – Q ´ Y1 = 1 – 19 ´ 0 = 1,

T2 = X2 – Q ´ Y2 = 0 – 19 ´ 1 = -19,

T3 = X3 – Q ´ Y3 = 96 – 19 ´ 5 = 1.

X1 = Y1 = 0,

X2 = Y2 = 1,

X3 = Y3 = 5.

Y1 = T1 = 1,

Y2 = T2 = -19,

Y3 = T3 = 1.

Соотношения:

f ´ T1 + d ´ T2 = 96 ´ 1 + 5 ´ (-19) = 1 = T3,

f ´ X1 + d ´ X2 = 96 ´ 0 + 5 ´ 1 = 5 = X3,

f ´ Y1 + d ´ Y2 = 96 ´ 1 + 5 ´ (-19) = 1 = Y3.

Так как Y3 = 1, то Y3 gcd (5, 96) = 1 наибольший общий делитель.

Тогда Y2 = d-1 mod 96 = -19. Так как Y2 отрицательное целое, то мультипликативное обратное будет 96-19 = 77.

Таким образом, для нашего примера e = 5 и d = 77.

Цель:

освоение основных методов и алгоритмов криптографии с открытым ключом.

Результаты обучения:

После успешного завершения занятия пользователь должен:

· уметь зашифровывать открытое сообщение открытым ключом с помощью алгоритма RSA;

· уметь расшифровывать зашифрованное сообщение секретным ключом с помощью алгоритма RSA.

Список рекомендуемой литературы:

1. Шаньгин В.Ф. Информационная безопасность компьютерных систем и сетей. Учебное пособие. – М.: ИД «ФОРУМ»: ИНФРА-М, 2008.

2. Осипян В.О., Осипян К.В. Криптография в задачах и упражнениях. – М.: Гелиос АРВ, 2004.

3. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. – М.: Гелиос АРВ, 2002.