Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ВИВЧЕННЯ ТА ДОСЛІДЖЕННЯ АЛГОРИТМІВ ШИФРУВАННЯ РЮКЗАКА
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2012
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Криптографічні системи та протоколи
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ВИВЧЕННЯ ТА ДОСЛІДЖЕННЯ АЛГОРИТМІВ ШИФРУВАННЯ РЮКЗАКА.
МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ № 4
З ДИСЦИПЛІНИ “КРИПТОГРАФІЧНІ СИСТЕМИ ТА ПРОТОКОЛИ”
для студентів базового напряму
6.170101 “Безпека інформаційних і комунікаційних систем”
Затверджено на засiданнi кафедри
“Безпека інформаційних технологій”,
протокол № від 2012 р.
Львів – 2012
Вивчення та дослідження алгоритмів шифрування рюкзака: Методичні вказівки до лабораторної роботи №4 з дисципліни “Криптографічні системи та протоколи” для студентів базового напряму 6.170101 “Безпека інформаційних і комунікаційних систем” /Укл.: А.Е.Лагун, А.В.Петришин - Львів: НУЛП 2012. - 8 с.
Укладачі:
А.Е.Лагун, к.т.н., доцент
А.В.Петришин, асистент
Відповідальний за випуск:
Л.В. Мороз, к.т.н., доцент.
Рецензент:
В.М.Максимович, д.т.н., професор.
Мета роботи – навчитися практично використовувати алгоритми шифрування рюкзака і розробляти програмне забезпечення для реалізації цих алгоритмів.
1. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Концепція криптографії з відкритими ключами була висунута Уітфілдом Діффі, Мартіном Хелманом, і незалежно Ральфом Мерклом. Їхня ідея полягала в тому, що ключі можна використовувати парами – ключ шифрування та ключ розшифрування – і що можна одержати один ключ з іншого.
Не всі криптографічні алгоритми з відкритим ключем є безпечними і практичними. Одні з безпечних та практичних алгоритмів можуть бути використані лише для розподілу ключів. Другі використовуються для шифрування. Треті можуть використовуватися лише для цифрових підписів. Проте всі ці алгоритми є повільними, оскільки шифрують та розшифровують значно повільніше, ніж симетричні алгоритми.
Гібридні криптосистеми дозволяють прискорити процес: для шифрування повідомлення використовується симетричний алгоритм із випадковим ключем, а алгоритм з відкритим ключем використовується для шифрування випадкового сеансового ключа.
Безпека алгоритмів з відкритими ключами.
Оскільки у криптоаналітика є доступ до відкритого ключа, він завжди може вибрати для шифрування довільне повідомлення. Це означає, що криптоаналітик для заданого C=Ek(P) може спробувати вгадати значення P і легко перевірити свій здогад. Це є проблемою, якщо кількість можливих відкритих текстів є дуже малою, що дозволяє зробити вичерпний пошук. Проте ця проблема вирішується за рахунок доповнення повідомлення рядком випадкових бітів.
Це особливо важливо, якщо алгоритм з відкритим ключем використовується для шифрування сеансового ключа. Алгоритми з відкритими ключами спроектовані таким чином, щоб запобігати викриванню з вибраним відкритим текстом. Їхня безпека полягає як на складності одержання секретного ключа з відкритого, так і на складності одержання відкритого тексту за шифротекстом.
В системах, в яких операція, обернена до шифрування, використовується для цифрового підпису, цьому викриванню неможливо запобігти, якщо для шифрування підписів використовувати однакові ключі.
Алгоритми рюкзака.
Безпека алгоритму рюкзака полягає в проблемі рюкзака, NP-повну проблему.
Дано багато предметів різної маси. Необхідно поскладати деякі з цих предметів в рюкзак так, щоб маса рюкзака дорівнювала певному значенню.
У формалізованому вигляді задача виглядає так: дано набір значень M1, M2, … , Mn і сума S; обчислити значення bi такі, що
S=b1M1+b2M2+…+bnMn (1)
де bi може бути або нулем , або одиницею; одиниця означає, що предмет складають в рюкзак, а нуль – що не складають.
Наприклад маси предметів можуть бути 1, 5, 6, 11, 14, 20. Можна запакувати рюкзак так, щоб його маса була 22, використавши маси 5, 6 і 11. Проте неможливио одержати результуючу масу 24. Час, необхідний для вирішення цієї проблеми із збільшенням кількості предметів зростає експонентно.
Ідеєю алгоритму Меркла-Хелмана є шифрування повідомлення як розв’язку набору проблем рюкзака. Предмети вибираються за допомогою блоку відкритого тексту, який за довжиною дорівнює кількості предметів (біти відкритого тексту відповідають значенням b), а шифротекст є одержаною сумою. Приклад шифрування:
Відкритий текст
111001
010110
000000
011000
Рюкзак
1 5 6 11 14 20
1 5 6 11 14 20
1 5 6 11 14 20
1 5 6 11 14 20
Шифротекст
1+5+6+20=32
5+11+14=30
0=0
5+6=11
Насправді існує дві різні проблеми рюкзака, одна з яких розв’язується протягом лінійного часу, а друга – ні. Відкритий ключ є важкою проблемою, яку можна використати для шифрування, але не можна для розшифрування повідомлень. Закритий ключ є легкою проблемою, даючи простий спосіб розшифрувати повідомлення. Тому, хто не знає закритого ключа доведеться розв’язати важку проблему рюкзака.
Надзростаючі рюкзаки.
Якщо перелік мас є надзростаючою послідовністю, то проблему рюкзака легко розв’язати. Надзростаюча послідовність – це послідовність, в якій кожен член більший за суму всіх попередніх членів, наприклад послідовність {1, 3, 6, 13, 27, 52}.
Для надзростаючого рюкзака проблема вирішується так. Необхідно взяти повну масу і порівняти з найбільшим числом послідовності. Якщо повна маса більша або дорівнює цьому числу, то воно складається в рюкзак. Маса рюкзака зменшується на це число і переходять до наступного числа послідовності. Повторюють, доки процес не закінчиться. Якщо повна вага зменшиться до нуля, то розв’язок знайдено, інакше – ні.
Наприклад, нехай повна вага рюкзака – 70, а послідовність ваг {2, 3, 6, 13, 27, 52}. Найбільша вага 52 є меншою за 70, тому 52 складаємо в рюкзак. Віднявши 52 від 70, одержимо 18. Наступна вага, 27, більша за 18, тому 27 пропускаємо.13 є менше за 18, тому 13 складаємо. Далі маємо 18-13=5; 6>5; 3<5 (беремо 3); 5-3=2; 2≤2 (беремо 2); 2-2=0. Для блоку шифрування методом Меркла-Хелмана відкритий текст, одержаний із значення шифротексту 70 становить 110101.
Надзростаючі рюкзаки не є складною проблемою, проте для звичайних рюкзаків швидкого алгоритму не знайдено. Єдиним способом визначити предмети, що складаються в рюкзак є перевірка всіх можливих розв’язків доки не одержиться правильний. Найшвидший алгоритм має експонентну залежність від кількості можливих предметів. Якщо до послідовності мас добавити ще одну, то знайти розв’язок стане вдвічі важче. В свою чергу, для надзростаючого рюкзака пошук розв’язку збільшиться лише на одну операцію.
Алгоритм Меркла-Хелмана використовує цю властивість. Закритий ключ є послідовністю мас проблеми надзростаючого рюкзака. Відкритий ключ – це послідовність мас звичайного рюкзака з таким самим розв’язком.
Створення відкритого ключа із закритого.
Щоб одержати звичайну послідовність рюкзака візьмемо надзростаючу послідовність, наприклад {2, 3, 6, 13, 27, 52} і помножимо за модулем m всі значення на число n. Значення модуля має бути більше за суму всіх чисел послідовності, наприклад 105. Множник має бути взаємно простим числом з модулем, наприклад 31. Звичайною послідовністю рюкзака буде
2*31 mod 105 = 62
3*31 mod 105 = 93
6*31 mod 105 = 81
13*31 mod 105 = 88
27*31 mod 105 = 102
52*31 mod 105 = 37
Отже, {62, 93, 81, 88, 102, 37}.
Надзростаюча послідовність рюкзака є закритим ключем, а звичайна – відкритим.
Шифрування.
Для шифрування повідомлення спочатку розбиваємо на блоки, що дорівнюють за довжиною кількості елементів послідовності рюкзака. Далі, знаючи що одиниця – це наявність маси, а нуль – відсутність, обчислюємо повну масу рюкзаків – по одному для кожного блоку.
Наприклад, якщо повідомлення у бінарному вигляді 011000110101101110, то шифрування матиме вигляд:
повідомлення = 011000 110101 101110
011000 відповідає 93+81=174
110101 відповідає 62+93+88+27=280
101110 відповідає 62+81+88+102=333
Шифротекстом буде послідовність 174 280 333.
Розшифрування.
Законний одержувач повідомлення знає закритий ключ: оригінальну надзростаючу послідовність, а також n і m, які використані для перетворення її в звичайну послідовність рюкзака. Для розшифрування повідомлення одержувач повинен спочатку визначити n-1, таке що n(n-1)=1(mod m). Кожне значення шифротексту множиться на n-1 mod m, а потім розділяється за допомогою закритого ключа, щоб одержати значення відкритого тексту.
В нашому прикладі надзростаюча послідовність {2, 3, 6, 13, 27, 52}, m=105, n=31, шифротекст – 174 280 333. В нашому випадку n-1=61, тому значення шифротексту потрібно помножити на 61 mod 105.
174*61 mod 105 =9=3+6, що відповідає 011000
280*61 mod 105 =70=2+3+13+52, що відповідає 110101
333*61 mod 105 =48=2+6+13+27, що відповідає 101110
Розшифрованим відкритим текстом є 011000 110101 101110.
Практичні реалізації.
Для послідовності з шести елементів розв’язати задачу рюкзака не важко. Реальні рюкзаки повинні містити не менше 250 елементів. Довжина кожного члена надзростаючої послідовності повинна бути між 200 і 400 бітами, а довжина модуля – від 100 до 200 бітів. Для одержання таких значень використовуються генератори випадкових послідовностей.
Розкривати такі рюкзаки за допомогою грубої сили не має змісту. Якщо комп’ютер може перевіряти мільйон варіантів за секунду, то перевірка всіх можливих варіантів вимагатиме більше 1046 років.
Безпека методу рюкзака.
Проте алгоритм рюкзака не є абсолютно стійким. Шамір і Ципел знайшли слабі місця в перетвореннях методу рюкзака і змогли за допомогою відомих криптометодів відновити надзростаючу послідовність за звичайною.
Після зламування алгоритму Меркла-Хелмана були запропоновані інші криптосистеми на принципі рюкзака – кілька послідовних рюкзаків, рюкзаки Грем-Шаміра, криптосистеми Лу-Лі, Ніємі, – проте і вони були зламані за допомогою одних і тих самих криптометодів.
На цей час існує криптосистема на основі багатошарового рюкзака, яка ще не зламана, проте вона не є оптимальною через значну кількість обчислень.
2. ЗАВДАННЯ
2.1. Домашня підготовка до роботи
1) Вивчити основні характеристики алгоритмів шифрування з відкритими ключами та теоретичні основи побудови алгоритмів шифрування рюкзака.
2) Скласти блок-схеми алгоритмів та програму для реалізації зашифрування та розшифрування відкритого тексту за допомогою шифру рюкзака із надзростаючою послідовністю з 12 елементів.
2.2. Робота в лабораторії
1) Ввести в комп'ютер програми згідно із завданням.
2) Відлагодити програми. При необхідності скоригувати блок-схеми алгоритмів та програми у відповідності з виявленими логічними та синтаксичними помилками.
3) Остаточні версії блок-схем, програм та отримані результати оформити у звіті з лабораторної роботи.
4) Здати звіт з лабораторної роботи.
3. ЗМІСТ ЗВІТУ
1) Номер і назва лабораторної роботи.
2) Повний текст завдання.
3) Остаточні версії блок-схем алгоритмів.
4) Список ідентифікаторів констант, змінних, процедур і функцій, використаних у блок-схемах алгоритмів і програм, та їх пояснення.
5) Остаточні версії програм.
6) Результати роботи програм.
4. КОНТРОЛЬНІ ЗАПИТАННЯ
1. Запишіть формулу для формалізованого опису алгоритму рюкзака.
2. Що таке над зростаюча послідовність?
3. Що є відкритим та закритим ключем в алгоритмі рюкзака?
4. Як відбувається розшифрування в алгоритмі рюкзака?
5. Якою має бути довжина кожного члена надзростаючої послідовності в алгоритмі рюкзака для забезпечення необхідної криптостійкості?
6. Якою має бути довжина модуля в алгоритмі рюкзака для забезпечення необхідної криптостійкості?
7. Охарактеризуйте криптографічну стійкість алгоритмів рюкзака.
СПИСОК ЛІТЕРАТУРИ
О.Н.Василенко, Теоретико-числовые алгоритмы в криптографии. – М.: Изд-во МГУ, 2000
К.Шеннон. Теория связи в секретных системах. В Работы по теории информации и кибернетике, стр. 333-402. М., Изд. Иностр. Лит., 1963.
М.Вельшенбах. Криптография на Си и С++ в действии. М., Триумф, 2004.
Б.Шнайер. Прикладная криптография, 2-е издание: протоколы, алгоритмы, исходные тексты на языке Си. М., Триумф, 2002.
Навчальне видання
Розроблення алгоритмів та програм для афінних шифрів: Методичні вказівки до лабораторної роботи №4 з дисципліни “Криптографічні системи та протоколи” для студентів базового напряму 6.170101 “Безпека інформаційних і комунікаційних систем”.
Укладачі:
Лагун Андрій Едуардович
Петришин Андрій Васильович
19.01.2013 21:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора