Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
РОЗРОБЛЕННЯ АЛГОРИТМІВ ТА ПРОГРАМ ДЛЯ АФІННИХ ШИФРІВ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2012
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Криптографічні системи та протоколи
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
РОЗРОБЛЕННЯ АЛГОРИТМІВ ТА ПРОГРАМ ДЛЯ АФІННИХ ШИФРІВ.
МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ № 3
З ДИСЦИПЛІНИ “КРИПТОГРАФІЧНІ СИСТЕМИ ТА ПРОТОКОЛИ”
для студентів базового напряму
6.170101 “Безпека інформаційних і комунікаційних систем”
Затверджено на засiданнi кафедри
“Безпека інформаційних технологій”,
протокол № від 2012 р.
Львів – 2012
Розроблення алгоритмів та програм для афінних шифрів: Методичні вказівки до лабораторної роботи №3 з дисципліни “Криптографічні системи та протоколи” для студентів базового напряму 6.170101 “Безпека інформаційних і комунікаційних систем” /Укл.: А.Е.Лагун, А.В.Петришин - Львів: НУЛП 2012. - 11 с.
Укладачі:
А.Е.Лагун, к.т.н., доцент
А.В.Петришин, асистент
Відповідальний за випуск:
Л.В. Мороз, к.т.н., доцент.
Рецензент:
В.М.Максимович, д.т.н., професор.
Мета роботи – вивчити математичний апарат для опису афінних шифрів та розробити програмне забезпечення для реалізації афінних шифрів.
1. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Афінні шифри є підкласом шифрів заміни, що містять як частковий випадок шифр Віженера і шифр перестановки з фіксованим періодом.
Шифри простої заміни
Моноалфавітні k-грамні шифри заміни є блоковими шифрами з періодом k. Відповідно, шифри простої заміни можна трактувати як блокові шифри з періодом 1.
Опишемо шифр зсуву із застосуванням математичного апарату. n-символьний алфавіт утотожнюємо з кільцем Zn. А саме, кожна буква замінюється своїм номером у алфавіті, причому нумерація починається з нуля.
Наприклад, латинська абетка утотожнюється із Z26, а українська із Z33. Літера а української абетки трактується як 0, літера б як 1, в як 2 і т.д. Тепер до букв відкритого тексту можна застосовувати операції додавання та множення за відповідним модулем. Надалі п означає кількість букв у алфавіті відкритого тексту.
Шифр зсуву.
Ключ: s таке, що .
Шифрування. У повідомленні кожна буква х заміщується буквою E(x)=(x+s) mod n.
Розшифрування. У криптотексті кожна буква х' заміщується буквою D(x’)=(x’+s’) mod n, де s’=n-s.
Величина зворотного зсуву s' називається розшифровуючим ключем.
Лінійний шифр.
Ключ: а таке, що 0<a<n і НСД(a,n)=1.
Шифрування. У повідомленні кожна буква х заміщується буквою E(x)=(ax) mod n.
Розшифрування. У криптотексті кожна буква х' заміщується буквою D(x’)=(a’x’) mod n, де a’=a-1 mod n - розшифровуючий ключ.
Нехай повідомлення записуються українською абеткою без пропусків між словами та розділових знаків, тобто п=33. Для шифрування використовується ключ а=5. За допомогою розширеного алгоритму Евкліда знаходимо, що а'=20. Розглянемо процедуру шифрування повідомлення місто. У цифровій формі воно представляється послідовністю чисел 16, 11, 21, 22, 18. Множення на 5 за модулем 33 дає послідовність 14, 22, 6, 11, 24, яка відповідає криптотекстові ктеіф.
Розшифрування відбувається так само, лише із використанням розшифровуючого ключа а' = 20.
Узагальненням шифру зсуву і лінійного є
Афінний шифр .
Ключ: a, s такі, що 0 ≤ s <n, 0 < a < n і НСД(a,n)=1.
Шифрування. У повідомленні кожна буква х заміщується буквою E(x)=(ax+s) mod n.
Розшифрування. У криптотексті кожна буква х' заміщується буквою D(x’)=(a’x’+s’) mod n, де пара a’=a-1 mod n, і s’=(-a’s) mod n є розшифровуючим ключем.
Нехай для шифрування використовується ключ а = 5, s = 11. Один з розшифровуючих ключів було знайдено раніше – а' = 20. Тоді,
s’=(-20·11) mod 33 = 11.
Для зашифрування повідомлення місто, представляємо його у цифровій формі як послідовність 16, 11, 21, 22, 18. Множення на 5 за модулем 33 було виконано вище. До результату додаємо 11 і отримуємо послідовність 25, 0, 17, 22, 2, яка відповідає криптотексту хантв.
Розшифрування криптотексту відбувається з використанням розшифровуючого ключа а' = 20, s' = 11.
Афінні шифри вищих порядків.
Проведемо розширення монограмних шифрів, розглянутих вище, таким чином, щоб вони оперували з k-грамами для довільного k > 1.
Введемо операцію додавання в Znk. Сумою векторів X=(x1,…,xk) і S=(s1,…,sk) із Znk є вектор X+S=((x1+s1)mod n, (x2+s2)mod n …,(xk+sk)mod n). Znk з операцією додавання є групою. Вектор –S = (n-s1, …, n-sk) є оберненим до вектора S=(s1,…,sk).
Шифр зсуву k-го порядку (шифр Віженера з періодом k).
Ключ: S( Znk.
Шифрування. Повідомлення розбивається на k-грами. Кожна k-грама X заміщується k-грамою E(X)=X+S.
Розшифрування. Кожна k-грама X' криптотексту заміщується k-грамою D(X’)=X’+S’, де S’=-S є розшифровуючим ключем.
Mk(Zn) позначаємо множину матриць розміру k х k з коефіцієнтами з кільця Zn; GLk(Zn) - підмножину оборотних матриць. Для A(GLk(Zn) обернену до неї матрицю позначаємо А-1. Добутком АХ матриці A=(aii) з Mk(Zn) на вектор-стовпчик X=(x1,…,xk) із Znk є вектор-стовпчик
=
Лінійний шифр k-го порядку.
Ключ: A(GLk(Zn).
Шифрування. Повідомлення розбивається на k-грами. Кожна k-грама X заміщується k-грамою E(X)=AX.
Розшифрування. Кожна k-грама X' криптотексту заміщується k -грамою D(X’)=A’X’, де А'=А-1 - розшифровуючий ключ.
Розглянемо докладніше випадок k= 2, тобто біграмний лінійний шифр. Ключем вибирається матриця з коефіцієнтами a, b, c, d ( Zn. Матриця А повинна бути оборотною. Це рівнозначно умові НСД(w,n)=1 для w=ad-bc – визначника матриці. За цієї умови за допомогою розширеного алгоритму Евкліда можна знайти в Zn обернений елемент w-1 і за формулою оберненої матриці обчислити розшифровуючий ключ
Наприклад, для із Z33 маємо w = 31. За розши реним алгоритмом Евкліда знаходимо w-1 =16 і .
Нехай потрібно зашифрувати повідомлення місто. Першій біграмі мі відповідає вектор . Множення матриці А на цей вектор дає . Таким самим чином знаходимо образи біграм cт = та о = . Зауважимо, що множення А на три вектори-біграми еквівалентне множенню цієї матриці на матрицю розміру 2 на 3:
.
Насамкінець перетворюємо стовпчики отриманої матриці у біграми і отримуємо криптотекст дцяпос.
Розшифрування відбувається так само, лише із використанням оберненої матриці, а саме матриця А' множиться на матрицю :
.
В результаті дістаємо повідомлення містоа.
Проведемо загальний аналіз лінійного шифру. Вираз D(E(X))=X для будь-якого X(Znk випливає з рівностей A’(AX) = (A’A)X = IkX = X, де Іk - одинична матриця порядку k. Розшифровуючий ключ А' для вибраної оборотної матриці А обчислюється за формулою для оберненої матриці. Потрібне для цього значення (det A)-1 mod n знаходиться за допомогою розширеного алгоритму Евкліда. Необоротні матриці А непридатні для використання як ключ.
Афінний шифр k-го порядку.
Ключ: A(GLk(Zn) і S( Znk.
Шифрування. Повідомлення розбивається на k-грами. Кожна k-грама X заміщується k-грамою E(X)=AX+S.
Розшифрування. Кожна k-грама X' криптотексту заміщується k-грамою D(X’)=A’X’+S’, де A’=A-1 і S’=–A’S - розшифровуючий ключ.
Нехай потрібно зашифрувати повідомлення місто за допомогою ключа
i в Z33.
Частину операції зашифрування наведено вище. Після розбиття повідомлення на вектори-біграми і множення на них матриці А за модулем 33 було отримано . Додаємо до кожного стовпчика вектор S і отримуємо тобто криптотекст ияґхуч.
Знайдемо також розшифровуючий ключ. У попередньому прикладі було отримано матрицю . Обчислюємо .
Провівши розшифрування, одержимо
,
а саме повідомлення містоа.
Криптоаналіз. Атака з вибором відкритого тексту. Афінний шифр нестійкий до цього виду криптоаналізу. Позначимо Xi 1 ( i ( k, вектор з i-тою компонентою 1 і з рештою компонент, що дорівнюють 0, а Х0 – нульовий вектор. Супротивнику достатньо дізнатись, в які криптотексти переходять відповідні цим векторам k-грами. Справді, E(X0)=S, а образ Е(Хi) дорівнює i-тому стовпчику матриці А, що дозволяє повністю визначити ключ.
Атака з відомим відкритим текстом. Лінійний шифр вразливий від такої атаки. Припустимо супротивник знає, що шифруюче відображення E(X)=AX перетворює вектори X=(X1,…,Xk) у вектори X1’,…,Xk’. Сформуємо із стовпчиків X1,…,Xk матрицю М, а із стовпчиків X1’,…,Xk’ матрицю С. Таким чином, C=AM і M=A’C. Якщо матриця С оборотна, то можна визначити розшифровуючий ключ A’=MC-1. Якщо матриця С виявиться необоротною, то супротивник не зможе визначити А' однозначно. Однак кількість можливостей може зменшитись настільки, що А' вдасться знайти після деякого перебору.
Для афінного шифру E(X)=AX+S необхідно знати на одну пару (X, X’), де X’ = E(X), більше. Віднявши рівність AX+S=X’ від кожної з рівностей AXi+S=Xi, i(k, задачу визначення розшифровуючого ключа зводиться до попереднього випадку.
Атака лише за криптотекстом. Афінний шифр 2-го порядку не стійкий до частотного аналізу як і будь-який біграмний шифр. Якщо порядок k дещо збільшити, частотний метод перестане працювати.
2. ЗАВДАННЯ
2.1. Домашня підготовка до роботи
1) Вивчити основні математичні залежності, які використовуються для опису шифрів зсуву, лінійного та афінного першого та вищих порядків.
2) Скласти блок-схеми алгоритмів та програму для реалізації зашифрування та розшифрування відкритого тексту за допомогою афінного шифру 3-го порядку.
2.2. Робота в лабораторії
1) Ввести в комп'ютер програми згідно із завданням.
2) Відлагодити програми. При необхідності скоригувати блок-схеми алгоритмів та програми у відповідності з виявленими логічними та синтаксичними помилками.
3) Остаточні версії блок-схем, програм та отримані результати оформити у звіті з лабораторної роботи.
4) Здати звіт з лабораторної роботи.
3. ЗМІСТ ЗВІТУ
1) Номер і назва лабораторної роботи.
2) Повний текст завдання.
3) Остаточні версії блок-схем алгоритмів.
4) Список ідентифікаторів констант, змінних, процедур і функцій, використаних у блок-схемах алгоритмів і програм, та їх пояснення.
5) Остаточні версії програм.
6) Результати роботи програм.
4. КОНТРОЛЬНІ ЗАПИТАННЯ
1. Запишіть формули для операцій зашифрування та розшифрування шифром зсуву 1-го порядку.
2. Яка умова повинна виконуватися для ключа шифрування a в лінійному та афінному шифрах 1-го порядку?
3. Запишіть формули для операцій зашифрування та розшифрування лінійним шифром 1-го порядку.
4. Яка умова повинна виконуватися для того, щоб матриця a була оборотною?
5. Запишіть формули для операцій зашифрування та розшифрування афінним шифром 1-го порядку.
6. Як відбувається криптоаналіз афінного шифру при виборі відкритого тексту і з відомим відкритим текстом?
СПИСОК ЛІТЕРАТУРИ
О.Н.Василенко, Теоретико-числовые алгоритмы в криптографии. – М.: Изд-во МГУ, 2000
К.Шеннон. Теория связи в секретных системах. В Работы по теории информации и кибернетике, стр. 333-402. М., Изд. Иностр. Лит., 1963.
М.Вельшенбах. Криптография на Си и С++ в действии. М., Триумф, 2004.
Б.Шнайер. Прикладная криптография, 2-е издание: протоколы, алгоритмы, исходные тексты на языке Си. М., Триумф, 2002.
Навчальне видання
Розроблення алгоритмів та програм для афінних шифрів: Методичні вказівки до лабораторної роботи №3 з дисципліни “Криптографічні системи та протоколи” для студентів базового напряму 6.170101 “Безпека інформаційних і комунікаційних систем”.
Укладачі:
Лагун Андрій Едуардович
Петришин Андрій Васильович
19.01.2013 21:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора