Стандарт Data Encryption Stantart (DES)

Шифр Цезаря

Шифр Цезаря основан на фиксированном смещении по кругу букв алфавита. Буквы сдвигаются по кругу, так что после последней буквы алфавита идет его первая буква. В следующем листинге (на языке java) приводится алгоритм шифрования на основе шифра Цезаря.

Листинг 1. класс CaesarCipher

package ru.festu.u031.asanov.security.ref1;

 

public class CaesarCipher {

/** Зашифровать строку */

public static String encrypt(String s, int key) {

   String result = "";

   for(int i = 0; i < s.length(); i++) {

       // зашифровать каждый символ в строке

       result += encrypt(s.charAt(i), key);

   }

   return result;

}

/** Зашифровать отдельный символ */

public static char encrypt(char c, int key) {

   // преобразовать строчные буквы в прописные

   if(c >= 'а' && c <= 'я') c = Character.toUpperCase(c);

   // "повертуть" букву

   if(c >= 'А' && c <= 'Я') c = rotate(c, key);

   return c;

}

/** Расшифровать строку */

public static String decrypt(String s, int key) {

   // выполнить шифрование с "обратным" ключем

   return encrypt(s, -key);

}

/** Расшифровать отдельный символ */

public static char decrypt(char c, int key) {

   if(c < 'А' || c > 'Я') return c;

   else return rotate(c, key);

}

/** "Поворот" символа */

private static char rotate(char c, int key) {

   int l = 'Я' - 'А';

   c += key % l;

   if(c < 'А') c += l;

   if(c > 'Я') c -= l;

   return c;

}

}

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

В шифре Цезаря ключи представляют собой число символов, на которое сдвигаются буквы алфавита. При шифровании вместо каждой буквы открытого текста ставится буква отстоящая от нее вправо на число букв задаваемое значением ключа. Расшифровка заключается в смещении каждой буквы влево на число букв, задаваемое тем же значением ключа, которое использовалось при шифровании. (То есть decryptKey = -encrypKey)

Не нужно быть опытным дешифровальщиком, чтобы понять, что Шифр Цезаря обладает низкой стойкостью. В нем (в случае русского алфавита) возможны всего 32 различных кличей, один из которых отображает открытый текст в тот же открытый текст.

 Это дает представление о размере пространства ключей. Пространство ключей шифра – это набор всех возможных ключей, которые работаю с этим шифром. Чтобы шифр был эффективным, пространство ключей должно быть большим. Размер пространства ключей обычно измеряется числом двоичных разрядов ключа. В n-битном пространстве ключей возможны 2ⁿ разных ключа. Для 32-х-битного ключа это число составляет 4 294 967 296 разных ключей. Хотя такое число может показаться большим, на самом деле оно достаточно мало. Средней мощности компьютер может за день “перепробовать” 4 миллиарда ключей.

Простой подстановочный шифр

Еще одним видом простого шифра являются подстановочные шифры. Они были одними из наиболее популярных шифров со Средних веков до 19-го столетия. В простых подстановочных шифрах вместо одной буквы алфавита подставляется другая. В более сложных подстановочных шифрах вместо одной группы букв подставляется другая.

Даже простые подстановочные шифры сложнее шифра Цезаря. Если вы сможете расшифровать одну букву в шифре Цезаря, то после этого расшифруете любую букву в нем. Но в случае с простым подстановочным шифром так не происходит. Ключом к простому подстановочному шифру является таблица соответствия буквам открытого текста букв зашифрованного текста. Этот ключ может быть представлен в виде 32-х-буквенной строки. Например: НАФЧЫРИЦЛЙЯДМЗСЪЖЩТПОКЭЬГЮЕУШВБХ

Число ключей для простого подстановочного шифра составляет 32!, а это больше чем 2,6*10³⁵.

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

Листинг 2. класс SubstitutionCipher

package ru.festu.u031.asanov.security.ref1;

 

