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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

«УЛЬЯНОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра «Вычислительная техника»

Отчёт по лабораторной работе №2

«Изучение работы блоковых шифров и способов их объединения»

Вариант №9
Выполнил:

студент группы ИСТд-41

Корнеев А.В.

Проверил:

доцент каф. «Вычислительная техника»

к.т.н. Мартынов А.И.

Ульяновск, 2012 г.

Задание на лабораторную работу

Изучить блочные алгоритмы шифрования: алгоритм перестановки, алгоритм скремблеров, алгоритм замены по таблице, матричный метод преобразования и алгоритм Винжера;
Изучить режимы использования блочных шифров (ECB, CBC, CFB и OFB);
Изучить способы объединения блочных шифров (многократное шифрование, сеть Фейстела);
Реализовать систему и оценить работу алгоритма;

Матричный метод шифрования

Для шифрования матричным методом будем использовать следующий алгоритм:

Исходный текст разбивается на блоки (вектора) заданной длины . Это справедливо также для последнего блока, ему сопоставляется вектор, который начиная с ого элемента заполнен нулями. Таким образом, полученные вектора принадлежат пространству .
Возьмём линейный оператор над пространством , дефект которого равен 0 . Согласно этому имеет отображение . Каждому блоку исходного текста сопоставим его образ , что и будет блоком зашифрованного текста.

Отметим, что при реализации для каждого блока выбирается свой оператор

Оператору всегда сопоставляется матрица размера , которая в силу того, что дефект оператора равен 0, невырожденная и имеет обратную. Таким образом, ,

При дешифровании блоки зашифрованного текста отображаются в пространство обратным оператором с матрицей и .

Режим сцепления блоков

Режим сцепления блоков шифротекста (англ. Cipher Block Chaining, CBC) — один из режимов шифрования для симметричного блочного шифра с использованием механизма обратной связи. Каждый блок открытого текста (кроме первого) побитово складывается по модулю 2 (операция XOR) с предыдущим результатом шифрования.

Шифрование может быть описано следующим образом:

$c_i = e_k \left( p_{i} \oplus c_{i-1} \right)$

где — номера блоков, — вектор инициализации, и — блоки зашифрованного и открытого текстов соответственно, а — функция блочного шифрования. Расшифровка:

$p_i=c_{i-1} \oplus d_k \left( c_{i} \right)$ .

Графически это можно изобразить:

http://upload.wikimedia.org/wikipedia/ru/thumb/7/7a/encryptcbc.png/500px-encryptcbc.png

Шифрование в режиме CBC

http://upload.wikimedia.org/wikipedia/ru/thumb/2/22/decryptcbc.png/500px-decryptcbc.png

Расшифрование в режиме CBC
Особенности:

Наличие механизма распространения ошибки: если при передаче произойдёт изменение одного бита шифротекста, данная ошибка распространится и на следующий блок. Однако на последующие блоки (через один) ошибка не распространится, поэтому режим CBC также называют самовосстанавливающимся;
Неустойчив к ошибкам, связанным с потерей или вставкой битов, если не используется дополнительный механизм выравнивания блоков;
Злоумышленник имеет возможность добавить блоки к концу зашифрованного сообщения, дополняя тем самым открытый текст (однако без ключа получается мусор);
Для очень крупных сообщений (32 Гбайта при длине блока 64 бита) всё-таки возможно применение атак, основанных на структурных особенностях открытого текста.

Выводы

Режим шифрования матрицей обеспечивает высокую криптостойкость при выборе новой случайной матрицы для каждого блока, но это требует значительные временные затраты (в том числе и при дешифровании). Использование CBC позволяет сдерживать ошибки при их возникновении, а также повышает криптостойкость (за исключением крупных сообщений). Контрольная сумма позволяет установить целостность данных при их разшифровки.

Листинг программы

Простые в реализации функции и код графического интерфейса опущен.

Класс Coder: функции шифрования матрицей и гаммирования.

class Coder

{
public static byte[] encodeBlock(byte[] block)

{

DenseVector vector = convertArrayToVector(block);

var encodeVector = MatrixUtils.getRandomDenseMatrix().Multiply(vector);

byte[] result = deconvertArrayFromVector(encodeVector);

return result;

}
public static byte[] decodeBlock(byte[] block)

{

DenseVector vector = new DenseVector(block.Length / 2);

for (int i = 0; i < block.Length; i+=2) {

vector[i/2] = (block[i] << 8) + block[i+1];

}

var decodeVector = MatrixUtils.getRandomDenseMatrix().Inverse().Multiply(vector);

byte[] result = deconvertArrayFromVector(encodeVector);

return result;

}
public static byte[] gammaBlock(byte[] key, byte[] block)

{

int length = Math.Min(key.Length, block.Length);

for (int i = 0; i < length; ++i )

{

block[i] ^= key[i];

}

return block;

}

}

Рассмотрим как это комбинируется, допустим, при шифровании:

private void runCoder_Click(object sender, RoutedEventArgs e)

{

MatrixUtils.Random = new LinearCongruentGenerator(password.Text);

var key = getInitialVector();

bool needCbc = (useCbc.IsChecked == true);

var t = Utils.FileToByteArray(inputFileName.Text);

var sw = new Stopwatch();

//записать пароль

var fs = new FileStream(outputFileName.Text, FileMode.Create);

writePassword(fs);

sw.Start();

//зашифровать

byte checkSum = 0;

for (int i = 0; i < t.Length; i+=9)

{

var temp = new byte[9];

int copyLength = Math.Min(9, t.Length - i);

Array.Copy(t, i, temp, 0, copyLength);

if (needCbc)

{

temp = Coder.gammaBlock(key, temp);

}

temp = Coder.encodeBlock(temp);

checkSum = Crc8.ComputeChecksum(checkSum, temp, 2*copyLength);

fs.Write(temp, 0, copyLength*2);

key = temp;

}

sw.Stop();

//записать контрольную сумму

fs.WriteByte(checkSum);

speed.Text = ((double)t.Length / (sw.ElapsedMilliseconds)).ToString();

fs.Flush();

fs.Close();

}

Контрольная сумма считается по алгоритму CRC8:

public static class Crc8

{

static byte[] table = new byte[256];

// x8 + x7 + x6 + x4 + x2 + 1

const byte poly = 0xd5;

public static byte ComputeChecksum(params byte[] bytes)

{

byte crc = 0;

if (bytes != null && bytes.Length > 0) {

foreach (byte b in bytes) {

crc = table[crc ^ b];

}

return crc;

}
public static byte ComputeChecksum(ulong sum, byte[] bytes, int maxLength = 100)

{

int l = Math.Min(bytes.Length, maxLength);

for (int i = 0; i < l; ++i )

{

sum += bytes[i];

}

return (byte)(sum % byte.MaxValue);

}
static Crc8()

{

for (int i = 0; i < 256; ++i) {

int temp = i;

for (int j = 0; j < 8; ++j) {

if ((temp & 0x80) != 0) {

temp = (temp << 1) ^ poly;

}

else {

temp <<= 1;

}

table[i] = (byte)temp;

}

}

}