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

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

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

Рисунок 1

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

procedure TForm1. Button3Click (Sender: TObject);

const

A: array[0.15] of char = ('0','1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F');

var

i: integer;

begin

Form1.Caption := '';

for i := 0 to 15 do

Form1.Caption := Form1. Caption + A[i] + ' ';

end;

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

procedure TForm1. Button1Click (Sender: TObject);

var

A: array[1.32] of char;

i: integer;

begin

{Строем алфавит}

i := 1;

A[i] := 'А';

Repeat

inc (i, 1);

A[i] := Succ (A[i-1]);

until i >= 32;

Form1.Caption := '';

for i := 1 to 32 do

Form1.Caption := Form1. Caption + A[i] + ' ';

end;

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

procedure TForm1. Button2Click (Sender: TObject);

var

A: array[1.32] of char;

i: integer;

begin

i := 1;

A[i] := 'Я';

Repeat

inc (i, 1);

A[i] := Pred (A[i-1]);

until i >= 32;

Form1.Caption := '';

for i := 1 to 32 do // в цикле от 1 до 32

Form1.Caption := Form1. Caption + A[i] + ' ';

end;

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

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

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

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

{Private declarations}

function VCR (PSW, TXT: string; CRT: boolean):string;

Тело функции

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

function TForm1. VCR (PSW, TXT: string; CRT: boolean): string;

var

i, NS: integer;

TMP:string;

begin

tmp:='';

NS:=1;

for i:=1 to length (TXT) do

begin

if CRT = true then

TMP := TMP + chr (ord (TXT[i])+ord (PSW[NS]))

else

TMP := TMP + chr ((ord (TXT[i])+256)-ord (PSW[NS]));

NS := NS + 1;

if NS > length (PSW) then NS:=1;

end;

Result:=TMP;

end;

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

procedure TForm1. Button1Click (Sender: TObject);

begin

Memo2.Text := VCR (Edit1.Text, Memo1. Text, true);

end;

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

procedure TForm1. Button2Click (Sender: TObject);

begin

Memo3.Text := VCR (Edit1.Text, Memo2. Text, false);

end;

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

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

{ Private declarations }

function VCR (PSW, TXT: string; CRT: boolean):string;

function CZR (PSW, TXT: string; CRT: boolean):string;

Тело функции

function TForm1. CZR (PSW, TXT: string; CRT: boolean):string;

var

i, NS: integer;

TMP:string;

begin

tmp:='';

NS:=1;

for i:=1 to length (TXT) do

begin

if CRT = true then

TMP := TMP + Chr ((Ord (TXT[i]) + Ord (PSW[NS])) mod 256)

else

TMP := TMP + Chr ((Ord (TXT[i]) — Ord (PSW[NS])) mod 256);

NS := NS + 1;

if NS > length (PSW) then NS:=1;

end;

Result:=TMP;

end;

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

procedure TForm1. Button3Click (Sender: TObject);

begin

Memo2.Text := CZR (Edit1.Text, Memo1. Text, true);

end;

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

procedure TForm1. Button4Click (Sender: TObject);

begin

Memo3.Text := CZR (Edit1.Text, Memo2. Text, false);

end;

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

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

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

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

{Private declarations}

function VCR (PSW, TXT: string; CRT: boolean):string;

function CZR (PSW, TXT: string; CRT: boolean):string;

function TXT_XOR (PSW, TXT: string):string;

Тело функции

function TForm1. TXT_XOR (PSW, TXT: string):string;

var

i, NS: integer;

TMP:string;

begin

tmp:='';

NS:=1;

for i:=1 to length (TXT) do

begin

TMP := TMP + Chr (Ord (TXT[i]) xor Ord (PSW[NS]));

NS := NS + 1;

if NS > length (PSW) then NS:=1;

end;

Result:=TMP;

end;

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

procedure TForm1. Button5Click (Sender: TObject);

begin

Memo2.Text := TXT_XOR (Edit1.Text, Memo1. Text);

end;

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

procedure TForm1. Button6Click (Sender: TObject);

begin

Memo3.Text := TXT_XOR (Edit1.Text, Memo2. Text);

end;

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

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

Особенностью алгоритма ЭНИГМА является сдвиг текущего символа на значение некоторой функции, зависимой от позиции символа в тексте (строке текста). В нашей работе мы применяли функцию сдвига 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. Расположение компонентов в форме Ниже приводится универсальная функция шифрования и дешифрования текста по описанному алгоритму. Входными параметрами функции являются:

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

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

{ Private declarations }

function EnDeCrupt (Tx:String; Kx: Integer; Encrupt: boolean):String;

Тело функции

function TForm1. EnDeCrupt (Tx:String; Kx: Integer; Encrupt: boolean):String;

var

i: integer;

X: String;

begin

X:='';

for i :=1 to Length (Tx) do

if Encrupt = true then

X := X + Chr ((Ord (Tx[i]) + Round (SQR (i * Kx))) mod 256)

Else

X := X + Chr ((Ord (Tx[i]) — Round (SQR (i * Kx))) mod 256);

Result := X;

end;

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

procedure TForm1. Button1Click (Sender: TObject);

begin

Memo2.Text := EnDeCrupt (Memo1.Text, SpinEdit1. Value, true);

end;

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

procedure TForm1. Button2Click (Sender: TObject);

begin

Memo3.Text := EnDeCrupt (Memo2.Text, SpinEdit1. Value, false);

end;

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

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).

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

Например:

GCD (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

{ Private declarations }

Function GCD (A, B: integer): Integer;

Тело функции

Function TForm1. GCD (A, B: integer): Integer;

begin

If B Mod A = 0 Then

Result := A

else

Result := GCD (B mod A, A);

end;

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

procedure TForm1. Button1Click (Sender: TObject);

var

A, B, X: integer;

begin

A := 12; B := 9;

X := GCD (A, B);

if X = 1 then Form1. Caption := 'Нет НОД !' else Form1. Caption := 'НОД = ' + IntToStr (X);

end;

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);

const N = 255;

type NP = set of 2. N;

var

simple: NP;

i, K, L: integer;

begin

Memo1.Clear;

Memo1.Lines.Add ('Простые числа меньшие N: ');

simple :=[2.N];

L := trunc (sqrt (N+1));

K := 1;

while K <= L do //Выполнять цикл до K <= L

begin

repeat K := K+1 until K in simple;

Memo1.Lines.Add (intToStr (K));

for i := 2 to N div K do simple := simple — [K*i];

end;

for K := L+2 to N do

if K in simple then Memo1.Lines.Add (intToStr (K));

end;

Тест на основе малой теоремы Ферма Для проверки простоты чисел 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 выше тела команды теста.

function Simple (n:integer):Boolean;

var k: Boolean; i: integer;

begin

k:=true;

if n<>2 then

for i:=2 to trunc (sqrt (n))+1 do

if n mod i = 0 then

begin

k := false;

break;

end;

Result:=k;

end;

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

procedure TForm1. Button1Click (Sender: TObject);

var

i:integer;

begin

Memo1.Clear;

for i := SpinEdit1. Value to SpinEdit2. Value do

if Simple (i) = true then Memo1.Lines.Add (IntToStr (i));

end;

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

g_i = a g_i-1 + b (mod m),

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

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

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

b и m —взаимно простые числа; a-1 делится на любой простой делитель числа m; a-1 кратно 4, если m кратно 4.

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

Рис. 7

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

procedure RND_CODE (X, M: integer; var RCOD: array of integer);

var

i, A: integer;

begin

A:= M + 1;

RCOD[0] := X mod 255;

for i := 1 to M — 1 do

RCOD[i] := (A*RCOD[i-1] + X) mod 255;

end;

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

procedure TForm1. Button1Click (Sender: TObject);

var

A: array[1.500] of integer;

i, X: integer;

begin

X := SpinEdit1. Value;

RND_CODE (X, High (A), A);

Memo1.Clear;

for i:= 1 to High (A) do

Memo1.Lines.Add ('№ ' + IntToStr (i) + ' Значение числа = ' + IntToStr (A[i]));

end;

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

Для реализации программы использовала следующие компоненты (рис. 7):

SpinEdit 1,2 — ввод начальных значений стартового и мультипликативного ключей;

Memo 1,2,3 — окна ввода текста, представления шифрограммы и дешифрованного текста;

Button 1,2 — командные кнопки.

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

var

Form1: TForm1;

StartKey, MultKey: integer;

implementation

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

function CCR (const TXT: string; StartKey, MultKey: Integer; CRT: Boolean): string;

var

i: Integer;

begin

Result:='';

for i:=1 to Length (TXT) do

begin

Result := Result + Chr (Ord (TXT[i]) xor (StartKey shr 8));

if CRT = true then

StartKey := (Ord (Result[i]) + StartKey) * MultKey

else

StartKey:=(Ord (TXT[i]) + StartKey) * MultKey;

end;

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

procedure TForm1. Button1Click (Sender: TObject);

begin

StartKey := SpinEdit1. Value;

MultKey := SpinEdit2. Value;

Memo3.Text := CCR (Memo2.Text, StartKey, MultKey, true);

end;

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

procedure TForm1. Button2Click (Sender: TObject);

begin

StartKey := SpinEdit1. Value; // (567) Значение стартового ключа

MultKey := SpinEdit2. Value; // (18 367) Значение множителя

Memo2.Text:= CCR (Memo1.Text, StartKey, MultKey, false);

end;

8. Вычисление первообразного корня (алгоритм Эль-Гамаля) Общие положения В основе алгоритма Эль-Гамаля лежит процедура открытого распределения ключей, опубликована в 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³(mod 7) = 6, а вторым корнем будет, 5³(mod 7) = 6.

Первообразные корни образуют мультипликативную группу кольца, которая представляет ряд чисел, степени которых g⁰, g¹, g²,…g ^{ц (m) —1} представляет собой совокупность всех взаимно простых с m чисел, меньших m. То есть g^k пробегает систему вычетов при k = 1, 2,… ц (m), где: ц (m) — функция Эйлера.

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

Рис. 9

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

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

function Simple (n:integer):Boolean;

var k: Boolean; i: integer;

begin

k:=true;

if n<>2 then

for i:=2 to trunc (sqrt (n))+1 do

if n mod i = 0 then

begin

k := false;

break;

end;

Result:=k;

end;

function IntModPower (A, B, P:integer):integer;

var

x:array of integer;

i:integer;

begin

SetLength (x, P);

x[1]: =A mod P;

for i:=2 to B do

x[i]: =x[i-1] * A mod P;

Result:=x[B];

end;

procedure TForm1. Button1Click (Sender: TObject);

var

i:integer;

begin

Memo1.Clear;

for i := SpinEdit1. Value to SpinEdit2. Value do

if Simple (i) = true then Memo1.Lines.Add (IntToStr (i));

end;

procedure TForm1. Button3Click (Sender: TObject);

var

i, d, P: integer;

begin

Memo2.Clear;

P := SpinEdit3. Value;

d := (P-1) div 2;

for i := 2 to P-2 do

if (IntModPower (i, d, P) = P-1) then

Memo2.Lines.Add ('g = ' + IntToStr (i) + ' (^' + IntToStr (d) + ') = ' + FloatToStr (Power (i, d)));

end;

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

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

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

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.