Защита информации

1. Личные алфавиты


Создала собственный алфавит, как массив символов, возможно непосредственным описанием последовательности следования символов.

Установила в форму компонент Button 1-3


Рисунок 1

алгоритм шифрование виженер делитель

procedure TForm1.Button3Click(Sender: TObject);: array[0..15] of char = ('0','1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'); : integer; .Caption := ''; i := 0 to 15 do .Caption := Form1.Caption + A[i] + ' ';;


Создать алфавит, как массив символов, возможно путем использования функции Succ, поэтому я указала ее как начальный параметр первый символ.

TForm1.Button1Click(Sender: TObject);: array[1..32] of char; : integer;

{Строем алфавит}:= 1; [i] := 'А'; (i,1); [i] := Succ(A[i-1]); i >= 32; .Caption := ''; i := 1 to 32 do .Caption := Form1.Caption + A[i] + ' '; ;


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

TForm1.Button2Click(Sender: TObject);: array[1..32] of char; : integer; := 1; [i] := 'Я'; (i,1); [i] := Pred(A[i-1]); i >= 32; .Caption := ''; i := 1 to 32 do // в цикле от 1 до 32.Caption := Form1.Caption + A[i] + ' '; ;


. Шифр Виженера - модифицированный шифр Цезаря, шифр XOR


Установила в форму компонент Edit1 (ввод пароля), три компонента Мемо1,2,3, три компонента Label 1,2,3 (надписи), три компонента GroupBox 1, 2, 3 в которые установить по 2 кнопки Button (вид указан на рисунке 2).


Рис. 2. Расположение компонентов в форме


В качестве алфавита использовала встроенную таблицу ASCII (Z-256)

Алгоритм ВИЖЕНЕРА (модифицированный шифр Цезаря)

Декларируем функции

{Private declarations}VCR(PSW, TXT: string; CRT: boolean):string;

Тело функции

{Шифрование, Дешифрование по Виженеру}


function TForm1.VCR(PSW, TXT: string; CRT: boolean): string;, NS:integer; :string; :=''; :=1; i:=1 to length(TXT) do CRT = true then := TMP + chr(ord(TXT[i])+ord(PSW[NS])) := TMP + chr((ord(TXT[i])+256)-ord(PSW[NS]));:= NS + 1; NS > length(PSW) then NS:=1; ;:=TMP; ;


Команда шифрования

TForm1.Button1Click(Sender: TObject);.Text := VCR(Edit1.Text,Memo1.Text, true);;


Команда дешифрования

TForm1.Button2Click(Sender: TObject);.Text := VCR(Edit1.Text,Memo2.Text,false);;


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


Декларирование функции


{ Private declarations }VCR(PSW,TXT:string; CRT: boolean):string; CZR(PSW,TXT:string; CRT: boolean):string;


Тело функции

TForm1.CZR(PSW,TXT:string; CRT: boolean):string;, NS:integer; :string; :=''; :=1; i:=1 to length(TXT) do CRT = true then := TMP + Chr((Ord(TXT[i]) + Ord(PSW[NS])) mod 256) := TMP + Chr((Ord(TXT[i]) - Ord(PSW[NS])) mod 256);:= NS + 1; NS > length(PSW) then NS:=1; ;:=TMP; ;


Команда шифрования

TForm1.Button3Click(Sender: TObject);.Text := CZR(Edit1.Text,Memo1.Text, true);;


Команда дешифрования

TForm1.Button4Click(Sender: TObject);.Text := CZR(Edit1.Text,Memo2.Text,false);;


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

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

Шифрование методом XOR


Декларирование функции


{Private declarations}VCR(PSW,TXT:string; CRT: boolean):string; CZR(PSW,TXT:string; CRT: boolean):string; TXT_XOR(PSW,TXT:string):string;

Тело функции

TForm1.TXT_XOR(PSW,TXT:string):string;, NS:integer; :string; :=''; :=1; i:=1 to length(TXT) do := TMP + Chr(Ord(TXT[i]) xor Ord(PSW[NS]));:= NS + 1; NS > length(PSW) then NS:=1; ;:=TMP; ;


Команда шифрования

