Лабораторная - Шифр Плейфера - файл n1.doc

Лабораторная - Шифр Плейфера
Скачать все файлы (285.5 kb.)

Доступные файлы (1):
n1.doc286kb.01.02.2014 07:56скачать

n1.doc



Министерство образования и науки РФ

ГОУ ВПО Череповецкий государственный университет

Институт информационных технологий


Кафедра программного обеспечения ЭВМ

дисциплина: Методы и средства защиты

компьютерной информации
Лабораторная работа №1

Классические шифры


Выполнила: студентка

группы 1ПО – 41

Костерева Елена

Проверила: Юдина О. В.

Череповец, 2009

Задания

  1. Изучить алгоритмы кодирования-декодирования с помощью классических шифров.

  2. Реализовать свой вариант алгоритма кодирования-декодирования согласно варианту (шифр Плейфера)

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


Описание шифра Плейфера

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

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

1. Если два символа биграммы совпадают, добавляем после первого символа «Ь», зашифровываем новую пару символов и продолжаем.

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

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

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

Для расшифровки необходимо использовать инверсию этих четырёх правил.

Блок-схемы алгоритмов


Листинг программы:
unit Unit1;

interface

uses

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

Dialogs, Grids, StdCtrls, XPMan;

type

TForm1 = class(TForm)

StringGrid1: TStringGrid;

Edit2: TEdit;

Button1: TButton;

XPManifest1: TXPManifest;

Button2: TButton;

Label1: TLabel;

Label2: TLabel;

Memo: TMemo;

Label3: TLabel;

Label4: TLabel;

Memo1: TMemo;

Button3: TButton;

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure Button3Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

r:string;

z:boolean;

A:array of byte;

len, k:integer;

implementation
{$R *.dfm}
//---Шифрование Плэйфера---

function PlayfairCrypt(s,key:string):string;

const

MaxX = 6;

MaxY = 6;

RusAlf = 'АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ .,'; //алфавит

var i,j,t,x1,x2,y1,y2 :integer;

M:array[1..MaxY,1..MaxX]of Char; //ключевая матрица

temp:string;
//---Функция поиска символа "z" в ключевой матрице.---

Procedure SimbolPosition(z:char;var x,y:integer);

var i,j:integer;

begin

x:=0;

y:=0;

for i := 1 to MaxY do

for j := 1 to MaxX do

if z=M[i,j] then

begin

x:=j;

y:=i;

exit;

end;

end;
label Metka;

begin

key:=AnsiUpperCase(key);

s:=AnsiUpperCase(s);

len:=2*length(s);

SetLength(A,len);

for i:=1 to len do

A[i]:=0;
//---удаление из строки всех символов, не входящих в алфавит---

temp:='';

for i := 1 to length(s) do

if pos(s[i],RusAlf)<>0 then temp:=temp+s[i];

s:=temp;
//---создание ключевой матрицы---

temp:='';

for i:=1 to length(key) do

if pos(key[i],temp)=0 then temp:=temp+key[i];

for i:=1 to length(RusAlf) do

if pos(RusAlf[i],temp)=0 then temp:=temp+RusAlf[i];

t:=0;

for i:=1 to 6 do

for j:=1 to 6 do

begin

inc(t);

M[i,j]:=temp[t];

Form1.StringGrid1.Cells[j,i]:=temp[t];

end;
//---просмотр строки по парам символов и вставка разделяющего символа---

//---"Ь" в случае, когда в паре попались одинаковые символы---

k:=0;

Metka:

for i:=1 to length(s)div 2 do

begin

if s[2*i-1]=s[2*i] then

begin

insert('Ь',s,2*i);

A[2*i-1-k]:=1;

inc(k);

goto Metka;

end;

end;

//---добавление символа в конец строки, если её длина нечётная---

z:=false;

if length(s) mod 2 = 1 then

begin

if s[length(s)]<>'Ъ' then s:=s+'Ъ'

else s:=s+'Ё';

z:=true;

end;

temp:='';

for i:=1 to length(s)div 2 do

begin

SimbolPosition(s[2*i-1],x1,y1);

SimbolPosition(s[2*i],x2,y2);
//---правило №1---

if y1 = y2 then

begin

inc(x1);

inc(x2);

if x1 > MaxX then x1:=x1-MaxX;

if x2 > MaxX then x2:=x2-MaxX;

temp:=temp+M[y1,x1]+M[y2,x2];

end;

//---правило №2---

if x1 = x2 then

begin

inc(y1);

inc(y2);

if y1 > MaxY then y1:=y1-MaxY;

if y2 > MaxY then y2:=y2-MaxY;

temp:=temp+M[y1,x1]+M[y2,x2];

end;

//---правило №3---

if (x1<>x2) and (y1<>y2) then temp:=temp+M[y1,x2]+M[y2,x1];

end;

PlayfairCrypt:=temp;

r:=temp;

end;

//---дешифрование Плэйфера---

function PlayfairDeCrypt(s,key:string):string;

const

MaxX = 6;

MaxY = 6;

RusAlf = 'АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ .,';

var i,j,t,x1,x2,y1,y2 :integer;

M:array[1..MaxY,1..MaxX]of char; //ключевая матрица

temp:string;
//---функция поиска символа "z" в ключевой матрице---

Procedure SimbolPosition(z:char;var x,y:integer);

var i,j:integer;

begin

x:=0;

y:=0;

for i := 1 to MaxY do

for j := 1 to MaxX do

if z=M[i,j] then

begin

x:=j;

y:=i;

exit;

end;

end;
label Metka;

