Образовательный портал

Известные алгоритмы шифрования

Казарян Анаит Рафиковна,
канд. физ.-мат. наук,
учитель информатики школы № 156
с углублённым изучением информатики
Калининского района Санкт-Петербурга
E-mail: Адрес электронной почты защищен от спам-ботов. Для просмотра адреса в вашем браузере должен быть включен Javascript.

АННОТАЦИЯ

Цели: 

• Познавательные: краткое знакомство с известными алгоритмами симметричных криптосистем.

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

• Воспитательные:  воспитание интереса к изучаемому предмету, воспитание познавательной активности и положительного отношения к знаниям.

Методы обучения: объяснительно-иллюстративный, исследовательский.
Результат: развитие умений применять изученные понятия, результаты, методы для решения задач практического характера.
Выводы: объяснительно-иллюстративный, исследовательский.
Ключевые слова: криптология; криптография; криптоанализ; симметричная криптосистема; асимметричная криптосистема; открытый текст; шифр; ключ.
 
Криптологические методы защиты информации являются одними из наиболее мощных средств защиты информации при передаче информации по каналам связи большой протяженности, так как. большинство средств защиты информации в компьютерных системах и сетях базируется на использовании криптографии. Криптология — эта наука о защите информации. Она делится на две части: криптографию и криптоанализ. Криптография – это часть криптологии, связанная с проектированием секретных систем. Криптоанализ – это часть криптологии, связанная со взломом секретных систем. Криптограф ищет методы, обеспечивающие секретность и/или подлинность информации путём шифрования исходного текста. В проектируемой криптографической системе криптограф должен предусмотреть защиту от всех видов атак.  Криптоаналитик же пытается выполнить обратную задачу, раскрывая шифр или подделывая сообщение так, чтобы выдать их за подлинные. Для взлома криптосистемы ему достаточно отыскать единственное слабое звено в цепи криптографической защиты и организовать атаку только против этого звена. Изучение криптоанализа не менее важно, чем криптографии, так как без понимания техник криптоанализа невозможно спроектировать секретные криптографические системы.
Классическая задача криптографии заключается в следующем (см. Рисунок 1,[1]):
Рисунок 1. Классическая схема криптографии. 
Передатчик (Алиса) хочет передать секретную информацию приёмнику (Бобу) по публичному несекретному каналу связи (например, по телефону, по компьютерной сети) таким образом, чтобы третье лицо («злоумышленник» Ева) по перехваченной на канале связи информации не смог бы восстановить исходное сообщение передатчика. Для обеспечения надёжной передачи, передатчик шифрует исходное сообщение (называемое открытым текстом)  с помощью некоторой секретной информации (называемой секретным ключом) и отправляет полученный зашифрованный текст (называемый шифром) по публичному  несекретному каналу связи. Получив шифр, приёмник расшифровывает открытый текст передатчика с помощью секретного ключа. Злоумышленник имеет доступ к каналу связи и может получить шифр, но у него нет секретного ключа. Что такое «секретность» системы, представленной на Рис. 1? Современными методами криптографии эта задача решается с помощью

• симметричных (с закрытым ключом) криптосистем,

• асимметричных (с открытым ключом) криптосистем.

В симметричных криптосистемах для шифрования и дешифрования сообщения используется секретный общий ключ (см. Рисунок 2, [1]).
Рисунок 2. Схема симметричной криптосистемы. 
Этот ключ должен быть передан по секретному каналу связи от передатчика (Алисы) приёмнику (Бобу). На практике реализация симметричных криптосистем наталкивается на серьезные трудности:

• использование общего секретного ключа для шифрования и дешифрования,

• наличие второго секретного канала связи (для передачи секретного ключа).

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

• простота и быстрота построения и реализации,

• высокое быстродействие,

• все классические криптосистемы симметричные (некоторые примеры рассмотрим ниже).

