Необходимостта и желанието дадена информация да бъде достъпна само за определен кръг от хора съпътстват човешката цивилизация от възникването и, но дори до преди
´
30-40 години това бяха приоритети основно на военните и дипломатически служби. Днес нещата са твърде различни. Развитието на компютърните технологии и изграждането на глобална компютърна мрежа драстично промениха ситуацията. Правителствени, обществени и частни организации и фирми съхраняват или обменят информация за хора, продукти, услуги и процеси, които имат съществено влияние върху голям брой граждани.
Нейното разкриване или неправомерно използване може да засегне интересите на огромни маси от хора с всички тежки социални последици от това. Всеки бизнес дори и найлегалния има своите тайни. Например при електронната търговия, продавачът не иска да попадне на измамник, а клиентът не желае всички да разберат какво си е купил или да бъде измамен. Всичко това превръща защитата на информация в приоритетна задача не само за правителствените органи, но и за редица обществени организации и частни икономически субекти. Приоритетна задача е разбира се и общественият контрол върху средствата за защитата за да не се допусне използването им за осъществяване и прикриване на терористични и криминални деяния.
Блок-диаграмата на фиг.1 представя абстрактен модел на комуникационна система с наличие на опонент.
Опонентът (противникът) неправомерно включил се към обмена на информация между легитимните участници може да бъде
• пасивен, когато чрез подслушване на канала се опитва да определи ключовете
(e, d) или поне да разкрие съобщението m . Пасивното следене на канала може да бъде използвано и за анализ на трафика, т.е за наблюдение и анализ на източника, получателя, времето за комуникация и количеството информация, която се обменя.
• активен (tampering), когато използва твърде разнообразни форми на противодействие, например като
- блокиране на информационния поток;
- записване на прихванатата информация и излъчването и по-късно, по време на
´
фалшива комуникационна сесия;
- промяна съдържанието на информацията чрез заличаване, вмъкване и/или разместване
85
86
ЛЕКЦИИ ПО ТЕОРИЯ НА ЧИСЛАТА
Н. Л. МАНЕВ
на части от нея и др. такива.
Опонент
Източник
E Криптиране
T
c
E Декриптиране
e u e
¡
e
E Получател
!
¡
¡
ee e ¡
¡ d
e
¡
e
¡
Генератор
на ключове
Фиг. 4.1. (e и d са съответно криптиращия и декриптиращия ключ)
Това ясно показва, че защитата на информацията включва много и най-разнообразни проблеми. Тя се осъществява на три нива:
• физическо (хардуерно) - преди всичко информацията трябва да бъде физически налична и достъпна. По принцип този кръг проблеми се решават с изграждане на отказоустойчиви устройства за съхранение и обработка на информация, комуникационни възли и софтуерни продукти за изграждане и управление на отказоустойчиви компютърни системи. • защита при съхранение и предаване на информацията от подслушване, разрушаване или подправяне, както и от грешки породени от естествено зашумяване на комуникационните канали - криптографията и теория на кодирането са теоретичните основи за решаване на такъв кръг задачи. Към това ниво ще причислим и защитата на използваните операционни системи, макар че частично този проблем се отнася и към предното ниво.
• организационни и законодателни мерки, които подпомагат и регламентират горните нива и аспекти на защитата на данни.
Ето някои от задачите и целите спадащи към второто ниво, които трябва да бъдат постигнати с помощта на съвременната криптография:
• Неприкосновеност и поверителност на информацията (privacy and confidentiality): Постигането на тази цел осигурява информацията да остане тайна и недостъпна за всички, освен за тези, които са оторизирани да си служат с нея.
• Осигуряване цялост на данните (data integrity), с което се цели изпратената информацията да не бъде подправяна или подменена в процеса на предаване или обработка.
• Идентификация (identification or entity authentication): Задачата е легално включените в обмена на информация страни (лица, компютърни терминали, кредитни карти и др.)
6.1. Цели, задачи и основни понятия.
87
да се убедят взаимно, че наистина комуникират една с друга, т.е. че отсрещната страна е наистина тази, за която се представя.
• Автентичност на съобщението (message authentication): Получателят на съобщението трябва да се убеди дали подателят му е наистина този, който е заявен в съобщението като такъв. Тази задача е известна още като data origin authentication.
• Осъществяване на електронен подпис (signature): Целта е реализацията на електронен аналог на класическия подпис върху писмени документи. В електронния вариант получателят на даден електронен документ също трябва да е в състояние да убеди трета независима страна (“съдия”), че той действително е изпратен и в точно същия вид от страната, която го е подписала.
• Неотменимост (неотричаемост) (nonrepudiation): Осигурява, че никоя от страните в комуникационния процес не може да отрече реално осъществени свои действия (например, че е изпратила дадено съобщение) и/или поети ангажименти. Това е особено важна цел както от правна така и от комерсиална гледна точка.
• Управление на ключовете (key management): фактор от жизнено значение за сигурността.
Управлението на ключовете включва всички аспекти на боравенето с тях, като се започне от създаването им до евентуалното им унищожаване. Най-голямата сложност е при съхраняването и разпространението на ключовете. Тези проблеми се решават отново с криптографски алгоритми.
• Разпределение на секрета (sharing schemes): В ситуация на многостранно сътрудничество дадено свойство (съглашение) действа докато броят на противниците му в групата не надвиши определен праг. Такъв тип задачи възникват при съхранение и управление на ключовете. • Анонимност (anonymity): Да се прикрие идентичността на определен участник в даден процес.
• Авторизация (authorization): задача, която трябва да осигури прехвърляне правото на друга страна да бъде или да извърши нещо.
• Контрол на достъпа (access control): Да ограничи в определени рамки правата и възможностите, които легитимен ползвател на една компютърна система или мрежа има. • Едновременен обмен (simultaneous exchange): В ситуация на много участници някакво желано свойство (качество) е в сила, докато нещо друго ценно (например подписа на отсрешната страна) не се получи.
Криптографията, която осигурява методите и средствата за защита заедно с Криптоанализа, който има за задача разбиването на шифрите формират науката Криптология.
Всеки механизъм, процес или структура опиращи се на достиженията на съвременната криптография привличат и използват нейните базисни средства (методи, алгоритми и др.), наричани най-общо криптографски примитиви. Естествено, възниква въпроса за оценка на тяхната ефиктивност и полезност. Формулирани са редица практически и математически критерии за оценка на криптографски примитиви. Последните се основават на теорията на вероятностите и теорията на сложността на алгоритми, а по-долу излагаме критерии за оценка от практическа гледна точка.
Още в 1883 г. Керкхоф формулира съвкупност от изисквания за една криптосистема, наричани Kerckhoffs’ desiderata:
1. да бъде, ако не теоретически, то поне практически неразбиваема;
88
ЛЕКЦИИ ПО ТЕОРИЯ НА ЧИСЛАТА
Н. Л. МАНЕВ
2. компрометирането на един неин детаил да не създава проблеми на кореспондиращите;
3. ключът трябва да се запомня лесно и без да се записва както и лесно да се сменя;
4. криптограмите трябва да могат да се изпращат с телеграф (това е “върха” на комуникациите тогава);
5. апаратурата за криптиране трябва да бъде портативна и да позволява само един човек да работи с нея;
6. системата трябва да бъде лесна, да не изисква нито знанието на голямо количество правила, нито умствено пренапрежение.
Тези препоръки са актуални и днес, а ето и някои съвременни практически критерии:
• ниво на секретност.
Определя се от работния фактор (т.е. необходимите време и изчислителски ресурси) за компрометиране на криптографския механизъм при най-добрата известна в момента на оценка атака, както и предполагаемите в близко бъдеще развитие на компютърните технологии и методи за криптоанализ.
• функционалност.
Как се съгласува с други примитиви при изграждане на механизми, каква и колко съществена е ролята му. За решаване на какви криптографски задачи даденият примитив е по подходящ и ефективен.
• методи за опериране.
Оценява се поведението по отношение на сигурността при различни начини на прилагане, свързване с други примитиви, вида на входните данни и др.
• производителност и бързина.
Например скоростта на криптиране измерена в бит/сек. Към критериите от този тип спадат, например, необходимото време да се създаде електронен подпис (ЕП), времето за проверката му, времето, необходимо за генериране на основните параметри на системата и ключовете. Оценяването винаги се прави за фиксирана форма на опериране.
• внедримост.
Оценява каква е сложността при хардуерна и/или софтуерна реализация на съответния криптографски механизъм. Небходимите ресурси (дисково пространство, памет и др) за съхраняване на ЕП както и всички данни и/или резултати получени по време на създаване на електрония подпис, издаване на сертификат и др.
Интересна от практическа гледна точка представлява така наречената “Ad hoc security”. При нея се прави оценка на ресурсите на потенциалния противник и те се сравняват с ресурсите необходими за разбиване на криптосистемата.
Дефиниция 6.1.1 Под криптосистема се разбира съвкупността от три множества
M, C и K от редици, съответно над азбуки A1 , A2 и A3 , и двойка (E, D) множества от изображения E = {Ee : M → C | e ∈ K} и D = {Dd : C → M | d ∈ K}, които притежават свойството, че за всяко e ∈ K (криптиращ ключ) съществува единствен d ∈ K (декриптиращ ключ) така, че
Dd (Ee (m)) = m, за всяко m ∈ M.
Множествата M, C и K се наричат съответно пространство от съобщенията
((plaintext) message space), пространство от шифротекста (ciphertext space)
6.1. Цели, задачи и основни понятия.
89
и пространство от ключовете (key space), а елементите на E и D криптиращи и декриптиращи трансформации.
Забележка 6.1 Понятието криптографски алгоритъм в литературата се употребява в широк смисъл като синоним на криптосистема, а в тесен за означаване на криптиращата и декриптираща трансформации.
Криптосистемите се делят на две групи:
• Симетрични: e = d или “изчислително лесно” може да се извлече d от e.
Примери на такива криптосистеми са AES, DES, RC4, Stream ciphers и др.
• Асиметрични (наричани още двуключови, с публичен ключ): когато е “изчислително невъзможно” да се определи d, знаейки само e. Ключът e използван за шифриране може да бъде направен публично известен докато този за дешифриране d трябва да се държи в тайна.
Примери на такива криптосистеми са RSA, Elliptic curve cryptography (ECC), тези на Rabin, ElGamal и McEliece.
Понятието “изчислително невъзможно” трябва да се разглежда в контекста на Теория на сложността на алгоритми (theory of complexity). “Невъэможно/лесно” означава, че не съществува/съществува алгоритъм, който дава решение на проблема за време, зависещо полиномиално от параметъра (параметрите) на проблема. Когато такъв алгоритъм не съществува, се казва още, че задачата е в класа NP. Прецизирането на тези понятия излиза извън рамките на тези лекции и ние ще се опрем на интуитивния им смисъл. На читатели, които искат да се запознаят по-подробно с горните понятия и съпъстващите ги проблеми препоръчваме да прочетат някоя книга по теория на сложността на алгоритми
(например [?]).
Дефиниция 6.1.2 Нека X и Y са произволни множество. Еднопосочна функция
(one-way function) се нарича функция f : X → Y , такава че е “лесно” да се пресметне f (x) за всяко x ∈ X, докато за случайно y ∈ Im(f ) е “изчислително невъэможно” да се намери x, такова че f (x) = y.
Пример 6.1.1 Нека g е примитивен корен по модул простото число p. Функцията f :
∗
∗
Zp → Zp дефинирана с f (x) = g x (mod p) е пример за еднопосочна функция.
Изчисляването на f (x) не представлява трудност, но намирането на ind a, за произволно a ∈ Z∗ , дори за не големи p, вече създава проблеми. Както отбелязахме по-горе в p настоящото изложение няма да разглеждаме сложността на тази операция, но препоръчваме на читателя да направи таблица с индексите относно простото число p = 53993 (твърде малко от криптографска гледна точка), за да добие представа за сложността на проблема.
При системите с публичен ключ се използва най-често следният подклас от еднопосочни функции. 90
ЛЕКЦИИ ПО ТЕОРИЯ НА ЧИСЛАТА
Н. Л. МАНЕВ
Дефиниция 6.1.3 Еднопосочна функция със секрет (Trapdoor one-way) се нарича еднопосочна функция f : X → Y със свойството, че при зададена допълнителна
(тайна) информация (trapdoor information) за всяко y ∈ Im(f ) става “възможно” да се намери x, така че f (x) = y.
6.2
Криптографски примитиви и механизми.
Основните криптографски примитиви, използвани при изграждане на системи за защита на информацията са следните:
• симетрични криптографски алгоритми
• асимитрични криптографски алгоритми
• управление създаване, съхранение и разпределение на ключове
• хеш-функции
• генератори на случайни числа
В частност те са в основата на механизмите за създаване на електронен подпис и генерирането на частните и публичните ключове.
По-долу ще разгледаме малко по-подробно първите три, а сега да дефинираме и посочим ролята на последните две.
Дефиниция 6.2.1 Хеш-функция (hash function) се нарича еднопосочна функция h, която изобразява редица (от битове) с произволна дължина в редица с фиксирана дължина n (например, n = 64, 128, 160) и притежава свойството, че е свободна от колизии, т.е. изчислителски невъзможно е да се намерят две различни съобщения m и m , така че h(m) = h(m ).
Примери на хеш-функции са MD4, MD5, SHA-1, RIPEMD-160. Препоръчително е да се използват хеш-функции с n = 128 или 160 бита, за да са свободни от колизии и същевременно n да не е твърде голямо, за да не се забавя обработката на информацията.
Но поради увеличаване производителността на компютрите в крайна фаза на стандартизация е дори SHA-512 (n = 512).
Основните приложения на хеш-функциите са за проверка цялостта на данните и създаване на кратка добавка, която да бъде подписана при реализация на електронен подпис, както и при някои идентификационни протоколи.
Важен клас криптографски примитиви са и генераторите на случайни числа.
Те стоят в основата на програмите за пораждане на ключове и тяхното качество е от съществено значение за пораждането на добри неподдаващи се на отгатване ключове.
Под случайна поредица (низ) от битове ще разбираме такава редица от 0 и 1, за която знанието на произволно подмножество от елементите и не дава никаква информация
´
за останалите битове. С всяка такава редица може да се свърже случайно число, като се вземе числото, чиито запис в двоична бройна система е тази редица. Под генератор на случайна двоична редица (случайно число) разбираме устройство и/или алгоритъм, който поражда случаен низ от битове.
Всеки генератор на случайна редица изисква естествен източник на шум (например, физическо устройство с топлинен шум), който може впоследствие да бъде обработен криптографски (например, подложен на хеш-функция).
6.2. Криптографски примитиви и механизми.
91
Всеки случаен генератор се подлага на най-разнообразни тестове (чиито резултат се дава най-често с вероятността редицата да е случайна) доколко случайни редици произвежда. Най-простите примери за такива тестове са проверка за равенство между броя на единиците и нулите, и проверка за автокорелационните свойства на генерираната редица. Един универсален тест (Maurer) е степента на компресиране на редицата. Колкото по-малко може да се компресира, толкова по-случайна е тя.
Когато се изискват случайни редици с много голяма дължина, се използват така наречените псевдослучайни редици. Генератор на псевдослучайна редица наричаме детерминиран алгоритъм, който от напълно случаен низ от k бита поражда двоична редица с дължина на порядъци по-голяма от k, която с голяма вероятност издържа статистически тестове за случайност. Доколкото изходът на такъв генератор е еднозначно определен по началната редица, k трябва да бъде достатъчно голямо, за да не може с пълно изчерпване да се генерират всички възможни псевдослучайни редици.
6.2.1
Симетрични криптосистеми.
Предимства:
- Голяма скорост на криптиране и декриптиране както при хардуерна, така и при софтуерна реализация.
- Лесни за реализация.
- Използват се като съставни части на най-разнообразни криптографски примитиви.
Недостатъци:
- Секретният ключ е само един и всяка от страните, участващи в процеса, може да го компрометира случайно или целенасочено.
- При комуникация по двойки в мрежа от n участника са необходими n(n − 1)/2 ключа. - Изисква често смяна на ключа (при всяка сесия), което поражда проблеми с разпространението на ключовете.
- Не са удобни за използване в механизми за електронен подпис, защото изискват много големи ключове за проверяващата трансформация и въвличане на Трета доверена страна (ТТР).
В $ 5.2.3 е описан един механизм (използващ Теория на числата) как да се реши проблемът с управлението на ключовете за симетрични криптосистеми.
Най-употребяваните симетрични криптосистеми са блоковите криптосистеми (block ciphers). Дефиниция 6.2.2 Криптосистема, чието пространство от съобщенията M се състои от редици m = (m1 , . . . , mn ) с дължина n, т.е. разделя открития текст на блокове от по n символа на азбуката, се нарича блоков шифър с дължина n.
92
ЛЕКЦИИ ПО ТЕОРИЯ НА ЧИСЛАТА символ 0
1
2
3
4
5
6
7
8
9
интервал а б в г д е ж з и число
00
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
Н. Л. МАНЕВ число 60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
символ
V
*
=
+
/
ˆ
!
?
$
число
80
81
82
83
84
85
86
87
88
Таблица 5.1.
Повечето добре известни симетрични криптосистеми са блокови. Такива са и следните класически криптосистеми:
Заместващи шифри (Substitution ciphers)
Дефиниция 6.2.3 Критосистема, която попада в една от следващите категории, се нарича заместващ шифър (субституция):
Проста субституция Нека е даден блокова криптосистема с дължина n и пространство от ключовете K, състоящо се от пермутации на азбуката. Криптирането с ключа e ∈ K се извършва по правилото
Ee (m) = (e(m1 ), e(m2 ), . . . , e(mn )).
Хомофоник (homophonic) Всеки символ от азбуката се изобразява a −→ H(a) в множество от редици с дължина t, като H(a) ∩ H(b) = Ø, за a = b.
Многоазбукови (polyalphabetic) За разлика от простата субституция, ключовете e = (π1 , . . . , πn ) представляват наредени n−орки от пермутации на азбуката и
Ee (m) = (π1 (m1 ), π2 (m2 ), . . . , πn (mn )).
Разместващи (пермутационни) шифри (Transposition ciphers)
Дефиниция 6.2.4 Нека M е пространството от съобщения на блоков шифър с дължина
n. Криптосистемата се нарича разместваща (пермутационна), ако всеки ключ e еднозначно определя пермутация π ∈ Sn на {1, 2, . . . , n}, такава че
Ee (m) = (mπ(1) , . . . , mπ(n) ).
6.2. Криптографски примитиви и механизми.
93
Използваните днес блокови шифри принадлежат на класа от така наречените итеративни шифри от тип на Фейстел (Feistel), но тази тематика остава в страни от целите на нашето изложение.
Друг много използван тип симетрични криптосистеми са поточните шифри (stream ciphers). При тях криптирането представлява прибавяне по модул 2 на бинарна редица към бинарния запис на открития текст.
Ще илюстрираме заместващите шифри с една криптосистема основана на афинната трансформация x a b x e
=⇒
+ y c d y f
В нашия случай ще изберем
A=
a b c d
=
2 13
17 22
и B=
e f =
−7
5
,
които ще представляват ключа. На елементите на матриците ще гледаме като на елементи на Z89 , т.е. действията ще ги извършваме по модул 89. Съответствието, при което на буквите и другите текстови символи се съпоставят числа по модул 89 се задава с Таблица
5.1.
Да криптираме текста: “Теория на числата”. На него му съответства редицата от двуцифрени числа 59 16 25 27 19 40 10 24 11 10 34 19 28 22 11 29 11 10. Накрая допълваме текста с интервал (10) за да станат числата четен брой. Първите две числа се преобразуват в
2 13
59
−7
52
+
=
17 22
16
5
25
Извършвайки последователно пресмятанията получаваме 52 25 38 45 17 51 58 80 56 56
41 22 68 75 36 29 56 56 Следователно шифротекстът е
ЛоьДжКСVППАлЬ;щтПП
Декриптирането се извършва като се приложи обратната трансформация: x y
=⇒ A−1
x y − A−1 B =
22 −13
−17
2
x y −
−7
5
Разгледаният тип криптосистеми са предложени в 1931 от Хил (Hill). Поради линейността си те нямат криптографска стойност днес, макар че все още се използват (алгоритми използващи същия принцип) в някои комуникационни системи за да увеличат ентропията на предаваната информация.
6.2.2
Асиметрични криптосистеми.
Предимства:
- Двойката ключове (частен и публичен) могат да бъдат ползвани многократно и през дълъг период (дори няколко години).
- В контраст на симетричния случай, при мрежа от много участници са необходими толкова двойки ключове, колкото са участниците.
94
ЛЕКЦИИ ПО ТЕОРИЯ НА ЧИСЛАТА
Н. Л. МАНЕВ
- Позволяват създаване на ефективни схеми за електронен подпис с проверяваща функция, изискваща ключ с доста по-малки размери от съответните, построени на симетрични алгоритми.
Недостатъци:
- Относително по-бавни в сравнение със симетричните.
- При използване за криптиране ключът им е много по-дълъг от този на симетричните.
- Дължината на добавения електронен подпис е относително голяма.
Към асиметричните криптосистеми спадат RSA, RSA(Rabin-Williams modification),
ElGamal, Elliptic Curves Cryptography и др.
Криптосистема RSA:
Носи името на създателите си: Rivest, Shamir, Adleman. Описанието и може да се
´
намери в почти всички книги по криптография (виж [?]) както и в стандартите PKCS
#1 [?], ISO 11166 [?, ?]. Сигурността на RSA се основава на трудността да се разложи едно естествено число n на прости множители. За достатъчно големи n съвременните математически методи и компютърна техника не могат да се справят с тази задача.
Нека n = pq е произведение на две големи прости числа и e, 1 < e < ϕ(n), е случайно число, такова че (e, ϕ(n)) = 1 (ϕ(n) е функцията на Ойлер от n). RSA ползва два ключа:
ПУБЛИЧЕН КЛЮЧ: (n, e), състоящ се от модул n и експонента e;
ЧАСТЕН КЛЮЧ: d, 1 < d < ϕ(n), такова че ed ≡ 1 (mod ϕ(n)).
КРИПТИРАНЕ: Съобщението се превръща в поредица от числа m1 , m2 , . . ., всяко от които се криптира по правилото: mi −→ ci ≡ me (mod n). i Поредицата c1 , c2 , . . . представлява шифротекста.
ДЕКРИПТИРАНЕ: Открития текст се получава с mi ≡ cd (mod n). i Наистина cd ≡ med (mod n). Но от ed ≡ 1 (mod (p − 1)) и теоремата на Ферма следва, i i че med ≡ mi (mod p). Аналогично med ≡ mi (mod q). Тъй като p и q са различни прости i i числа, то med ≡ mi (mod pq). i Криптосистемата RSA се използва най-вече за създаване на електронен подпис, при разпространение и съхраняване на ключове за симетрични алгоритми и за аутентификация.
Понастоящем модулът n трябва да бъде число поне от 768 бита (в двоичен запис). При приложения, които изискват по-дълъг срок на надежност (месеци или години, както е при електронния подпис), трябва да се ползват модули с дължина поне 1024 бита. Числата p и q също трябва да удовлетворяват някои ограничения, които са описани в стандартизационните документи.
Експонентата и частният ключ не е препоръчително да бъдат много малки, защото при определени обстоятелства може да се разкрие съобщението m. Има
6.2. Криптографски примитиви и механизми.
95
реализации, при които e = 3, но в тези случаи, особено за малки m, сигурността е слаба. В тези случаи към съобщението се добавя случайна информация, за да се избегне малко m. Ако вместо малки експоненти се вземат такива, които имат малко единици в двоичното им представяне, криптирането също ще изисква по-малко ресурси.
Вариант на RSA е криптосистемата на Rabin-Williams. Сигурността и се основава
´
на трудността на разлагане на прости множители и на намирането квадратен корен по модул съставно n.
Пример 6.2.1 Нека p = 73 и q = 109. Тогава n = pq = 7957, а ϕ(n) = 7776. Да изберем за експонента e = 17. Публичния ключ ще бъде (7776, 17). Тъй като 17·7489 ≡ 1 (mod 7776), то частния ключ е d = 7489.
Да криптираме съобщението “Кой е Ойлер?”. За целта всеки два последователни текстови символа ще разглеждаме като двузначни числа в 89-ична бройна система, т.е. от Ко|й |е
|Ой|ле|р? получаваме 51 · 89 + 25 | 20 · 89 + 10 | . . . | 27 · 89 + 87. Следователно на нашия текст съответства съвкупност от 6 числа: 4564 | 1790 | 1434 | 4915 | 1974 | 2490. Сега всяко от тези числа трябва да подигнем на степен 17 по модул 7957. Да забележим, че a17 = (((a2 )2 )2 )2 · a, т.е. повдигането може да извършим с последователни повдигания в квадрат и едно умножение. След изпълнение на операциите получаваме
456417 ≡ 7859 (mod 7957), 179017 ≡ 3552 (mod 7957), . . . , 249017 ≡ 2911 (mod 7957)
И така шифротекстът е набора от шесте числа
7859 | 3552 | 1885 | 2339 | 1557 | 2911.
Ако всяко от тях представим в 89-ична бройна система и използваме Таблица 5.1 ще получим текстови запис на шифротекста: р$ | *ю | ек | оп | Гж | Цх
Трябва да отбележим, че 88 · 89 + 88 = 7920 < 7957, то след повдигане в степен по модул n може да се получи число, което е с 3 цифри в 89-ична бройна система. Затова, ако шифротекстът ще се преобразува в текстова форма, то някакво разделяне (както горе) трябва да се направи. Тази възможност също създава неудобства при използване на RSA. Затова обикновено се ползва за електронен подпис или криптиране на кратки съобщения (например парола или ключ за симетрична криптосистема), така че да не се налага разбиване на текста на блокове.
Криптосистема на ElGamal:
Вариант на тази ситема се използва като асиметричен алгоритъм в механизма за електронен подпис DSA. Сигурността и се основава върху трудността на намиране на дискретен
´
логаритъм в Zp . Публичният ключ на даден потребител U представлява тройка (p, g, E), където g е примитивен корен по модул p и E = g a . Частният ключ е a, 1 ≤ a ≤ p − 2.
Ако група ползватели имат едни и същи p и g, то публичният ключ, който се записва в регистъра, е само E = g a . Процедурата по криптирането е следната: Потребител S, който иска да изпрати съобщение m на U избира произволно число k и изпраща двойката
(g k , mE k ). За да декриптира съобщениет U изчислява D = (g k )a = E k и след това намира mE k D−1 ≡ mE k E −k ≡ m (mod p).
96
ЛЕКЦИИ ПО ТЕОРИЯ НА ЧИСЛАТА
Н. Л. МАНЕВ
Простото число p трябва да е с дължина поне 768 бита, като за подългосрочна сигурност се препоръчва дължина поне 1024 бита. Като недостатък на криптосистемата на ElGamal може да се посочи, че шифротекста е два пъти по-дълъг от открития текст.
При варианта, фиксиран в DSA (FIPS 186), цикличната група не е Zp , а нейна подгрупа от ред простото число q с дължина 160 бита и делящо p−1. Затова публичният ключ включва и q.
Криптосистемата на ElGamal естествено се обобщава като Zp се замени с произволна крайна циклична група от достатъчно голям ред. Частен случай на обобщената криптосистема на ElGamal е криптоситемата, основана на елиптични криви.
6.2.3
Управление на ключове. Протокол на Diffie-Hellman.
Управлението на ключовете включва тяхното създаване, съхранение, разпределение и унищожаване. Пропуски в предаването и съхранението на ключа стават най-често причина за компроментиране на дадена система за защита. Описаният протокол представлява един математически подход при решаването на този тип проблеми в защитата на информация.
Протокол на Diffie-Hellman (DH): Нека А и В са двама участника (например терминални устройства или потребители) в комуникационен процес, които трябва да договорят ключ за предстоящата им комуникационна сесия. На А и В са известни
(обикновено те са публично известни или са заложени във всяко устройство) базисните параметри на протокола, които са постоянни за всички сесии. Това са:
• голямо просто число p - поне 512 бита, обикновено с дължина 1024 бита, и
• цяло число g : 1 < g < p − 1, за което g k ≡ 1 (mod p) за всяко k < p − 1.
Протоколът се състои от следните стъпки:
1. А генерира случайно число a : 1 < a < p−1, и изпраща на В числото x ≡ g a (mod p).
2. В генерира случайно число b : 1 < b < p−1, и изпраща на А числото y ≡ g b (mod p).
3. А изчислява K ≡ y a ≡ g ab (mod p).
4. В изчислява K ≡ xb ≡ g ab (mod p).
5. Всеки от А и В прилагат хеш-функция H към (двоичния запис на) K и намират
S = H(K).
Получената бинарна поредица S е сесийния ключ. Случайните числа a и b се пазят в тайна от А и В, съответно, и се унищожават веднага след намирането на ключа или поне в края на сесията. Не трябва да съществува възможност те да бъдат изпратени или извлечени от устройството, което пресмята S. Ключат S също се унищожава веднага след приключване на сесията.
С цел да се намали времето за изчисление обикновено се реализира модифициран вариант на DH. Модулът се избира от вида p = 2tq + 1, където q е също просто число с дължина 160 бита (трябва да е поне 128 бита), а за g се взема число с показател q по модул p, т.е. g = α2t , където α е примитивен корен по модул p. За да се избегнат някои атаки t може да се избере също просто.
6.3. Електронен подпис.
6.3
97
Електронен подпис.
Всеки механизъм за електронен подпис (МСЕП) включва алгоритъм за генериране на подписа и проверяващ автентичността му алгоритъм. Алгоритъмът за генериране на подписа, заедно с методите за привеждане на съобщението в подходящ за подписване вид, формират процеса на цифрово (електронно) подписване, а проверяващият алгоритъм заедно със средствата за разкриване на съобщението - процеса на проверка на цифровия подпис. Формализираното описание на механизма, по който един участник U в компютърна комуникационна система подписва своите съобщения (електронни изявления) включва:
• пространство от съобщенията M и пространство от подписите S
• трансформация SU : M → S, която е известна само на U
• проверяваща трансформация VU : M × S → {true, f alse}, като са в сила следните свойства:
• s ∈ S е валиден подпис тогава и само тогава, когато VU (m, s) = true
• изчислително невъзможно е за всеки освен U да намери за всяко m ∈ M такова s ∈ S, че VU (m, s) = true.
Подписване:
1. Пресмятане на s = SU (m)
2. Изпращане на (m, s).
Процедура за проверка:
1. Получаване на VU (от U или от регистър)
2. Пресмяне на u = VU (m, s)
3. Приемане на подписа при u = true и отхвърляне в противния случай.
На практика МСЕП трябва да притежава следните свойства:
- лесно да се създава ЕП, т.е. SU да бъде достатъчно бърза и удобна за прилагане;
- лесна проверка на ЕП, т.е. VU да бъде достатъчно бърза и удобна за прилагане;
- механизмът да остава сигурен поне за периода, през който подписа е валиден, т.е. времето, необходимо за разбиване на системата, да надхвърля този период. Понятието
“сигурен” включва практическата невъзможност друг освен автора на подписа да създаде смислени съобщения, които подложени заедно с подписа на проверяващата функция VU , да дават резултат true.
Трябва изрично да отбележим, че необходимостта от електронен подпис предполага две взаимно подозиращи се и/или готови да го оспорят страни. Затова не е възможно използването на общ ключ при реализацията на SU и проверяващата трансформация
VU . Това предопределя използването на асиметрични криптографски алгоритми (както е показано във Фиг. 5.1) с два ключа - частен и публичен. В литературата съществуват описания на МСЕП на базата на симетричен алгоритъм, но те изискват въвличане на
ТТР в процесите на генериране и проверка на подписа и то в твърде тромави процедури.
Затова тези схеми не са и залегнали в международните документи.
Трансформацията SU най-често е сложна функция, представляваща композиция
(последователно прилагане) на хеш-функция h и криптографска трансформация E. Фигура
5.1 изобразява блоковата структура на механизъм за електронен подпис с такава трансформация
SU . При него съобщението се предава в явен вид. Възможни са, обаче, и реализации, при които то е зашифровано. Подходящи за тази цел са симетричните алгоритми, защото са по-бързи и удобни за реализация. Освен това засекретяване на текста на съобщението
98
ЛЕКЦИИ ПО ТЕОРИЯ НА ЧИСЛАТА
Н. Л. МАНЕВ
предполага желание за това от двете страни (или нормативни изисквания), което предполага и сътрудничество между страните за грижливо съхранение на общия ключ.
Фиг. 5.1 Блокова схема на система за електронен подпис
Вторият тип механизм за електронен подпис, който предполага извличане на съобщението от самия подпис, се използва само за много кратки съобщения (парола, ключ, идентификационен номер), тъй като прилагането на асиметричен алгоритъм за криптиране на дълги съобщения е бавен процес, изискващ много ресурси. Този механизъм въвлича функция, която създава излишък (разширява съобщението), за да не бъде всеки възможен подпис в действителност подпис на истинско съобщение, т.е. броят на възможните съобщения да бъде много помалък от този на възможните подписи.
Този тип електронен подпис не е визиран от “Закона за електронния документ и електронния подпис” (ЗЕДЕП), но би могъл да се ползва при разпространение на секретни ключове
(за симетрични криптосистеми) или подписване на сертификати.
В някои случаи е необходимо да се подпише дадено съобщение, но без да се разкрива неговото съдържание. В тези случаи се прилага така нареченото сляпо подписване
(blind signature). Този механизъм е реализиран в разпространения протокол електронни разплащания “Digicash". Ето накратко описанието на този механизъм:
6.4. Генериране на големи прости числа.
99
Да предположим, че A иска B (частно лице, овластен субект, ТТР или ДУУ и др.) да подпише неговия документ M , но без съдържанието му да стане известно на B. Нека e и d са, съответно, публичния и частен ключ на B. Тогава
1. A генерира случайно число R, изчислява M1 = Re M (mod n) и го изпраща на B. d 2. Използвайки своя частен ключ, d, B пресмята S = M1 = Red .M d = R.M d по модул n и го връща на A.
3. При получаването на S, A умножава S с R−1 за да намери M d , което представлява подписания документ.
В литературата са описани и редица други механизми от тип електронен подпис, които са реализирани в специфични приложения . Един такъв механизъм е така наречения fail-stop подпис. Той позволява да се открива, ако е направена фалшификация и съответния публичен ключ да се изважда веднага от употреба. Друг тип е така наречения undeniable signature schemе, който изисква сътрудничеството на подписващия за проверка на подписа. Реализира се например, когато подписващият осъществява достъп до нещо
(например, сейф) в дадено време. Целта е никой да не може да твърди, че този достъп е направен, когато не е осъществяван или във време различно от истинското. Тези и други подобни механизми излизат от рамките на нашия курс и няма да ги разглеждаме подробно. 6.4
Генериране на големи прости числа.
Както видяхме в предходните параграфи много от съвременнитеза асиметрични криптосистеми изискват като ключове или параметри големи прости числа от порядъка на 1024 бита.
Методи като решетото на Ератостен и проверки за простотота чрез деление на прости
√
делители < n са очевидно неефективни дори за 128 битови числа. Затова на основата на резултати от Теория на числата са създадени множество тестове, чрез които се проверява дали дадено нечетно число е просто. Процесът на генериране на голямо просто число представлява поредица от по две стъпки - генериране на голямо нечетно число (най-често случайно) и проверката му чрез тест за простота. Процедурата продължава докато теста даде положителен резултат.
Тестовете за простота се делят на два типа:
• вероятностни
• детерминистични
Най-често се използват първите.
6.4.1
Вероятностни тестове за простота. Тест на Miller-Rabin.
Най-общо тези тестове се описват така:
Дефинира се множество W (n) ⊂ {1, 2, . . . , n − 1}, което за всяко нечетно естествено число n притежава следните свойства:
(1) Ако n е просто число, то W (n) = ∅;
(2) Ако n е съставно число, то | W (n) |≥
n
2
(3) За всяко a ∈ {1, 2, . . . , n − 1} може “лесно” (за полиномиално време) да се определи дали a ∈ W (n).
100
ЛЕКЦИИ ПО ТЕОРИЯ НА ЧИСЛАТА
Н. Л. МАНЕВ
1
При проверка за дадено a тестът дава, че или n е съставно, или с вероятност ≥ 2 е просто. Ако се направят t проверки (итерации на теста) и те са положителни, то n е t съставно (т.е. тестът е дава грешен резултат) с вероятност < 1 .
2
Тест на Miller-Rabin.
Твърдение 6.4.1 Нека p е нечетно просто число и p − 1 = 2e r, където r е нечетно i число. Ако a удовлетворява (a, p) = 1, то или ar ≡ 1 (mod p), или a2 r ≡ −1 (mod p) за някое i : 0 ≤ i ≤ e − 1.
Доказателство. Съгласно теоремата на Ферма за всяко такова a е в сила p−1 ap−1 ≡ 1 (mod p). Следователно x = a 2 удовлетворява x2 ≡ 1 (mod p). Но p−1 p−1 последното влече a 2 ≡ ±1 (mod p). Ако a 2 ≡ 1 (mod p) продължаваме p−1 аналогично като разглеждаме a 4 и т.н. С това твърдението е доказано.
Горното твърдение дава необходимо, но не и достатъчно, условие едно нечетно число да е просто, на което се основава тестът на Милер. На всяка итерация от теста за дадено a, (a, n) = 1, се проверява, дали се изпълнява някое от сравненията в Твърдение 6.4.1.
Ако резултатът е отрицателен, n е съставно число. Ако е положителен се преминава към следваща итерация (за друго a) докато се извършат първоначално зададен брой от t итерации.
Дефиниция 6.4.2 Съставно нечетно число n, което издържа теста на Милер за дадено a, (a, n) = 1, се нарича силно псевдопросто число при основа a. t Вероятността за грешка след t итерации на теста на Милер-Рабин е ≤ 1 , тъй като
4
съгласно Теорема 6.4.4 вероятността за грешка при една итерация не надминава 1/4.
Лема 6.4.3 Нека p е нечетно просто число и p − 1 = 2k r. Тогава сравнението i x2 t ≡ −1 (mod p)
(6.1)
има точно 2i (t, r) решения, ако i ≤ k − 1 и няма решение при i ≥ k.
Доказателство. Нека d = (2i t, ϕ(p)) = (2i t, 2k r) = 2m (t, r), където m = min(k, i). Съгласно Теорема 4.1.3 сравнението (6.1) има решение тогава и само тогава, когато ϕ(p) (−1) d ≡ 1 (mod p) и броят на решенията му е d. Но това е изпълнено тогава и само тогава, когато
2k r
2m (t, r) е четно число, т.е. k > m. Следователно при i ≥ k (6.1) няма решение, а при i ≤ k − 1 има точно 2i (t, r) решения.
Теорема 6.4.4 Ако n е нечетно и съставно естествено число, то n издържа теста на Милер-Рабин най-многа за 1 ϕ(n) основи a, (a, n) = 1, и 1 ≤ a ≤ n − 1.
4
6.4. Генериране на големи прости числа.
101
Доказателство. Възможни са два случая.
(1) Нека p2 | n за някое просто число p. Да предположим, че a е основа относно, която n е силно псевдопросто. Тогава от an−1 ≡ 1 (mod n) следва, че an−1 ≡ 1 (mod p2 ). Съгласно Теорема 4.1.3 броят на решенията на последното сравнение е d = (ϕ(p2 ), n − 1) = (p(p − 1), n − 1)
и
d | (p − 1),
тъй като p (n − 1). Следователно d ≤ p − 1 и отношението на основите a, относно които n е силно псевдопросто към всички възможни p2 − 1 по модул p2 числа е p−1 1
1
≤ 2
=
≤ . p −1 p+1 4
2 равенството се достига.
Да отбележим, че при n = 3
(2) Нека сега n е произведение на различни прости числа. Ще разгледаме само n = pq. В общия случай се процедира аналогично. Нека p − 1 = 2k t1 и q − 1 = 2l t2 , където t1 , t2 са нечетни и k ≤ l. Ако a е основа относно, която n е силно псевдопросто и n − 1 = 2e t, то една от следните възможности трябва да е в сила:
(i) at ≡ 1 (mod p) и at ≡ 1 (mod q) j j
(ii) a2 t ≡ −1 (mod p) и a2 t ≡ −1 (mod q), за някое 0 ≤ j ≤ e − 1.
Съгласно Теорема 4.1.3, ако е изпълнено (i) броят на решенията на всяко от сравненията е съответно (t, p − 1) = (t, t1 ) и (t, q − 1) = (t, t2 ). Сега Китайската теорема ни дава, че (i) е изпълнено за (t, t1 )(t, t2 ) ≤ t1 t2 числа a.
Нека е налице (ii). Съгласно Лема 6.4.3 сравненията на (ii) имат съответно
2j (t, t1 ) и 2j (t, t2 ) решения за 0 ≤ j ≤ k − 1. Следователно за фиксирано j броят на търсените числа a удовлетворяващи (ii) е 22j (t, t1 )(t, t2 ) ≤ 4j t1 t2 .
Сумирайки по j получаваме
4k − 1
.
3
Следователно отношението R на търсените основи към всички ϕ(n) = 2k+l t1 t2 възможни основи при k < l е t1 t2 (1 + 4 + · · · + 4k−1 ) = t1 t2
Нека k = l. Тогава не е възможно едновременно (t, t1 ) = t1 и (t, t2 ) = t2 .
Наистина да допуснем противното. В такъв случай t1 | t и t2 | t. Тъй като p = 2k t1 + 1 и q = 2k t2 + 1, то 2e t = n − 1 = pq − 1 = 22k t1 t2 + 2k t1 + 2k t2 .
Следователно t1 | t2 и t2 | t1 , т.е. t1 = t2 . Но тогава p = q, което е противоречие.
1
И така, нека за конкретност (t1 , t) < t1 . Тъй като t1 е нечетно, то (t1 , t) ≤ 3 t1 .
Тогава за фиксирано j броят на търсените числа a удовлетворяващи (ii) е
22j (t, t1 )(t, t2 ) ≤ 4j t1 t2 /3. Следователно
R≤
При този тип тестове се доказва, че нечетното число n е просто. За целта се проверява, че някое достатъчно условие е изпълнено. Естествено, този тип тестове изискват повече изчислителни ресурси и са по бавни от вероятностните. Те се използват за доказване на простота (ако е необходимо) на числа, които вече са намерени с вероятностни тестове.
Един такъв тест например се базира на следното добре известно твърдение.
Твърдение 6.4.5 Числото n ≥ 3 е просто тогава и само тогава, когато съществува a, такова че
(1) an−1 ≡ 1 (mod n) и
(2) a
n−1 q ≡ 1 (mod n) за всеки прост делител q на n − 1.
Един тест за проверка дали 2k − 1 е просто число на Мерсен се основава на следния резултат. Теорема 6.4.6 Нека k ≥ 3. Числото Mk = 2k − 1 е просто тогава и само тогава, когато са изпълнени следните две условия:
(a) k е просто число и
(b) рекурентната редица дефинирана с sj+1 ≡ (s2 − 2) (mod Mk ) за j ≥ 1, и j s1 = 4,
(6.2)
удовлетворява sk−1 ≡ 0 (mod Mk ).
√
√
Доказателство. Да положим α = 2 + 3 и β = 2 − 3. Очевидно, че αβ = 1. С метода на математическата индукция лесно се показва, че общият член на редицата {sn }, определена с (6.2), се задава с формулата sn = α2
n−1
n−1
+ β2
, n = 1, 2, . . . ,
(6.3)
Достатъчност. Нека p ≥ 3 е просто число и sp−1 ≡ 0 (mod Mp ). Тогава p−2 p−2 p−2 sp−1 = α2
+ β 2 , откъдето умножавайки по α2 получаваме p−1
α2
+ 1 = sp−1 α2
p−2
.
В такъв случай условието Mp | sp−1 влече p−1 α2
+ 1 = Mp · d · α2
p−2
.
Да допуснем, че Mp не е просто. Тогава съществува просто число q ≤ p−1 ≡ −1 (mod q), т.е. със свойството q | Mp . Следователно α2 p α2 ≡ 1 (mod q).
Mp
(6.4)
6.4. Генериране на големи прости числа.
103
√
√
Да разгледаме мултипликативната група на пръстена Zq [ 3] = {a + b 3 |
√
a, b ∈ Zq } Тогава (6.4) означава, че редът на α в Zq [ 3] е o(α) = 2p . Следователно
√
2p ≤| Zq [ 3] |≤ q 2 − 1 ≤ Mp − 1 = 2p − 2, което е противоречие.
Необходимост. Нека Mp = 2p − 1 е просто число на Мерсен. Очевидно p трябва да е просто. Остава √ покажем, че е изпълнено и условие (b). За да √
√ √ целта да √ разгледаме τ = (1 + 3)/ 2 и τ = (1 − 3)/ 2, τ τ = −1. Тъй като
¯
¯ p p−1 τ 2 = 2 + 3 = α, то τ q+1 = τ 2 = α2 , където q = Mp . Тогава
√
√ q−1 √ q q √ i
(τ 2)q = 1 + q 3 +
3 + ··· +
( 3) + · · · + 3 2 3.
2
i
Но q дели
q i , тъй като е просто и следователно
2
q−1
2
√
√
q−1 √ τ q 2 = 1 + qa 3 + qb + 3 2 3,
където a, b ∈ Z. Тъй като q = 2p − 1 ≡ −1 − 1 ≡ 1(mod 3), то съгласно квадратичния закон за реципрочност
3
q
= (−1)
q−1
2
1
3
(6.5) q 3
=
1
3
=1и
= −1.
Тогава критерият на Ойлер ни дава, че
3
q−1
2
≡ −1 (mod q).
Аналогично (за p ≥ 3) е в сила q ≡ −1(mod 8), т.е.
2
q−1
2
2 q = 1 и следователно
≡ 1 (mod q).
Замествайки в (6.5) получаваме, че съществуват цели числа c, d:
√
√
√
(1 + cq)τ q 2 = 1 + qa 3 + qb + (−1 + dq) 3,
т.е.
горното равенство и αβ = 1 ни където e, f ∈ Z. След умножаване с 2β 2 дават √ p−2 p−2 p−2 2α2 (1 + cq) = −2β 2
+ (e + f 3)β 2 q,
104
ЛЕКЦИИ ПО ТЕОРИЯ НА ЧИСЛАТА
т.е.
p−2
2(α2
p−2
+ β2
p−2
) = −2α2
Следователно
2sp−2 = [−2α2
p−2
Н. Л. МАНЕВ
√ p−2 cq + (e + f 3)β 2 q.
√ p−2 c + (e + f 3)β 2 ]q.
Тъй като лявата страна е цяло число, то и в скобите на дясната страна трябва да е рационално (т.е. цяло) число. Но тогава sp−2 ≡ 0 (mod q).
С това доказателството е завършено.
