Практическая работа № 8

Шифрование данных методом замены в симметричных криптосистемах. Криптосистема Хилла.

Криптосистема Хилла - это алгебраический метод, обобщающий аффинную подстановку Цезаря

Е_a,b : Z_m  Z_m,

E_a,b(t) = t at + b(mod m)

для определения n-грамм, был сформулирован Лестером С. Хиллом.

Множество целых Z_m, для которого определены операции сложения, вычитания и умножения по модулю m, является примером кольца. Кольцо R представляет собой алгебраическую систему, в которой определены операции сложения, вычитания и умножения пар элементов. Эта алгебраическая система обладает рядом свойств:

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

• умножение и сложение удовлетворяют ассоциативному и дистрибутивному законам.

Мультипликативное обратное ^-1 элемента  кольца может существовать не всегда. Например, если модуль m = 26, то значе­ния 2^-1(mod 26) и 13^-1(mod 26) не могут существовать.

Если модуль m является простым числом р, то существует обратная величина любого ненулевого элемента t из Z_p (при m = р), поскольку значения

t (mod m), 2t (mod m), 3t (mod m), .... ,(p-1) t (mod m)

различаются, если 1  t  p -1.

Множество Z_p, где р – простое число, является примером алгебраической системы, называемой конечным полем. Ненулевые элементы Z_p образуют мультипликативную группу.

Множество всех n-грамм х = (х₀, х,, х₂,.... x_n-1) с компонентами из кольца Z_m образует векторное пространство Z_m,n над кольцом Z_m. Каждая n-грамма х называется вектором. В векторном про­странстве Z_mn для векторов х определены операции сложения и вычитания по модулю n, а также скалярное умножение вектора на элемент t кольца Z_m . Сложение и скалярное умножение являются операциями, удовлетворяющими коммутативному, ассоциативному и дистрибутивному законам. Вектор х является линейной комбинацией векторов

{х⁽ⁱ⁾: 0 <i < L}, если

х = t₀x⁽⁰⁾ + t₁x⁽¹⁾ +... + t_L-1.,x^(L-¹⁾(mod m).

Линейное преобразование Т является отображением:

T : Z_m,n  Z_m,n,, T : x  y, y=T(x),

которое удовлетворяет условию линейности

T = (tx + sy)-tТ(х) + sТ(у) (mod m) для всех s, t в Z_m и х, у в Z_{m п}.

Линейное преобразование Т может быть представлено матрицей размером nn вида

причем .

Базисом для векторного пространства является набор векторов из {х⁽ⁱ⁾ : 0 < i < L} которые линейно независимы и порождают .Каждый базис для содержит n линейно независи­мых векторов Любой набор из n векторов которые линейно независимы над является базисом.

Пусть является линейным преобразованием, описываемым матрицей, причем .

Если векторы {х⁽ⁱ⁾ 0 < i < n} линейно независимы над тогда их образы {Т(х⁽ⁱ⁾) : 0  i < п} линейно независимы над , только в том случае если определитель матрицы обозначаемый как det (Т) не делится на любое простое р которое делит m. В этом случае преобразование называется обратимым (или невырожденным) линейным преобразованием, имеющим обратное преобразование , где l-единичная матрица. Кроме того, также является линейным преобразованием.

Например, когда m = 26 и матрица преобразования

,

то определитель этой матрицы

det(T) = 9 = 1(mod 2),

det(T) = 9 = 9{mod 13).

Поэтому существует обратное преобразование . Нетрудно убедиться, что

удовлетворяет соотношению .

Пусть является линейным преобразованием на с матрицей

Используем это преобразование для определения биграммной подстановки в английском алфавите {ABCDEFGH..XYZ}. Сначала разобьем n-грамму открытого текста на биграммы, причем выберем n кратным 2. Например, 12-грамма PAYMOREMONEY делится на шесть биграмм:

PA YM OR EM ON EY

Затем в каждой биграмме открытого текста заменим каждую букву ее числовым эквивалентом из таблицы:

.

Преобразование биграмм открытого текста в биграммы , шифртекста осуществляется в соответствии с уравнением

или

где и– вектор столбцы биграмм шифртекста и открытого текста соответственно.

Получаем

, ,

, , .

Заменяя в биграммах шифртекста числа на соответствующие буквы согласно таблицы, получаем 12-грамму шифртекста

ТЕ ЕЕ PJ WQ DP GY

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

В рассмотренном примере матрицы преобразования имели размер 2x2 и шифровались биграммы (пары) букв Хотя буква Е может быть зашифрована по-разному в различных парах исходного сообщения одна и та же пара, например ЕМ будет шифроваться всегда одинаково на протяжении всего исходного текста.

Задание:

1. Используя алгоритм шифрования данных по криптосистеме Хилла, написать программу шифрования и дешифрования произвольного набора символов

.

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Text;

using System.Windows.Forms;

namespace Хилла

{

public partial class Form1 : Form

{

Random rnd = new Random();

int[,] matrica = new int[2, 2];

int[,] obr_matr = new int[2, 2];

public Form1()

{

InitializeComponent();

}

private void Matrix_bt1_Click(object sender, EventArgs e)

{

richTextBox1.Text = "";

int i, j;

int opr = 0;

while (opr != 1)

{

for (i = 0; i < 2; i++)

for (j = 0; j < 2; j++)

matrica[i, j] = rnd.Next(10);

opr = matrica[0, 0] * matrica[1, 1] - matrica[0, 1] * matrica[1, 0];

}

for (i = 0; i < 2; i++)

{

for (j = 0; j < 2; j++)

richTextBox1.Text += matrica[i, j]+" ";

richTextBox1.Text += "\n";

}

//Обратная матрица

for (i = 0; i < 2; i++)

for (j = 0; j < 2; j++)

obr_matr[j, i] = Convert.ToInt32(Math.Pow(-1, (i + j)) * matrica[(1 - i), (1 - j)]);

richTextBox1.Text += "Обратная матрица" + "\n";

for (i = 0; i < 2; i++)

{

for (j = 0; j < 2; j++)

richTextBox1.Text +=obr_matr[i, j] + " ";

richTextBox1.Text += "\n";

}

}

//Шифрование

private void Shifr_bt2_Click(object sender, EventArgs e)

{

if (textBox1.Text.Length % 2 != 0)

textBox1.Text += " ";

string fraza = textBox1.Text;

int dl_frazy = fraza.Length;

int i, j, t, sum = 0;

string alfavit = "абвгдежзийклмнопрстуфхцчшщъыьэюя ";

int dl_alf = alfavit.Length;

int[] index = new int[dl_frazy];

int[] ind_shifr = new int[dl_frazy];

string shifr = "";

for (i = 0; i < dl_frazy; i++)

for (j = 0; j < dl_alf; j++)

{

if (String.Compare(Convert.ToString(fraza[i]), Convert.ToString(alfavit[j])) == 0)

index[i] = j;

}

for (t = 0; t < dl_frazy; t += 2)

for (i = 0; i < 2; i++)

{

sum = 0;

for (j = 0; j < 2; j++)

sum += index[t + j] * matrica[i, j];

ind_shifr[t + i] = sum % dl_alf;

}

for (i = 0; i < dl_frazy; i++)

shifr += alfavit[ind_shifr[i]];

textBox2.Text = shifr;

}

//Дешифрование

private void Deshifr_bt3_Click(object sender, EventArgs e)

{

string shifr = textBox2.Text;

int dl_shifra = shifr.Length;

if (dl_shifra % 2 != 0)

shifr += " ";

int i, j, t, sum = 0;

string alfavit = "абвгдежзийклмнопрстуфхцчшщъыьэюя ";

int dl_alf = alfavit.Length;

int[] index = new int[dl_shifra];

int[] ind_deshifr = new int[dl_shifra];

string deshifr = "";

for (i = 0; i < dl_shifra; i++)

for (j = 0; j < dl_alf; j++)

{

if (String.Compare(Convert.ToString(shifr[i]), Convert.ToString(alfavit[j])) == 0)

index[i] = j;

}

for (t = 0; t < dl_shifra; t += 2)

for (i = 0; i < 2; i++)

{

sum = 0;

for (j = 0; j < 2; j++)

sum += index[t + j] * obr_matr[i, j];

ind_deshifr[t + i] = sum % dl_alf;

if (ind_deshifr[t + i] < 0)

ind_deshifr[t + i] += dl_alf;

}

for (i = 0; i < dl_shifra; i++)

deshifr += alfavit[ind_deshifr[i]];

textBox3.Text = deshifr;

}

}

}

Алгоритм Шеннона — Фано — один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Роберт Фано. Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже и является логическим продолжением алгоритма Шеннона. Алгоритм использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. Коды Шеннона — Фано — префиксные, то есть никакое кодовое слово не является префиксом любого другого. Это свойство позволяет однозначно декодировать любую последовательность кодовых слов.