TForm1.Button5Click(Sender: TObject);.Text := TXT_XOR(Edit1.Text,Memo1.Text);;


Команда дешифрования

TForm1.Button6Click(Sender: TObject);.Text := TXT_XOR(Edit1.Text,Memo2.Text);;


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


. Модель шифровальной машины ЭНИГМА


Особенностью алгоритма ЭНИГМА является сдвиг текущего символа на значение некоторой функции, зависимой от позиции символа в тексте (строке текста). В нашей работе мы применяли функцию сдвига f(x,i) = (Kx * i)^2, где i - порядковый номер символа в строке, Kx - множитель (нечетное число = 0, 1, 3, 5, 7,..., n).

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

Шифрование по таблице ASCII


, (1)


Дешифрование по таблице ASCII


. (2)


Примечание: При Kx = 0 шифрование и дешифрование происходить не будут, так как Ci = Ti + 0 (mod 256) и Ti = Ci - 0 (mod 256).

Для работы мы использовали компоненты SpinEdit (множитель), три компонента Memo 1,2,3 (открытый текст, шифрограмма, дешифрованный текст) и две кнопки Button (1 - шифровать, 2 - дешифровать). (расположили их следующим образом: смотреть рисунок ниже)

Рис. 3. Расположение компонентов в форме


