Поговорим опять о шифровании. На этот раз рассмотрим алгоритм DES. DES — алгоритм блочного шифрования на основе сети Фейстеля, которая проходится 16 раз. DES может использоваться в нескольких режимах; мы рассмотрим режим «электронной кодовой книги» — ECB (electronic code book). Разработку будем вести на языке программирования C#.
Алгоритм DES. Описание
DES — блочный алгоритм, то есть при шифровании исходное сообщение переводится в двоичный код, а затем разбивается на блоки и каждый блок отдельно зашифровывается (расшифровывается). По стандарту (принят в 1977 году) размер блока DES равен 64 бита, то есть используя 8-ми битовую кодировку ASCII, применяемую в те времена, получим в одном блоке — 8 символов.
Теперь же в основном используется 16-ти битная кодировка Юникода (UTF-16), поэтому, чтобы сохранить длину блока равную 8-ми символам, увеличим размер блока DES до 128 бит.
Алгоритм DES. Шаги
Итак, для того, чтобы зашифровать сообщение алгоритмом DES, необходимо выполнить следующую последовательность шагов:
- довести исходное сообщение до такого размера (в битах), чтобы оно нацело делилось на размер блока (sizeOfBlock = 128 бит);
- разделить исходное сообщение на блоки;
- довести длину ключа до длины половины блока;
- перевести ключ в бинарный формат (в нули и единицы);
- провести над каждым блоком прямое преобразование сетью Фейстеля в течении 16-ти раундов. После каждого раунда необходимо выполнять циклический сдвиг ключа на заданное количество символов;
- соединить все блоки вместе; таким образом получим сообщение, зашифрованное алгоритмом DES.
Расшифровка DES производится по аналогии. Используется обратное преобразование сетью Фейстеля.
Алгоритм DES. Сеть Фейстеля
Сеть Фейстеля используется в алгоритме DES для зашифровывания (прямое преобразование сетью) и расшифровывания (обратное преобразование). Эти преобразования изображены на рисунках 1 и 2 соответственно.
Рисунок 1. Прямое преобразование сетью Фейстеля
Рисунок 2. Обратное преобразование сетью Фейстеля
Чтобы вам было понятнее, давайте рассмотрим один раунд прямого преобразования сетью Фейстеля.
На i-й итерации исходный блок делится пополам — левая часть обозначается L, правая R. Над R и ключом ki вычисляется какая-либо выбранная логическая функция f (мы будем использовать XOR). Затем выполняется вычисление логической операции «исключающее или» над L и вычисленным ранее значением функции (L xor f). Старое значение R переносится в левую часть блока, а в правую часть заносится значение L xor f. И последняя операция раунда — нужно выполнить циклический сдвиг ключа: keyi+1 = keyi >> shiftKey (при расшифровке keyi-1 = keyi << shiftKey); shiftKey — количество символов, на которое необходимо циклически сдвинуть ключ.
Алгоритм DES. Программная реализация
Создадим для разрабатываемой программы следующий интерфейс (рисунок 3).
Рисунок 3. Пользовательский интерфейс программы
Объявим ряд переменных, требующихся для программы.
|
1 2 3 4 5 6 7 8 |
private const int sizeOfBlock = 128; //в DES размер блока 64 бит, но поскольку в unicode символ в два раза длинее, то увеличим блок тоже в два раза private const int sizeOfChar = 16; //размер одного символа (in Unicode 16 bit) private const int shiftKey = 2; //сдвиг ключа private const int quantityOfRounds = 16; //количество раундов string[] Blocks; //сами блоки в двоичном формате |
Напишем методы, реализующие необходимый функционал для программы DES.
Метод, доводящий строку до такого размера, чтобы она делилась на sizeOfBlock. Размер увеличивается с помощью добавления к исходной строке символа «решетка».
|
1 2 3 4 5 6 7 |
private string StringToRightLength(string input) { while (((input.Length * sizeOfChar) % sizeOfBlock) != 0) input += "#"; return input; } |
Метод, разбивающий строку в обычном (символьном) формате на блоки.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
private void CutStringIntoBlocks(string input) { Blocks = new string[(input.Length * sizeOfChar) / sizeOfBlock]; int lengthOfBlock = input.Length / Blocks.Length; for (int i = 0; i < Blocks.Length; i++) { Blocks[i] = input.Substring(i * lengthOfBlock, lengthOfBlock); Blocks[i] = StringToBinaryFormat(Blocks[i]); } } |
Метод, разбивающий строку в двоичном формате на блоки.
|
1 2 3 4 5 6 7 8 9 |
private void CutBinaryStringIntoBlocks(string input) { Blocks = new string[input.Length / sizeOfBlock]; int lengthOfBlock = input.Length / Blocks.Length; for (int i = 0; i < Blocks.Length; i++) Blocks[i] = input.Substring(i * lengthOfBlock, lengthOfBlock); } |
Метод, переводящий строку в двоичный формат.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
private string StringToBinaryFormat(string input) { string output = ""; for (int i = 0; i < input.Length; i++) { string char_binary = Convert.ToString(input[i], 2); while (char_binary.Length < sizeOfChar) char_binary = "0" + char_binary; output += char_binary; } return output; } |
Метод, доводящий длину ключа до нужной длины.
|
1 2 3 4 5 6 7 8 9 10 |
private string CorrectKeyWord(string input, int lengthKey) { if (input.Length > lengthKey) input = input.Substring(0, lengthKey); else while (input.Length < lengthKey) input = "0" + input; return input; } |
Один раунд шифрования алгоритмом DES.
|
1 2 3 4 5 6 7 |
private string EncodeDES_One_Round(string input, string key) { string L = input.Substring(0, input.Length / 2); string R = input.Substring(input.Length / 2, input.Length / 2); return (R + XOR(L, f(R, key))); } |
Один раунд расшифровки алгоритмом DES.
|
1 2 3 4 5 6 7 |
private string DecodeDES_One_Round(string input, string key) { string L = input.Substring(0, input.Length / 2); string R = input.Substring(input.Length / 2, input.Length / 2); return (XOR(f(L, key), R) + L); } |
XOR двух строк с двоичными данными.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
private string XOR(string s1, string s2) { string result = ""; for (int i = 0; i < s1.Length; i++) { bool a = Convert.ToBoolean(Convert.ToInt32(s1[i].ToString())); bool b = Convert.ToBoolean(Convert.ToInt32(s2[i].ToString())); if (a ^ b) result += "1"; else result += "0"; } return result; } |
Шифрующая функция f. Мы решили использовать в качестве нее также логическую операцию XOR.
|
1 2 3 4 |
private string f(string s1, string s2) { return XOR(s1, s2); } |
Вычисление ключа для следующего раунда шифрования DES. Циклический сдвиг >> shiftKey.
|
1 2 3 4 5 6 7 8 9 10 |
private string KeyToNextRound(string key) { for (int i = 0; i < shiftKey; i++) { key = key[key.Length - 1] + key; key = key.Remove(key.Length - 1); } return key; } |
Вычисление ключа для следующего раунда расшифровки DES. циклический сдвиг << shiftKey.
|
1 2 3 4 5 6 7 8 9 10 |
private string KeyToPrevRound(string key) { for (int i = 0; i < shiftKey; i++) { key = key + key[0]; key = key.Remove(0, 1); } return key; } |
Метод, переводящий строку с двоичными данными в символьный формат.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
private string StringFromBinaryToNormalFormat(string input) { string output = ""; while (input.Length > 0) { string char_binary = input.Substring(0, sizeOfChar); input = input.Remove(0, sizeOfChar); int a = 0; int degree = char_binary.Length - 1; foreach (char c in char_binary) a += Convert.ToInt32(c.ToString()) * (int)Math.Pow(2, degree--); output += ((char)a).ToString(); } return output; } |
Теперь реализуем функционал кнопки «Зашифровать».
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
private void buttonEncrypt_Click(object sender, EventArgs e) { if (textBoxEncodeKeyWord.Text.Length > 0) { string s = ""; string key = textBoxEncodeKeyWord.Text; StreamReader sr = new StreamReader("in.txt"); while (!sr.EndOfStream) { s += sr.ReadLine(); } sr.Close(); s = StringToRightLength(s); CutStringIntoBlocks(s); key = CorrectKeyWord(key, s.Length / (2 * Blocks.Length)); textBoxEncodeKeyWord.Text = key; key = StringToBinaryFormat(key); for (int j = 0; j < quantityOfRounds; j++) { for (int i = 0; i < Blocks.Length; i++) Blocks[i] = EncodeDES_One_Round(Blocks[i], key); key = KeyToNextRound(key); } key = KeyToPrevRound(key); textBoxDecodeKeyWord.Text = StringFromBinaryToNormalFormat(key); string result = ""; for (int i = 0; i < Blocks.Length; i++) result += Blocks[i]; StreamWriter sw = new StreamWriter("out1.txt"); sw.WriteLine(StringFromBinaryToNormalFormat(result)); sw.Close(); Process.Start("out1.txt"); } else MessageBox.Show("Введите ключевое слово!"); } |
И кнопки «Расшифровать».
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
private void buttonDecipher_Click(object sender, EventArgs e) { if (textBoxDecodeKeyWord.Text.Length > 0) { string s = ""; string key = StringToBinaryFormat(textBoxDecodeKeyWord.Text); StreamReader sr = new StreamReader("out1.txt"); while (!sr.EndOfStream) { s += sr.ReadLine(); } sr.Close(); s = StringToBinaryFormat(s); CutBinaryStringIntoBlocks(s); for (int j = 0; j < quantityOfRounds; j++) { for (int i = 0; i < Blocks.Length; i++) Blocks[i] = DecodeDES_One_Round(Blocks[i], key); key = KeyToPrevRound(key); } key = KeyToNextRound(key); textBoxEncodeKeyWord.Text = StringFromBinaryToNormalFormat(key); string result = ""; for (int i = 0; i < Blocks.Length; i++) result += Blocks[i]; StreamWriter sw = new StreamWriter("out2.txt"); sw.WriteLine(StringFromBinaryToNormalFormat(result)); sw.Close(); Process.Start("out2.txt"); } else MessageBox.Show("Введите ключевое слово!"); } |
Готово!
DES — демонстрация работы программы и исходник
На рисунках 4 и 5 представлена демонстрация работы написанной программы для шифрования алгоритмом DES.
Рисунок 4. Демонстрация работы
Рисунок 5. Входные и выходные данные
Скачать исходник программы, написанной в Visual Studio 2013 на языке программирования C# можно, нажав на кнопку ниже.
Скачать исходник
Поделиться в соц. сетях:
Добрый день. Скажите, пожалуйста, а это правильно, что какой бы я не ввел текст и ключ, текст кодируется в азиатские иероглифы?
Добрый день, Антон! Да, это правильно.
DES — побитовый алгоритм. После шифрования и преобразования закодированных битов в графическое представление символов, как правило, получаются иероглифы. Когда Вы расшифруете текст — всё пройдёт успешно.
Здравствуйте, а откуда был взят данный алгоритм? Можно источник пожалуйста
Здравствуйте. Источник: статья в Википедии «DES».
Добрый день! Скажите, пожалуйста, а в тестовый файл in нужно что то добавлять? И почему при расшифровки слова, в текстовом файле out2 отображаются иероглифы?
Здравствуйте!
Да, в текстовый файл in.txt нужно добавить тот текст, который нужно зашифровать.
В выходном файле out2.txt должен быть исходный текст. Если возникают какие-то проблемы, то проблема с кодировкой файлов. У исходного файла выставите кодировку UTF-8 (без BOM) — сделать это можно, например, с помощью текстового редактора Notepad++.
Благодарю за статью, программу и ее описание.
Чуваки, ну вы молодцы, реально выручили, у всех будет такое точно на сдаче :))) !