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

Шифри заміни і модульного гамування

Розширення простого поля.

Існування оберненого елемента в кільці лишків

Алгоритм Евклида показує, що для взаємно простих чисел і завжди існує число таке, що.

Таке число називається оберненим до за модулем і позначається.

Дійсно, якщо, то відносно і розв'язуване рівняння. Приводячи за модулем обидві частини зазначеної рівності, одержимо конгруенцію, тобто.

Якщо модуль є простим числом, усі ненульові лишки за модулем взаємно прості з модулем. Отже, кільце.

За аналогією з кільцем лишків за модулем, можна побудувати кільце лишків поліномів за модулем нормованого незвідного полінома над полем.

Для цього досить розглянути множину залишків від ділення всіх поліномів із коефіцієнтами з та помітити, що розширений алгоритм Евкліда може бути переформульований для розв’язування рівняння аналогічного, а саме:.

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

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

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

Довільний вектор можна розглядати як набір коефіцієнтів деякого полінома. При цьому сумі поліномів буде відповідати сума зазначених векторів. Результатом добутку векторів є вектор коефіцієнтів залишку від ділення добутку поліномів на.

У підсумку, елементи поля можна розглядати як - вимірні вектори з координатами з підполя.

Число називається степенем розширення.

Елемент поля представляється в поле - вимірним вектором (розширеним числом) виду.

Шифри заміни і коди. Рандомізація.

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

						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-грамами.

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

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

Шифр пропорційної заміни.

Ш и ф р а н т

Д е ш и ф р а н т

	1 2 3 4 5 6 7 8 9 0
	С В Т И О Ы И Ч А О Е Ю А Л Ж П О И Я Р К Н О И Б У Е Т Д М Т А О Р Н И Ш А С Л О З Е Я Д Т О П В Ц А Б М И С Э М Е Н Т Н Л Е Щ О А Ы И Р К Ь В И Л Ф О Е Н А С К Х Д Р И Н В У О П С А Н Т Г О Е Р Е В

Аналогічна процедура, що називається рандомизацією, може застосовуватися для перетворення відкритого тексту перед зашифруванням, незалежно від системи шифру. Перетворення полягає у тім, що знаки відкритого тексту заміняються на символи іншого алфавіту, більшого за кількістю, ніж вхідний. У процесі заміни конкретна літера переходить випадковим образом в один із пов'язаних з нею символів. Кількість таких символів для кожної літери різна і пропорційна частоті її появи у відкритому тексті. У результаті виходить послідовність, усі знаки якої зустрічаються приблизно з однаковою частотою. Рандомизація може бути введена у будь-яку криптографічну систему. Її використання ускладнює розкриття шифру на основі статистичного аналізу.

Дата добавления: 2014-10-15