28544

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

Доклад

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

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

Русский

2013-08-20

152.5 KB

26 чел.

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


 

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

69218. Статистика основных фондов 28 KB
  ОПФ это здания сооружения передаточные устройства машины и оборудование транспортные средства производственный инвентарь и принадлежности хозяйственный инвентарь рабочий и продуктивный скот многолетние сады и насаждения капитальные затраты по улучшению земель...
69219. Статистичні показники 158 KB
  Статистичний показник це кількісна характеристика соціальноекономічних явищ та процесів в умовах якісного визначення тобто це міра якісного і кількісного відображення певної властивості соціальноекономічного явища чи процесу.
69220. Статистика продукції 138.5 KB
  Промислова продукція - це прямий корисний результат промислово-виробничої діяльності підприємства (фірми), виражений у формі продуктів або виробничих послуг. Отже, звідси: продукція є результатом діяльності підприємства, тому сировина та матеріали, що ще не вступили у виробництво...
69221. Статистичне спостереження, його суть, форми та помилки 112 KB
  Форми статистичного спостереження його види та способи проведення. Програмно методологічні та організаційні питання статичного спостереження. Помилки статистичного спостереження та заходи щодо їх усунення.
69222. Вибірковий метод 437 KB
  Причини і умови застосування та організації вибіркового спостереження. Так для визначення втрат при збиранні урожаю суцільне спостереження потребує значних затрат часу та коштів а при перевірці якості продукції наприклад жирності молока схожості зерна його не можна провести...
69223. Статистичні методи вивчення взаємозв’язків 398.5 KB
  Кореляційно-регресійний аналіз звязку його завдання і основні етапи. Оцінка щільності та істотності кореляційного звязку. При функціональному звязку кожному можливому значенню факторної ознаки відповідає чітко визначене значення результативної ознаки тобто...
69224. Статистичне вивчення динаміки соціально-економічних явищ 507.5 KB
  Для будь-якого динамічного ряду характерні перелік хронологічних дат моментів або інтервалів часу і конкретні значення відповідних статистичних показників які називають рівнями ряду. Приймаючи будь-який інтервал за одиницю послідовність рівнів можна записати так: де число рівнів довжина динамічного ряду.
69225. Предмет, метод та завдання статистики 187.5 KB
  Статистика - самостійна суспільна наука, яка має свій предмет и метод дослідження. Виникла вона з практичної необхідності суспільного життя. Уже в давньому світі з’явилась необхідність підраховувати чисельність жителів держави; рахувати людей, пригодних до військової справи...
69226. Графічний метод зображення статистичних даних 334.5 KB
  Вимоги до статистичного графіка та його основні елементи. Слід нагадати що побудова графіка виправдана якщо він дає будьякі переваги порівняно з цифрами які зведені в ряди або таблиці. Основні елементи графіка.