Методы и средства защиты информации. Внимание!!! В книге могут встречаться существенные ошибки (в рисунках и формулах). Они не связаны ни со
 Скачать 4.86 Mb.
|
|
Глава 18. Криптографическая защита понять последующего обмена сообщениями Второй подход реализует крипто - графические системы с открытыми ключами , в которых для шифрования исполь - зуются разные ключи Причина , по которой ключи в обычных криптографических системах должны столь тщательно защищаться , состоит в том , что функции шифрования и де - шифрования в ней неразделимы Любое лицо , получившее ключ для шифро - вания сообщений , может также дешифровать сообщения Если средства шиф - рования разделены , то секретность можно обеспечить без засекречивания ключа шифрования , так как его нельзя использовать для расшифровывания Взаимодействуя по открытым каналам связи , абоненты А и В решают сле - дующие задачи : • вначале у А и В нет никакой общей секретной информации , но в конце проце - дуры такая общая секретная информация ( общий ключ ) у А и В появляется , т е вырабатывается ; • противник , который перехватывает все передачи и знает , что хочет получить А и В , тем не менее не может восстановить выработанный общий ключ А и В Предложено решать эти задачи с помощью функции F(x) = α x (mod p) , где р — большое простое число , x — произвольное натуральное число , α — некото - рый примитивный элемент поля G F(p) Примитивным называется такой элемент α из G F(p) , что каждый элемент поля , может быть представлен в виде степени α Доказывается , что примитив - ный элемент всегда существует Общепризнанно , что инвертирование функции α x (mod p) , т е дискретное ло - гарифмирование , является трудной математической задачей Саму же процедуру или , как принято говорить , протокол выработки общего ключа , можно описать следующим образом Числа р и α считаются общедоступными Абоненты А и В независимо друг от друга случайно выбирают по одному на - туральному числу — скажем x A и x B и Эти элементы они держат в секрете Да - лее каждый из них вычисляет новый элемент : у A = α x A (mod p), у B = α x B (mod p) Потом они обмениваются этими элементами по каналу связи Теперь або - нент А , получив у B и зная свой секретный элемент x A , вычисляет новый эле - мент : у B x A = (α x B ) x A (mod p) Аналогично поступает абонент В : у A x B = (α x A ) x B (mod p) Анализ основных криптографических методов ЗИ 385 Из свойств поля следует , что тем самым у А и В появится общий элемент , ко - торый и является общим ключом А и В Из описания протокола видно , что противник знает p , α , α x A , α x B , не знает x A , x B и хочет узнать α x A x B В настоящее время нет алгоритмов действий противника , более эффективных , чем дискретное логарифмирование , а это — труднейшая математическая задача Эти системы должны разрабатываться таким образом , чтобы облегчить гене - рацию случайных пар инверсных ключей Е для шифрования и Д для дешифро - вания и работу с этими ключами , но чтобы вычисления Д по Е было вычисли - тельно нереализуемым Криптографическая система с открытым ключом представляет собой пару семейств алгоритмов {E K } K ∈ {K} и {Д K } K ∈ {K} , определяющих обратимые преобра - зования EK:{M} → {m} ДK:{M} → {m} , на конечном пространстве сообщений {M} со следующими свойствами 1. Для каждого K ∈ {K} Д K обратно к E K , т е при любых К и М справедливо Д К Е К (М) = М 2. Для каждого K ∈ {K} и M ∈ {M} нетрудно вычислить величины Е К (М) и Д К (М) 3. Для почти каждого K ∈ {K} невозможно в вычислительном отношении вывести из Е К какой - либо легко выполнимый алгоритм , эквивалентный Д К 4. По каждому заданному K ∈ {K} можно получить инверсную пару Е К и Д К Свойство 3 позволяет не засекречивать ключи шифрования пользователя Е К и при этом не компроментировать секретность ключа дешифрования Д К Следо - вательно , криптогафические системы распадаются на две части ( семейство пре - образований шифрования и семейство преобразований дешифрования ) таким образом , что по данному члену одного семейства невозможно определить соот - ветствующий член другого Свойство 4 гарантирует наличие реализуемого пути вычисления соответст - вующих пар обратных преобразований , когда не наложено никаких ограничений на то , каким должно быть преобразование шифрования или дешифрования На практике криптографическое оборудование должно содержать генератор истин - ных случайных чисел для генерации К , а также генерирующий пару E К и Д К по заданному K Система такого рода упрощает проблему распределения ключей Каждый пользователь генерирует пару взаимно обратных преобразований Е и Д Он держит преобразование дешифрования Д в секрете , а преобразование шифро - вания публикует в открытом справочнике наподобие технического справочника Теперь любой желающий может шифровать сообщения и посылать их пользова - 386 Глава 18. Криптографическая защита телю , но никто , кроме него , не может дешифровать предназначенные для него сообщения Если вместо приведенных условий 1–4 множество преобразований обеспечи - вает , что для каждого K ∈ {K} E K является обратным Д K , т е при любых К и М справедливо утверждение Е К Д К (М) = М , то возможно , а часто и желательно осуществлять шифрование с помощью ключа Д , а дешифрование — с помощью ключа Е По этой причине часто называют E K открытым ключом , а Д K — лич - ным ключом За время , истекшее после того , как была предложены эта система , разрабо - тано несколько путей ее реализации Цифровая подпись Идея цифровой подписи ( ее еще называют электронной подписью ) была предложена Диффи и Хеллманом Суть ее заключается в использовании одно - сторонней функции с секретом F К В настоящее время эта идея реализована в большом количестве систем передачи данных Сообщение , подписанное циф - ровой подписью , можно представить в виде пары (x,y) , где x — сообщение , F К : x → y — односторонняя функция , известная всем взаимодействующим абонентам , y — решение уравнения F К (y) = x Из определения функции F К очевидны сле - дующие достоинства цифровой подписи 1. Подписать сообщение x , т е решить уравнение F K (y) = x , может только або - нент , являющийся обладателем данного секрета К ; другими словами , подде - лать подпись невозможно 3. Проверить подлинность подписи может любой абонент , знающий открытый ключ , т е саму функцию F K 4. При возникновении споров отказаться от подписи невозможно в силу ее не - подделываемости 5. Подписанные сообщения (x,y) можно , не опасаясь ущерба , пересылать по любым каналам связи Именно перечисленные достоинства и обусловили широкой применение и распространение систем цифровой подписи Как практически выглядит использование цифровой подписи ? Рассмотрим , как осуществляется работа банка с платежными поручениями своих клиентов Все абоненты этой сети знают одностороннюю функцию F K , и каждый клиент имеет собственный , никому неизвестный секрет К Клиент подписывает платеж - ное поручение x с помощью функции F K со своим секретом К и посылает подпи - санное платежное поручение в банк Банк , получив сообщение от клиента и зная открытый ключ , проверяет подлинность подписи клиента и только после этого выполняет его платежное поручение В силу отмеченных достоинств цифровой подписи и банк , и клиент уверены , что их интересы не пострадают Криптографическая система RSA 387 Широкое развитие систем электронных платежей , электронной почты и дру - гих систем передачи данных потребовало большого разнообразия цифровых подписей Это привело к развитию теории протоколов цифровой подписи , кото - рая в настоящее время составляет большой раздел теоретической криптогра - фии В рамках этой теории систематизированы различные виды взломов систем цифровой подписи , различные виды успехов , которых противник может достиг - нуть , различные виды стойкости схем цифровой подписи Удалось также дока - зать эквивалентность существования двух гипотетических объектов : односто - ронней функции и стойкой схемы цифровой подписи Криптографическая система RSA Как бы ни были сложны и надежны классические криптографические систе - мы , их слабым местом при практической реализации является проблема рас - пределения ключей Для того чтобы был возможен обмен конфиденциальной информацией между двумя абонентами , ключ должен быть сгенерирован одним из них , а затем каким - либо образом передан другому в конфиденциальном по - рядке В общем случае для передачи ключа по каналам связи требуется исполь - зование еще одной криптосистемы , для которой вновь возникает проблема рас - пределения ключей и т д Для решения этой и ряда других проблем были предложены криптоси - стемы с открытым ключом , называемые также асимметричными крип - тосистемами Перед отправкой сообщения адресату исходный текст шифруется открытым ( общедоступным ) ключом адресата Алгоритм шифрования построен таким об - разом , что расшифровывание сообщения возможно только с использованием личного ( секретного ) ключа адресата Впервые модель системы секретной связи с открытым ключом была предло - жена Диффи и Хеллманом в 1976 году Суть этой модели состоит в том , что ключ известен полностью только получа - телю сообщения и представляет собой тройку чисел k = (е, d, n) , где подключ e служит ключом шифрования , а ключ d — ключом расшифровывания При этом только d является секретным ( личным ) ключом Стойкость системы обеспечива - ется за счет особых свойств шифрпреобразования , которое представляет собой так называемую одностороннюю функцию с лазейкой Вычисление значения та - кой функции ( от открытого текста и параметра e ) должно быть несложным , в то же время ее обращение должно быть вычислительно нереализуемым без зна - ния секретной информации , “ лазейки ”, связанной с секретным ключом d В криптосистеме с открытым ключом сообщение , предназначенное абоненту , зашифровывается отправителем с помощью ключа e и расшифровывается по - лучателем с помощью ключа d Если шифрпреобразование действительно яв - ляется односторонней функцией , то сам отправитель не в состоянии расшифро - вать сформированную им криптограмму 388 Глава 18. Криптографическая защита Широко известным примером криптосистемы с открытым ключом является криптосистема RSA, разработанная в 1977 году и получившая название в честь ее создателей : Ривеста , Шамира и Эйдельмана Стойкость этой системы осно - вывается на сложности обратимости степенной функции в кольце вычетов целых чисел по составному модулю n ( при надлежащем выборе модуля ). Необходимые сведения из элементарной теории чисел 1. Простым числом называется натуральное число , имеющее только два не - равных натуральных делителя 2. Каждое натуральное число единственным образом , с точностью до порядка записи сомножителей , представляется в виде произведения степеней про - стых чисел 3. Наибольшим общим делителем двух целых чисел НОД(a,b) ( или (a,b) ) на - зывается наибольшее целое , на которое без остатка делится как a , так и b 4. Пусть a > b и d = (a,b) . Тогда существуют целые x и у , являющиеся реше - нием уравнения xa + yb = d Если d = 1 , то a и b называются взаимно про - стыми 5. Наибольший общий делитель двух чисел можно найти с помощью алгоритма Эвклида Для этого a делится с остатком на b , т е а = q 1 b + r 1 Далее вместо a и b , рассматриваем соответственно b и r 1 : b = q 2 r 1 + r 2 На следующем шаге роль b и r 1 , играют r 1 и r 2 : r 1 = q 3 r 2 + r 3 и т д Процесс заканчивается на не - котором шаге k+1 , для которого r k+1 = 0 Тогда НОД(a,b) = r k Рассмотрим пример Найти НОД (1547, 560) 1547 = 2 х 560 + 427 560 = 1 х 427 + 133 427 = 3 х 133 + 28 133 = 4 х 28 + 21 28 = 1 х 21 + 7 21 = 3 х 7 + 0 НОД (1547,560)=7 6. Для решения уравнения xa + yb = d можно использовать данные , полученные в каждом шаге алгоритма Эвклида , двигаясь снизу вверх , с помощью выра - жения остатка через другие элементы , используемые в соответствующем ша - ге Например , из r 2 = q 4 r 3 + r 4 следует r 4 = r 2 +q 4 r 3 В последнем равенстве r 3 можно заменить , исходя из соотношения r 1 = q 3 r 2 + r 3 , т е r 4 = r 2 – q 4 (q 3 r 2 – r 1 ) Поэтому r 4 = (1 – q 4 q 3 )r 2 + q 4 r 1 Таким образом , мы выразили r 4 в виде целочисленной комбинации остатков с меньшими номерами , кото - рые , в свою очередь , могут быть выражены аналогично Продвигаясь “ снизу вверх ”, в конце концов , мы выразим r 4 через исходные числа a и b Если Криптографическая система RSA 389 бы мы начали не с r 4 , а с r k , то получили бы r k = xa + yb = d Рассмотрим пример Решить 1547 х + 560y = 7 7 = 28 – 1 х 21 = 28 – 1 х (133 — 4 х 28) = 5 х 28 - 1 х 1 ЗЗ = = 5 х (427 - 3 х 133) — 1 х 13 З = 5 х 427 – 16 х (560 - 1 х 427)= = 21 х 427 - 16 х 560 = 21 х (1547 - 2 х 560) - 16 х 560 = = 21 х 547 - 58 х 560 Решение : x = 21, y = -58 7. Число a сравнимо с числом b по модулю n , если a – b делится на n За - пись данного утверждения имеет следующий вид : а = b(mod n) Наимень - шее неотрицательное число а , такое , что а = A(mod n) называется выче - том числа A по модулю n . Если (a,n) = 1 , то существует x , такое , что x = a -1 (mod n) Действительно , (a,n) = 1 = d = ax + ny , поэтому ax = 1(mod n) Такое число x называется обратным к а по модулю n и записывается в виде a -1 (mod n) 8. Пусть функция ϕ (n) , где n — натуральное число , равна количеству натураль - ных чисел , меньших n , для которых (а,n)=1 Такая функция называется функ - цией Эйлера Для чисел n вида n = i П p i ( p i — простое ) функция Эйлера опре - деляется как φ(n) = i П (p i – 1) 9. Теорема Эйлера Пусть (а,n) = 1 Тогда a φ(n) = 1(mod n) . Следствие Если ed = 1(mod φ(n)) и (a, n) = 1 , то (а e ) d = а(mod n) 10. Для большинства вычетов по модулю n = pq показатель степени в соотноше - нии a φ(n) = 1(mod n) может быть уменьшен , но в этом случае он зависит от a Наименьший показатель k(a) , для которого a k(a) = 1(mod n) , называется по - рядком числа a по модулю n и обозначается как оrd n (a) Для любого a значе - ние оrd n (a) является делителем значения функции Эйлера φ(n) . Алгоритм RSA Криптосистема RSA на каждом такте шифрования преобразует двоичный блок открытого текста m длины size(n) , рассматриваемый как целое число , в со - ответствии с формулой : c = m e (mod n) При этом n = pq , где p и q — случайные простые числа большой разрядно - сти , которые уничтожаются после формирования модуля и ключей Открытый ключ состоит из пары чисел e и n . Подключ e выбирается как достаточно боль - шое число из диапазона 1 < e < φ(n) , с условием : НОД(e, ϕ (n)) = 1 , где ϕ (n) — наименьшее общее кратное чисел p–1 и q–1 . Далее , решая в целых числах x , y уравнение xe + yφ(n) = 1 , полагается d = х , т е ed = 1( ϕ (n)) При этом для всех m выполняется соотношение m ed = m(n) , поэтому знание d позволяет расшиф - ровывать криптограммы |