Лабораторная работа по дисциплине «Защита информации»: Криптографический шифр на основе биграмм

Московский государственный институт электроники и математики

Кафедра Информационно-Коммуникационных Технологий

Лабораторная работа по дисциплине «Защита информации»:

Криптографический шифр на основе биграмм
Выполнил: студент группы С-84, Новиков Р.О.

Москва 2008

Содержание

Введение	3
Описание модели на формальном языке	4
Описание алгоритма шифрования	5
Примеры шифрования информации	6
Листинг	7

1. Введение

Разработанный алгоритм производит не последовательное шифрование всего открытого текста целиком, а последовательно зашифровывает n-граммы (в нашем случае десятисловия). Открытый текст превращается в набор из биграмм, их частотного спектра и позиций, на которых они встречаются в тексте. Данная информация шифруется и готова к передаче по каналам данных. Таким образом, зашифрованная по данному алгоритму информация не поддается классическим способам «взлома», например таким, как частотный анализ.

2. Описание модели на формальном языке

Каждый текст, состоящий из k слов можно разбить на k/n n-грамм. В свою очередь, каждая полученная n-грамма разбивается на набор из биграмм. Следовательно, мы получаем модель текста T={x1, … xi, … xl} – где x – это n-грамма, l = k/n, где k – размерность множества слов текста T, а n – размерность n-граммы (в словах). Можно полагать, что для ∀xi ∃{b1,, … bi, … bm }, где b – это биграмма (уникальная), m – f/2, где f – размерность n-граммы xi (в буквах). Справедливо утверждение, что для ∀ уникальной ненулевой биграммы xj ∃ единственный, ненулевой набор Bj. Но, набор Bj может соответствовать нескольким биграммам одновременно. Любой набор неуникальных биграмм B (т.е. такой набор, где bi может совпадать с bj) можно представить в виде списка B’ уникальных биграмм, где каждой биграмме bi будет поставлено некоторое число α, соответствующее частоте употребления биграммы bi в наборе B. На число α накладывается ряд ограничений, во-первых α – целое натуральное число и α < f/2, где f – размерность n-граммы в буквах. Также введем понятие позиций биграммы, которое характеризуется набором {a1 … aα}. Число ai – это целое натуральное число, кратное 2, соответствующее позиции биграммы bj в n-грамме xi. Размерность списка позиций биграммы всегда равна α.

Из вышесказанного следует, что базовой единицей текста T будет являться не предложение, а n-грамма, базовой единицей которой будет являться биграмма, которая, в свою очередь, описывается тремя параметрами: значение биграммы, частота употребления биграммы, набор позиций биграммы в n-грамме. Набор из таких кортежей, состоящий из этих трех неуникальных параметров, однозначно характеризует текст. Следовательно, имеет смысл шифровать именно этот кортеж. В ходе шифрования кортеж из 3-х элементов превращается в кортеж из 2-х элементов, т.к. значение биграммы и её частотность превращаются в одно число. После этого числа всегда идет набор из позиций биграммы. Данные кортежи могут быть отсортированы в любом порядке, что усложняет задачу для дешифровщика.

3. Описание алгоритма шифрования

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

Значение биграммы

Значение биграммы переводится в уникальное число β, это натуральное число и β =< ε2, где ε – количество букв в используемом алфавите. К числу β прибавляется число Ω - некоторое натуральное число, отчасти выполняющее функции сигнатуры ключа.

Ω= k1kv

Где k1 и kv - соответственно первая и последняя цифра в ключе K.

В зависимости от места биграммы в списке биграмм B к ней будет применяться четный или нечетный способ нормализации (упаковки). Для обеспечения крипто стойкости все члены кортежа приводятся к единому виду – натурального числа > 10.000 и < 1000.000.

Четный и нечетный способ нормализации отличаются лишь одним: к Ω последовательно прибавляется число µ пока не будет выполнено условие Ω + µ . Число µ = , где j < v, при четном способе нормализации и , где j > 0, при нечетном. Т.е. µ представляет собой последовательность цифр, входящих в ключ К.

Частотность биграммы

Частотность «приклеивается» к зашифрованному значению биграммы в определенное место p, зависящее от позиции биграммы в списке B. Зависимость от позиции определяется ключом K, а конкретно p = kj mod 3, где kj - цифра ключа K, j=o mod v, где o – позиция биграммы в списке B, v – размерность ключа K.

Позиции биграммы

Позиция биграммы подвергается нормализации (упаковке), схожей с той, что была описана для значения биграммы. Однако, имеется ряд различий: к числу λ = позиции биграммы, последовательно прибавляется число ε = - где kikj выбранные определенным образом цифры из ключа K, пока λ + ε < 2000. Далее к этому числу приклеивается на позицию p случайное число в интервале от 0…9, для создания шума и нормализации.

4. Примеры шифрования информации

Пример 1.

Открытый текст: roman novikov student avt s84

Ключ: 948873

Шифрограмма:

91538 72416 92195 74412 93314 74064 93915 73976 101063 74300 110085 77398 110215 73394 96143 74508 96517 74260 96928 74184 74188 101317 74510 110360 71402 110389 71406 20178 74522

Пример 2.

Открытый текст: the quick brown fox jumping over lazy dogs

Ключ: 438791

Шифрограмма:

87191 91685 41418 95177 88512 91513 45121 91481 41597 93159 46139 91983 90161 91969 41698 93149 91114 91617 47155 91363 41790 95173 48109 91145 92151 91551 41902 91165 93615 91547 49184 91671 41985 99155 50159 91447 95163 91343 51341 98161 97813 91719 58110 91275

Пример 3.

Открытый текст: moscow is the capital of russia

Ключ: 384721

Шифрограмма:

31888 27168 48011 21532 51142 21850 43144 21658 52314 21318 44126 21360 41444 27142 53411 21594 54149 21640 45181 21466 54814 21466 46111 21956 41618 21148 55412 21684 21139 21544 52175 21462

5.Листинг

Шифратор

$ABC = "abcdefghijeklmnopqrstuvwxyz1234567890 "; //38

$key_val_first = substr($KEY, 0, 1);

$key_val_last = substr($KEY, strlen($KEY) - 1, 1);

$KEY_SIGNATUR += $key_val_first * $key_val_last;

for($i = 1; $i <= 38; $i++)

{

$liter_one = substr($ABC, $i - 1, 1);

for($j = 1; $j <= 38; $j++)

{

$liter_cnt++;

$liter_second = substr($ABC, $j - 1, 1);

$liters = $liter_one.$liter_second;

$ABC_FRONT_INDEX[$liters] = $liter_cnt + $KEY_SIGNATUR;

$ABC_BACK_INDEX[$liter_cnt + $KEY_SIGNATUR] = $liters;

}

}

$TEXT_OPEN .= " ";

for($i = 0; $i < strlen($TEXT_OPEN); $i += 2)

{

$liter = substr($TEXT_OPEN, $i, 1);

$liter_next = substr($TEXT_OPEN, $i + 1, 1);

$par_num = $ABC_FRONT_INDEX[$liter.$liter_next];

$bigrams[$par_num]++;

$bigrams_pos[$par_num][$i] = 1;

}

ksort($bigrams);

$j = 0;

foreach($bigrams as $key1 => $val1)

{

if ($j >= strlen($KEY))

$j = 0;

$i = 0;

$plussum = 0;

while (($plussum + $key1) < 2000)

{

$i++;

if (substr($KEY, $j, 1) % 2 == 0)

$plussum = substr($KEY, strlen($KEY) - $i, $i);

else

$plussum = substr($KEY, 0, $i);

}

$code1 = $plussum + $key1;

$insert_pos = substr($KEY, $j, 1) % 3 + 1;

$code_frq = substr($code1, 0, $insert_pos).$val1.substr($code1, $insert_pos);

$j++;

$code_general .= $code_frq." ";

foreach($bigrams_pos[$key1] as $key2 => $val2)

{

$z = 0;

$plussum = 0;

while (($plussum + $key2) < 2000)

{

$z++;

$plussum = substr($KEY, strlen($KEY) - $z, $z).substr($KEY, 0, $z);

}

$code2 = $plussum + $key2;

//$code_pos = $code2;

$code_pos = substr($code2, 0, $insert_pos).mt_rand(1, 9).substr($code2, $insert_pos);

$code_general .= $code_pos." ";

}

?>
Дешифратор

$ABC = "abcdefghijeklmnopqrstuvwxyz1234567890 "; //38

$key_val_first = substr($KEY, 0, 1);

$key_val_last = substr($KEY, strlen($KEY) - 1, 1);

$KEY_SIGNATUR += $key_val_first * $key_val_last;

for($i = 1; $i <= 38; $i++)

{

$liter_one = substr($ABC, $i - 1, 1);

for($j = 1; $j <= 38; $j++)

{

$liter_cnt++;

$liter_second = substr($ABC, $j - 1, 1);

$liters = $liter_one.$liter_second;

$ABC_FRONT_INDEX[$liters] = $liter_cnt + $KEY_SIGNATUR;

$ABC_BACK_INDEX[$liter_cnt + $KEY_SIGNATUR] = $liters;

}

}

$num_array = split(" ", $TEXT_OPEN);

for($i = 0; $i < sizeof($num_array) - 1; $i++)

{

if ($frq_num >= strlen($KEY))

$frq_num = 0;

$num = $num_array[$i];

$insert_pos = substr($KEY, $frq_num, 1) % 3 + 1;

$insert_num = substr($num, $insert_pos, 1);

$code_clear = substr($num, 0, $insert_pos).substr($num, $insert_pos + 1);

$k = 0;

$minus_sum = 0;

while (($code_clear - $minus_sum) > 2000)

{

$k++;

if (substr($KEY, $frq_num, 1) % 2 == 0)

$minus_sum = substr($KEY, strlen($KEY) - $k, $k);

else

$minus_sum = substr($KEY, 0, $k);

$num_res = $code_clear - $minus_sum;

}

$g = 0;

while($g < $insert_num)

{

$i++;

$pos = $num_array[$i];

$pos_clear = substr($pos, 0, $insert_pos).substr($pos, $insert_pos + 1);

$z = 0;

$minus_sum = 0;

while (($pos_clear - $minus_sum) > 2000)

{

$z++;

$minus_sum = substr($KEY, strlen($KEY) - $z, $z).substr($KEY, 0, $z);

//print "

----> $plussum";

}

$pos_res = $pos_clear - $minus_sum;

$POS_ARRAY[$pos_res] = $num_res;

$g++;

}

$frq_num++;

}

foreach($POS_ARRAY as $key => $val)

$RES_ARRAY[$key] = $val;

ksort($RES_ARRAY);