Шифр двозначної заміни
Шифри заміни і модульного гамування
Розширення простого поля.
Існування оберненого елемента в кільці лишків
Алгоритм Евклида показує, що для взаємно простих чисел і завжди існує число таке, що .
Таке число називається оберненим до за модулем і позначається .
Дійсно, якщо , то відносно і розв'язуване рівняння . Приводячи за модулем обидві частини зазначеної рівності, одержимо конгруенцію , тобто .
Якщо модуль є простим числом , усі ненульові лишки за модулем взаємно прості з модулем. Отже, кільце .
За аналогією з кільцем лишків за модулем , можна побудувати кільце лишків поліномів за модулем нормованого незвідного полінома над полем .
Для цього досить розглянути множину залишків від ділення всіх поліномів із коефіцієнтами з та помітити, що розширений алгоритм Евкліда може бути переформульований для розв’язування рівняння аналогічного , а саме: .
Якщо покласти , то, при , і співвідношення , після зведення за модулем дає . Тому всі ненульові елементи нашого кільця оборотні тобто воно є полем.
Оскільки коефіцієнти поліномів обчислюються за правилами арифметики , то число є характеристикою нашого поля . Очевидно, що кількість елементів поля дорівнює кількості поліномів, степеня меншої .
Для визначення зауважимо, що набору коефіцієнтів кожного полінома степеня меншого , відповідає вектор, кількість координат якого дорівнює . Кожна координата може приймати лишь значення . Отже, . Таким чином, .
Довільний вектор можна розглядати як набір коефіцієнтів деякого полінома. При цьому сумі поліномів буде відповідати сума зазначених векторів. Результатом добутку векторів є вектор коефіцієнтів залишку від ділення добутку поліномів на .
У підсумку, елементи поля можна розглядати як - вимірні вектори з координатами з підполя .
Число називається степенем розширення .
Елемент поля представляється в поле - вимірним вектором (розширеним числом) виду .
Шифри заміни і коди. Рандомізація.
Шифр заміни - (шифр підстановки) - метод шифрування, при якому кожен елемент тексту взаємно однозначно заміняється одним, або декількома знаками деякого алфавіту. Шифр простої заміни заміняє кожен знак алфавіту відкритого тексту на деякий знак з того ж алфавіту, Результат заміни не залежить від розташування знака у відкритому тексті. Ключами для шифрів заміни є таблиці заміни.
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 | |
С В Т И О Ы И Ч А О Е Ю А Л Ж П О И Я Р К Н О И Б У Е Т Д М Т А О Р Н И Ш А С Л О З Е Я Д Т О П В Ц А Б М И С Э М Е Н Т Н Л Е Щ О А Ы И Р К Ь В И Л Ф О Е Н А С К Х Д Р И Н В У О П С А Н Т Г О Е Р Е В |
Аналогічна процедура, що називається рандомизацією, може застосовуватися для перетворення відкритого тексту перед зашифруванням, незалежно від системи шифру. Перетворення полягає у тім, що знаки відкритого тексту заміняються на символи іншого алфавіту, більшого за кількістю, ніж вхідний. У процесі заміни конкретна літера переходить випадковим образом в один із пов'язаних з нею символів. Кількість таких символів для кожної літери різна і пропорційна частоті її появи у відкритому тексті. У результаті виходить послідовність, усі знаки якої зустрічаються приблизно з однаковою частотою. Рандомизація може бути введена у будь-яку криптографічну систему. Її використання ускладнює розкриття шифру на основі статистичного аналізу.