public class SubstitutionCipher {

/** Зашифровать строку */

public static String encrypt(String s, String key) {

   String r = "";

   for(int i = 0; i < s.length(); i++) {

       r += encrypt(s.charAt(i), key);

   }

   return r;

}

/** Зашифровать отдельный символ */

public static char encrypt(char c, String key) {

   // преобразовать строчные символы в заглвные

   if(c >= 'а' && c <= 'я') c = Character.toUpperCase(c);

   if(c >= 'А' && c <= 'Я') return key.charAt(c-'А');

   else return c;

}

/** Расшифровать строку */

public static String decrypt(String s, String key) {

   String r = "";

   for(int i = 0; i < s.length(); i++) {

       r += decrypt(s.charAt(i), key);

   }

   return r;

}

/** Расшифровать отдельный символ */

public static char decrypt(char c, String key) {

   if(c >= 'А' && c <= 'Я') return (char)(key.indexOf(c)+'А');

   else return c;

}

/** Создать ключ */

public static String createKey() {

   int length = 'Я'-'А'+1;

   char[] alphabet = new char[length];

   for(int i = 0; i < alphabet.length; i++) alphabet[i] += i+'А';

   for(int i = 0; i < alphabet.length; i++) {

       int n1 = i; //(int)(Math.random()*length);

       int n2 = (int)(Math.random()*length);

       char c = alphabet[n1];

       alphabet[n1] = alphabet[n2];

       alphabet[n2] = c;

   }

   return new String(alphabet);

}

}

На первый взгляд может показаться, что простой подстановочный шифр обладает высокой стойкостью, особенно потому, что у него огромное пространство ключей. Однако, он легко раскрывается методом, в котором применяются буквенные шаблоны, присущие конкретному языку.

В русском языке буквы О и Е встречаются значительно чаще других букв, таких, например, как Ъ и Ф. В таблице 1 приведены относительные частоты использования букв от А до Я, т.е. Ожидаемые числа использования этих букв в последовательности из 100 букв осмысленного текста. Это не означает, что среди 100 букв любого текста на русском языке буква В встретится всегда ровно 2 раза, а Ъ вообще не встретится. Но в среднем это действительно так.

Таблица 1. относительные частоты букв.

А	5,7	И	4,8	Р	2,9	Ш	0,5
Б	1,3	Й	0,7	С	3,7	Щ	0,3
В	3,0	К	2,1	Т	4,4	Ъ	0,0
Г	1,3	Л	3,4	У	1,9	Ы	1,4
Д	2,2	М	2,2	Ф	0,1	Ь	1,3
Е	5,8	Н	4,7	Х	0,6	Э	0,3
Ж	0,8	О	7,8	Ц	0,2	Ю	0,4
З	1,2	П	1,9	Ч	0,9	Я	1,4

Подобное распределение частот может быть найдено для диграфов (двухбуквенных комбинаций), триграфов (трехбуквенных комбинаций) и n-графов (n-буквенных комбинаций).

Это распределение частоты дает дешифровальщикам громадную информацию. Кроме распределения частот может быть использован словарь русской лексики, для автоматической проверки подстановочного отображения конкретной буквы. Например, однобуквенными словами в русском языке являются а, в, и, к и с. Дополнительно в распоряжении специалистов по криптоанализу имеется дополнительная информация, такая как частота слов и основные правила русской грамматики. Этого обычно оказывается достаточно для того, чтобы раскрыть простой подстановочный шифр.

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

Шифрование с секретным ключом

В некоторых алгоритмах шифрования для шифрования и расшифровки используется один и тот же ключ, или дешифровальный ключ может быть вычислен по шифровальному ключу за небольшое время. Такие алгоритмы называются алгоритмами с секретным ключом, алгоритмами с закрытым ключом или симметричными алгоритмами. Ключ используемый в таких алгоритмах должен храниться в тайне. Примером алгоритма с секретным ключом является алгоритм Data Encryption Stantart (DES).

Стандарт Data Encryption Stantart (DES).

В 1997 г. в США Национальным Институтом Стандартов и Технологий (NIST) в качестве стандартного алгоритма шифрования для защиты несекретной информации был принят алгоритм DES. Этот алгоритм вполне уверенно противостоял открытым попыткам взлома вплоть до середины 90-х годов, когда были отмечены попытки взлома с использованием методов дифференциального и линейного криптоанализа. К январю 1999 г. фонду Electronic Frontier Foundation уже удавалось взламывать сообщения, зашифрованные с помощью алгоритма DES, не более чем за сутки.

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

