Описание объекта исследования

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

Открытый текст: meet me after the toga party

Шифрованный текст: PHHW PH DIWHU WKH WRJD SDUMB

Алфавит считается «циклическим» поэтому после Z идет А. Определить преобразование, можно перечислив все варианты, как показано ниже.

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

Шифрованный текст: DEFGHIJKLMNOPQRSTUVWXYZABC

Если каждой букве назначить числовой эквивалент (а=1, b=2, с=3 и т.д.), то алгоритм можно выразить следующими формулами. Каждая буква
открытого текста р заменяется буквой шифрованного текста С:

C = E (p) = (p +3)mod(26).

В общем случае сдвиг может быть любым, поэтому обобщенный
алгоритм Цезаря записывается формулой

С = Е (р) = (р +k) mod (26),

где k принимает значение в диапазоне от 1 до 25. Алгоритм дешифрования
также прост:

р = D (C) = (С-k)mod (26).

Если известно, что определенный текст был шифрован с помощью шифра Цезаря, то с помощью простого перебора всех вариантов раскрыть шифр очень просто - для этого достаточно перебрать 25 возможных вариантов ключей. На рисунке 4 показаны результаты применения этой стратегии к указанному выше сообщению. В данном случае открытый текст распознается в третьей строке.

Применение метода последовательного перебора всех возможных вариантов оправдано, если выполняются три важные характеристики данного шифра:

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

- необходимо перебрать небольшое количество вариантов;

- язык открытого текста известен и легко узнаваем.

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

практически бесполезным. Например, алгоритм DES, использующий 56-
битовые ключи, требует при последовательном переборе рассмотреть
пространство из 2⁵⁶, или более чем 7x10¹⁶ ключей.

 

PHHW PH DIWHU WKH WRJD SDUMB

KEY

 

	oggv	og	chvgt	vjg	vqic	rctva
	nffu	nf	bgufs	uif	uphb	qbsuz
	meet	me	after	the	toga	party
	ldds	ld	zesdq	sgd	snfz	ozqsx
	kccr	kc	ydrcp	rfc	rmey	nyprw
	jbbq	jb	xcqbo	qeb	qldx	mxoqv
	iaap	ia	wbpan	pda	pkcw	lwnpu
	hzzo	hz	vaozm	ocz	ojbv	kvmot
	gyyn	gy	uznyl	nby	niau	julns
	fxxm	fx	tymxk	max	mhzt	itkmr
	ewwl	ew	sxlwj	lzw	lgys	hsjlq
	dvvk	dv	rwkvi	kyv	kfxr	grikp
	cuuj	cu	gvjuh	jxu	jewq	fqhjo
	btti	bt	puitg	iwt	idvp	epgin
	assh	as	othsf	hvs	hcuo	dofhm
	zrrg	zr	nsgre	gur	gbtn	cnegl
	yggf	yg	mrfqd	ftq	fasm	bmdfk
	xppe	xp	lqepc	esp	ezrl	alcej
	wood	wo	kpdob	dro	dyqk	zkbdi
	vnnc	vn	jocna	cqn	cxpj	yjach
	ummb	um	inbmz	bpm	bwoi	xizbg
	tlla	tl	hmaly	aol	avnh	whyaf
	skkz	sk	glzkx	znk	zumg	vgxze
	rjjy	rj	fkyjm	ymj	ytlf	ufwyd
	qiix	qi	ejxiv	xli	xske	tevxc

Рисунок 4 - Криптоанализ шифра простой замены (шифра Цезаря) методом перебора всех вариантов ключей

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

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

 

 

Таблица 1 - Вероятности p (С) появления символов в среднестатистическом тексте для русского языка

 

Буква	p (C)	Буква	p (C)	Буква	p (C)
О	0,090	М	0,026	Й	0,010
Е	0,072	Д	0,025	Х	0,009
Ф	0,062	П	0,023	Ж	0,007
И	0,062	У	0,021	Ш	0,006
Н	0,053	Я	0,018	Ю	0,006
Т	0,053	З	0,016	Ц	0,004
С	0,045	Ы	0,016	Щ	0,003
Р	0,040	Б	0,014	Э	0,003
В	0,038	Ь,Ъ	0,014	Ф	0,002
Л	0,035	Г	0,013
К	0,028	Ч	0,012

 

Таблица 2 - Вероятности р (С)появления символов в среднестатистическом тексте для английского языка

 

