Конвертер разрешения. Мультиконвертер изображений с поддержкой RAW онлайн. Конвертеры фотографий онлайн
Аннотация: Одной из наиболее известных криптографических систем с закрытым ключом является DES – Data Encryption Standard. Эта система первой получила статус государственного стандарта в области шифрования данных. И хотя старый американский стандарт DES в настоящее время утратил свой официальный статус, этот алгоритм все же заслуживает внимания при изучении криптографии. Кроме того в этой лекции объясняется, что такое "двухкратный DES", атака "встреча посередине" и способы ее устранения. В этой же лекции кратко рассматривается новый стандарт США на блочный шифр – алгоритм Rijndael.
Цель лекции : познакомить студента с основными сведениями об алгоритме шифрования DES .
Основные сведения
Одной из наиболее известных криптографических систем с закрытым ключом является DES – Data Encryption Standard . Эта система первой получила статус государственного стандарта в области шифрования данных. Она разработана специалистами фирмы IBM и вступила в действие в США 1977 году. Алгоритм DES широко использовался при хранении и передаче данных между различными вычислительными системами; в почтовых системах, в электронных системах чертежей и при электронном обмене коммерческой информацией . Стандарт DES реализовывался как программно, так и аппаратно. Предприятиями разных стран был налажен массовый выпуск цифровых устройств, использующих DES для шифрования данных. Все устройства проходили обязательную сертификацию на соответствие стандарту.
Несмотря на то, что уже некоторое время эта система не имеет статуса государственного стандарта, она по-прежнему широко применяется и заслуживает внимания при изучении блочных шифров с закрытым ключом.
Длина ключа в алгоритме DES составляет 56 бит . Именно с этим фактом связана основная полемика относительно способности DES противостоять различным атакам. Как известно, любой блочный шифр с закрытым ключом можно взломать, перебрав все возможные комбинации ключей. При длине ключа 56 бит возможны 2 56 разных ключей. Если компьютер перебирает за одну секунду 1 000 000 ключей (что примерно равно 2 20), то на перебор всех 2 56 ключей потребуется 2 36 секунд или чуть более двух тысяч лет, что, конечно, является неприемлемым для злоумышленников.
Однако возможны более дорогие и быстрые вычислительные системы, чем персональный компьютер . Например, если иметь возможность объединить для проведения параллельных вычислений миллион процессоров, то максимальное время подбора ключа сокращается примерно до 18 часов. Это время не слишком велико, и криптоаналитик, оснащенный подобной дорогой техникой, вполне может выполнить вскрытие данных, зашифрованных DES за приемлемое для себя время.
Вместе с этим можно отметить, что систему DES вполне можно использовать в небольших и средних приложениях для шифрования данных, имеющих небольшую ценность. Для шифрования данных государственной важности или имеющих значительную коммерческую стоимость система DES в настоящее время, конечно, не должна использоваться. В 2001 году после специально объявленного конкурса в США был принят новый стандарт на блочный шифр , названный AES (Advanced Encryption Standard) , в основу которого был положен шифр Rijndael , разработанный бельгийскими специалистами. Этот шифр рассматривается в конце лекции.
Основные параметры DES : размер блока 64 бита, длина ключа 56 бит , количество раундов – 16. DES является классической сетью Фейштеля с двумя ветвями. Алгоритм преобразует за несколько раундов 64-битный входной блок данных в 64-битный выходной блок. Стандарт DES построен на комбинированном использовании перестановки, замены и гаммирования. Шифруемые данные должны быть представлены в двоичном виде.
Шифрование
Общая структура DES представлена на рис. 4.1 . Процесс шифрования каждого 64-битового блока исходных данных можно разделить на три этапа:
- начальная подготовка блока данных;
- 16 раундов "основного цикла";
- конечная обработка блока данных.
На первом этапе выполняется начальная перестановка 64-битного исходного блока текста, во время которой биты определенным образом переупорядочиваются.
На следующем (основном) этапе блок делится на две части (ветви) по 32 бита каждая. Правая ветвь преобразуется с использованием некоторой функции F и соответствующего частичного ключа , получаемого из основного ключа шифрования по специальному алгоритму преобразования ключей. Затем производится обмен данными между левой и правой ветвями блока. Это повторяется в цикле 16 раз.
Наконец, на третьем этапе выполняется перестановка результата, полученного после шестнадцати шагов основного цикла . Эта перестановка обратна начальной перестановке.
Рис.
4.1.
Рассмотрим более подробно все этапы криптографического преобразования по стандарту DES .
На первом этапе 64-разрядный блок исходных данных подвергается начальной перестановке. В литературе эта операция иногда называется "забеливание" – whitening . При начальной перестановке биты блока данных определенным образом переупорядочиваются. Эта операция придает некоторую "хаотичность" исходному сообщению, снижая возможность использования криптоанализа статистическими методами.
Одновременно с начальной перестановкой блока данных выполняется начальная перестановка 56 бит ключа. Из рис. 4.1 . видно, что в каждом из раундов используется соответствующий 48-битный частичный ключ K i . Ключи K i получаются по определенному алгоритму, используя каждый из битов начального ключа по нескольку раз. В каждом раунде 56-битный ключ делится на две 28-битовые половинки. Затем половинки сдвигаются влево на один или два бита в зависимости от номера раунда. После сдвига определенным образом выбирается 48 из 56 битов. Так как при этом не только выбирается подмножество битов, но и изменяется их порядок, то эта операция называется " перестановка со сжатием". Ее результатом является набор из 48 битов. В среднем каждый бит исходного 56-битного ключа используется в 14 из 16 подключей, хотя не все биты используются одинаковое количество раз.
Далее выполняется основной цикл преобразования, организованный по сети Фейштеля и состоящий из 16 одинаковых раундов. При этом в каждом раунде ( рис. 4.2) получается промежуточное 64-битное значение , которое затем обрабатывается в следующем раунде.
Рис. 4.2.
Левая и правая ветви каждого промежуточного значения обрабатываются как отдельные 32-битные значения, обозначенные L и R .
Вначале правая часть блока R i расширяется до 48 битов, используя таблицу, которая определяет перестановку плюс расширение на 16 битов. Эта операция приводит размер правой половины в соответствие с размером ключа для выполнения операции XOR . Кроме того, за счет выполнения этой операции быстрее возрастает зависимость всех битов результата от битов исходных данных и ключа (это называется "лавинным эффектом"). Чем сильнее проявляется лавинный эффект при использовании того или иного алгоритма шифрования, тем лучше.
После выполнения перестановки с расширением для полученного 48-битного значения выполняется операция XOR с 48-битным подключом K i . Затем полученное 48-битное значение подается на вход блока подстановки S (от англ. Substitution - подстановка), результатом которой является 32-битное значение . Подстановка выполняется в восьми блоках подстановки или восьми S-блоках (S-boxes). При выполнении этой DES на бумаге выглядит достаточно сложным, что уж говорить про его программную реализацию! Разработать правильно и оптимально функционирующую программу полностью в соответствии с DES , наверно, под силу только опытным программистам. Некоторые трудности возникают при программной реализации, например, начальной перестановки или перестановки с расширением. Эти сложности связаны с тем, что первоначально планировалось реализовывать DES только аппаратно. Все используемые в стандарте операции легко выполняются аппаратными блоками, и никаких трудностей с реализацией не возникает. Однако через некоторое время после публикации стандарта разработчики программного обеспечения решили не стоять в стороне и тоже взяться за создание систем шифрования. В дальнейшем DES реализовывался и аппаратно, и программно.
Который ANSI называет алгоритмом шифрования данных DEA (Data Encryption Algorithm) , a ISO — DEA-1, за 20 лет стал мировым стандартом. За годы своего существования он выдержал натиск различных атак и при известных ограничениях все еще считается криптостойким.
DES представляет собой блочный шифр, шифрующий данные 64-битовыми блоками. С одного конца алгоритма вводится 64-битовый блок открытого текста, а с другого конца выходит 64-битовый блок шифротекста. DES является симметричным алгоритмом: для шифрования и дешифрования используются одинаковые алгоритм и ключ (за исключением небольших различий в использовании ключа). Длина ключа равна 56 битам. (Ключ обычно представляется 64-битовым числом, но каждый восьмой бит используется для проверки четности и игнорируется. Биты четности являются наименьшими значащими битами байтов ключа.) Ключ, который может быть любым 56-битовым числом, можно изменить в любой момент времени.
Криптостойкость полностью определяется ключом. Фундаментальным строительным блоком DES является комбинация подстановок и перестановок. DES состоит из 16 циклов.
Oбщий вид цикла преобразования:
Если L i и R i — левая и правая половины, полученные в результате i -й итерации, K i — 48-битный ключ для цикла i , а f — функция, выполняющая все подстановки, перестановки и XOR с ключом, то один цикл преобразования можно представить как:
Учитывая подстановку F i (*) и перестановку Т (*), цикл преобразования можно представить так, как это сделано на рис.
Видно, что каждый цикл DES представляет собой композиционный шифр с двумя последовательными преобразованиями — подстановкой F i (*) и перестановкой Т (*) (за исключением последнего, шестнадцатого цикла, где перестановка опускается).
Подстановка:
(L i , R i) = (R i −1 , L i −1) ⊕ f (R i −1 , K)
является инволюцией, так как
F i (F i (L i −1 , R i −1)) = F i (R i −1 , L i −1) ⊕ (f (R i −1 , K i))) = (R i −1 , L i −1 ⊕(f (R i −1 , K i)) ⊕ (f (R i −1 , K i))) = (L i −1 , R i −1)
А подстановка
T (L i ′, R i ′) = (R i ′, L i ′),
так же является инволюцией, так как
T (T (L i ′, R i ′)) = T (R i ′, L i ′) = L i ′, R i ′
Если обозначить начальную и завершающую перестановки как (IP) и (IР) − 1 , то прямое DES-преобразование (шифрование) реализует функцию:
DES = (IP) F 1 TF 2 T … F 15 TF 16 (IP) − 1 ,
а обратное DES-преобразование (дешифрование) реализует функцию:
DES − 1 = (IP) −1 F 16 TF 15 T … F 2 TF 1 (IP).
Таким образом, DES является шифром Фейстеля и сконструирован так, чтобы выполнялось полезное свойство: для шифрования и дешифрования используется один и тот же алгоритм. Единственное отличие состоит в том, что ключи должны использоваться в обратном порядке.
То есть если при шифровании использовались ключи K 1 , K 2 , K 3 , …, K 16 , то ключами дешифрования будут K 16 , K 15 , K 14 , …, K 1 . Алгоритм использует только стандартную арифметику 64-битовых чисел и логические операции, поэтому легко реализуется на аппаратном уровне.
DES работает с 64-битовым блоком открытого текста. После первоначальной перестановки блок разбивается на правую и левую половины длиной по 32 бита. Затем выполняется 16 преобразований (функция f), в которых данные объединяются с ключом. После шестнадцатого цикла правая и левая половины объединяются, и алгоритм завершается заключительной перестановкой (обратной по отношению к первоначальной). На каждом цикле (см. рис.) биты ключа сдвигаются, и затем из 56 битов ключа выбираются 48 битов. Правая половина данных увеличивается до 48 битов с помощью перестановки с расширением, объединяется посредством XOR с 48 битами смещенного и переставленного ключа, проходит через 8 S-блоков, образуя 32 новых бита, и переставляется снова. Эти четыре операции и выполняются функцией f .
Затем результат функции f объединяется с левой половиной с помощью другого XOR. В итоге этих действий появляется новая правая половина, а старая правая становится новой левой половиной. Эти действия повторяются 16 раз, образуя 16 циклов DES.
Стандарт России — ГОСТ 28147-89
ГОСТ 28147-89 — это блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. В криптоалгоритме также используется дополнительный ключ, который рассматривается ниже. Для шифрования открытый текст сначала разбивается на левую и правую половины L и R . На i -м цикле используется подключ К i:
L i = R i −1 ,
R i = L i −1 ⊕ (f (R i −1 , K i)).
Функция f реализована следующим образом. Сначала правая половина и i -й подключ складываются по модулю 2 32 . Результат разбивается на восемь 4-битовых подпоследовательностей, каждая из которых поступает на вход своего S-блока. ГОСТ использует восемь различных S-блоков, первые 4 бита попадают в первый S-блок, вторые 4 бита — во второй S-блок и т. д. Каждый S-блок представляет собой перестановку чисел от 0 до 15. Например, S-блок может выглядеть как: 7,10,2,4,15,9,0,3,6,12,5,13,1,8,11. В этом случае, если на входе S-блока 0, то на выходе 7. Если на входе 1, на выходе 10 и т. д. Все восемь S-блоков различны, они фактически являются дополнительным ключевым материалом. Выходы всех восьми S-блоков объединяются в 32-битовое слово, затем все слово циклически сдвигается влево на 11 битов. Наконец, результат объединяется с помощью операции XOR с левой половиной, и получается новая правая половина, а правая половина становится новой левой половиной. Для генерации подключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: k 1 , k 2 , …, k 8 . На каждом цикле используется свой подключ. Дешифрование выполняется так же, как и шифрование, но инвертируется порядок подключей k i . Стандарт не определяет способ генерации S-блоков.
Основные различия между DES и ГОСТом
Главные различия между DES и ГОСТом заключаются в следующем:
- DES использует сложную процедуру для генерации подключей из ключей. В ГОСТе эта процедура очень проста;
- в DES 56-битный ключ, а в ГОСТе — 256-битный. Если добавить секретные перестановки S-блоков, то полный объем секретной информации ГОСТа составит примерно 610 бит;
- у S-блоков DES 6-битные входы и 4-битные выходы, а у S-блоков ГОСТа 4-битные входы и выходы. В обоих алгоритмах используется по восемь S-блоков, но размер S-блока ГОСТа равен четверти размера S-блока DES;
- в DES используются нерегулярные перестановки, названные Р-блоком, а в ГОСТе используется 11-битный циклический сдвиг влево;
- в DES 16 циклов, а в ГОСТе — 32.
Силовая атака на ГОСТ абсолютно бесперспективна. ГОСТ использует 256-битовый ключ, а если учитывать секретные S-блоки, то длина ключа будет еще больше. ГОСТ, по-видимому, более устойчив к дифференциальному и линейному криптоанализу, чем DES. Хотя случайные S-блоки ГОСТа при некотором выборе не гарантируют высокой криптостойкости по сравнению с фиксированными S-блоками DES, их секретность увеличивает устойчивость ГОСТа к дифференциальному и линейному криптоанализу. К тому же эффективность этих криптоаналитических методов зависит от количества циклов преобразования — чем больше циклов, тем труднее криптоанализ. ГОСТ использует в два раза больше циклов, чем DES, что, возможно, приводит к несостоятельности дифференциального и линейного криптоанализа.
ГОСТ не использует существующую в DES перестановку с расширением. Удаление этой перестановки из DES ослабляет его из-за уменьшения лавинного эффекта; разумно предположить, что отсутствие такой операции в ГОСТе отрицательно сказывается на его криптостойкости. С точки зрения криптостойкости операция арифметического сложения, используемая в ГОСТе, не хуже, чем операция XOR в DES.
Основным различием представляется использование в ГОСТе циклического сдвига вместо перестановки. Перестановка DES увеличивает лавинный эффект. В ГОСТе изменение одного входного бита влияет на один S-блок одного цикла преобразования, который затем влияет на два S-блока следующего цикла, затем на три блока следующего цикла и т.д. Потребуется восемь циклов, прежде чем изменение одного входного бита повлияет на каждый бит результата; в DES для этого нужно только пять циклов. Однако ГОСТ состоит из 32 циклов, a DES только из 16.
Разработчики ГОСТа пытались достигнуть равновесия между криптостойкостью и эффективностью. Взяв за основу конструкцию Фейстеля, они разработали криптоалгоритм, который лучше, чем DES, подходит для программной реализации. Для повышения криптостойкости введен сверхдлинный ключ и удвоено количество циклов. Однако вопрос, увенчались ли усилия разработчиков созданием более криптостойкого, чем DES, криптоалгоритма, остается открытым.
Воробьева Е., Лукьянова А.
DES (Data Encryption Standart) - Симметричный алгоритм шифрования, в котором один ключ используется, как для шифрования, так и для расшифрования данных. DES разработан фирмой IBM и утвержден правительством США в 1977 году как официальный стандарт (FTPS 46-3). DES имеет блоки по 64 бит и 16 цикловую структуру сети Фейстеля, для шифрования использует ключ с длиной 56 бит. Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований. Для DES рекомендовано несколько режимов:Блочный шифр
Входными данными для блочного шифра служат блок размером n бит и k-битный ключ. На выходе, после применения шифрующего преобразования, получается n-битный зашифрованный блок, причём незначительные различия входных данных как правило приводят к существенному изменению результата. Блочные шифры реализуются путём многократного применения к блокам исходного текста некоторых базовых преобразований.Базовые преобразования:
Преобразования Сетью Фейстеля
Это преобразование над векторами (блоками) представляющими собой левую и правую половины регистра сдвига. В алгоритме DES используются прямое преобразование сетью Фейстеля в шифровании (см. Рис.1) и обратное преобразование сетью Фейстеля в расшифрование (см. Рис.2).
Схема шифрования алгоритма DES
Исходный текст - блок 64 бит.
Шифрованный текст - блок 64 бит.
Процесс шифрования состоит в начальной перестановке, 16 циклах шифрования и конечной перестановке.
Рассмотрим подробную схему алгоритма DES:
L i R i =1,2\ldots.левая и правая половины 64-битового блока L i R i
k i - 48 битовые ключи
f - функция шифрования
IP - начальная перестановка
IP -1 - конечная перестановка.
По таблице первые 3 бита результирующего блока IP(T) после начальной перестановки IP являются битами 58, 50, 42 входного блока Т, а его 3 последние бита являются битами 23, 15, 7 входного блока. Дальше 64-битовой блок IP(T) участвует в 16-циклах преобразования Фейстеля.
16 циклов преобразования Фейстеля:
Разбить IP(T) на две части L 0 ,R 0 , где L 0 ,R 0 - соответствено 32 старших битов и 32 младших битов блока T0 IP(T)= L 0 R 0
Пусть T i -1 = L i -1 R i -1 результат (i-1) итерации, тогда результат i-ой интерации T i = L i R i определяется:
L i = R i - 1 Левая половина L i равна правой половине предыдущего вектора L i - 1 R i - 1 . А правая половина R i - это битовое сложение L i - 1 и f(R i - 1 , k i) по модулю 2.
В 16-циклх преобразования Фейстеля функция f играет роль шифрования. Рассмотрим подробно функцию f.
Аргументы функции f являются 32 битовой вектор R i - 1 , 48 битовой ключ k i , которые являются результатом преобразования 56 битового исходного ключа шифра k.
Для вычисления функции f используются фукция расширения Е, преобразование S, состоящее из 8 преобразований S-блоков , и перестановка P.
Функция Е расширяется 32 битовой вектор R i - 1 до 48 битовой вектор E(R i - 1) путем дублирования некоторых битов из R i - 1 при этом порядок битов вектора E(R i - 1) указан в таблице 2.
Первые три бита вектора E(R i - 1) являются битами 32, 1, 2 вектора R i -1 . По таблице 2 видно что биты 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 дублируются. Последние 3 биты вектора E(Ri - 1) - это биты 31, 32, 1 вектора R i - 1 . Полученный после перестановки блок E(R i -1) складывается по модулю 2 с ключами k i и затем представляются в виде восьми последовательных блоков B 1 ,B 2 ,...B 8 .
E(R i - 1) = B 1 B 2 ...B 8
Каждый B j является 6-битовым блоком. Далее каждый из блоков B j трансформируется в 4 битовой блок B" j с помощью преобразований S j . Преобразования S j определяется таблицей 3.
Предположим что B 3 = 101111 и мы хотим найти B" 3 . Первый и последний разряды B 3 являются двоичной записью числа а, 0Значение функции f(R i - 1 ,k i) (32 бит) получается перестановкой Р, применяемой к 32 битовому блоку B" 1 B" 2 ...B" 8 . Перестановка Р задана таблицей 4.
f(R i - 1 ,k i) = P(B" 1 B" 2 ...B" 8)
Согласно таблице 4, первые четыре бита результирующего вектора после действия функции f - это бита 16, 7, 20, 21 вектора B" 1 B" 2 ...B" 8
Генерирование ключей k i .
Ключи k i получаются из начального ключа k (56 бит = 7 байтов или 7 символов в АSCII) таким образом. Восемь битов, находящих в позициях 8, 16, 24, 32, 40, 48, 56, 64 добавляются в ключ k таким образом чтобы каждый байт содержал нечетное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей. Затем делают перестановку для расширенного ключа (кроме добавляемых битов 8, 16, 24, 32, 40, 48, 56, 64). Такая перестановка определенна как в таблице 5.
Эта перестановка определяется двумя блоками C 0 и D 0 по 28 бит каждый. Первые 3 бита C 0 есть биты 57, 49, 41 расширенного ключа. А первые три бита D 0 есть биты 63, 55, 47 расширенного ключа. C i ,D i i=1,2,3…получаются из C i - 1 ,D i - 1 одним или двумя левыми циклическими сдвигами согласно таблице 6.
Ключ k i , i=1,…16 состоит из 48 бит, выбранных из битов вектора C i D i (56 бит) согласно таблице 7. Первый и второй биты k i есть биты 14, 17 вектора C i D i
Конечная перестановка IP - 1 действует на T 16 и используется для востановления позиции. Она является обратной к перестановке IP. Конечная перестановка определяется таблицей 8.
Режимы использования DES
DES может используется в четырех режимах.