В алгоритме DES используется 64-х-разрядный ключ – 8 битов применяются для исправления ошибок (контроля четности). В результате эффективная длина ключа составляет 56 бит. Шифрование и расшифровка в алгоритме DES осуществляется блоками по 64 бита (8 байтов), и из 64 битов открытого текста получается 64 бита зашифрованного текста. Алгоритм заключается в не зависящей от ключа перестановке входных данных с последующим шифрованием их с помощью открытого ключа, после чего осуществляется обратная перестановка данных.

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

Алгоритм DES может быть использован в различных методах шифрования, в зависимости от назначения. Вот несколько примеров методов шифрования:

· Метод ECB (Electronic Codebook – Электронная шифровальная книга) – шифрование осуществляется 8-и-байтовыми блоками, причем последующий блок зашифрованного текста не зависит от предыдущих блоков как зашифрованного, так и открытого текста.

· Метод CBC (Cipher Block Changing – Сцепление зашифрованных блоков) – n-ный блок шифруемого текста получается в результате выполнения операции XOR (исключающего или) над (n-1)-м блоком защифрованного текста и n-ным блоком открытого текста.

· Метод CFB (Cipher Feedback – Обратная связь по шифру) – предыдущая порция зашифрованного текста объединяется со следующей порцией открытого текста.

· Метод OFB (Output Feedback – Обратная связь по выходу) – алгоритм DES используется для создания псевдослучайного потока битов, который объединяется с открытым текстом, в результате чего создается поток зашифрованного текста.

· Метод PCBC (Propagating Cipher Block Changing – Сцепление зашифрованных блоков с множественной связью) – Отличается от метода CBC тем, что с n-ным блоком зашифрованного текста объединяется как (n-1)-й блок зашифрованного текста, так и (n-1)-й блок открытого текста.

Когда требуется зашифровать не 8-и-байтовый, а более короткий блок открытого текста (например, последние байты файла или сообщения), он дополняется до заполнения 64-х-разрядного регистра. В связи с этим возникает проблема – как при расшифровке отличить исходный текст от дополняющих байтов. Для решения этой проблемы компанией RSA Data Encryption, Inc. Был разработан стандарт под названием “Public Key Cryptography Standart #5 padding ” (“Дополнение к стандарту шифрования с открытым ключом #5”). Это дополнение заключается в следующем: “Если n – число байтов, которыми нужно дополнить блок, то значение каждого дополняющего байта устанавливается в n. Если дополнение не требуется, то добавляется один блок, в котором значение каждого байта устанавливается в 8”

Методы шифрования и дополнения блоков, используемые с алгоритмом DES, по своей природе, универсальны и могут быть использованы с другими шифрами, такими, например, как DESede или Blowfish

Алгоритм DESede

В связи с популярностью алгоритма DES и его недостатками, выявленными во второй половине 90-х годов, криптографы искали способы повышения его стойкости, при одновременном сохранении его в качестве базового алгоритма шифрования. В алгоритмах DESede выполняется троекратное шифрование по алгоритму DES, что приводит к эффективной длине ключа в 168 разрядов. В одном из вариантов DESede третий ключ равен первому, эффективная длина ключа в таком случае составляет 112 разрядов.

Алгоритм Blowfish

Blowfish – это шифр с секретным ключом, разработанный Брюсом Шейнером, ведущим специалистом-криптографом, автором нашумевшей книги Applied Cryptography (Прикладная криптография). Этот алгоритм на запатентован, он бесплатный и беспошлинный, и на его использование не требуется лицензии.

Blowfish является 64-х-разрядным блочным шифром, предназначенным для встраиваемой замены алгоритма DES. Он превосходит DES по скорости шифрования и намного – по стойкости. Длина его ключа варьируется от 32-х до 448-и разрядов.

Шифрование с открытым ключом

В предыдущих главах рассматривались методы шифрования с закрытым ключом. Но шифрование с секретным ключом – это не единственный способ шифрования данных. Одним из наиболее значительных прорывов в криптографии двадцатого столетия была разработка шифрования с открытым ключом.

Алгоритмы с открытым ключом, или асимметричные алгоритмы, базируются на использовании отдельных шифровального (открытого – public) и дешифровального (закрытого – private) ключей. В алгоритмах с открытым ключом требуется, чтобы закрытый ключ было невозможно вычислить по открытому ключу. Исходя из этого требования шифровальный ключ может быть доступным кому угодно без какого-либо ущерба безопасности алгоритма шифрования.