Буква	p (C)	Буква	p (C)	Буква	p (C)
E	0,131	N	0,071	H	0,053
T	0,104	R	0,068	D	0,038
A	0,082	I	0,063	L	0,034
O	0,080	S	0,061	F	0,029
C	0,028	P	0,020	X	0,002
M	0,025	W	0,015	J	0,001
U	0,024	B	0,014	Q	0,001
G	0,020	V	0,009	Z	0,001
Y	0,020	K	0,004

 

Если сообщение достаточно длинное, этой методики уже может быть достаточно для распознавания текста. Выяснив значения всего лишь 3-4 букв можно расшифровать уже значительную часть сообщения. Продолжая анализ частоты появления букв, а также применяя метод проб и ошибок, необходимо воспользоваться особенностями языка. Например, для русского языка это удвоение букв, окончания слов, короткие слова типа «как», «или», союзы и т.п.

Порядок выполнения работы

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

1.1. Выполнить частотный анализ символов зашифрованного текста.

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

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

1.4. Выбрать 3-4 наиболее частых символа в шифртексте и русском языке с одинаковыми рангами.

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

2. Использовать результаты грамматического анализа шифртекста и на этой основе произвести полное дешифрование текста.

2.1. Выполнить предварительный анализ и расшифровку коротких
слов (предлогов, местоимений, союзов междометий и т.п.) с использованием результатов, полученных в п. 1.5.

2.2. Для идентификации остальных символов шифртекста
воспользоваться особенностями русского языка (удвоения букв, окончания
слов и т.п.).

Содержание отчета

 

- Титульный лист

- Результаты частотного анализа шифрованного текста для первых символов, имеющих частоту большую 0,04

- Ранжирование наиболее часто встречающихся символов в порядке убывания.

- Таблица замены наиболее часто встречающихся символов шифртекста на соответствующие им по рангу символы в русском языке.

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

- Таблица ранжирования символов, имеющих в расшифрованном тексте частоту большую 0,04, и сравнения с ранжированием наиболее частых символов русского языка.

- Ответы на контрольные вопросы.

- Выводы.

Варианты заданий

Варианты для выполнения лабораторной работы представлены в таблице 3

 

Таблица 3

 