begin

key:=AnsiUpperCase(key);

s:=AnsiUpperCase(s);
//---удаление из строки всех символов, не входящих в алфавит---

temp:='';

for i := 1 to length(s) do

begin

if pos(s[i],RusAlf)<>0 then temp:=temp+s[i];

end;

s:=temp;
//---создание ключевой матрицы---

temp:='';

for i:=1 to length(key) do

if pos(key[i],temp)=0 then temp:=temp+key[i];

for i:=1 to length(RusAlf) do

if pos(RusAlf[i],temp)=0 then temp:=temp+RusAlf[i];

t:=0;

for i:=1 to 6 do

for j:=1 to 6 do

begin

inc(t);

M[i,j]:=temp[t];

end;

temp:='';

for i:=1 to length(s)div 2 do

begin

SimbolPosition(s[2*i-1],x1,y1);

SimbolPosition(s[2*i],x2,y2);
//---правило №1---

if y1 = y2 then

begin

dec(x1);

dec(x2);

if x1 <= 0 then x1:=x1+MaxX;

if x2 <= 0 then x2:=x2+MaxX;

temp:=temp+M[y1,x1]+M[y2,x2];

end;

//---правило №2---

if x1 = x2 then

begin

dec(y1);

dec(y2);

if y1 <= 0 then y1:=y1+MaxY;

if y2 <= 0 then y2:=y2+MaxY;

temp:=temp+M[y1,x1]+M[y2,x2];

end;

//---правило №3---

if (x1<>x2) and (y1<>y2) then temp:=temp+M[y1,x2]+M[y2,x1];

end;

if z=true then Delete(temp,length(temp),1);

for i:=1 to len do

if A[i]=1 then Delete(temp,(i+1),1);

PlayfairDeCrypt:=temp;

end;
procedure TForm1.FormCreate(Sender: TObject);

var i,j:integer;

begin

for i:=1 to 6 do

begin

Form1.StringGrid1.Cells[i,0]:=IntToStr(i);

Form1.StringGrid1.Cells[0,i]:=IntToStr(i);

end; end;
procedure TForm1.Button1Click(Sender: TObject);

begin

if Memo1.Text='' then

MessageDlg('Введите текст для шифрования/дешифрования',mtWarning,[mbOk],0)

else

if Edit2.Text='' then

MessageDlg('Введите ключ',mtWarning,[mbOk],0)

else

Memo.Text:= PlayfairCrypt(Memo1.Text,Edit2.Text);

end;




procedure TForm1.Button2Click(Sender: TObject);

var z:string;

begin

if Memo1.Text='' then

MessageDlg('Введите текст для шифрования/дешифрования',mtWarning,[mbOk],0)

else

if Edit2.Text='' then

MessageDlg('Введите ключ',mtWarning,[mbOk],0)

else begin

z:=PlayfairDeCrypt(Memo1.Text,Edit2.Text);

Memo.Text:= z;

end;

end;


procedure TForm1.Button3Click(Sender: TObject);

begin

Memo1.Text:=Memo.Text;

Memo.Clear;

end;

end.


Результаты:


рис. 1. Результат шифрования


рис. 2. Результат дешифрования

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

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


рис. 4. Частоты букв для европейских языков


рис. 5. Частоты букв для русского языка
Необходимо также обратить внимание на пары повторяющихся букв. В английском языке чаще всего повторяются буквы ss, ее, tt, ff, 11, mm и оо. В русском языке нн, ии, ее, лл. Таким образом, если шифротекст содержит какие-либо повторяющиеся символы, то можно предположить, что они представляют одну из этих пар.

Если в шифротексте есть пробелы между словами, то необходимо определить слова, состоящие из одной, двух или трех букв. Единственными словами в английском языке, состоящими из одной буквы, являются а и I. Чаще всего встречающимися двухбуквенными словами будут of, to, in, it, is, be, as, at, so, we, he, by, or, on, do, if, me, my, up, an, go, no, us, am. Наиболее часто появляющиеся трехбуквенные слова – the и and.

Устойчивыми являются также частотные характеристики биграмм, триграмм и четырехграмм осмысленных текстов. Неравномерность k-грамм (и даже слов) тесно связана с характерной особенностью открытого текста – наличием в нем большого числа повторений отдельных фрагментов текста: корней, окончаний, суффиксов, слов и фраз. Так, для русского языка такими привычными фрагментами являются наиболее частые биграммы и триграммы: ст, но, ен, то, на, ов, ни, ра, во, ко, сто, ено, нов, тов, ово, ова.

Полезной является информация о сочетаемости букв, то есть о предпочтительных связях букв друг с другом, которую легко извлечь из таблицы частот биграмм. В ней слева и справа от каждой буквы расположены наиболее предпочтительные "соседи" (в порядке убывания частоты соответствующих биграмм). В таких таблицах обычно указывается также доля гласных и согласных букв (в процентах), предшествующих (или следующих за) данной букве.
Вывод: Как и большинство шифров формальной криптографии, шифр Плейфера также может быть легко взломан, если имеется достаточный объем текста. Получение ключа является относительно простым, если известны шифрованный и обычный текст. Но он более устойчив к взлому по сравнению с шифром простой замены, так как затрудняется частотный анализ. Он может быть проведен, но не для 26 возможных символов (латинский алфавит), а для 26х26=676 возможных биграмм. Анализ частоты биграмм возможен, но является значительно более трудным и требует намного большего объема зашифрованного текста.

Учебный текст
© perviydoc.ru
При копировании укажите ссылку.
обратиться к администрации