Розділ 2. Симетричні криптосистеми

Тема 3. Шифри заміни і перестановки

24. Шифр заміни (підстановки).

Шифр заміни (шифр підстановки) – метод шифрування, при якому кожен елемент тексту взаємно однозначно заміняється одним, або декількома знаками деякого алфавіту. Шифр простої заміни заміняє кожен знак алфавіту відкритого тексту на деякий знак з того ж алфавіту, Результат заміни не залежить від розташування знака у відкритому тексті. Ключами для шифрів заміни є таблиці заміни.

Шифр двозначної заміни

						T O B E O R N O T T O B E 133002243014113013 13300224
	v	p	b	a	c
	q	n	z	t	r
	d	u	x	l	e
	o	j	s	i	f
	k	g	v	h	m
	w

У загальному випадку, перетворення відкритого тексту в шифрах заміни задається за допомогою різних таблиць, що звуться таблиць заміни. Таблиці заміни є ключами.

Шифри заміни перетворять на кожнім такті групу символів. Кількість знаків у групі при цьому фіксовано і називається значністю групи. Групи значності 2 називаються біграмами, значності 3 -триграмами, значности 4 – чотириграмами і так далі. У загальному випадку групи значності n називаються n-грамами.

Є можливою побудова шифра, аналогічного шифру заміни, коли в такті шифрування можуть перетворюватися групи різної значности. Така властивість характеризує шифрсистеми, що називаються кодами.

Основною слабкістю шифру простої заміни є відображення в частоті шифрпозначень ймовірнисних властивостей літер відкритого тексту. У зв'язку з цим можливо удосконалення такого шифру. Можна додати кожному знаку відкритого тексту декілька шифрпозначень, причому тим більше, чим більше ймовірність появи знаку у відкритому тексті. Такий шифр називається шифром пропорційної заміни.

25. Криптосистема Віжінера.

Криптосистема Віжінера є однією з найстаріших і найбільш відомих систем багатоалфавітної підстановки.

Нехай потрібно зашифрувати відкритий текст на ключі . Занумеруємо букви алфавіту відкритого тексту (наприклад, українського) і ключа числами: А↔00, Б↔01, В↔02, …, Я↔32, пробіл↔33. Підпишемо під послідовністю чисел повідомлення послідовність чисел ключа і додамо числа цих послідовностей за модулем , де – потужність алфавіту повідомлень (у нас ). Рівняння шифрування і розшифрування -ої букви повідомлення виражаються відповідно формулами:

, ,

, ,

де , , – номери букв у відкритому тексті, криптограмі і ключі відповідно.

26. Шифри гамування.

Розрізняють два види гамування - модульне і табличне.

При модульному гамуваннісимволи алфавіту відкритого тексту, попередньо замінені на числа, складаються за модулем з елементами деякої числової послідовності, що називається гамою. Гама є ключом. Кількість знаків в алфавіті називається модулем гаммирования.

При табличному гамуванні, перед зашифруванням формується двохрядковий запис, де в одному рядку послідовно виписано знаки відкритого тексту, а в іншій - відповідні знаки гами. Кожному знакові відкритого тексту відповідає свій знак гами, тобто вони утворюють вертикальні біграми знаків. Вертикальні біграми заміняються на знаки шифротекста за допомогою таблиці таблиці. Для реалізації взаємно однозначного перетворення, така таблиця має бути так званим «латинським квадратом», тобто будь-який її рядок, і будь-який стовпець повинні являти собою перестановку знаків заданого алфавіту (або чисел від 1 до m). Таким чином, в кожнім стовпці і рядку даної таблиці всі елементи мають бути різні. Наприклад, для m=5:

27. Шифр Вернама (одноразовий шифр-блокнот).

У 1926 році американський інженер Г.Вернам запропонував для зашифрування кожного біта відкритого тексту використовувати свій ключ.

У системі Г.Вернама потрібно, щоб джерело ключів виробляло випадкову равновероятную двоичную послідовність, знаки якої незалежні і щоб черговий біт відкритого тексту перешифровувався черговим бітом ключа (гами).

К.Шеннон показав, що система Г.Вернама не дешифрується навіть при повному переборі усіх варіантів послідовності гами, внаслідок відсутності критерію відкритого тексту.

На практиці застосовуються послідовності гами, з параметрами, що наближаються до вимог системи Г.Вернама.

Однак чисто випадкова послідовність (у принципі) може містити неякісні ділянки. Тому необхідно розробляти математичні алгоритми для її коректування, що призводить до необхідності формальної оцінки якості гами. Проте, криптосистемы, основані на подібному підході, існують.

У свій час використовувався ручний шифр гамування, для якого гама зберігалася у виглядіі блокнота з відривними аркушами. Після використання чергової сторінки блокнота вона знищувалася.

Можливо, з цієї причини шифр Вернама часто називають одноразовим шифр-блокнотом (one-time pad), хоча, по суті, він є шифром з одноразовою гамою.

28. Шифри перестановки. Шифр вертикальної перестановки.

Відмінність цього типу шифра від шифрів заміни полягає в тому, що при зашифруванні буква відкритого тексту переходить не у фіксований знак алфавіту, а в іншу букву того ж відкритого тексту, скажемо , у результаті чого букви розташовуються на нових місцях, тобто переставляються. Ключом для даного шифра служить таблиця заміни індексів (номерів місць) елементів тексту. У загальному випадку розмір таблиці заміни дорівнює довжині відкритого тексту. Такі таблиці зручно формувати (і записувати) у вигляді підстановок.

Припустимо, що номера букв відкритого тексту довжиною в N знаків розбито якимось чином на множини , що не перетинаються. Впливаючи на кожну множину своєю підстановкою (циклом) , ми реалізуємо процес зашифрування шифром перестановки, причому підстановка, що відповідає шифрперетворенню, дорівнює . Змінюючи розбиття множини індексів і вибираючи різними способами відповідні підстановки , ми будемо одержувати різні перетворення відкритого тексту виду . Рано чи пізно, ми побудуємо всі підстановки ступеня N, оскільки будь-яка підстановка розкладається в добуток циклів. Звідси випливає, що вдалий спосіб генерації підстановок міг би, у принципі, забезпечити досить якісний шифр перестановки, при якому використовувалися би підстановки ступеня меншої, чим довжина відкритого тексту. Саме способами генерації підстановок і розрізняються різні види шифрів перестановки.