Существует много симметричных криптосистем, которые удовлетворяют практическим требованиям как в смысле безопасности, так и в смысле эффективности. Из известных симметричных криптосистем можно указать DES (Data Encryption Standard) и AES (Advanced Encryption Standard) ([2]). Криптосистема DES, разработанная фирмой IBM для правительства США, была одной из широко используемых (например, в банковской индустрии) криптосистем мира. Криптосистема DES была национальным стандартом шифрования США в 1977-2000 годах. По причине ряда недостатков криптосистемы DES, была создана новая криптосистема AES (создана бельгийскими учёными Дейманом и Рейманом), которая является усовершенствованием криптосистемы DES. Криптосистема AES является национальным стандартом шифрования США с 2000 года.
Идея асимметричных криптосистем впервые была предложена в 1976 году Диффи и  Хеллманом на национальной компьютерной конференции [3] как способ решения указанных выше трудностей симметричных криптосистем. В асимметричных криптосистемах для шифрования и дешифрования сообщения используются различные ключи: для шифрования сообщения используется открытый ключ, являющийся общедоступным, а для дешифрования сообщения используется закрытый ключ, являющийся секретным (см. Рисунок 3, [1]).

Рисунок 3. Схема асимметричной криптосистемы.
 
Приёмник (Боб) публикует свой открытый ключ и алгоритм шифрования, при этом сохраняя в секрете соответствующий секретный ключ. Передатчик (Алиса) из соответствующего справочника берёт открытый ключ и алгоритм шифрования приёмника (Боба), шифрует сообщение, используя открытый ключ и алгоритм шифрования приёмника (Боба) и посылает  полученный шифр приёмнику (Бобу). Приёмник (Боб) получает шифр от передатчика (Алисы), дешифрует шифр, используя свой секретный ключ и алгоритм дешифрования.
Основными свойствами асимметричных криптосистем являются:

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

• знание открытого ключа не даёт возможность определить закрытый ключ.

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

• не требуется секретный общий ключ,

• простая схема обеспечения секретности (не требуется доверяемая третья сторона).

Изобретение асимметричных криптосистем - это одно из важных изобретений в истории секретной коммуникации. Секретность используемых в настоящее время алгоритмов асимметричного шифрования опирается на вычислительную сложность алгоритмов шифрования. Из известных асимметричных криптосистем можно указать криптосистемы RSA, El-Gamal и McEliece (названы в честь своих создателей) ([2]). Криптосистема RSA (создатели Ривест, Шамир и Адлеман (1977 год)) – одна из известных надёжных асимметричных криптосистем.
Приведём примеры построения некоторых классических симметричных криптосистем.
 1.  Шифр Цезаря
Рассмотрим классическую симметричную криптосистему, которая использовалась знаменитым римским императором Юлием Цезарем.
Шифр Цезаря строится по следующему алгоритму ([1], [4]): заменить каждую букву слова четвертой (в порядке следования) буквой алфавита.
Алгоритм шифрования букв английского языка согласно шифру Цезаря можно представить в Таблице 1:

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

a

b

c

Таблица 1. Алгоритм шифрования английского алфавита согласно шифру Цезаря.
Пример 1.1: при исходном тексте meet me at central park с помощью шифра Цезаря получается шифр phhw ph dw fhqwudo sdun.
Замечаниe 1.1: Заметим, что в шифре Цезаря ключ равен 3 (величине сдвига букв алфавита).
Замечаниe 1.2: Возможны модификации шифра Цезаря с другим значением ключа (ключ может быть любым числом от 0 до 25).
Замечаниe 1.3: Шифр Цезаря можно применить и к русскому алфавиту, при этом ключ может быть любым числом от 0 до 32. Алгоритм шифрования букв русского языка согласно модификации шифра Цезаря с ключом, равным 7, можно представить в Таблице 2:

а

б

в

г

д

е

ё

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

а

б

в

г

д

е

ё

