Міністерство освіти Російської Федерації
Пермський державний університет
Механіко-математичний факультет
Кафедра математичного забезпечення обчислювальних систем
УДК 519.6 + 681.83
ВІДПРАВКА ПОВІДОМЛЕННЯ В МАЙБУТНЄ
Курсова робота.
виконала студентка
3-го курсу 1 групи
Науковий керівник
професор
Міков Олександр Іванович.
Пермь 2000
Анотація
Маючи намір зануритися в летаргічний сон або стати клієнтомкриогенного діпозітарія, Ви, напевно, побажаєте послати секретне повідомлення в майбутнє, сподіваючись на те, що його розшифруютьтільки в потрібний термін. Саме розгляду рішень даної проблеми і присвячена ця робота. Зараз існує два основні методивирішують проблему розкриття повідомлення у зазначений термін:
. «Шаради» з тимчасовим замком на базі обчислювальних проблем із суттєво послідовними алгоритмами рішення;
. використання довірених агентів, які беруть на себе зобов'язання не розкривати інформацію протягом заданого інтервалу часу.
Специфіка першого методу полягає в тому, що на відмінувід традиційних криптографічних методів, що передбачають наявність в одержувача повідомлення секретного ключа відправника (всиметричних криптосистемах) або у відправника повідомленняавтентичного (справжнього) відкритого ключа одержувача (васиметричних криптосистемах), секретний ключ знищується відразупісля шифрування і невідомий ні відправнику, так іодержувачу повідомлення. А при використанні другого методу здовіреними довірених агентів виникає проблемма надійності,яка частково може бути вирішена за рахунок застосуваннякриптографічного техніки поділу секрету. У даній роботібудуть розглянуті обидва методи.
Зміст
1. Ведення ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 4
2. Аналіз літератури ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 5
3. Використані позначення ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 6
4. Глава 1. Вирішуються проблеми ... ... ... ... ... ... ... ... ... ... ... ... ... .... 7
5. Глава 2. Методи побудови криптосистем з тимчасовим розкриттям ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 8
1. «Шаради» з тимчасовим замком (time - lock puzzles) ... ... 9
2. Використовувані поняття ... ... ... ... ... ... ... ... ... ... ... ... ... ... .12
3. Схема з використанням довірених агентів ... ... ... ... 14
6. Висновок ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 19
7. Список літератури ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 20
Ведення
Споконвіку не було цінності більшої, ніж інформація. ХХ століття --вік інформатики та інформатизації. Технологія дає можливість передавати ізберігати все більші обсяги інформації. Це благо має й зворотний бік.
Інформація стає все більш вразливою з різних причин:
. зростаючі обсяги збережених і переданих даних;розширення кола користувачів, які мають доступ до ресурсів ЕОМ, програмам іданими;
. ускладнення режимів експлуатації обчислювальних систем.
Тому все більшу важливість здобуває проблема захисту інформації віднесанкціонованого доступу при передачі і зберіганні.
Зараз послуги криптографії необхідні майже у всіхобластях діяльності людини. З розвитком прогресу,з'являється необхідність вирішувати завдання, які, зовсім недавно, письменники науково-фантастичного жанру описували у своїхтворах.
Ще зовсім недавно проблема відправки секретних повідомлень в майбутнє хвилювала тільки любителів фантастичноїлітератури. Однак сьогодні вона стає все більшактуальної, у зв'язку з науково-технічним прогресом.
Наприклад, відомо, що сучасні технології дозволяють
«заморожувати» тіло людини до рівня підтримкимінімальних функцій життєдіяльності організму і надійнозберігати певний час. Послуги подібного роду, що в рядівипадків, є єдиною надією людей, які страждаютьважкими захворюваннями. Слід врахувати, що із зростаннямтривалості життя людини, погіршення екологічноїобстановки, кількість таких хвороб сильно збільшилася в наші дні. Наприклад, якщо людина мучиться хворобою, яка сьогодні невиліковна, але має достатньо коштів, то він може
«Відправити себе у майбутнє», скориставшись послугами кріогеннихдепозитаріїв. Саме тут і постає проблема надійностішифрування повідомлень. Очевидно, що «заморожений» людина неє дієздатним і не може відповідати за будь-якусекретну інформацію. Разом з тим, він повинен мати можливість залишити деякі розпорядження (встановити номер рахунку, точнезміст заповіту, якщо станеться нещасний випадок, історіюхвороби і т. п.), які гарантовано були б виконані тільки після закінчення визначеного терміну - не раніше і не пізніше.
Цю проблему допомагають вирішити криптографічні методизабезпечення конфіденційності та цілісності при заданомучасу дешифрування повідомлення на невідомому ключі.
Аналіз літератури.
Публікацій на тему даної роботи дуже мало. Це обумовлено, в першу чергу тим, що раніше не існувало сильноїнеобхідності в шифровці повідомлень на такий довгий періодчасу. Перший, хто звернувся до спільноти Intеrnet зпропозицією розглянути подібне завдання у зв'язку з потребамилюдей, що користуються послугами кріогенних депозитаріїв, був Тімоті
Мей. Саме він і запропонував використовувати в криптографічного схемою довірених агентів. Як відповідь на цей запит і виниклисхеми що розглядаються, які були розроблені відомимикриптографами Рональдом Л. Рівестом, Аді Шамір та Девідом А.
Вагнером. Наскільки мені відомо, інших криптографічних схем,спрямованих саме на вирішення цієї проблемми немає. Ніякоїлітератури, крім відповідної статті Рівестом, Шаміра, Вагнера ідоповнення цієї ж статті в журналі "Конфідент" 5'96 мені знайти не вдалося. Слід врахувати, що запропоновані схеми грунтуються на базових поняттях криптографії, з якими можнаознайомитися в будь-якій спеціалізованій літературі.
Використані позначення.
. М-секретне повідомлення.
. К-секретний ключ, на якому шифрується М.
. t - час, на який шифрується М.
. t? - поточний час.
. S - продуктивність комп'ютера.
. Е-вибраний алгоритм шифрування.
. p, q - прості числа.
. n-формується, як добуток чисел p і q.
. f (n)-формується, як добуток чисел (p-1) і (q-1).
. d-кількість, довірених агнтов.
. i-номер агента.
. ? - Поріг схеми поділу секрету.
. Si, t-секретний ключ агента.
. Di, t - відкритий ключ агента.
. yj - "тінь" ключа К, j-ого агента
. rj - криптограма "тіні" ключа К, j-ого агента
. F - однобічна хеш-функція.
Глава 1. Вирішуються проблеми.
Крім збереження інформації про «замороженому», на заданий термінтакож, необхідно згадати і деякі інші практичніпрограми криптографії з тимчасовим розкриттям:
. учасник торгів може побажати «запечатати» пропозиція ціни з тим, щоб воно було «роздруковане» по завершенні торгової сесії;
. домовласник хоче надати власнику заставної можливість здійснювати платежі з використанням зашифрованого цифрового кеша (digital cash) з різними датами дешифрування так, щоб оплата виконувалася на початку кожного наступного місяця;
. приватна особа може побажати зашифрувати свій щоденник так, щоб він міг бути дешифрований після закінчення певного терміну;
. схема шифрування з депонуванням ключів (key-escrow scheme) може бути реалізована на базі "шарад" з тимчасовим замком з тим, щоб урядові організації могли отримати ключі для розшифровки повідомлення тільки тільки після закінчення певного періоду часу.
В деяких з перерахованих вище ситуаціях час на яке повідомлення залишається секретним коливається в рамках
1 року, коли у випадку з «заморожених» людиною або шифровкою щоденника цей термін обмежується знизу, якмінімум, 2-3 роками, верхня оцінка є взагаліневизначеною. З огляду на цю обставину, природно було б запропонувати два методи шифрування повідомлення, на не дужетривалий період часу 2-3 роки і на досить тривалийчас, порядку декількох десятиліть, що і було зроблено. Кожен з методів повинна використовуватися у відповідній ситуації.
В основному, криптографічний завдання шифрування повідомленнярозглядається таким чином, щоб отримана криптограмамогла бути дешифрована (у тому числі і самим відправникомповідомлення) після закінчення заданого інтервалу часу. Атакана подібну криптосистем вважається успішною, якщо вдаєтьсядешифрувати повідомлення істотно раніше встановленого терміну.
Такий спосіб захисту, з можливістю розкриття секретноїінформації після закінчення певного часу, і називаєтьсякриптографією з тимчасовим розкриттям (timed - releasecrypto).
Глава 2. Методи побудови криптосистем з тимчасовим розкриттям.
Криптосистема з тимчасовим розкриттям, запропонована
Р. Л. Райвестом, А. Шамір і Д. А. Вагнером отримала назву «шаради» з тимчасовим замком (time - lock puzzles). Даний підхід дозахист інформації пов'язаний саме з проблемами, що виникають при відправленні секретного повідомлення в майбутнє. Його специфікаполягає в тому, що на відміну від традиційнихкриптографічних методів, які передбачають наявність у одержувачаповідомлення секретного ключа відправника (в симетричнихкриптосистемах) або у відправника повідомлення автентичного (справжнього) відкритого ключа одержувача (в асиметричнихкриптосистемах), секретний ключ знищується відразу післяшифрування і невідомий ні відправнику, так і одержувачуповідомлення.
В даний час існує два основні методи побудови криптосистем з тимчасовим розкриттям:
. «Шаради» з тимчасовим замком на базі обчислювальних проблем із суттєво послідовними алгоритмами рішення;
. використання довірених агентів, які беруть на себе зобов'язання не розкривати інформацію протягом заданого інтервалу часу.
Очевидно, що при використанні довірених агентів виникаєпроблемма надійності, яка частково може бути вирішена за рахунок застосування криптографічного техніки поділу секрету.
Процесорний час необхідний для вирішення «шаради» залежить відкількості та виду застосовуваного апаратного забезпечення, а також досягнень в області распаралеліванія обчислень. Далі будутьрозглянуті обидва методи.
«шаради» з тимчасовим замком (time - lock puzzles)
Ідея полягає в тому, що рішення «шаради»дозволяє отримати секретний ключ для дешифрування ранішезашифрованого повідомлення. Це виходить, що застосовуючи «силову атаку»
(вичерпний перебір у ключовому просторі), зловмисникзможе розкрити повідомлення, тільки тоді, коли зміст,розкритої їм повідомлення вже не буде актуальним. Як булозазначено вище, складність (час) рішення «шаради» істотнозалежить від кількості обчислювальних ресурсів. Таким чином,основне завдання при побудові будь-який «шаради» зводиться довибору алгоритму доказовою - природи послідовною, тобтоалгоритму, який не може бути распараллелен в принципі іефективність (складність) якого істотно не залежить відвкладених в апаратуру та програмне забезпечення засобів. Прицьому використання декількох паралельно працюючих комп'ютерів не дозволяє прискорити вирішення «шаради».
Проте такий підхід до побудови «шарад» не дозволяєточно визначити час рішення, тому що використання різнихтехнологічних елементів приводить до розкидання продуктивностікінцевих апаратної реалізації. Метод, заснований на використанні довірених агентів, є більш продподчтітельним у випадку,коли рішення має бути предьявлено точно в зазначений термін.
Необхідно підкреслити, що запропонований метод побудови
«Шарад» не може автоматично отримувати рішення черезпевний час, а вимагає безперервної роботи комп'ютера протягом певного часу. Наприклад, рішення, розраховане на
10 років, вимагає безперервних обчислень протягом усього цього часу. Очевидно, що рішення не буде отримано через 10 років, якщо обчислювальний процес був запущений через 5 років (на машині, продуктивність якої відповідає п'ятирічноїдавності) після того, як повідомлення було зашифровано. Такимчином в порівнянні з використанням довірених агентів, методпослідовних ввичісленій вимагає більшої кількостіресурсів (для виконання безперервних обчислень) і можеефективно застосовуватися для вирішення простих «шарад» (наприклад зчасом розкриття в один місяць).
Для пояснення завдання розглянемо наступний приклад. Позначимо через М повідомлення, яке повинно бути зашифрована, а через S продуктивність (дешифрування в секунду) комп'ютера.
Для шифрування повідомлення М так, щоб воно могло бутидешифрована після закінчення Т секунд, виберемо симетричнукриптосистем (наприклад RC5). І виконаємо шифрування повідомлення наключі довжиною
K = lg
(2ST)біт. Збережемо криптограму і знищимо ключ. Після цього застосування
«силовий атаки» (вичерпного перебору в ключовомупросторі) дозволить знайти ключ в середньому за Т секунд.
У зв'язку з такою побудовою виникають дві проблеми:
. «Силова атака» допускає тривіальне розпаралелювання, в результаті чого застосування N комп'ютерів дозволяє отримати результат в N разів швидше
. час T є очікуваним часом дешифрування; на практиці цей час може бути істотно більше або менше, залежно від того, в якому порядку перевіряються ключі.
Тобто, необхідно, щоб, схема була побудована такимчином, щоб распараллеліть обчислення не уявлялосяможливим. Справитися з другої проблемми при побудові схемине вдасться, тому що порядок перебору ключів, в усьому їхмножині, може регулювати лише сам зловмисник, який бажаєдізнатися конфіденційну інформацію. Першу проблему можна вирішитивибравши алгоритм шифрування доказовою - послідовної природи,що й було зроблено.
Розглянемо метод побудови "шарад", запропонований
Р. Л. Райвестом, О. Шамір, Д. А. Вагнером і заснований напослідовному застосуванні операції зведення в квадрат.
Припустимо, Аліса бажає зашифрувати повідомлення М,так, щоб його можна було розшифрувати через Т секунд.
Для цього Аліса:
. генерує сооставной модуль n = pq
як добуток двох простих випадково вибраних чисел p і q і обчислює
f (n) = (p-1) (q-1);
. далі обчислює t = T
S, де
S - продуктивність (число возведений в квадрат за модулем n в секунду) комп'ютера, призначеного для вирішення шаради;
. генерує випадковий ключ До для симетричної криптосистеми, наприклад RC5. Ключ повинен бути досить довгим;
. шифрує М на К за допомогою RC5.
C (M) = RC5 (K, M);
. випадковим чином вибирає а за модулем n (1
