28544

МЕТОДЫ ЗАМЕНЫ

Доклад

Информатика, кибернетика и программирование

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

Русский

2013-08-20

152.5 KB

24 чел.

PAGE  2

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

3.2.2  МЕТОДЫ ЗАМЕНЫ

Шифрование методом замены (подстановки) основано на алгебраической операции, называемой подстановкой. Подстановкой называется взаимно-однозначное отображение некоторого конечного множества М на себя. Число N элементов этого множества называется степенью подстановки. Природа множества M роли не играет, поэтому можно считать, что M = {1, 2, ..., N}.

Если при данной подстановке S число j переходит в Ij, то подстановка обозначается символом S:

В этой записи числа 1, 2, ..., n можно произвольным образом переставлять, соответственно переставляя числаРезультат последовательного выполнения двух подстановок S1 и S2 одной и той же степени также является подстановкой, которая называется произведением подстановок S1 и S2 и обозначается S1S2.

Пусть S – произвольная подстановка степени n. Если для некоторого j число Ij отлично от j, то говорят, что подстановка S действительно перемещает число j; в противном случае – подстановка S оставляет число j на месте.

Количество m чисел, действительно перемещаемых подстановкой S, называется длиной цикла подстановки.

Подстановка S называется транспозицией, если существует пара различных элементов из M, удовлетворяющих условиям:

Любая подстановка разлагается в произведение транспозиций.

В криптографии рассматриваются четыре типа подстановки (замены): моноалфавитная, гомофоническая, полиалфавитная и полиграммная. Далее всюду в примерах, где необходимо, будем использовать кодирование букв русского алфавита, приведенное в табл. 3.2.2. Знак "_" в табл. 2.2 и далее означает пробел.

3.2.2. Коды букв русского алфавита

Буква

А

Б

В

Г

Д

Е

Ж

З

И

Й 10

К

Л

М

Н

О

П

Р

Код

01

02

03

04

05

06

07

08

09

11

12

13

14

15

16

17

Буква

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

27

Ы

Ь

Э

Ю

Я

-

Код

18

19

20

21

22

23

24

25

26

28

29

30

31

32

33

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

Пpимеp. Открытый текст: "ШИФРОВАНИЕ_ЗАМЕНОЙ". Подстановка задана в табл.3. 2.3.

3.2.3. Подстановка шифра

ИТ

А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

Р

ШТ

-

Я

Ю

Э

Ь

Ы

Ъ

Щ

Ш

Ч

Ц

Х

Ф

У

Т

С

Р

ИТ

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

-

ШТ

П

О

Н

М

Л

К

Й

И

З

Ж

Е

Д

Г

В

Б

А

ИТ – алфавит исходного текста ШТ – алфавит шифpтекста. Шифртекст: "ИШМРТЮ_УШЫАЩ_ФЫУТЧ".

Основным недостатком рассмотренного метода является сохранение статистических свойств открытого текста (частота повторения букв) в шифртексте.

Общая формула моноалфавитной замены выглядит в виде:

где Yi i-й символ aлфавитa; k1 и k2 – константы; Xi i-й символ открытого текста (номер буквы в алфавите); N – длина используемого алфавита. Шифр, задаваемый фоpмулой:

где ki i-я буква ключа, в качестве которого используются слово или фраза, называется шифpом Вижинера.

Пример. Открытый текст: "ЗАМЕНА". Ключ: "КЛЮЧ" (табл. 2.4).

3.2.4. Шифр Вижинера

Открытый текст

Ключ

Преобразование

Шифр

З

К

yl= 8 + ll(mod 33) = 19

Т

А

Л

у2 = 1 + 12(mod 33) = 13

М

М

Ю

уЗ = 13 + 31(mod 33) = 11

К

Е

Ч

у4 = 6 + 24(mod 33) = 30

Э

Н

К

у5 = 14 +ll(mod 33) = 25

Ш

А

Л

уб = 1 + 12(mod 33) = 13

М

Шифртекст: "ТМКЭШМ".

Шифр Бофорта – многоалфавитная криптосистема, аналогичная криптосистеме Вижинера. Строками квадрата Бофорта являются строки квадрата Вижинера, записанные в обратном порядке. Криптосистема названа в честь адмирала Френсиса Бофорта. Шифр Бофорта использует  формулы

уi = ki – xi(mod n)  и  yi = xi – ki(mod n).

Гомофоническая замена одному символу открытого текста ставит в соответствие несколько символов шифртекста.

Этот метод применяется для искажения статистических свойств шифртекста.

Пример. Открытый текст: "ЗАМЕНА". Подстановка задана табл.3. 2.5.

3.2.5. Гомофоническая подстановка

Алфавит открытого текста

А

Б

Е

Ж

З

М

Н

17

23

97

47

76

32

55

Алфавит  шифртек-

31

44

51

67

19

28

84

48

63

15

33

59

61

34

Шифртекст: "76 17 32 97 55 31".

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

Полиалфавитная подстановка использует несколько алфавитов шиф-ртекста. Пусть используется k алфавитов. Тогда открытый текст

заменяется шифртекстом

где Fi(Xj) – символ шифртекста алфавита i для символа открытого текста Xj.

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

В этом шифре алфавит располагается в матрице. Открытый текст разбивается на пары символов XiXi+1. Каждая пара символов открытого текста заменяется на пару символов из матрицы следующим образом:

если символы находятся в одной строке, то каждый из символов пары заменяется на стоящий правее его (за последним символом в строке следует первый);

если символы находятся в одном столбце, то каждый символ пары заменяется на символ, расположенный ниже его в столбце (за последним нижним символом следует верхний);

если символы пары находятся в разных строках и столбцах, то они считаются противоположными углами прямоугольника. Символ, находящийся в левом углу, заменяется на символ, стоящий в другом левом углу; замена символа, находящегося в правом углу, осуществляется аналогично;

• если в открытом тексте встречаются два одинаковых символа под
ряд, то перед шифрованием между ними вставляется специальный символ
(например, тире).

Пример. Открытый текст: "ШИФР_ПЛЭЙФЕРА.". Матрица алфавита представлена в табл.3. 2.6.

3.2.6. Матрица алфавита

Шифртекст: "РДИЫ,-СТ-И.ЖЧС".

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

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

Пример. Открытый текст: "ШИФРОВАНИЕ_ЗАМЕНОЙ". Первичный


ключ: "КЛЮЧ". Шифрование с автоключом при использовании открытого текста представлено в табл.3. 2.7.

3.2.7. Шифрование с автоключом при использовании открытого текста

ИТ

Ш

И

Ф

Р

О

В

А

Н

И

Е В 09 И

_

З

А

М

Е

Н

О

Й

Кл

К

Л

Ю

Ч

Ш

И

Ф

Р

О

А

Н

И

Е

 

З

А

М

Код

03

21

19

08

07

12

22

31

24

01

22

10

19

06

22

16

23

ШТ

В

Ф

Т

З

Ж

Л

Х

Ю

Ч

А

Х

Й

Т

Е

Х

П

Ц

ИТ – алфавит исходного текста; Кл – ключ; ШТ – алфавит шифpтекста.

Шифрование с автоключом при использовании криптограммы представлено в табл. 2.8.

3.2.8. Шифрование с автоключом при использовании криптограммы

ИТ – алфавит исходного текста; Кл – ключ; ШТ – алфавит шифpтекста.

3.2.9. МЕТОДЫ ПЕРЕСТАНОВКИ

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

Пример. Открытый текст: "ШИФРОВАНИЕ_ПЕРЕСТАНОВКОЙ". Ключ (правило перестановки): группы из 8 букв с порядковыми номерами 1, 2, ..., 8 переставить в порядок 3-8-1-5-2-7-6-4.

Шифртекст: "ФНШОИАВР_СИЕЕЕРПННТВАОКО".

Можно использовать и усложненную перестановку. Для этого открытый текст записывается в матрицу по определенному ключу k1. Шифртекст образуется при считывании из этой матрицы по ключу k2.

Пример. Открытый текст: "ШИФРОВАНИЕ_ПЕРЕСТАНОВКОЙ". Матрица из четырех столбцов. Ключи: k1 = {5-3-1-2-4-6}; k2 = {4-2-3-1}. Запись по стpокам производится в соответствии с ключом k1. Чтение по столбцам в соответствии с ключом k2 (табл. 3.2.9.).

3.2.9. Шифрование перестановкой

Шифртекст: "ПСНОРЙЕРВАИК_ЕАНФОИЕОТШВ".

Наиболее сложные перестановки осуществляются по гамильтоновым путям, которых в графе может быть несколько.


Пример.   Открытый   текст:   "ШИФРОВАНИЕ_ПЕРЕСТАНОВКОЙ". Ключ: гамильтонов путь на графе (рис. 2.13).

Общий вид Маршрут 1 Маршрут 2

Рис.3. 2.13. Гамильтоновы пути на графе

Шифртекст: "ШАОНИРФВИЕЕСЕП_РТОВИАОНК".

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

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

В 1992–1994 гг. идея применения объемной перестановки для шифрования открытого текста получила дальнейшее развитие. Усовершенствованная схема перестановок по принципу кубика Рубика, в которой наряду с открытым текстом перестановке подвергаются и функциональные элементы самого алгоритма шифрования, легла в основу секретной системы "Рубикон". В качестве прообразов пространственных многомерных структур, на основании объемных преобразований которых осуществляются перестановки, в системе "Рубикон" используются трехмерные куб и тетраэдр. Другой особенностью системы "Рубикон" является генерация уникальной версии алгоритма и ключа криптографических преобразований на основании некоторого секретного параметра (пароля). Это обеспечивает как дополнительные трудности для криптоанализа перехваченных сообщений нарушителем (неопределенность примененного алгоритма), так и возможность априорного задания требуемой криптостойкости. Криптостойкость данной системы определяется длиной ключа, криптостойкостью отдельных функциональных элементов алгоритма криптографических преобразований, а также количеством таких преобразований.

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

3.2.5. ГАММИРОВАНИЕ (ШИФРОВАНИЕ С ПОМОЩЬЮ ДАТЧИКАПСЕВ-ДОСЛУЧАЙНЫХ ЧИСЕЛ)

Различают два случая: метод конечной гаммы и метод бесконечной гаммы. В качестве конечной гаммы может использоваться фраза, а в качестве бесконечной – последовательность, вырабатываемая датчиком псевдослучайных чисел.

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

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

Чтобы получить линейные последовательности элементов гаммы, длина которых превышает размер шифруемых данных, используются датчики ПСЧ. На основе теории групп было разработано несколько типов таких датчиков. В настоящее время наиболее доступными и эффективными являются конгруэнтные генераторы ПСЧ. Они вырабатывают последовательности псевдослучайных чисел Т(i), описываемые соотношением

где А и С – константы; Т(0) – исходная величина, выбранная в качестве порождающего числа.

Для шифрования данных с помощью датчика ПСЧ может быть выбран ключ любого размера. Например, пусть ключ состоит из набора чисел размерностью b, где j = 1, 2, ...., N. Тогда создаваемую гамму шифра G можно представить как объединение непересекающихся множеств

где– множество соответствующих j-му сегменту данных и получен-

ных на основе порождающего числаопределенного как функция от

