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


 

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

70463. Проблема оптимального и эффективного поведения в конфликт 48 KB
  Методы прекращения конфликта. Уклонение Такой стиль поведения обычно выбирают в тех случаях когда: проблема вызвавшая столкновение не представляется субъекту конфликта существенной; предмет расхождения по его мнению мелочный основан на вкусовых различиях не заслуживает траты времени и сил...
70465. Общение в единстве процессов обмена информации, восприятия и понимания людьми друг друга, воздействия и взаимодействия 50 KB
  Из определения общения вытекает что это сложный процесс в который входят три составляющие: коммуникативная сторона общения обмен информацией между людьми; интерактивная сторона организация взаимодействия между индивидами; перцептивная сторона процесс восприятия друг друга партнерами...
70466. Социально-психологические закономерности формирования первого впечатления о человеке 29.5 KB
  Среди факторов которые определяют характер формирующегося у нас впечатления о человеке которого мы встречаем в своей жизни впервые важнейшее значение имеют особенности внешнего облика и поведения человека о котором у нас формируется мнение.
70467. Механизмы межличностного восприятия 27.5 KB
  Значительное число исследований восприятия межличностного посвящено изучению формирования первого впечатления о человеке. В них выясняются закономерности достраивания образа другого человека на основе наличной обычно ограниченной информации о нем а также при выявлении...
70468. Психология воздействия как область социальной психологии 42.5 KB
  Психология воздействия одно из самых традиционных направлений социально-психологического знания. Однако несмотря на это проблематика психологического воздействия и сегодня продолжает оставаться пожалуй наиболее популярной и интегрирующей сферой исследовательских и практических интересов...
70469. Социально-психологические механизмы и факторы формирования убеждений 32 KB
  Во-первых образуя упорядоченную систему взглядов и представлений человека совокупность убеждений выступает как его мировоззрение; во-вторых под убеждением понимают процесс усвоения человеком внешнего мира что предполагает качественное изменение исходных установок под влиянием жизненного...
70470. Межличностные отношения, их виды, динамика, мехнизмы формирования и развития 36 KB
  Межличностные отношения их виды динамика мехнизмы формирования и развития Межличностные отношения это отношения складывающиеся между отдельными людьми. Межличностные отношения делятся на следующие виды: 1 официальные и неофициальные; 2 деловые и личные; 3 рациональные и эмоциональные...
70471. Социально-психологические характеристики больших групп 42.5 KB
  Социально-психологические характеристики больших групп Большая социальная группа количественно не ограниченная социальная общность имеющая устойчивые ценности нормы поведения и социально-регулятивные механизмы партии этнические группы производственно-отраслевые и общественные организации.