№ варианта	Шифртекст
	СЛБПЗНЮЛЦХБО КИЮНЯВО МУИ АИЭЦО НЗЛЦКЭЫ ЕВЦВББ ЕЦЦФЦЗРФЦЫЦЦО НЮЛНТВРИ ЛЦЕЯИЭР ЯЛМЮБД ВЦМС АИЭЫЬ СНЗНЛНБ ОФЭОИЗКО БЕМЧИВБИ Б КНЕЯЦВБИ СЛБПЗНЮЛЦХБЧИКСБД ПЛИНГЛЦЕНФЦВББ Б ЦЭЮНЛБЗТНФ
	ФЕЫМК ЖПВ ЗЫВЮЫЦТТНР СВЯ ФНИЯЬШННРЕ Ф ЗЫВЮЫЦТТМ Е ФНИЯЫОЬЩЕЕ КФВЕ СВЗЕЕ Ф ЯЫМЮЕИ ЗЫВЮЫЦТТР ЗВТЕТВ ХМНСАЕЕ ЫЦКЗЫВКПЫЦНИНЕО ФЕЫМК ФРЗВЭНОИП НИУИЭЦПИЭЧНМЬ ХМНСАЕЬ ЯЭО КЕКПИТР
	ЛПВ ОФЯОИПКО ЦЕЮФТВЭ ЭЕИИЭ БЮЩЭПР ВПЫЮСИТЭИ АЕЮЫЮ ЛПВ ОФЯОИПКО ШЮЫЮУПИЫТВЭ ВКВГИТТВКПЗЬ БЮЩЭПР ЧВКПВОТТВИ ВСЭЕЮТЭИ АЕЮЫЮ ЭКУАК КПФВ ФИЕИТЭО ФВЭТР
	ЧПДШЭЗ ЖЮШ ГЮДШИП ГЯНФШЭШФ ЯГЧШЭЗБАУНПО ЕЭО ПАЮУТЮЯЫЯИПМЯЯ ШКЗУИЮП БПЕПТЯУ ЧШДШЭО Я ГФОБПТТШЦШ Г ТЯН ЯЕУТЮЯЫЯИПЮШДП ЧШЭЗБШФПЮУЭО ДПГГНПЮДЯФПУЮГО ИПИ ЕШИШБПЮУЭЗГЮФШ ЧДПФП ТП ЯГЧШЭЗБШФПТЯУ ФШБНШСТШГЮУЯ ГФОБПТТРВ Г ЕПТТРН ЯЕУТЮЯЫЯИПЮШДШН ЧШЭЗБШФПЮУЭО
	ЮДБОТУИАА ИБТЗ ИБЕЧЗЬЮГДТПО ЧДБСДПЕЕП У ИПЦЯЩАЕАУО АЭА НГАУЮФАЮГЭЗТБ ЧБЭГШТРЕА ЫЯТИМАОЕА УБНГДЦПЩПО НБЧБЭТАЮГЭЗТРГ УИДРЮРГ ЫЯТИМАА ЮПАИБЕ АУЧБЭЗШЯЬЩАГ ШПИБТТРГ ЧДПФП ФРЧБЭТОЫЦАГ ГГ ЧДБМГУУП ФБ ФДГН ШПЩАЮГ
	ЕИХЭДЫВФЮТЭИ ЖПВ ЧИЫИФВЕ ХЭДЫВФЮТТВЦВ ПИУКПЮ ЭЯЭ ЕЮТТРШ Ф ВЫЭЦЭТЮЯЗТРЭ ПИУКП ЭЯЭ ЕЮТТРИ ТЮБРФЮИНРИ ВПУЫРПРН ПИУКПВН ПВ СИ ЛПВ Э ЫЮКХЭДЫВФЮТЭИ
	ГУИДУЮТРЯ ИЭЬЛ ЖЮШ ИЭЬЛ ЧДЯНУТОУНРЯ Ф ГЯГЮУНУ ГЯННУЮДЯЛТШЦШ ХЯЫДШФПТЯО ШКУ АЛПГЮФАЬЩЯУ Ф ШКНУТУ ЕПТТРНЯ ГЮШДШТР ЕШЭСТР ГШФНУГЮТШ ЯГЧШЭЗБШФПЮЗ ШЕЯТ Я ЮШЮ СУ ИЭЬЛ ИШЮШДРЯ ЕШЭСУТ ШГЮПФПЮЗГО ГУИДУЮТРН ЛЮШКР ГФОБЗ ШГЮПФПЭПГЗ ГУИДУЮТШЯ
	ИКЯЭ КИУЫИПТРИ КФИЕИТЭО ВУЮБРФЮЬПКО ЫЮКУЫРПРНЭ УИН ПВ ЫЮТЗХИ ФЫИНИТЭ ПВ ИЦВ КЯИЕАИП АГЭПЗ ЫЮФТВ УЮУ Э ПВЦВ УВНА ВТ ЖПЭ КФИЕИТЭО ВПУЫРЯ ФВИТТВИ ЭКУАККПФВ
	ЦНЦЭЕБ Е НЦГЭЬЯИНЕИ ПИВЫЕО Е ВЗРП НЕСВЮЯЦ НИ ЯВЭУНР ЕКСЭЬЛЦПЧ ЯЫМЮ ЯЫМЮЦ ЕЭЕ ВПНВКЕПЧКО ЯЫМЮ С ЯЫМЮМ К ЗЫИНИГЫИУИНЕИТ НЦЗЫВПЕФ ВНЕ ЯВЭУНР ЯВЗВЭНОПЧ ЯЫМЮ ЯЫМЮЦ

Контрольные вопросы

1. Что такое энтропия языка?

2. Что понимается под избыточностью сообщения?

3. Что такое шифр простой замены?

4. Объясните принцип дешифрования шифра простой замены.

5. Объяснить, почему при вскрытии шифра простой замены используется не полная ранжировка по частоте всех символов русского языка, а лишь 3-4 наиболее частых символов, как в п. 1.4?

6. Какие основные разновидности шифров простой замены применялись в прошлом?

7. Правила шифрования/дешифрования шифра Цезаря.

Литература

1. Бабаш А.В., Шанкин Г.П. История криптографии. Учебное пособие. -М.»Гелиос АРВ», 2001 г.

2. Столингс В. Криптография и защита сетей. Принципы и практика. 2-е изд. - М.: Вильямс, 2001.

Лабораторная работа №2
ИССЛЕДОВАНИЕ ШИФРА ПЕРЕСТАНОВКИ (ШИФР КАРДАНО)

Цель работы: Исследовать шифр Кардана. Разработать алгоритмы
шифрования и дешифрования.