Ниже приводится универсальная функция шифрования и дешифрования текста по описанному алгоритму. Входными параметрами функции являются:- текст или криптограмма, Kx - множитель сдвига и Encrupt - флаг вида операции (true - шифрование, false - дешифрование. Результатом работы функции является текст либо криптограмма.


Декларировала функции


{ Private declarations }EnDeCrupt(Tx:String; Kx:Integer; Encrupt: boolean):String;


Тело функции

TForm1.EnDeCrupt(Tx:String; Kx:Integer; Encrupt: boolean):String;: integer;: String;:=''; i :=1 to Length(Tx) do Encrupt = true then := X + Chr((Ord(Tx[i]) + Round(SQR(i * Kx))) mod 256) := X + Chr((Ord(Tx[i]) - Round(SQR(i * Kx))) mod 256);:= X; ;


Команда шифрования

TForm1.Button1Click(Sender: TObject);.Text := EnDeCrupt(Memo1.Text, SpinEdit1.Value, true);;


Команда дешифрования

TForm1.Button2Click(Sender: TObject);.Text := EnDeCrupt(Memo2.Text, SpinEdit1.Value, false);;


Выполнила шифрование и дешифрование текста при различных значениях множителя.


4. Алгоритм рекурсивного вычисление наибольшего общего делителя


Рекурсивными процедурами (recursive procedure) называются процедуры, вызывающие сами себя.

Наибольшим общим делителем (greatest common divisor, GCD) двух чисел называется наибольшее целое, на которое делятся два числа без остатка. Например, наибольший общий делитель чисел 12 и 9 равен 3. Два числа называются взаимно простыми (relatively prime), если их наибольший общий делитель равен 1.

Математик Эйлер, живший в восемнадцатом веке, обнаружил интересный факт:


Если A нацело делится на B, то GCD(A, B) = A

Иначе GCD(A, B) = GCD(B Mod A, A).


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

Например:

(9, 12)= GCD(12 Mod 9, 9)

GCD(3, 9) = 3


На каждом шаге числа становятся все меньше, так как 1<= B Mod A < A, если A не делится на B нацело. По мере уменьшения аргументов, в конце концов, A примет значение 1. Так как любое число делится на 1 нацело, на этом шаге рекурсия остановится. Таким образом, в какой то момент B разделится на A нацело, и работа процедуры завершится.

Открытие Эйлера закономерным образом приводит к рекурсивному алгоритму вычисления наибольшего общего делителя.

Для выполнения работы использовала два компонента SpinEdit и командная кнопка Button (рис. 4).


Рис. 4

Декларирование функции


{ Private declarations }GCD(A, B:integer): Integer;


Тело функции

TForm1.GCD(A, B:integer): Integer;B Mod A = 0 Then := A := GCD(B mod A, A); ;


Команда вызова функции

TForm1.Button1Click(Sender: TObject);, B, X : integer;:= 12; B := 9; := GCD(A,B); X = 1 then Form1.Caption := 'Нет НОД !' else Form1.Caption := 'НОД = ' + IntToStr(X);;


5. Простые числа


Натуральное число p, большее единицы, называется простым, если оно делится нацело только на 1 и на себя. Основная теорема арифметики гласит, что любое натуральное число n, большее единицы, может быть разложено в произведение простых чисел, причем это разложение единственно с точностью до порядка простых сомножителей. Каноническое разложение натурального числа n имеет вид: , где: p1 < p2 <...< pk - различные простые числа, .

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

Элементарные методы проверки простоты чисел

Пусть n N. Как проверить, является ли n простым?

Метод пробных делений

Если n - составное число, то n = ab, где: 1< a b, причем .

Поэтому для d = 2, 3,..., проверяем, делится ли n на d? Если, делитель числа n не будет найден, то n - простое число. В противном случае будет найден минимальный простой делитель числа n, т.е. мы даже разложим n на два множителя.

Возможны модификации этого метода. Например, мы можем проверить, делится ли n на 2 и на 3, и если нет, то перебираем далее только числа d вида: 1 + 6j и 5+ 6j где, j =1, 2,...

Решето Эратосфена

Если необходимо составить таблицу всех простых чисел в диапазоне чисел 2, 3,..., N, то нужно в начале вычеркнуть все числа, делящиеся на 2, кроме 2. Затем взять число 3 и вычеркнуть все последующие числа, делящиеся на 3. Затем взять следующее, не вычеркнутое число (т. е. 5) и вычеркнуть все последующие делящиеся на него числа, и так далее.

В итоге останутся лишь простые числа.

Для работы использовала компонент Mеmo и командную кнопку Button, в обработчике события OnClick которой реализуется вычисление (Рис. 5).


Рис. 5


Текст программы, демонстрирующей создание таблицы простых чисел в диапазоне 2 - 255.


procedure TForm1.Button1Click(Sender: TObject);N = 255; NP = set of 2..N; : NP;,K,L: integer;.Clear; .Lines.Add('Простые числа меньшие N,: ');:=[2..N]; := trunc(sqrt(N+1));:= 1;K <= L do //Выполнять цикл до K <= LK := K+1 until K in simple; .Lines.Add(intToStr(K)); i := 2 to N div K do simple := simple - [K*i]; ;K := L+2 to N do K in simple then Memo1.Lines.Add(intToStr(K));;


Тест на основе малой теоремы Ферма

Для проверки простоты чисел n порядка метод пробных делений уже неприменим. Следующий тест основан на малой теореме Ферма: если n простое, то для любого a Z выполнено сравнение:

если же при этом (a, n) = 1, то:

Поэтому для проверки простоты n необходимо выбрать какое-либо a Z и проверить выполнение малой теоремы Ферма за log n арифметических операций (с помощью бинарного возведения в степень в кольце Z/nZ). Если малая теорема Ферма не выполнена, то n является составным числом.

Если же условия выполнены, то предварительно можно сделать вывод о простоте n, поскольку теорема дает лишь необходимое условие. Этот тест является эффективным для обнаружения составных чисел.

Например, для 100-значных чисел n вида: , где проверялось выполнение теста, и первые десять чисел, прошедших этот тест, оказались впоследствии простыми.

Однако существуют такие большие числа, называемые числами Кармайкла, для которых условия теста Ферма выполняются, тем не менее, эти числа являются составными. Наименьшим числом Кармайкла является число 561, которое образуется произведением простых чисел 561=3*11*17. Для обнаружения таких чисел имеются специальные алгоритмы, основанные на теоремах Лагранжа, Эллера и ряда других математиков.

Современные методы

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

В примере использовала компоненты SpinEdit 1,2 (для выбора значений диапазона чисел), компонент Memo - для отображения результатов и командную кнопку Button.


Рис. 6. Расположение элементов в форме


Функция проверки на простоту числа

Так, как функция не декларируется в разделах декларирования то, тело функции расположила в Unit'e выше тела команды теста.

Simple(n:integer):Boolean;k:Boolean; i:integer;:=true;n<>2 theni:=2 to trunc(sqrt(n))+1 don mod i = 0 then:= false;;;:=k;;


Команда теста функции

TForm1.Button1Click(Sender: TObject);:integer;.Clear;i := SpinEdit1.Value to SpinEdit2.Value doSimple(i) = true then Memo1.Lines.Add(IntToStr(i));;


. Генератор псевдо случайной последовательности


Генератор псевдослучайных чисел может быть описан рекуррентной формулой:

i = a gi-1 + b (mod m),


где: gi - i-й член последовательности псевдослучайных чисел; a, b, m и g0 - ключевые параметры.

Данная последовательность состоит из целых чисел от 0 до m-1, и если элементы gi и gj совпадут, то последующие участки последовательности также совпадут: gi+1 = gj+1, gi+2 = gj+2, и т.д.

Поэтому последовательность {gi} является периодической, и ее период не превышает m. Для того чтобы период последовательности псевдослучайных чисел, сгенерированной по формуле (1), был максимальным (равным m), параметры формулы (1) должны удовлетворять следующим условиям: и m -взаимно простые числа; a-1 делится на любой простой делитель числа m; a-1 кратно 4, если m кратно 4.

Пример, демонстрирующий работу процедуры: использовала компонент SpinEdit - для ввода стартового (секретного) числа B большего L(255), компонент Memo - для отображения результата и командная кнопка Button (рис. 6).


Рис. 7


Процедура, реализующая алгоритм

RND_CODE(X, M: integer; var RCOD: array of integer);,A: integer;:= M + 1; [0] := X mod 255; i := 1 to M - 1 do [i] := (A*RCOD[i-1] + X) mod 255; ;

Команда создания последовательности псевдо случайных чисел

TForm1.Button1Click(Sender: TObject);: array[1..500] of integer; , X: integer;:= SpinEdit1.Value; _CODE(X,High(A),A); .Clear; i:= 1 to High(A) do .Lines.Add('№ ' + IntToStr(i) + ' Значение числа = ' + IntToStr(A[i]));;


. Шифрование мультипликативным ключом


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

Для реализации программы использовала следующие компоненты (рис. 7):1,2 - ввод начальных значений стартового и мультипликативного ключей;1,2,3 - окна ввода текста, представления шифрограммы и дешифрованного текста; 1,2 - командные кнопки.


Рис. 8. Компоненты, используемые в программе


Глобальные переменные уровня модуля

: TForm1;, MultKey: integer;


Функция шифрования и дешифрования

CCR(const TXT:string; StartKey,MultKey:Integer; CRT:Boolean): string;: Integer;:='';i:=1 to Length(TXT) do:= Result + Chr(Ord(TXT[i]) xor (StartKey shr 8));CRT = true then:= (Ord(Result[i]) + StartKey) * MultKey:=(Ord(TXT[i]) + StartKey) * MultKey;;

Команда шифрования

TForm1.Button1Click(Sender: TObject);:= SpinEdit1.Value; := SpinEdit2.Value; .Text := CCR(Memo2.Text, StartKey, MultKey, true);;


Команда дешифрования

TForm1.Button2Click(Sender: TObject);:= SpinEdit1.Value; // (567) Значение стартового ключа:= SpinEdit2.Value; // (18367) Значение множителя.Text:= CCR(Memo1.Text, StartKey, MultKey, false);;


. Вычисление первообразного корня (алгоритм Эль-Гамаля)


Общие положения

В основе алгоритма Эль-Гамаля лежит процедура открытого распределения ключей, опубликована в 1976 году в работе У. Диффи и М.Э. Хеллмана «Новые направления в криптографии».

Ключи шифрования и дешифрования вычисляются по алгоритму , где P - большое простое число, g - первообразный корень по модулю P. Секретное число a может быть любым целым числом, лучше случайным. Величина числа не ограничена.

Первообразным (примитивным) корнем по модулю P, будет число g < P и взаимно простое с P, принадлежащее показателю d. Показатель d (дискретный логарифм числа g по модулю P при основынии i т.е или ) является наименьшим, натуральным числом, обеспечивающим сравнение . Отсюда следует, что для взаимно простых P и = P-1 чисел показатель (индекс) и следовательно , где: i = 2,3,4,…,P-2. Исходя из того факта, что первым основанием i, (для простого P и взаимно простого ) образующим первый примитивный корень могут быть только числа 2 и 3, следовательно, вычислить первый корень не составляет труда. Например, для модуля P=11, первым корнем будет число 2, так как: = , где: и d = 5 = . Для модуля P = 7 первым корнем будет число 3^3(mod 7) = 6, а вторым корнем будет, 5^3(mod 7) = 6.

Первообразные корни образуют мультипликативную группу кольца , которая представляет ряд чисел, степени которых g0, g1, g2,…g ?(m)-1 представляет собой совокупность всех взаимно простых с m чисел, меньших m. То есть gk пробегает систему вычетов при k = 1, 2,… ?(m), где: ?(m) - функция Эйлера.

В программе использовала компоненты SpinEdit 1,2,3- для ввода чисел, Memo 1,2 - для отображения результатов и командные кнопки Button 1,2. (рис. 9)


Рис. 9

Примечание: Для вычисления значенией действительных чисел в раздел Uses Unitaвключить модуль Math.

Реализация алгоритмов

Simple(n:integer):Boolean;k:Boolean; i:integer;:=true;n<>2 theni:=2 to trunc(sqrt(n))+1 don mod i = 0 then:= false;;;:=k;;IntModPower(A,B,P:integer):integer;:array of integer;:integer;(x,P);[1]:=A mod P;i:=2 to B do[i]:=x[i-1] * A mod P;:=x[B];;TForm1.Button1Click(Sender: TObject);:integer;.Clear;i := SpinEdit1.Value to SpinEdit2.Value doSimple(i) = true then Memo1.Lines.Add(IntToStr(i));;TForm1.Button3Click(Sender: TObject);,d,P: integer;.Clear;:= SpinEdit3.Value;:= (P-1) div 2;i := 2 to P-2 do(IntModPower(i,d,P) = P-1) then.Lines.Add('g = ' + IntToStr(i) + ' (^' + IntToStr(d) + ') = ' + FloatToStr(Power(i,d)));;


. Вычисление значения ХЭШ функции сообщения


Вычисление значения ХЭШ функции выполняется методом посимвольной свертки сообщения в соответствии с алгоритмом: , где: - начальное значение функции, - текущие символы сообщения (таблица ASCII).

Приложение (рис. 1) содержит два поля ввода Edit1 и Edit2, кнопку Button1 и две метки Label1 и Label2. Исполняемый код реализован в обработчике события щелчка кнопки onClick.

Рис. 10 Дизайн приложения



. Криптографический алгоритм Псевдослучайная последовательность ключа


Алгоритм основан на псевдослучайной последовательности:

равной длине сообщения M, значения которой принадлежат алфавиту длиной L. Где: параметр а, взаимно простой с M; ; , i = 1, 2,…,N < M.

При этом общая процедура шифрования имеет вид: или

Приложение (рис. 2), реализующее алгоритм содержит:

Сетку StringGrid1, предназначенную для отображения собственного алфавита, пять полей ввода Edit1 - Edit5, поле ввода секретного числа - SpinEdit1, три кнопки Button1 - Button3 и метки Label1 - label5 статически описывающие назначение полей.

Рис 11. Дизайн приложения.


Личный алфавит описан глобальной константой A.



Для реализации алгоритма использовала три личных метода. Процедура RND_CODE вычисляет последовательность ПСЧ. Функция ALNo возвращает номер символа в алфавите. Функция NoAL возвращает символ, соответствующий номеру символа в алфавите.




Вывод алфавита в сетку выполнила при помощи создания формы в обработчике события onCreate.



Процедура шифрования реализована в обработчике события onClick кнопки Button1.

Процедура дешифрования реализована в обработчике события onClick кнопки Button2.

Процедура очистки полей реализована в обработчике события onClick кнопки Button3.




Теги: Защита информации  Практическое задание  Информационное обеспечение, программирование
Просмотров: 6685
Найти в Wikkipedia статьи с фразой: Защита информации
Назад