Новиков Ф.А. Дискретная математика для программистов (860615), страница 44
Текст из файла (страница 44)
При увеличении п экспоненциально увеличиваетсякриптостойкость шифра.2336.5. ШифрованиеОТСТУПЛЕНИЕЭтот очень простой и эффективный метод часто применяют «внутри» программных систем, например, для защиты данных на локальном диске. Для защиты данных, передаваемых по открытым каналам связи, особенно в случае многостороннего обмена сообщениями, этот метод применяют не так часто, поскольку возникают трудности с падёжнойпередачей секретного ключа многим пользователям.6.5.3.
КриптостойкостьОписаиный в предыдущем подразделе метод шифрования обладает существенным недостатком. Если известна хотя бы часть исходного сообщения, то всёсообщение может быть легко дешифровано. Действительно, пусть известно одноисходное слово Si. ТогдаTI-.=CI+2SI,и далее вся правая часть гаммы шифра определяется по указанной формуледатчика псевдослучайных чисел.ЗАМЕЧАНИЕНа практике часть сообщения вполне может быть известна злоумышленнику.
Например, многие текстовые редакторы помещают в начало файла документа одну и ту жеслужебную информацию. Если злоумышленнику известно, что исходное сообщение подготовлено в данном редакторе, то он сможет легко дешифровать сообщение.Для повышения криптостойкости симметричиых шифров применяют различныеприёмы:1. Вычислеиие гаммы шифра по ключу более сложным (или секретным) способом.2. Применение вместо +2 более сложной (по обратимой) операции для вычисления шифровки.3. Предварительное перемешивание битов исходного сообщения по фиксированному алгоритму.Наиболее надёжным симметричным шифром считается DES (Data EncryptionStandard), в котором используется сразу несколько методов повышения криптостойкости.6.5.4.
Модулярная арифметикаДля объяснения метода шифрования с открытым ключом, описанного в следующем подразделе, нужны некоторые факты из теории чисел, изложенные здесьбез доказательств.В этом подразделе рассматриваются только целые числа. Говорят, что число асравнимо по модулю п с числом b (обозначение а = b mod п), если а и b приделении на п дают один и тот же остаток:а = b mod n =' a mod п — b mod п.234Глава 6. Кодирование 234ЗАМЕЧАНИЕВ левой части этого определения слово mod является частью обозначения трехместногоотношения, а в правой части слово mod является обозначением двухместной операцииопределения остатка от деления.Отношение сравнимости рефлексивно, симметрично и транзитивно и являетсяотношением эквивалентности.
Классы эквивалентности по отношению сравнимости (по модулю п) называются вычетами (по модулю п). Множество вычетовпо модулю п обозначается Z n . Обычно из каждого вычета выбирают одного представителя — неотрицательное число, которое при делении на п дает частное 0.Это позволяет считать, что Z n = {0,1,2,...
,п — 1}, и упростить обозначения.Над вычетами (по модулю п) определены операции сложения и умножения помодулю п, обозначаемые, соответственно, +те ии определяемые следующимобразом:а +п b = (а + b) mod п,а -п b = f (а • b) mod п.ЗАМЕЧАНИЕЕсли из контекста ясно, что подразумеваются операции по модулю п, то индекс п опускается.Легко видеть, что (Z n ; + п ) является абелевой группой, a (Z n ; + п , •„) — коммутативным кольцом с единицей.ЗАМЕЧАНИЕЕсли п — простое число, то (Zn; +п, -п) является полем.Рассмотрим Z* — подмножество множества вычетов Z n , взаимно простых с п.ЗАМЕЧАНИЕЧисла а и b называются взаимно простыми, если их наибольший общий делитель равен 1.Можно показать, что (Z*; n ) — абелева группа.
Таким образом, для элементовмножества Z* существуют обратные по умножению по модулю п.Функция ip(n) = f |Z* | называется функцией Эйлера.ЗАМЕЧАНИЕЕсли р — простое число, то ip(p) = р — 1, и вообще, <р(п) < п.Можно показать, чтогде p i , . . . , pk — все простые делители п.Имеет место следующая теорема.2356.5. ШифрованиеТЕОРЕМА (Эйлера)Если тг > 1, тоVa € Z* (a?™ = 1 mod n j .Отсюда непосредственно вытекаетТЕОРЕМА (малая теорема Ферма1)Va Gz;Если р> 1 — простое число, то( a p _ 1 = 1 mod р ) .Имеет место следующее утверждение.ТЕОРЕМА Если числа п\,...,пкпопарно взаимно просты, п = П1П2 • • • Пк — ихпроизведение, хиа — целые числа, тох = a mod п •<==> Vi €(х = a mod щ).ЗАМЕЧАНИЕПоследнее утверждение известно как «китайская теорема об остатках».6.5.5.
Шифрование с открытым ключомВ настоящее время широкое распространение получили шифры с открытымключом. Эти шифры не являются симметричными — для зашифровки и расшифровки используются разные ключи. При этом ключ, используемый для зашифровки, является открытым (не секретным) и может быть сообщен всем желающим отправить шифрованное сообщение, а ключ, используемый для расшифровки, является закрытым и хранится в секрете получателем шифрованных сообщений.
Даже знание всего зашифрованного сообщения и открытогоключа, с помощью которого оно было зашифровано, не позволяет дешифроватьсообщение (без знания закрытого ключа).Шифрование с открытым ключом производится следующим образом:1. Получателем сообщений производится генерация открытого ключа (пара чисел п и е) и закрытого ключа (число d). Для этого:• выбираются два простых числа р и q\• вычисляется первая часть открытого ключа n:=pq;• определяется вторая часть открытого ключа — выбирается небольшое нечётное число е, взаимно простое с числом (р — l)(g - 1) (заметим, что(р - 1 )(q ~1)= pq( 1 - l/p)(l - l/q) = <р{п)У,• определяется закрытый ключ: d \ = е - 1 mod (р - 1 )(q - 1).После чего открытый ключ (числа п и е) сообщается всем отправителямсообщений.1Пьерде Ферма (1601-1665).236Глава 6. Кодирование 2362.
Отправитель шифрует сообщение (разбивая его, если нужно, на слова Si длипой менее log2 п разрядов):Ci: ={Si)e mod n,и отправляет получателю.3. Получатель расшифровывает сообщение с помощью закрытого ключа d:Pi: =(Ci)d mod п.Шифрование с открытым ключом корректно, то есть в предыдущихобозначениях Рг = Si.ТЕОРЕМАДОКАЗАТЕЛЬСТВОЛегко видеть, что Pi = (Si) e d mod п. Покажем, чтоVM < п (Med = М mod п) .Действительно, числа d и е взаимно обратны по модулю (р — 1)(д - 1), то естьed= 1 + k(p — l)(q — 1)при некотором к.
Если М ф 0 mod р, то по малой теореме Ферма имеем:Med = М (м^-1^44^= М • 1к{ч'1]= М mod р.Если М = 0 mod р, то сравнение Med = М mod р, очевидно, выполняется. Такимобразом,V0 ^ М < п (Med = М mod р).Совершенно аналогично имеемV0 ^ М < п ( M e d = М mod q) ,и по китайской теореме об остаткахVM < n (Med = М mod п) .Поскольку Si < п и Pi < п, заключаем, что Vг {Pi = Si).Пример•Генерация ключей:1. р: = 3, q : = n.2.
п: = pq = 3 * 11 = 33.3. (р - l)(q - 1) = 2 * 10 = 20, е : = 7.4. d: = 7~l mod 20 = 3, (7 * 3 mod 20 = 1).Пусть Si: = 3, S2: = l, S3: = 2 (Si,S2,S3следующим образом:1. C i : = З7 mod 33 = 2187 mod 33 = 9.2. С 2 : = l 7 mod 33 = 1 mod 33 = 1.3.
C 3 : = 27 mod 33 = 128 mod 33 = 29.< n = 33). Тогда код определяется6.5. Шифрование237При расшифровке имеем:1. Pj : = 9 3 mod 33 = 729 mod 33 = 3.2. Р 2 : = l 3 mod 33 = 1 mod 33 = 1.3. P 3 : = 29 3 mod 33 = 24389 mod 33 = 2.ОТСТУПЛЕНИЕШифры с открытым ключом сравнительно просты в реализации, очень практичны (поскольку нет необходимости пересылать по каналам связи закрытый ключ и можно безопасно хранить его в одном месте) и в то же время обладают высочайшей криптостойкостыо. Кажется, что дешифровать сообщение несложно: достаточно разложить открытоопубликованное число п на множители, восстановив числа р и q, и далее можно легковычислить секретный ключ d.
Однако дело заключается в следующем. В настоящее времяизвестны эффективные алгоритмы определения простоты чисел, которые позволяют занесколько минут подобрать пару очень больших простых чисел (по 100 и больше цифрв десятичной записи). В то же время неизвестны эффективные алгоритмы разложенияочень больших чисел на множители. Разложение на множители числа в 200 и больше цифрпотребовало бы сотен лет работы самого лучшего суперкомпьютера. При практическомприменении шифров с открытым ключом используют действительно большие простыечисла (не менее 100 цифр в десятичной записи, а обычно значительно больше).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