Х(j) (например, ПСЧ, полученное на основе.

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

где символобозначает операцию "исключающее ИЛИ".

Шифрование с помощью датчика ПСЧ является довольно распространенным криптографическим методом, а качество шифра определяется не только и не столько характеристиками датчика, сколько алгоритмом получения гаммы. Хорошие результаты дает метод гаммирования с обратной связью, который заключается в том, что для получения сегмента гаммы используется контрольная сумма определенного участка шифруемых данны


PAGE  


PAGE  7


 

А также другие работы, которые могут Вас заинтересовать

43394. Построение схемы Делитель частоты на 10 на JK-триггерах 79 KB
  Поставленная задача: Изучить как работает JKтриггеры и построить схему Делитель частоты на 10 на JKтриггерах. В остальных случаях он функционирует в соответствии с таблицей истинности RSтриггера при этом вход J эквивалентен входу S а вход K входу R. JKтриггер относится к разряду универсальных триггеров поскольку на его основе можно построить RS D и Tтриггера.
43395. Разработка информационно-поискового справочника «Шеф-повар» 1.14 MB
  В реальных задачах информация, которую требуется обрабатывать, может иметь достаточно сложную структуру. Для ее адекватного представления используются типы данных, построенные на основе базовых типов данных, массивов и указателей. Языки высокого уровня позволяют программисту определять свои типы данных и правила работы с ними, т.е. типы, определяемые пользователем. В языке Си к ним относятся структуры, объединения и перечисления. Рассмотрим их более подробно.
43397. Диагностика влияния молодёжных субкультур на развитие ценностных ориентаций подростка 227 KB
  Объединение подростков в отдельные группы обусловлено тем, что подростки, как наиболее чуткая и восприимчивая группа первой воспринимает новые формы развития в сфере досуга со всеми позитивными и негативными явлениями. Их не могут до конца удовлетворить существующие общепринятые развлечения, и способы провождения времени
43398. Расчет L50MC/MCE MAN-B and W DIESEL A/S 260.5 KB
  Судовой дизель фирмы МАН - Бурмейстер и Вайн (MAN B_W Diesel A/S), марки L50MC/MCE - двухтактный простого действия, реверсивный, крейцкопфный с газотурбинным наддувом (с постоянным давлением газов перед турбиной) со встроенным упорным подшипником, расположение цилиндров рядное, вертикальное.
43399. Аналіз ліквідності, платоспроможності та кредитоспроможності підприємства на матеріалах базового підприємства 193.5 KB
  Він характеризується забезпеченістю фінансовими ресурсами які необхідні для нормального функціонування підприємства доцільністю їх розміщення та ефективністю використання фінансовими взаємовідносинами з іншими юридичними та фізичними особами платоспроможністю та фінансовою стійкістю. Сигнальним показником в якому проявляється фінансовий стан є платоспроможність підприємства тобто його здатність своєчасно задовольняти платіжні вимоги постачальників сировини матеріалів техніки згідно з господарськими угодами повертати банківські...
43400. Базові засоби мови С++. Технологія складу програм 244 KB
  Для полегшення сприйняття таких алгоритмів їх розбивають на подзадачи кожна з яких розглядається як окреме завдання й може бути вирішена при заданих значеннях її аргументів. Позначення відноситься до операції нарощування С. Основне його призначення спростити та зробити більш приємним процес програмування для окремого програміста. Ключові зарезервовані слова це слова які мають спеціальне значення для компілятора.
43401. Проектування інформаційної підсистеми складу магазина Фуршет 3.22 MB
  Логічна модель бази даних Фізична модель бази даних Схема бази даних у MS SQL Server 2008 DtModule підсистеми Главная форма О программе Безопасность Форми для перегляду: Акт прийома Накладная Квитанция Складской ордер Поставщики Товар Автотранспорт Операторы Форма Меню форми для введення даних Акт прийома Поставщик Товар НУХТ АКС46 31 Листів.ПЗ 3 Лист. Лист. НУХТ АКС46 31 Листів.
43402. Мониторинг, система и меры антикризисного управления 157.5 KB
  Мировая практика показывает то что проработанная политика государственного регулирования является мощным фактором подъема экономики страны. Задачи государственного регулирования экономики это набор целевых установок органов власти при регулировании экономических отношений. Раньше в стране преобладала установка официального планомерного и пропорционального а следовательно и бескризисного развития экономики стало быть нужда в антикризисном управлении отсутствовала. Отмечая важность этой темы для нашей экономики необходимо указать...