Таблица 2. Алгоритм шифрования русского алфавита согласно шифру Цезаря.
Пример 1.2: При шифровании  по указанному в замечании 2.3 алгоритму исходного текста секретные системы получим шифр шлсчлщфгл шпшщлуг.
Замечаниe 1.4: Заметим, что шифр Цезаря является частным случаем шифра подстановки.
Замечаниe 1.5: Мы с вами увидели, что шифр подстановки, шифр Цезаря и его модификации просты в реализации, но их легко можно раскрыть без знания ключа, наблюдая частоту распределения символов в шифрованном тексте и имея таблицу относительных частот букв соответствующего алфавита. Шифр Цезаря был взломан арабами в 9 веке.
2. Шифр Виженера
Рассмотрим классическую симметричную криптосистему по фамилии французского криптографа шестнадцатого столетия Блеза де Виженера.
Шифр Виженера строится по следующему алгоритму ([1], [4]):

1. заменить каждую букву английского языка цифрой согласно Таблице 3:

a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16

 

 

r	s	t	u	v	w	x	y	z
17	18	19	20	21	22	23	24	25

 

Таблица 3. Алгоритм шифрования английского алфавита согласно шифру Виженера.

1. в качестве ключа рассмотреть любую последовательность букв английского языка;

2. заменить ключ последовательностью цифр согласно пункту 1;

3. заменить открытый текст последовательностью цифр согласно пункту 1 (пробелы при замене не учитывать);

4. записать под последовательностью цифр открытого текста последовательность цифр ключа, при этом последовательность цифр ключа записать необходимое число раз;

5. сложить попарно эти две последовательности, при этом если сумма равна или больше 26, то вычесть 26;

6. заменить полученные цифры буквами английского языка согласно пункту 1.

Пример 2.1: Зашифруем исходный текст meet me at central park с помощью шифра Виженера с помощью ключа cipher. Тогда согласно алгоритму (пункты 4. и 5.) ключ cipher заменяется последовательностью цифр (2,8,15,7,4,17), а открытый текст meet me at central park заменяется последовательностью цифр (12,4,4,19,12,4,0,19,2,4,13,19,17,0,11,15,0,17,10). Тогда согласно алгоритму (пункт 6.) получим Таблицу 4:

12	4	4	19	12	4	0	19	2	4	13	19	17	0	11	15	0	17	10
2	8	15	7	4	17	2	8	15	7	4	17	2	8	15	7	4	17	2

 

Таблица 4. Промежуточная таблица шифрования исходного текста согласно шифру Виженера.
Сложив попарно эти две последовательности с возможной заменой (согласно пункту 6. алгоритма), получим последовательность (14,12,19,0,16,21,2,1,17,11,17,12,19,8,0,22,4,8,12). Следовательно,  согласно пункту 7. алгоритма в качестве шифра исходного текста получим последовательность omtaqvcbrlrmtiaweim.
Замечаниe 2.1: Шифр Виженера можно применить и к русскому алфавиту.
Замечаниe 2.2: Заметим, что шифр Виженера является обобщением шифра Цезаря, но он более трудный для построения (по сравнению с шифром Цезаря), а также и для взлома. Шифр Виженера был невзламываемым до середины 19 века, но в 1854 году Ч. Бэббидж нашёл простой теоретико-числовой метод поиска длины ключа и самого ключа. Независимо от него в 1863 году прусский офицер Касисский нашёл подобный метод взлома шифра Виженера. Решения Бэббиджа и Касисского основывались на том, что длина ключа в шифре Виженера может быть найдена путём поиска повторяющихся блоков в шифрованном тексте. Если длина ключа определена, буквы ключа можно определить с помощью анализа частот букв алфавита (как в случае шифра Цезаря).
Замечаниe 2.3: Были предложены различные модификации шифра Виженера, такие как шифр с автоключом, шифр Виженера с перемешанным один раз алфавитом, шифр Вернама ([2], [4]).
 
Список литературы:

1. Работы по теории информации и кибернетике. / Шеннон К. — М.: Изд-во иностранной литературы, 1963.

2. Cryptography. Theory and Practice. / Stinson D.  – University of Waterloo, Ontario, Canada, 2006.

3. Multi-user cryptographic techniques. / Diffie W., Hellman M. – Proceedings of AFIPS National Computer Conference, pp. 109-112, 1976.

4. Основы компьютерной алгебры с приложениями. / Акритас А. – М: Мир, 1994.

You have no rights to post comments