Введение в системы БД (542480), страница 159
Текст из файла (страница 159)
Одним из таких алгоритмов является Рата Епсгурйоп Бгапбагб (РЕЯ), разработанный фирмой!ВМ и принятый в 1977 году в качестве Федерального стандарта шифрования данных США [16.18[. Согласно этому стандарту открытый текст делится на блоки по 64 бит и каждый блок шифруется с помощью 64-битного ключа (в действительности этот ключ состоит из 56 бит данных и 8 бит четности, так что существует не 2, а только 2 возможных клюы 56 чей). Сначала блок шифруется путем перестановки, затем переставленные данные блока подвергаются обработке посредством подстановки, включающей 16 последовательных сложных шагов, после этого к данным еше раз применяется обратная начальной процедура перестановки, которая и приводит к получению окончательного результа~а шифрования.
Подстановка на з-м шаге контролируется не самим исходным ключом шифрования К, а ключом Кз, который вычисляется на основе значений К и [, Более подробно этот материал излагается в [16.18[. Стандартом шифрования данных предусматривается, что алгоритм расшифровки идентичен алгоритму шифрования, но ключи КГ применяются в обратном порядке.
Шифрование на основе открытого ключа В течение многих лет существовало предположение, что стандарт шифрования данных РЕБ не является абсолютно безопасным. Действительно, после создания систем с большим количеством высокопроизводительных параллельных процессоров стало ясно, что этот стандарт может быть взломан путем применения одной лишь "грубой силы", без использования каких-либо сложных методов расшифровки. Многие специалисты считают, что по сравнению с самыми современными методами, построенными на основе использования открытого ключа, стандарт шифрования данных РЕК и подобные ему традиционные методы выглядят технологически устаревшими.
В методах с использованием открытого ключа внешнему миру доступны как алгоритм шифрования, так и ключ шифрования, поэтому любой желающий может преобразовать открытый текст в зашифрованный. Однако соответствующий ключ расшифровки хранится в секрете (в методах открытого ключа используются два ключа: один — для шифрования, другой — для расшифровки). Более того, ключ расшифровки не может быть просто выведен из ключа шифрования, поэтому лицо, выполнившее шифрование исходного текста, не сможет его расшифровать без специального разрешения.
Первоначальная идея использования такого метода принадлежит Диффи (Р1(бе) и Хельману (Не!!тап) [16.7], однако здесь для демонстрации подобных методов будет описан наиболее известный подход, разработанный Райвестом (%чек!), Шамиром (БЬаш!г) и Адлеманом (Аг!!етап) [!6.15[, В основу этого подхода, названного ЛБА-схемой (по первым буквам фамилий его авторов), положены следующие два факта. 1. Существует быстрый алгоритм определения, является ли данное число простым.
2. Не существует быстрого алгоритма разложения данного составного числа (т.е. числа, которое не является простым) на простые множители. В [!6.10[ приведен пример, в котором для определения, является ли число из 130 цифр простым, потребовалось 7 минут вычислений на некотором компьютере, тогда как для поиска (на том же компьютере) двух простых множителей числа, получаемого Глава 16. Защигпа данньп 623 умножением двух простых чисел, состоящих из 63 цифр, потребуется около 40 квадричьонов лет (! квадрильон = ! 000 000 000 000 000)4.
зчБА-схема предусматривает выполнение приведенной ниже последовательности действий. !. Выберите два произвольных и разных больших простых числа р и а, а затем вычислите их произведение г = р * д. 2. Выберите произвольное большое целое число е, которое является взаимно простым (т.е. не имеет общих множителей) по отношению к произведению (р-1] * (з2-1). Это целое число е и будет служить ключом шифрования. Замечание. Выбрать число е достаточно просто, например для него подойдет любое простое число, которое больше чисел р и а. 3.
Выберите в качестве ключа расшифровки число б, которое является "обратным относительно умножения" на е по модулю (р-1) ' (а-1), т.е, такое число, для которого выполняется следующее соотношение. с! ь е = 1 нобц1о (р - 1) ' (а - 1) Алгоритм вычисления с( для заданных чисел е, р и а достаточно прост и полностью приведена [!6.!5). 4. При этом огласке могут быть преданы числа г и е, но не 4 5.
Для шифрования части открытого текста Р (который для простоты рассматривается как целое число, меньшее г) заменим его зашифрованным текстом согласно следующей формуле. С = )я аюдц1о г 6. Для расшифровки части зашифрованного текста С замените его открытым текстом Р, определяемым согласно следующей формуле. Р С' нобц1о г В [16,15] доказывается работоспособность этой схемы, т.е. возможность расшифровки текста С с использованием числа с( для восстановления исходного открытого текста Р. Однако, как упоминалось ранее, вычисление с! для известных чисел г и е (а не р и а) практически неосуществимо. Поэтому любой пользователь может зашифровать открытый текст, но расшифровать зашифрованный текст смогут только санкционированные пользователи (т.е.
те, кто знают число с!). Для иллюстрации работы этого метода рассмотрим приведенный ниже простой пример, в котором по очевидным причинам используются очень небольшие целые числа, г Несмотря иа это некоторые сомнения существуют и в отношении Я5А-схемы. Работа (16.10) была опубликована в 1977 году, а в 1990 году Арьеиу Денстра (Ас!еп Сепг!го) и Мару Маиассе (Маей Маяаше) удалось успешно разложить на простые множители число из 155 цифр (1622). Они оценили, что выполненные вычиспения, в козпорых участвовала лзысяча компьютеров, эквивалентны расчету на одном компьютере со скоростью 1 млн инструкций в секунду в течение 273 лепи Данное чист из 155 цифр было девятым числом Ферма: 2 ~~41 (обратите виимазы ние, что 512 = 2"). Слз.
также работу )16.12), в которой сообщается о совершенно другом — и успешном — подходе к расшифровке алгоритма йбА. 624 Часть К Дополнительные аспекты Пример. Пусть р = 3, а = 5; тогда г = 15, а произведение (р-1) ' (а-1) = 8. Пусть е = ! 1 (простое число, большее р и а). Вычислим с) согласно следующей формуле. б ' 11 = 1 вобц1о 8 В результате получим а' = 3. Теперь допустим, что открытый текст Р состоит из целого числа 13; тогда зашифрованный текст С будет иметь следующий вид. С = )к вобц1о г = 13п вог)ц1о 15 = 1 792 180 394 037 вобц1о 15 = 7 Теперь исходный открытый текст Р может быть получен с помощью обратной процедуры.
Р С' аюбп1о г = 7' вобц1о 15 ~ 343 вобц1о 15 = 13 ° Поскольку числа е и а взаимно обратны, в методах шифрования на основе открытого ключа также можно подписывать отсылаемые сообщения, что позволит получателю иметь уверенность в том, что данное сообщение было получено именно от того лица, которое объявлено его отправителем (т.е. такая подпись не может быть подделана). Допустим, что пользователи А и В обшаются друг с другом с помощью метода шифрования на основе открытого ключа.
Пусть они предали гласности по одному алгоритму шифрования (с включением в каждый из них соответствующего ключа шифрования), но хранят в секрете друг от друга алгоритм и ключ расшифровки. Пусть алгоритмы шифрования сообщений ЕСА и ЕСВ используются для шифрования сообщений, посылаемых пользователям А и В соответственно, а отвечающими им алгоритмами расшифровки являются алгоритмы 0СА и 0СВ. Следует отметить, что алгоритмы шифрования н расшифровки ЕСА и 0СА, как и алгоритмы ЕСВ и 0СВ, являются взаимно обратными.
Теперь предположим, что пользователь А хочет отослать часть открытого текста Р пользователю В. Вместо вычисления результата ЕСВ(Р) и отправки его пользователю В пользователь А сначала применяет для открытого текста Р алгоритм расшифровки РСА, а затем зашифровывает полученный результат н в зашифрованном виде С передает его пользователю В. С = ЕСВ ( 0СА ( Р ) ) После получения зашифрованного текста С пользователь В применяет сначала алгоритм расшифровки 0СВ, а затем — алгоритм шифрования ЕСА, что позволяет ему в результате получить открытый текст Р.
ЕСА ( 0СВ ( С ) ) = ЕСА ( 0СЕ ( ЕСЕ ( 0СА ( Р ) ) ) ) = ЕСА ( 0СА ( Р ) ] // поскольку 0СВ и ЕСВ взаимно исключаются и // поскольку ЕСА и 0СА взаимно нсклвчавтся Глава 16. Защита данных 625 Таким образом, пользователь Б знает, что полученное им сообщение действительно пришло от пользователя А, поскольку алгоритм шифрования ЕСА приведет к получению результата Р, только если в процессе шифрования применялся алгоритм расшифровки ОСА. Причем никто, даже пользователь В, не сможет подделать подпись пользователя А. 16.6.
Средства языка ЯОЕ В действующем стандарте языка Б()Ь предусматривается поддержка только избирательного метода управления доступом. Она строится на основе двух более или менее независимых функций языка ЯС)Ь. Первая нз них является механизмом представлений, который (как говорилось выше, в главе 8) может быть использован для сокрытия важных данных от несанкционированных пользователей. Вторая функция называется подсистемой полномочий и позволяет одним пользователям, обладающим определенными правами доступа, избирательно и динамично предоставлять эти полномочия другим пользователям, а также отменять предоставленные ими полномочия в случае необходимости.
Ниже эти функции языка ЯС(Ь обсуждаются более подробно. Представления и защита данных Продемонстрируем использование представлений для организации зашиты данных с помощью записи на языке Я )Ь примеров 2-4 из раздела ( б.2. 2. СВЕАТЕ т'1ЕН ЬЯ АЯ ЯЕЬЕСТ Б.Я((, Я.ЯНАМЕ, Я.ЯТАТОБ, Б.С1ТУ РВОМ Я ИНЕВЕ Я, С1ТТ = 'Ьопбоп' ( Это представление определяет данные, по отношению к которым будут предоставлены некоторые привилегии. Само же предоставление привилегий осуществляется с помощью операторов ОВАМТ. ОВАНТ БЕЬЕСТ, ОРОАТЕ ( ЯНАЕВ, БТАТОЯ ), ОЕЬЕТЕ ОН ЬЯ ТО Рап, МЬвйа ) Здесь следует отметить, что, поскольку привилегии задаются с помощью оператора ОВАНТ, а не с помощью гипотетического оператора СВЕАТЕ АОТНОВ1ТУ, привилегиям в языке БОЬ имена не присваиваюглся.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
