 |
Главная |
Перестановочные (транспозиционные) шифры. Решетка Кардано и другие примеры шифров перестановки
 2015-11-20 |
 2074 |
 Обсуждений (0) |
из
5.00
|
Наряду с шифрами подстановки существуют транспозиционные шифры: шифрование состоит из изменения положения букв исходного текста, при этом сами буквы остаются неизменными.
Приведем 2 примера: сообщение разбивается на группы букв например по 3 буквы в каждой группе, а затем в каждой группе делается одна и та же перестановка.
Например:
LET US GO TO LONDON
ETL SGUT OO ONLOND
Выполнить шифрование так же можно, записав это сообщение в прямоугольнике 3х5:
| L | E | T | U | S |
| G | O | T | O | L |
| O | N | D | O | N |
LGO EO NT TD UOOSLN
К классу перестановки принадлежит шифр решетка Кардано: представляет собой прямоугольную карточку с отверстиями, которые, при наложении на лист бумаги, оставляют открытыми только некоторые его части. Число строк и столбцов карточки должно быть четным. Как правило, используется квадратная карточка. Она сделана таким образом, что при ее последовательном использовании (повороте), каждая клетка, лежащего под ней места, окажется занятой. Карточку вначале поворачивают вдоль Оу, затем вдоль Ох на 180 град., и вновь повторяют эту же процедуру. Если решетка Кардано – квадрат, то возможен 2ой вариант, последовательный поворот вокруг центра на 90 град.
СЕТЬ ФЕЙСТЕЛЯ
Процедура дешифрования аналогична шифрованию,ноkвыбирается в обратном порядке.Констр. Фейстеля хороша тем,что структура шифрования и дешифрования идентичны.
Блочный шифр,использующий подобную констр. обратим и гарантирует возможность восстановления входных данных функции fна каждом цикле.Сама же функция fне обязательно должна быть обратимой.При задании произвольной функции fне потребуется реализовывать 2 последовательных функции.
Существует еще 1 объяснение функционирования констр. Фейстеля-инволютное отображение.
f(f(x))=X-инволюция (XOR)
Рассмотрим композиционный блочный шифр, включающий Nпоследовательных крипто-преобразований.
Eki(•),1≤i≤n, K
C=Ekn(E k n-1 (…Ek2(Ek1(p))…))
Если Eki-инволюция, то открытый текст м.б. восстановлен так:
P=Ek1(E k2 (…Ekn-1(Ekn(p))…))
При за шифровании очередного блока его биты подвергаются начальной перестановке(IP),согласно установленной таблицы.Полученные новые перестановки блок разделяет на 2 половины:L0-32 старших бита;R0-32 младших бита.Затем выполняется итеративный процесс шифрования,состоящий из 16 циклов преобразования Фейстеля.Результатом последней итерации является блок L16R16.По окончании шифрования восстановление порций битов применением к результату обратной перестановки IP-1.При расшифровании все действия повторяются в обратном порядке.
Общий вид цикла DES-преобразования
Каждый цикл DESпредставляет собой композиционный шифр с 2-мя последовательными преобразованиями:подстановкой и перестановкой,за исключением последнего,16-го цикла,где перестановка опускается.
Т.О. DES-это шифр Фейстеля,сконструированныйтак,чтобы выполнялось полезное свойство:применение одного и того же алгоритма для шифрования и дешифрования.Единственное отличие в том,что ключи должны использоваться в обратном порядке,т.е.:шифрование:k0,k1,k2,…,k15,тогда дешифрование:k15,k14,k13,…,k0.
Алгоритм использует только стандартную арифметике 64-битных чисел и логические операции,поэтому легко реализуем на аппаратном уровне.
С целью реализации базовых преобразований служат регистры сдвига.При этом рассеивающие преобразования определяются функциями обратной связи,а перемешивающие-сдвигами инфы в регистре.
Для алгоритма DES определены схемы вычисления значений функций шифрования,а также процедура преобразования ключа,которыеявл. стандартными.
36.Режимы использования блочного шифра DES. Режим «Сцепления блоков шифров» (CBC – Cipher Block Chaining). Структурная схема функционирования DES в режиме CBC. Достоинства и недостатки алгоритма. КАС – код аудиенции сообщения.
Блочные шифры используются в нескольких режимах работы, в зависимости от решаемых крипто-задач. Рассмотрим эти режимы на примере шифра DES. Алгоритм DES может применятся в следующих 4 режимах:
1)Режим “Электронная кодовая книга” (ECB-Electronic Code Book)
2)Режим сцепления блоков шифра (CBC-Cipher Block Chaining)
3)Режим обратной связи по шифру (CFB-Cipher Feed Back)
4)Обратная связь по выходу (OFB-Output Feed Back)
Режим сцепление блоков шифров.
Характеризуется тем, что исходный файл разбивается на 64-х битовые блоки:М=М1М2М3…Мn. 1-ый блок М1 складывается по модулю 2 с 64-х битовым начальным вектором, который ежедневно изменяется и сохраняется в секрете. Полученная сумма затем шифруется с использованием ключа DES, известного и отправитель и получателю инфы. Полученный при этом 64-бытный шифр C1 складывается по модулю 2 со 2-ым блоков исходного текста: результат шифруется и получает 2-ой 64-битный шифр С2 и тд. Процедура повторяется до тех пор , пока не будет обработаны все блоки исходного текста.
Структурная схема функционирования в DES в режиме CBC.
Для всех i=0..n, где n-число блоков, С0=IV, результат шифрования определяется следующим образом: С=DES(Mi+Ci-1). С0=IV – начальное значение шифра, равное нач. вектору (вектору инициализации).
Очевидно, что последний 64-битный блок шифротекста явл. функцией секретного ключа, начального вектора и каждого символа открытого текста, независимо от его длины. Этот блок шифротекста называется кодом аутентификации сообщения (КАС). Код касс м.б. легко проверен получателем, у которого имеется секретный ключ и начальный вектор, путём повторения процедуры, выполненной отправителем. Посторонний, однако, не может осуществить инерацию КАС, который воспринимался бы получателем как подлинный, чтобы добавить его к ложному сообщению или отделить КАС от истинного сообщения, для использования его с изменённым или ложным сообщением. Достоинство данного режима-не позволение накопления ошибок при передаче. Блок Mi явл. функцией только Сi-1 и Ci , поэтому ошибка при передаче приведёт к потере только 2-ух блоков исходного текста.
Файл, подлежащий шифрованию (расшифрованию) считывается последовательными блоками длинной К бит (К=1..64). Входной блок-64-битный регистр сдвига, к начале содержит вектр инициализации, выровненный по правому краю, если в результате разбиения на блоки получилось N блоков по К битов каждый (а остаток дописывается нулями и пробелами), то для любого i=1..n, блок шифротекста равен: Сi=Mi+(в кружочке)Pi-1 где Pi-1 означает К старших битов предыдущего зашифрованного текста. Сдвиговый регистр обновляется удалением его старших К битов и записи Сi в регистр. Восстановление зашифрованных данных тоже выполняется относительно просто. Pi-1 и Сi вычисляются аналогичным образом: Mi=Ci+(в кружочке)Рi-1.
38.Режимы использования блочного шифра DES. Режим «Обратная связь по выходу» (OFB – Output Feed Back). Структурная схема функционирования DES в режиме OFB. Формулы шифрования и дешифрования. Отличие от режима обратной связи по шифротексту (CFB).
Структурная схема функционирования DES в режиме OFB.
Для этого режима также характерен переменный размер блока шифра и использованного сдвигового регистра, который инициализируется таким же образом, как и регистр CLB(не уверен что С), а именно входной блок содержит вектор инициализации IV, выровненный по правому краю. Для каждого шага шифрования данных надо использовать новое начальное состояние регистра, которое должно пересылаться по каналу открытым текстом. При М=M1M2…Mn для всех i=1..n
Сi=Мi+(в кружочке)Рi , где Рi – К старших битов операции DES от Ci-1.
Отличие от режима обработки связи по шифротексту в методе обновление сдвигового регистра. Это осуществляется посредствам отбрасывания старших К битов и дописывания справа Р.
Все операции выполняются над 8-ю 16-битными субблоками. Операции несовместимы в то смысле, что никакие пары этих 3-ёх операций не удовлетворяют ассоциативному закону. Комбинирование этих 3-ёх операций обеспечивает комплексное преобразование кода, существенно осложняя криптоанализ idea по сравнению с des, который базируется исключительно на операции XOR.
Структурная схема алгоритма IDEA:
Обозначения: Xi-16-битный субблок открытого текста(i=1..4) Yi-16-битный субблок шифротекста (i=1..4) Zi-16-битный подключ (субблок ключа) (j=1..6). 64-битный блок данных делится на 4 16-битных слова. Эти 3 субблока станут входными в 1-ый цикл алгоритма. Всего 8 циклов. Между циклами 2 и 3 субблоки меняются местами. В каждом цикле имеет место следующая последовательность операций: 1) умножение субблока X1 и подключа Z1 2) сложение X2 и Z2 3)сложение X3 и Z3 4) сложение X4 и Z4 5) сложение рез-тов к шагу 1 и 3 6) сложение рез-тов шагов 2 и 4 7)умножение шагов 5 и Z5 8)сложение рез-тов шагов 6 и 7 9) умножение рез-тов 8 и Z6 10)сложение рез-тов 7 и 9 11)сложение рез-тов 1 и 9 12)сложение рез-тов шагов 3 и 9 13) сложение рез-тов шагов 2 и 10 14) сложение рез-тов шагов 4 и 10.
Выходом цикла явл. 4 субблок, которые формируются как рез-ты выполнения шагов 11 и 14. В завершении цикла переставляются местами 2 внутренних субблока (за исключением последнего цикла) и в рез-те формируется вход для следующего цикла. После 8-ого цикла суш. Заключительно преобразование выхода: 1) умножение X1 и Z1 2) сложение X2 и Z2 3) ) сложение X3 и Z3 4)умножение X4 и Z4. 4 субблока Y1-Y4 вновь объединяются для получения блока шифротекста. Создание подключей Zj также относительно не сложно. Американцы используют 52 подключа по 6 для каждого из 8 циклов и ещё 4 для преобразования выхода. Сначала 128 бит делят на 8 16-битных подключей. Это первые 8 подключей для алгоритма (6 для 1-ого цикла и первые 2 подключа для 2-ого цикла) Затем 128-битный ключ сдвигается влева на 25 бит и снова делится на 8 подключей(первые 4 из них используются в 2-ом цикле, последние 4 –в 3-ум цикле). Ключ снова циклически сдвигается влево ещё на 25 бит для получения следующих 8-и подключей и т.д. пока выполнение алгоритма не завершится. Дешифрование осуществляется аналогичным образом, за исключением того, что порядок использования ключей становиться обратным. Причём ряд используемых подключей хаменн на обратные их значения. Подключи расшифровывания являются в основном либо аддетивными либо мультипликативными обратными величинами подключей шифрования.Алгоритм idea может работать в любом режиме блочного шифра , предусмотренном для алгоритма des. Алгоритм idea обладает рядом преимуществ перед des: 1)Он значительно безопаснее , т.к. 128-битный ключ вдвое больше ключа des. 2) Внутренняя структура алгоритма idea обеспечивает лучшую устойчивость к криптоанализу 3) Существующие программные реализации алгоритма idea примерно вдвое быстрее реализации алгоритма des. Алгоритм idea шифрует данные со скоростью 24 Мбит/C
f(Ri-1,Ki).
На рисунке изображён 1 цикл преобразования. При описании алг использовались след обозначения:
- побитовое сложение по модулю 2 (XOR)
- сложение по модулю 2^32(+)
2 целых числа a и b, суммируются, удовл следующим условиям:
0≤a, b≤2^32-1;
a=a32*2^31+ a31*2^30+…+ a2*2+ a1
b=b32*2^31+ b31*2^30+…+ b2*2+ b1
Суммируются по следующему правилу:
a 
На схеме приведены след обозначения:
S – блок подстановки, состоящий из 8 узлов замены;
N1,N2 – 32-разрядные накопители;
CM1 – 32-разрядный сумматор по модулю 2^32;
CM2 – 32-разрядный сумматор по модулю 2;
R-32-разр регистр циклического сдвига;
КЗУ – ключевое запоминающее устр-во на 256бит, состоящее из 8 32-разр накопителей x0,x1…x7;
С целью шифр-я открытых данных в режиме простой замены, эти данные разбиваются на 64-разр блоки T0. Процедура шифр-я 64разр блоков T0 включает 32 цикла (j=1,32). В КЗУ вводят 256 бит ключа K в виде 8 32разр подключей (чисел) ki : k= k7 k6 k5 k4 k3 k2 k1 k0
Последовательность блоков T0 (битов):
T0=(a1(0), a2(0),…, a32(0), b1(0), b2(0),…, b32(0))
T0 разбивается на 2 послед по 32 бита, где b(0)-левые и старшие биты, а а(0) – правые и младшие. Эти послед вводят в накопители N1 и N2 перед началом цикла шифрования, в результате получится:
N1=a(0)= (a32(0), a31(0),…, a1(0))
N2=b(0)= (b32(0), b31(0),…, b1(0))
Первый цикл (j=1) процедуры шифр 64разр блока открытых данных можно описать след уравн:
а(1)=f(a(0) 