Лекции.Орг


Поиск:




Симметричные криптосистемы




Все мно­го­об­ра­зие су­ще­ст­вую­щих крип­то­гра­фи­че­ских ме­то­дов мож­но све­сти к сле­дую­щим клас­сам пре­об­ра­зо­ва­ний:

 
 

 


Мо­но- и мно­го­ал­фа­вит­ные под­ста­нов­ки.

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

Пе­ре­ста­нов­ки.

Так­же не­слож­ный ме­тод крип­то­гра­фи­че­ско­го пре­об­ра­зо­ва­ния. Ис­поль­зу­ет­ся как пра­ви­ло в со­че­та­нии с дру­ги­ми ме­то­да­ми.

Гам­ми­ро­ва­ние.

Этот ме­тод за­клю­ча­ет­ся в на­ло­же­нии на ис­ход­ный текст не­ко­то­рой псев­до­слу­чай­ной по­сле­до­ва­тель­но­сти, ге­не­ри­руе­мой на ос­но­ве клю­ча.

Блочные шифры.

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


Перестановки

Перестановкой s набора целых чисел (0,1,...,N-1) называется его переупорядочение. Для того чтобы показать, что целое i пере­мещено из позиции i в позицию s(i), где 0 £ (i) < n, будем использовать запись

s=(s(0), s(1),..., s(N-1)).

Число перестановок из (0,1,...,N-1) равно n!=1*2*...*(N-1)*N. Введем обозначение s для взаимно-однозначного отображения (гомо­морфизма) набора S={ s 0, s 1,..., s N-1}, состоящего из n элементов, на себя.

s: S ® S

s: s i ® s s(i), 0 £ i < n

Будем говорить, что в этом смысле s является перестановкой элементов S. И, наоборот, автоморфизм S соответствует пере­становке целых чисел (0,1,2,.., n -1).

Криптографическим преобразованием T для алфавита Zm называется последовательность автоморфизмов: T={T(n):1£n<¥}

T(n): Zm,n®Zm,n, 1£n<¥

Каждое T(n) является, таким образом, перестановкой n -грамм из Zm,n.

Поскольку T(i) и T(j) могут быть определены независимо при i¹j, число криптографических преобразований исходного текста размерности n равно (mn)![2]. Оно возрастает непропорционально при увеличении m и n: так, при m =33 и n =2 число различных криптографических преобразований равно 1089!. Отсюда следует, что потенциально существует большое число отображений исходного текста в шифрованный.

Практическая реализация криптогра­фических систем требует, чтобы преобразо­вания {T k: k Î K } были определены алгоритмами, зависящими от относительно небольшого числа параметров (ключей).

Сис­те­мы под­ста­но­вок

Определение Подстановкой p на алфавите Zm называется автоморфизм Zm, при котором буквы исходного текста t замещены буквами шифрованного текста p(t):

Zm à Zm; p: t à p(t).

Набор всех подстановок называется симметрической группой Zm è будет в дальнейшем обозначаться как SYM(Zm).

Утверждение SYM(Zm) c операцией произведения является группой, т.е. операцией, обладающей следующими свойствами:

Замкнутость: произведение подстановок p1p2 является подста­новкой:

p: tàp1(p2(t)).

Ассоциативность: результат произведения p1p2p3 не зависит от порядка расстановки скобок:

(p1p2)p3=p1(p2p3)

Существование нейтрального элемента: постановка i, опре­деляемая как i(t)=t, 0£t<m, является нейтральным элементом SYM(Zm) по операции умножения: ip=pi для "pÎSYM(Zm).

Существование обратного: для любой подстановки p существует единственная обратная подстановка p-1, удовлетворя­ющая условию

pp1=p1p=i.

Число возможных подстановок в симметрической группе Zm называется порядком SYM(Zm) и равно m!.

Определение. Ключом подстановки k для Zm называется последовательность элементов симметрической группы Zm:

k =(p 0, p 1,..., p n-1,...), p nÎSYM(Zm), 0£n<¥

Подстановка, определяемая ключом k, является крипто­гра­фи­ческим преобразованием T k, при помощи которого осуществляется преоб­разование n -граммы исходного текста (x0,x1,..,xn-1) в n -грамму шифрованного текста (y0,y1,...,yn-1):

yi= p (xi), 0£i<n

где n – произвольное (n=1,2,..). T k называется моноалфавитной под­ста­новкой, если p неизменно при любом i, i=0,1,..., в противном случае T k называется многоалфавитной подстановкой.

Примечание. К наиболее существенным особенностям подста­новки T k относятся следующие:

1. Исходный текст шифруется посимвольно. Шифрования n -граммы (x0,x1,..,xn-1) и ее префикса (x0,x1,..,x s -1) связаны соотношениями

T k (x0,x1,..,xn-1)=(y0,y1,...,yn-1)

T k (x0,x1,..,x s -1)=(y0,y1,...,y s -1)

2. Буква шифрованного текста yi является функцией только i-й компоненты ключа pi и i-й буквы исходного текста x i.

Подстановка Цезаря

Подстановка Цезаря является самым простым вариантом подстановки. Она относится к группе моноалфавитных подстановок.

Определение. Подмножество Cm={C k: 0£ k <m} симметрической группы SYM(Zm), содержащее m подстановок

C k: j®(j+ k) (mod m), 0£ k < m,

называется подстановкой Цезаря.

Умножение коммутативно, C k Cj=CjC k =Cj+ k , C0 – идентичная подстановка, а обратной к Cк является C k -1=Cm- k , где 0< k <m. Семейство подстановок Цезаря названо по имени римского императора Гая Юлия Цезаря, который поручал Марку Туллию Цицерону составлять послания с использованием 50-буквенного алфавита и подстановки C3.

Подстановка определяется по таблице замещения, содержащей пары соответствующих букв “исходный текст – шифрованный текст”. Для C3 подстановки приведены в Табл. 1. Стрелка (à) означает, что буква исходного текста (слева) шифруется при помощи C3 в букву шифрованного текста (справа).

Определение. Системой Цезаря называется моноалфа­витная подстановка, преобразующая n -грамму исходного текста (x0, x 1,..,xn-1) в n ‑грамму шифрованного текста (y0,y1,...,yn-1) в соответствии с правилом

yi=C k (xi), 0£i<n.

Например, ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯ посредством подстановки C3 преобразуется в еюыолхиврсеюивцнгкгрлб.

Таблица 1.

Аàг Йàм Тàх Ыàю
Бàд Кàн Уàц Ьàя
Вàе Лàо Фàч Эà_
Гàж Мàп Хàш Юàа
Дàз Нàр Цàщ Яàб
Еàи Оàс Чàъ _àв
Жàй Пàт Шàы  
Зàк Рàу Щàь  
Иàл Сàф Ъàэ  

 

При своей несложности система легко уязвима. Если злоумышленник имеет

1) шифрованный и соответ­ствующий исходный текст или

2) шифрованный текст выбранного злоумыш­ленником исходного текста,

то определение ключа и дешифрование исходного текста тривиальны.

Более эффективны обобщения подстановки Цезаря - шифр Хилла и шифр Плэйфера. Они основаны на подстановке не отдельных символов, а 2-грамм (шифр Плэйфера) или n -грамм[3] (шифр Хилла). При более высокой криптостойкости они значительно сложнее для реализации и требуют достаточно большого количества ключевой информации.





Поделиться с друзьями:


Дата добавления: 2016-11-23; Мы поможем в написании ваших работ!; просмотров: 501 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Самообман может довести до саморазрушения. © Неизвестно
==> читать все изречения...

1028 - | 877 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.008 с.