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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

 

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

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

 

  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
  С В Т И О Ы И Ч А О Е Ю А Л Ж П О И Я Р К Н О И Б У Е Т Д М Т А О Р Н И Ш А С Л О З Е Я Д Т О П В Ц А Б М И С Э М Е Н Т Н Л Е Щ О А Ы И Р К Ь В И Л Ф О Е Н А С К Х Д Р И Н В У О П С А Н Т Г О Е Р Е В

 

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