Криптографические методы

В в е д е н и
е
1.Симметричные
криптосистемы
8 1.1. Классификация криптографических
методов
8 1.2. Системы
подстановок
9 1.3. Подстановка
Цезаря
11 1.5.Системы шифрования
Вижинера
14 1.6.
Гаммирование
16 1.7.
Шифрование с помощью аналитических
преобразований 17 1.8.
Криптосистемы на основе эллиптических
уравнений 18 2.1.Системы с открытым
ключом
20 2.2. Типы криптографических
услуг
22 2.3. Цифровые
представления
2.4. Эллиптическая криптография
кривой.
2.5.Электронные платы и код с
исправлением ошибок
3.Описание
алгоритма
27 3 .1.1. Описание
задачи
28 3.2.1 Описание
задачи
30 3.3.1.
Описание
задачи
3.3.2. Разложения
на
множетели
3.3.3. Программные разложения
фунции на множетели
3.3.5.Стандарты кода с исправлением
ошибок
ЗАКЛЮЧЕНИЕ.
Список
литературы.
40 Про­бле­ма за­щи­ты ин­фор­ма­ции пу­тем ее
пре­об­ра­зо­ва­ния, исключающего ее про­чте­ние по­сто­рон­ним
ли­цомвол­но­ва­ла че­ло­ве­че­ский ум с дав­них вре­мен. История криптографии -
ровесница истории человеческого языка. Более того, первоначально
письменностьсама по себе была криптографической системой, так как в древних
обществах ею владели только избранные. Священные книги Древ­него Егип­та,
Древ­ней Индиитому примеры. С широким распространением письменности
криптография стала формироваться как самостоятельная наука. Первые криптосистемы
встречаются уже вначале нашей эры. Так, Цезарь в своей переписке использовал уже
более менее систематический шифр, получивший его имя. Бурное раз­ви­тие
крип­то­гра­фи­че­ские сис­те­мы по­лу­чи­ли в го­ды пер­вой и вто­рой ми­ро­вых
войн. Начиная с послевоенного времени и понынешний день появление вычислительных
средств ускорило разработку и совершенствование
криптографическихметодов. Криптографические методы защиты информации в
автоматизированных системах могут применяться как для защиты
информации,обрабатываемой в ЭВМ или хранящейся в различного типа ЗУ, так и для
закрытия информации, передаваемой между различными элементами системы по линиям
связи.Криптографическое преобразование как метод предупреждения
несационированного доступа к информации имеет многовековую историю. В настоящее
время разработанобольшое колличество различных методов шифрования, созданы
теоретические и практические основы их применения. Подавляющие число этих
методов может бытьуспешно использовано и для закрытия информации. Под
шифрованием в данном едаваемых сообщений, хра­не­ние ин­фор­ма­ции
(до­ку­мен­тов, баз данных) на но­си­те­ляхв за­шиф­ро­ван­ном
ви­де. По­че­му про­бле­ма ис­поль­зо­ва­ния крип­то­гра­фи­че­ских
ме­то­дов в информационных системах (ИС) ста­ла в на­стоя­щий мо­мент осо­бо
ак­ту­аль­на? С од­ной сто­ро­ны, рас­ши­ри­лось ис­поль­зо­ва­ние
ком­пь­ю­тер­ных се­тей, в частности глобальной сети Интернет, по ко­то­рым
пе­ре­да­ют­ся боль­шиеобъ­е­мы ин­фор­ма­ции го­су­дар­ствен­но­го,
во­ен­но­го, ком­мер­че­ско­го и ча­ст­но­го ха­рак­те­ра, не до­пус­каю­ще­го
воз­мож­ность дос­ту­па к ней по­сто­рон­нихлиц. С дру­гой сто­ро­ны,
по­яв­ле­ние но­вых мощ­ных ком­пь­ю­те­ров, тех­но­ло­гий се­те­вых и
ней­рон­ных вы­чис­ле­нийсде­ла­ло воз­мож­ным дис­кре­ди­та­цию
криптографических сис­тем еще не­дав­но счи­тав­ших­ся прак­ти­че­ски
нераскрываемыми. to крип­то­гра­фию за­ни­ма­ет­ся по­ис­ком
и ис­сле­до­ва­ни­ем ма­те­ма­ти­че­ских ме­то­дов пре­об­ра­зо­ва­ния
ин­фор­ма­ции. -
ис­сле­до­ва­ние воз­мож­но­сти рас­шиф­ро­вы­ва­нияин­фор­ма­ции без зна­ния
клю­чей. 2. Криптосистемы с открытым
ключом. Основные направления использования криптографических методов -
передача конфиденциальнойинформации по каналам связи (например, электронная
почта), установление подлинности передаваемых сообщений,хранение информации
(документов,баз данных) на носителях в зашифрованном
виде. Криптографические методы защиты информации в автоматизированных
системах могут применяться какдля защиты информации, обрабатываемой в ЭВМ или
хранящейся в различного типа ЗУ, так и для закрытия информации, передаваемой
между различными элементамисистемы по линиям связи. Криптографическое
преобразование как метод предупреждения несационированного доступа к информации
имеет многовековуюисторию. В настоящее время разработано большое колличество
различных методов шифрования, созданы теоретические и практические основы их
применения.Подавляющие число этих методов может быть успешно использовано и для
закрытия информации. Итак, криптография дает возможность преобразовать
информацию таким образом, что ее прочтение (восстановление) возможно только при
знанииключа. , построенные на некотором - конечное
множество используемых для кодирования информации знаков. В качестве примеров алфавитов,
используемых в современных ИС можно привести следующие:
восьмеричный алфавит или шестнадцатеричный алфавит; , ко­то­рый но­сит
так­же на­зва­ние - обратный шифрованию процесс. На
основе ключа шифрованный текст преобразуется в исходный. ин­фор­ма­ция, не­об­хо­ди­мая для
бес­пре­пят­ст­вен­но­го шиф­ро­ва­ния и де­шиф­ро­ва­ния
тек­стов. пре­об­ра­зо­ва­нийот­кры­то­го тек­ста. Чле­ны
это­го се­мей­ст­ва ин­дек­си­ру­ют­ся, или обо­зна­ча­ют­ся сим­во­лом
- это на­бор воз­мож­ных зна­че­ний клю­ча. Обыч­но ключ
пред­став­ля­ет со­бойпо­сле­до­ва­тель­ный ряд букв ал­фа­ви­та.
симметричных криптосистемах системах с
открытым ключом ,
которые математически связаны друг с другом. Информацияшифруется с помощью
открытого ключа, который доступен всем желающим, а расшифровывается с помощью
закрытого ключа,известного только получателю сообщения. от­но­сят­сяк
про­цес­сам сис­те­мы об­ра­бот­ки ин­фор­ма­ции, со­дер­жа­ни­ем ко­то­рых
яв­ля­ет­ся со­став­ле­ние и рас­пре­де­ле­ние клю­чей ме­ж­ду
поль­зо­ва­те­ля­ми. называется
присоединяемое к тексту его криптографическое преобразование,которое позволяет
при получении текста другим пользователем проверить авторство и подлинность
сообщения. на­зы­ва­ет­ся ха­рак­те­ри­сти­ка
шиф­ра, оп­ре­де­ляю­щая его стой­кость к де­шиф­ро­ва­нию без зна­ния
клю­ча(т.е. крип­тоа­на­ли­зу). Имеется несколько показателей криптостойкости,
среди которых:
оп­ре­де­ля­ет­ся со­от­вет­ст­вую­щим ал­го­рит­мом и зна­че­ни­ем па­ра­мет­ра
.Эф­фек­тив­ность шиф­ро­ва­ния с це­лью за­щи­ты ин­фор­ма­ции
за­ви­сит от со­хра­не­ния тай­ны клю­ча и криптостойкости шифра.
Про­цесс крип­то­гра­фи­че­ско­го за­кры­тия данных мо­жет
осу­ще­ст­в­лять­ся как про­грамм­но, так и аппаратно. Ап­па­рат­ная
реа­ли­за­цияот­ли­ча­ет­ся су­ще­ст­вен­но боль­шей стои­мо­стью, од­на­ко ей
при­су­щи и пре­иму­ще­ст­ва: вы­со­кая про­из­во­ди­тель­ность, про­сто­та,
за­щи­щен­ностьи т.д. Про­грамм­ная реа­ли­за­ция бо­лее прак­тич­на,
до­пус­ка­ет из­вест­ную гиб­кость в ис­поль­зо­ва­нии. Для со­вре­мен­ных
крип­то­гра­фи­че­ских сис­тем за­щи­ты ин­фор­ма­ции сфор­му­ли­ро­ва­ны
сле­дую­щие об­ще­при­ня­тые тре­бо­ва­ния: чис­ло опе­ра­ций, не­об­хо­ди­мых для оп­ре­де­ле­ния
ис­поль­зо­ван­но­го клю­ча шиф­ро­ва­нияпо фраг­мен­ту шиф­ро­ван­но­го
сообщения и со­от­вет­ст­вую­ще­го ему от­кры­то­го тек­ста, долж­но быть не
мень­ше об­ще­го чис­ла воз­мож­ных клю­чей; чис­ло опе­ра­ций,
не­об­хо­ди­мых для рас­шиф­ро­вы­ва­ния ин­фор­ма­ции пу­тем
пе­ре­бо­равсе­воз­мож­ных ключей долж­но иметь стро­гую ниж­нюю оцен­ку и
вы­хо­дить за пре­де­лы воз­мож­но­стей со­вре­мен­ных ком­пь­ю­те­ров (с учетом
возможностииспользования сетевых вычислений); не­зна­чи­тель­ное из­ме­не­ние клю­ча долж­но
при­во­дить к су­ще­ст­вен­но­му из­ме­не­нию ви­даза­шиф­ро­ван­но­го сообщения
да­же при ис­поль­зо­ва­нии од­но­го и то­го же
клю­ча; до­пол­ни­тель­ные би­ты,
вво­ди­мые в сообщение в про­цес­се шиф­ро­ва­ния, должен быть пол­но­стьюи
на­деж­но скры­ты в шиф­ро­ван­ном тек­сте; не долж­но быть про­стых и лег­ко ус­та­нав­ли­вае­мых
зависимостью ме­ж­ду клю­ча­ми,по­сле­до­ва­тель­но ис­поль­зуе­мы­ми в
про­цес­се шиф­ро­ва­ния; ал­го­ритм должен до­пус­кать как про­грамм­ную,
так и ап­па­рат­ную реа­ли­за­цию, при этом из­ме­не­ниедлины к­лю­ча не долж­но
вес­ти к ка­че­ст­вен­но­му ухуд­ше­нию алгоритма шифрования. 1.1.Классификация крип­то­гра­фи­че­ских
ме­то­дов Все мно­го­об­ра­зие су­ще­ст­вую­щих
крип­то­гра­фи­че­ских ме­то­дов мож­но све­сти к сле­дующим клас­сам
пре­об­ра­зо­ва­ний: src="/images/education/referats/img/./12331003.gif" alt="Скругленный
прямоугольник: Перестановки" > src="/images/education/referats/img/./12331004.gif" alt="Скругленный
прямоугольник: Блочные шифры" > аи­бо­лее
про­стой вид пре­об­ра­зо­ва­ний, за­клю­чаю­щий­ся в за­ме­не сим­во­лов
ис­ход­но­го тек­стана другие (того же алфавита) по бо­лее или ме­нее слож­но­му
пра­ви­лу. Для обес­пе­че­ния вы­со­кой крип­то­стой­ко­сти тре­бу­ет­ся
ис­поль­зо­ва­ниеболь­ших клю­чей. не­слож­ный
ме­тод крип­то­гра­фи­че­ско­го пре­об­ра­зо­ва­ния. Ис­поль­зу­ет­ся как
пра­ви­ло в со­че­та­нии с дру­ги­миме­то­да­ми. тот ме­тод за­клю­ча­ет­ся в на­ло­же­нии на ис­ход­ный текст не­ко­то­рой
псев­до­слу­чай­ной по­сле­до­ва­тель­но­сти,ге­не­ри­руе­мой на ос­но­ве
клю­ча. со­бой по­сле­до­ва­тель­ность (с
воз­мож­ным по­вто­ре­ни­ем и че­ре­до­ва­ни­ем) ос­нов­ных ме­то­дов
пре­об­ра­зо­ва­ния,при­ме­няе­мую к блоку (части) шиф­руе­мого­ тек­ста.
Блочные шифры на прак­ти­ке встре­ча­ют­ся ча­ще, чем "чис­тые"
пре­об­ра­зо­ва­ния то­го или ино­го клас­сав си­лу их бо­лее вы­со­кой
крип­то­стой­ко­сти. Рос­сий­ский и аме­ри­кан­ский стан­дар­ты шиф­ро­ва­ния
ос­но­ва­ны имен­но на этом классе шифров. набора целых чисел (0,1,...,N-1)
называется его переупорядочение. Для тогочтобы показать, что целое i пере­мещено
из позиции i в позицию (1),..., !=1*2*...*(N-1)*N. Введем обозначение i Будем говорить,
что в этом смысле S. И, наоборот, автоморфизм S соответствует
пере­становке целых чисел (0,1,2,.., называетсяпоследовательность
автоморфизмов: T={T m Каждое
T могут быть определены независимо при i
равно (m m =2 число различных криптографических преобразований
равно1089!. Отсюда следует, что потенциально существует большое число
отображений исходного текста в шифрованный. k } были определены алгоритмами,
зависящими от относительнонебольшого числа параметров (ключей). , при котором буквы исходного текста t замещеныбуквами шифрованного
текста ; Набор всех подстановок называется
симметрической группой Z ) c
операцией произведения является группой,т.е. операцией, обладающей следующими
свойствами: Ассоциативность p p Существование нейтрального
элемента t<m, является нейтральным элементом
SYM(Z Существование
обратного p ‑1 Число возможных подстановок в
симметрической группе Z
Ключом : ¥ ,x n-
1 где неизменно при любом i,i=0,1,..., в противном случае
T . К наиболее существенным особенностям
подста­новки T -граммы (x n-1
,x ) является функциейтолько i-й
компоненты ключа p Подстановка Цезаря
является самым простым вариантом подстановки. Она относится к группе
: 0
подстановок £ k – идентичная подстановка, а обратной к C <m. Семейство подстановок Цезаря названо по имениримского
императора Гая Юлия Цезаря, который поручал Марку Туллию Цицерону составлять
послания с использованием 50-буквенного алфавита и подстановки
C Подстановка определяется по таблице замещения, содержащей
пары соответствующих букв "исходный текст – шифрованный текст". Для
C ) означает, что букваисходного текста (слева)
шифруется при помощи C
называется моноалфа­витнаяподстановка, преобразующая ‑грамму шифрованного текста (y k Например,
ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯ посредством подстановки C
А
Ы à У Л Г Ю à Ц О Ж Р ь л
Ъ Таблица 1.1: Применение
подстановки Цезвря. 1) шифрованный и соответ­ствующий исходный текст
или то определение ключа и дешифрование исходного текста
тривиальны. . Ониоснованы на подстановке не отдельных
символов, а 2-грамм (шифр Плэйфера) или (шифр Хилла). При более высокой криптостойкости
они значительно сложнее для реализации и требуют достаточно большого количества
ключевой информации. 1.4.Многоалфавитныесистемы. Системы одноразового
использования Слабая криптостойкость моноалфавитных подстановок
преодолевается с применением подстановок
многоалфавитных. , ...), содержащим не менее двух различных
подстановок. В начале рассмотрим многоалфавитные системыподстановок с нулевым
начальным смещением. Пусть { i<n} – независимыеслучайные переменные с одинаковым
распределением вероятностей, 1 преобразует исходный текст в шифрованный
текст при помощи подстановки Цезаря +X Для такой системы подстановки используют также термин
"одноразовая лента" и "одноразовый блокнот". Пространство ключей К
системыодноразовой подстановки является вектором рангов ( Зашифруем с его помощью текст "ШИФР_НЕРАСКРЫВАЕМ". Шифрование оформим в
таблицу: 24
Наложение белого шума в виде бесконечного ключа на
исходный текст меняет статистические характеристики языка источника.
Системыодноразового использования , так как не
содержатдостаточной информации для восстановления текста. Почему же эти
системы неприменимы для обеспечения секретности при обработке информации? Ответ
простой - они непрактичны, так кактребуют независимого выбора значения ключа для
каждой буквы исходного текста. Хотя такое требование может быть и не слишком
трудным при передаче по прямомукабелю Москва - Нью-Йорк, но для информационных
оно непосильно, поскольку там придется шифровать многие миллионы знаков.
Посмотрим, что получится, если ослабить требование шифровать каждую букву
исходного текста отдельным значением ключа. 1.5.Системышифрования Вижинера , и продлим ее до
бесконечной последовательности, повторяя цепочку. Таким образом, получим
k j
< и ключе пользователя 158 2 10 11 4 18 рабочий
ключ будет периодической последовательностью: Определение. : (x n-
1
r 2) i-й фрагмент
исходного текста
x y Вариант системы подстановок
Вижинера при 1 ) записывался набумажной ленте. Каждая буква исходного переводилась с
использованием в пятибитовый символ. К исходному тексту Бодо
добавлялся ключ (помодулю 2). Старинный телетайп фирмы AT&T со считывающим
устройством Вернама и оборудованием для шифрования, использовался корпусом связи
армии США. практика использовать слово или фразу в качестве ключа ) было легко запомнить.В ИС для обеспечения безопасности информации это
недопустимо. Для получения ключей должны использоваться программные или
аппаратные средства случайнойгенерации ключей. Разобьем исходный текст на блоки по 4
символа: и наложим на них ключ (используя таблицу Вижинера):
ЧРЭЗ ХРБЙ ПЭЭЩ ДМЕЖ КЭЩЦ ЧРОБ ЭБЮ_ ЧЕЖЦ ФЦЫН Можно
выдвинуть и обобщенную систему Вижинера. ЕЕ можно сформулировать не только при
помощи подстановки Цезаря. r p -1 0 n-1 p 0 ),
)), гдеиспользуется условие
. Следует признать, чтои многоалфавитные подстановки в
принципе доступны криптоаналитическому исследованию. Криптостойкость
многоалфавитных систем резко убывает суменьшением длины
ключа. Тем не менее такая система как шифр Вижинера допускает
несложную аппаратную или программную реализацию и при достаточно большой
длинеключа может быть использован в современных ИС. Гам­ми­ро­ва­ние
яв­ля­ет­ся так­же ши­ро­ко при­ме­няе­мым крип­то­гра­фи­че­ским
пре­об­ра­зо­ва­ни­ем. На са­мом де­ле гра­ни­ца ме­ж­дугам­ми­ро­ва­ни­ем и
ис­поль­зо­ва­ни­ем бес­ко­неч­ных клю­чей и шиф­ров Ви­жи­не­ра, о ко­то­рых
речь шла вы­ше, весь­ма ус­лов­ная. гам­ми­ро­ва­ни­ем за­клю­ча­ет­ся в ге­не­ра­ции гам­мы шиф­ра с по­мо­щью
дат­чи­ка псев­до­слу­чай­ных чи­сел ина­ло­же­нии по­лу­чен­ной гам­мы на
от­кры­тые дан­ные об­ра­ти­мым об­ра­зом (на­при­мер, ис­поль­зуя сло­же­ние по
мо­ду­лю 2). дан­ных сво­дит­ся к по­втор­ной
ге­не­ра­ции гам­мы шиф­ра при из­вест­ном клю­че и на­ло­же­нии та­кой гам­мына
за­шиф­ро­ван­ные дан­ные. По­лу­чен­ный за­шиф­ро­ван­ный текст
яв­ля­ет­ся дос­та­точ­но труд­ным для рас­кры­тия в том слу­чае, ес­ли гам­ма
шиф­ра не со­дер­жит по­вто­ряю­щих­сяби­то­вых по­сле­до­ва­тель­ностей. По
су­ти де­ла гам­ма шиф­ра долж­на из­ме­нять­ся слу­чай­ным об­ра­зом для
ка­ж­до­го шиф­руе­мо­го сло­ва. Фак­ти­че­ски же, ес­липе­ри­од гам­мы
пре­вы­ша­ет дли­ну все­го за­шиф­ро­ван­но­го тек­ста и не­из­вест­на ни­ка­кая
часть ис­ход­но­го тек­ста, то шифр мож­но рас­крыть толь­ко пря­мымпе­ре­бо­ром
(про­бой на ключ). Криптостойкость в этом слу­чае оп­ре­де­ля­ет­ся раз­ме­ром
клю­ча. Ме­тод гам­ми­ро­ва­ния ста­но­вит­ся бес­силь­ным, ес­ли
зло­умыш­лен­ни­ку ста­но­вит­ся из­вес­тен фраг­мент ис­ход­но­го тек­ста и
со­от­вет­ст­вую­щаяему шиф­ро­грам­ма. Про­стым вы­чи­та­ни­ем по мо­ду­лю
по­лу­ча­ет­ся от­ре­зок ПСП и по не­му вос­ста­нав­ли­ва­ет­ся вся
по­сле­до­ва­тель­ность. Зло­умыш­лен­ни­ки мо­жет сде­лать это на
ос­но­ведо­га­док о со­дер­жа­нии ис­ход­но­го тек­ста. Так, ес­ли
боль­шин­ст­во по­сы­лае­мых со­об­ще­ний на­чи­на­ет­ся со слов
"СОВ.СЕК­РЕТ­НО", то крип­тоа­на­лиз все­готек­ста зна­чи­тель­но
об­лег­ча­ет­ся. Это сле­ду­ет учи­ты­вать при соз­да­нии ре­аль­ных сис­тем
ин­фор­ма­ци­он­ной безо­пас­но­сти. Ниже рассматриваются наиболее
распространенные методы генерации гамм, которые могут быть использованы на
практике. Достаточно надежное
закрытие информации может быть обеспечено при использовании для шифрования
некоторыханалитических преобразований. Для этого нужно использовать методы
алгебры матриц , например , умножение матрицы на вектор по
правилу: использовать вкачестве ключа , а вместо компонента вектора
bj подставить символы текста , то компоненты вектора cj будут представлять
собой символы зашифрованного текста. Приведем
пример , взяв в качествеключа квадратную матрицу третьего порядка
Заменим буквы алфавита цифрами, соответствующими
порядковому номеру в алфавите. Тогда отрывку текста ВАТАЛА соответствует
последовательностьномеров 3,0,19,0,12,0. По принятому алгоритму шифрования
выполним необходимые действия: 14 8 3
3 99 14 8 3 0
96 3 2 1 19
28 3 2 1 0 24 Расшифрование осуществляетсяс использованием того
же правила умножения матрицы на вектор,только в качестве основы берется матрица,
обратная той, с помощью которой осуществляется закрытие, а в качестве вектора-
самножителя – соответствующиеколличество символов закрытого текста; тогда
значениями вектора-результата будут цифровые эквиваленты знаков открытого
текста. к даннойназывается матрица, полущающая из так называемой
присоединенной матрицы делением всех ее элементов на определитель данной
матрицы. В свою очередь присоединенной называется матрица, составленная из
алгеброических дополнений А ,к элементам даннойматрицы, которые вычисляются по
формуле: Aij = (-1)^i+j Dij , где Dij – определитель матрицы,
получаемый вычеркиванием i-й ее строки и j-гостолбца. Определителем же как
известно, называется алгеброическая сумма n! членов (для определения n-ого
порядка), составленнаяследующим образом: членами служат всевозможные
произведения n элементов матрицы, взятых по одному в каждой строке и в каждом
столбце, причемчлен суммы берется со знаком ''+'', если его индексы составлят
подставку, и со знаком ''-'' - в противоположном случае. Для матрицытретьего
порядка, например, определитель вычисляется по следующей
формуле: 1 -2
1 99 1*99-2*62+1*28
3 1 -4 6 28 1*99-
4*62+6*28 19 1 -2
1 96 1*96-2*60+1*24
0 1 -4 6
24 1*96-4*60+6*24 0 Таким образом, получили следующюю последовательность знаков
раскрытого текста:3,0,19,0,12,0, что соответствуетисходному тексту. Этот метод
шифрования является формальнным , что позволяет легко реализовать его
программными средствами. 1.8.Криптосистемы на основе
эллиптических уравнений - математический
объект, который может определен над любым полем (конечным,
действительным,рациональным или комплексным). В криптографии обычно используются
конечные поля. Эллиптическая кривая есть множество точек а также
бесконечно удаленная точка. Для точек на кривой довольно легко вводится операция
сложения, которая играет ту же роль, что иоперация умножения в криптосистемах
RSA и Эль-Гамаля. 2 Проблема
дискретного логарифма на эллиптической кривой состоит в следующем: дана точка G
на эллиптической кривой порядка r (количество точек накривой) и другая точка Y
на этой же кривой. Нужно найти единственную точку
Как бы ни бы­ли слож­ны и на­деж­ны крип­то­гра­фи­че­ские
сис­те­мы - их сла­бое ме­ст при прак­ти­че­ской реа­ли­за­ции - про­блема
. Для то­го, что­бы был воз­мо­жен об­мен
кон­фи­ден­ци­аль­ной ин­фор­ма­ци­ейме­ж­ду дву­мя субъ­ек­та­ми ИС, ключ
дол­жен быть сге­не­ри­ро­ван од­ним из них, а за­тем ка­ким-то об­ра­зом опять
же в кон­фи­ден­ци­аль­ном по­ряд­ке пе­ре­дандру­го­му. То есть , в об­щем
слу­чае для пе­ре­да­чи клю­ча опять же тре­бу­ет­ся ис­поль­зо­ва­ние ка­кой-то
крип­то­си­сте­мы. Для ре­ше­ния этой про­бле­мы на ос­но­ве
ре­зуль­та­тов, по­лу­чен­ных классической и со­вре­мен­ной ал­геб­рой, бы­ли
пред­ло­же­ны Суть их со­сто­ит в
том, что ка­ж­дым ад­ре­са­том ИС ге­не­ри­ру­ют­ся два клю­ча, свя­зан­ные
ме­ж­ду со­бой по оп­ре­де­лен­но­му пра­ви­лу. Одинключ объ­яв­ля­ет­ся
. От­кры­тый ключ пуб­ли­ку­ет­ся
и дос­ту­пен лю­бо­му, кто же­ла­ет по­слать со­об­ще­ниеад­ре­са­ту. Секретный
ключ сохраняется в тайне. Ис­ход­ный текст шиф­ру­ет­ся от­кры­тым клю­чом
адресата и пе­ре­да­ет­ся ему. За­шиф­ро­ван­ный текст в прин­ци­пе не мо­жет
быть рас­шиф­ро­вантем же от­кры­тым клю­чом. Де­шиф­ро­ва­ние со­об­ще­ние
воз­мож­но толь­ко с ис­поль­зо­ва­ни­ем за­кры­то­го клю­ча, ко­то­рый
из­вес­тен толь­ко са­мо­муад­ре­са­ту. Рис.2.1.Реализация процедуры шифрования с открытым
ключом. не­об­ра­ти­мые или од­но­сто­рон­ние
функ­ции от­но­си­тель­но про­сто вы­чис­лить зна­че­ние Мно­же­ст­во клас­сов не­об­ра­ти­мых функ­ций и
по­ро­ж­да­ет все раз­но­об­ра­зие сис­тем с от­кры­тым клю­чом. Од­на­ко не
вся­кая не­об­ра­ти­маяфунк­ция го­дит­ся для ис­поль­зо­ва­ния в ре­аль­ных ИС.
понимается не
теоретическаянеобратимость, а практическая невозможность вычислить обратное
значение используя современные вычислительные средства за обозримый интервал
времени. По­это­му что­бы га­ран­ти­ро­вать на­деж­ную за­щи­ту
ин­фор­ма­ции, к сис­те­мам с от­кры­тым клю­чом (СОК) предъ­яв­ля­ют­ся два
важ­ных и оче­вид­ныхтре­бо­ва­ния: 1. Пре­об­ра­зо­ва­ние ис­ход­но­го
тек­ста долж­но быть не­об­ра­ти­мым и ис­клю­чать его вос­ста­нов­ле­ние на
ос­но­ве от­кры­то­го клю­ча. 2. Оп­ре­де­ле­ние за­кры­то­го клю­ча на
ос­но­ве от­кры­то­го так­же долж­но быть не­воз­мож­ным на со­вре­мен­ном
тех­но­ло­ги­че­ском уров­не.При этом же­ла­тель­на точ­ная ниж­няя оцен­ка
сложности (ко­ли­че­ст­ва опе­ра­ций) рас­кры­тия шиф­ра. Ал­го­рит­мы
шиф­ро­ва­ния с от­кры­тым клю­чом по­лу­чи­ли ши­ро­кое рас­про­стра­не­ние в
со­вре­мен­ных ин­фор­ма­ци­он­ных сис­те­мах.Так, ал­го­ритм RSA стал ми­ро­вым
стан­дар­том де-фак­то для от­кры­тых сис­тем и ре­ко­мен­до­ван
МККТТ. Вообще же все предлагаемые сегодня криптосистемы с открытым ключом
опираются на один из следующих типов необратимых преобразований: 3. Вычисление корней алгебраических уравнений. Здесь
же сле­ду­ет от­ме­тить, что ал­го­рит­мы криптосистемы с открытым ключом (СОК)
мож­но ис­поль­зо­ватьв трех на­зна­че­ни­ях. сред­ст­ва для рас­пре­де­ле­ния клю­чей .
Ал­го­рит­мы СОК бо­лее тру­до­ем­ки, чем тра­ди­ци­он­ные крип­то­си­сте­мы.
По­это­му час­тона прак­ти­ке ра­цио­наль­но с по­мо­щью СОК рас­пре­де­лять
клю­чи, объ­ем ко­то­рых как ин­фор­ма­ции не­зна­чи­те­лен. А по­том с
по­мо­щью обыч­ных ал­го­рит­мовосу­ще­ст­в­лять об­мен боль­ши­ми
ин­фор­ма­ци­он­ны­ми по­то­ка­ми. . Об этом бу­дет рас­ска­за­но в главе «Электронная
подпись». Не­смот­ря на до­воль­но боль­шое чис­ло раз­лич­ных СОК,
наиболее популярна - криптосистема RSA, разработанная в 1977 году и
по­лу­чив­шаяна­зва­ние в честь ее соз­да­те­лей: Рона Ри­ве­ста Они вос­поль­зо­ва­лись тем фак­том, что на­хо­ж­де­ние
боль­ших про­стых чи­сел в вы­чис­ли­тель­ном от­но­ше­нии осу­ще­ст­в­ля­ет­ся
лег­ко,но раз­ло­же­ние на мно­жи­те­ли про­из­ве­де­ния двух та­ких чи­сел
прак­ти­че­ски не­вы­пол­ни­мо. До­ка­за­но (тео­ре­ма Ра­би­на), что
рас­кры­тие шиф­ра RSAэк­ви­ва­лент­но та­ко­му раз­ло­же­нию. По­это­му для
лю­бой дли­ны клю­ча мож­но дать ниж­нюю оцен­ку чис­ла опе­ра­ций для
рас­кры­тия шиф­ра, а с уче­том про­из­во­ди­тель­но­стисо­вре­мен­ных
ком­пь­ю­те­ров оце­нить и не­об­хо­ди­мое на это вре­мя. Воз­мож­ность
га­ран­ти­ро­ван­но оце­нить за­щи­щен­ность ал­го­рит­ма RSA ста­ла од­ной из
при­чин по­пу­ляр­но­сти этой СОК на фо­не де­сят­ковдру­гих схем. По­это­му
ал­го­ритм RSA ис­поль­зу­ет­ся в бан­ков­ских ком­пь­ю­тер­ных се­тях,
осо­бен­но для ра­бо­ты с уда­лен­ны­ми кли­ен­та­ми
(об­слу­жи­ва­ниекре­дит­ных кар­то­чек). , S-MIME,
S/WAN, STT и Сегодня
безопасные решения используют некоторую комбинацию из пяти
различныхкриптографических услуг. Эти услуги: – введением пути в оперативную транзакцию, пользователь
подтверждает, что этоименно он. Целостность
Данных - получатель транзакции способен демонстрировать нейтральному
третьему лицу, что требуемый передатчикдействительно посылал
транзакцию. Существуют два главных типа криптографии симметрично -
ключевые и шифрование с открытым ключом, которые основаны на комплексных
математическихалгоритмах и управляются ключами. Симметрично - ключевые схемы
криптографии требуют две стороны, которые хотят войти в доверие, чтобы разделить
общий, секретныйключ. Каждый пользователь должен доверять другому, чтобы не
обнародовать общий ключ третьему лицу. Эти системы эффективно зашифруют большое
колличество данных; однако, они излагают существенные ключевые проблемы
управления в сетях больше чем в маленьком числе пользователей, и обычно
используются вместе с шифрованиемс открытым ключом. В системах шифрования
отправитель сообщения шифрует его открытым ключом получателя.
Получательрасшифровывает это сообщение своим личным (секретным) ключом. Имея
открытый ключ получателя, каждый момент послать ему сообщение ,а прочитать его
можеттолько обладатель личного ключа. При этом получить личный ключ из открытого
с помощью каких-либо математических операций невозможно. В системах
цифровой лодписи подпись ''накладывается'' с использованием секретного ключа , а
снимается с помощьюоткрытого отправителя . Схемы Шифрования с открытым
ключом требуют, чтобы каждая сторона имела ключевую пару: секретный ключ,
который не должен быть раскрыт другомупользователю, и общий ключ, который может
быть доступным в общем каталоге. Эти два ключа связаны жесткой
одностороннейфункцией, так что в вычислительном отношении неосуществимо
определить секретный ключ от общего ключа. Секретный ключ часто сохраняется в
программномобеспечении с использованием пароля; однако, секретный ключ должен
идеально быть сохранен в безопасной аппаратнойлексеме, которая предотвращает
прямой доступ или вмешательство. Криптосистемы с ключом общего
пользования решают ключевые проблемы управления, связанные ссимметрично -
ключевым кодированием; однако, шифрование с открытым ключом предлагает
способность эффективно осуществить цифровые представления. Цифровые представления – это электронный эквивалент
традиционных рукописныхсигнатур. Рукописные сигнатуры обеспечивают службу
безопасности, потому что уникальность почерка личностей делает сигнатуры
интенсивными. В отличие от почерка индивидуума, электронная информация
проста для дублирования. Если электронные сигнатуры использовались таким же
образом какписьменные сигнатуры, защита легко может быть поставлена под
угрозу. Цифровые представления могут использоваться, чтобы использовать
три криптогафических услуги: идентификацию,неотказ, и целостность данных. код
с исправлением ошибок может использоваться, чтобы генерировать сильные
цифровыепредставления с маленьким количеством обработки энергии. После изобретения шифрования с открытым ключом, были
предложены многочисленные общее- ключевые системы засекречивания на ее
основе.Криптография с открытым ключом может применяться как для шифрования
сообщений , так и для аутентификации (такназываемая цифровая
подпись). Каждая из этих систем полагается на трудную математическую
проблему для ее защиты. Они являютсятруднообрабатываемыми, потому что годы
интенсивного изучения ведущими математиками и компьютерными учеными не сумели
создать эффективные алгоритмыдля их решения, так, чтобы практически, они
остались труднообрабатываемыми с текущей вычислительной технологией.
Требуется время , чтобы получить безопасный ключ с лучшим известным алгоритмом
для этой проблемы. Обще - ключевая системашифрования, основана на этой
проблеме. - математические конструкции, которые
изучились математиками начиная ссемнадцатого столетия. В 1985 Нейл Коблиц и
Виктор Миллер независимо предложили криптосистемы с ключом общегопользования,
использующие группу точек на эллиптической кривой, и эллиптическая криптография
кривой (код с исправлением ошибок) была рождена. Начиная с тоговремени,
многочисленные исследователи и разработчики потратили несколько лет, исследуя
силу кода с исправлением ошибок и улучшая методы для его выполнения.Сегодня
более быстрая криптосистема с ключом общего пользования предлагает практическую
и безопасную технологию для наиболее сдерживаемой среды. Код с
исправлением ошибок дает самую высокую силу в любой известной криптосистемы с
ключом общего пользования из-за трудности жесткой проблемы, накоторой это
основано. Эта большая трудность жесткой проблемы эллиптической кривой,
дискретной проблемы логарифма (ECDLP)означает что меньший размер ключа выдает
эквивалентные уровни защиты. Учитывая лучшие известные алгоритмы к целым числам
множителя и вычисляют эллиптическиелогарифмы кривой, размеры ключа являются
эквивалентной силой, основанной на MIPS годах, необходимых, чтобы восстановить
один ключ. Трудность проблемы и заканчивающихся размеров ключа
эквивалентной силы предоставляетнесколько прямых выгод к выполнению электроной
платы. латы и код с исправлением
ошибок – это маленькие, переносные, устройства
противодействиявмешательству, обеспечивающие пользователей с хранением памятью и
возможностью обработки. Из-за их уникальной формы, электроные платы предложены
дляиспользования в широком разнообразии приложений типа электронной торговли,
идентификации, и здравоохранения. Для многих из этих предложенных
приложений,требовались бы криптогафические услуги, предлагаемые цифровыми
представлениями. Чтобы быть практическим дляширокого применения электроные платы
также должны быть недорогими. Электроная плата поддается
криптогафическому выполнению по нескольким причинам. Плата содержитмного
особенностей защиты, которые допускают защиту чувствительных криптогафических
данных и обеспечивают безопасную среду обработки. Защита секретного
ключакритическая; чтобы обеспечивать криптогафические услуги, этот ключ никогда
не должен быть показан. Электроная плата защищает секретный ключ, и
многиерассматривают ее как идеальную криптогафическую лексему.
Осуществление шифрования с открытым ключом в электроном применении платы
излагает многочисленные проблемы. Электроные платы представляют комбинациюсвязей
выполнения, которые другие платформы не делают: сдерживаемая память и
ограниченные вычислительные возможности. Как упомянуто ранее, секретный
ключ в общее - ключевой паре должен сохраниться секретным. Для истинного
неотказа, секретный ключ должен бытьполностью недоступен всем другим сторонам. В
приложениях, использующих другие типы используемых в настоящее время
криптосистем с ключом общего пользования,платы индивидуализированы в безопасной
среде, чтобы выполнить это требование. Из-за сложности требуемого вычисления,
плата, неэффективена и обычно непрактичена. С кодом исправления ошибок,
время, необходимое генерировать ключевую пару настолько коротко, что даже
устройство ссамыми ограниченными вычислительными возможностями электроной платы
может генерировать ключевую пару, если хороший генератор случайных чисел
доступен.Это означает, что процесс персонализации платы можно придавать
обтекаемую форму для приложений, в которых неотказ является важным. При
подведении итогов, преимущества размера ключа кода с исправлением ошибок
предоставляют много выгод для электроных плат, и превосходящаядеятельность,
предлагаемая выполнением кода с исправлением ошибок делает приложения
выполнимыми в низкихконечных устройствах без специализированных аппаратных
средств. Прежде, чем системы
засекречивания и соответствующие математические проблемы могут быть обсуждены,
должна быть определена трудность проблемы.Алгоритм – это процесс, описывающий
проблему , которую нужно решить. При поиске математической проблемы,
чтобы базировать криптографическую систему,шифровальщики ищут такую проблему,
для которой самый быстрый алгоритм берет показательное время. Чем больше времени
требуется, чтобы вычислить лучшийалгоритм для этой проблемы, тем более
безопасной будет общее - ключевая система шифрования, основанная на той
проблеме. 1. Целочисленная проблема факторизации (IFP): RSA и
Rabin-Уильям. 3. Эллиптическая кривая дискретная проблема логарифма
(ECDLP). 3.1. Целочисленная проблема
факторизации (IFP):RSA и Рабин-Уильям Целочисленная проблема факторизации (IFP): находит p и q,
учитывая составное число n, которыйявляется произведением двух больших простых
чисел p и q. Обнаружение больших простых чисел - относительно
простая задача, а проблема разложения на множители, произведение двух таких
чиселрассматривается в вычислительном отношении труднообрабатываемым.
Базирующиеся на трудности этой проблемы Ривест, Чамир и Адлеман разработали RSA
общее -ключевую систему шифрования. В то время как целочисленная проблема
факторизации занимала внимание известных математиков подобно Фермату иГауссу
более чем столетия ,только в прошлых 20 годах был сделан прогресс в разрешении
этой проблемы. Имеются две главных причины для этого явления.Сначала,
изобретение RSA-системы шифрования в 1978 стимулировало много математиков к
изучению этой проблему. И быстродействующие ЭВМ стали доступнымидля выполнения и
испытания сложных алгоритмов. Фермат и Гаусс имели небольшой стимул для
изобретения алгоритма разложения на множители решета поля цифр, таккак этот
алгоритм более громоздкий ,чем испытательное деление с целью разложения на
множители целых чисел вручную. Имеются в
основном два типа специализированных и универсальных алгоритмов разложения на
множители.Специализированные алгоритмы разложения на множители пытаются
эксплуатировать специальные особенности номера n разлагаемого на множители.
Текущие временауниверсальных алгоритмов разложения на множители зависят только
от размера n. Один из наиболее мощных специализированных алгоритмов
разложения на множители -эллиптический метод разложения на множители кривой
(режим исправления ошибок), который был изобретен в 1985 Х.Ленстром младшим.
Текущее время этого методазависит от размера главных множителей n, и
следовательно алгоритм имеет тенденцию находить сначала маленькие множители. 21
июня 1995 Andreas Mueller (студент в Universitaet des Saarlandes, Германия)
объявил, что он нашел 44-десятичнуюцифру с 147-разрядным множителем 99-
десятичной цифрой с 329-разрядным составным целым числом,используя режим
исправления ошибок. Вычисление было выполнено на сети АРМ, и долговечность была
приблизительно 60 MIPS годы. Самый большой главныймножитель, найденный к
настоящему времени режимом исправления ошибок - 47-десятичная цифра с 157-
разряднымглавным множетелем 135-десятичной цифры 449-разрядный номер. До
развития RSA системы шифрования, лучший универсальныйалгоритм разложения на
множители был алгоритм цепной дроби , который имел числа множителя до 40
десятичных цифр (133 бита). Этот алгоритм был основан на идееотносительного
использования основы множителя штрихов и производства связанного с набором
линейных уравнений, чее решение в конечном счете вело к факторизации.Та же самая
идея лежит в основе лучших универсальных алгоритмов, используемых сегодня:
квадратичное решето (QS) и решето поля цифр (NFS). Оба эти алгоритмымогут быть
легко параллелизованы, чтобы разрешить разложение на множители на
распределительных сетях АРМ. Квадратичное решето было разработано
КарломПомерансом 1984. Первоначально, это применялось к числам множителя в 70-
десятичной цифре 233-разрядныйдиапазон. В 1994 это использовалось группой
исследователей во главе с А.Ленстром к множителю 129-десятичной цифры429-
разрядного номера проблемы RSA, который был изложен Мартином Гарднером 14 1977.
Факторизация была выполнена через 8 месяцев примерно на 1600 компьютерахво всем
мире. Долговечность для факторизации была оценена как 5000 MIPS
годы. Сначала было разработано в 1989 ,что Решето поля цифр работает лучше
всего на числах специальной формы.Алгоритм привык к множителю 155-десятичной
цифры 513-разрядного номера. Это было впоследствии расширено к универсальному
алгоритму факторизациию. Эксперименты доказали, что NFS являетсядействительно
превосходящим алгоритмом для целых чисел разложения на множители, имеющих по
крайней мере 120 десятичных цифр (400 битов). В 1996, группа воглаве с
А.Ленстром использовала NFS к множителю 130-десятичной цифры 432-разрядного
номера. Это - самый большой номер, разложенный на множители донастоящего
времени. Факторизация, как оценивали, брала меньше чем 15 % из 5000 MIPS годы,
которые требовались дляфакторизации 129-десятичной цифры проблемы RSA.
Разложение на множители 155 десятичной цифры 512-разрядного номера могло брать
меньше усилия в 5 раз. 512-разрядный модуль n обеспечиваеттолько крайнюю защиту
, когда используется в RSA системе шифрования. 3.2.Дискретнаяпроблема
логарифма (процессор передачи данных): Алгоритм цифрового представления Американского правительства
(системный агент каталога), Diffie-Hellman ключевая схема соглашения,ElGamal
кодирование и схемы сигнатуры, Schnorr схема сигнатуры, и Nyberg-Rueppel схема
сигнатуры. Если p - простое число, то Zp обозначает набор целых чисел 0,
1, 2,..., p - 1, где сложение иамплитудное искажение - выполняются с модулем.
Известно, что существует ненулевой элемент О Zp такой, что каждый ненулевой
элемент в Zp может бытьнаписан как мощность a, такой элемент называется
генератором Zp. Дискретная проблема логарифма (процессор передачи данных)
заключается в следующем:учитывая штрих p, генератор Zp, и ненулевой элемент О
Zp, находит уникальное целое число 0,1,2,..., p - 2, такое чтоb
принадлежит Базируясь на трудности этой проблемы, Диффи и Хеллман
предложили известную Diffie-Hellman ключевую схему соглашения в 1976. Стех пор
были предложены многочисленные другие криптогафические протоколы, чья защита
зависит от процессора передачи данных, включая: Американскийправительственный
алгоритм цифрового представления (системный агент каталога), ElGamal кодирование
и схемы сигнатуры, Schnorr схема сигнатуры, иNyberg-Rueppel схема сигнатуры.С
должным интересом процессор передачи данных экстенсивно изучился математиками
втечение прошлых 20 лет. Как с
целочисленной проблемой факторизации, имеются два типа алгоритмов для решения
дискретнойпроблемы логарифма. Специализированные алгоритмы пытаются
эксплуатировать специальные особенности главной с. Текущие времена универсальных
алгоритмовзависят только от размера с. Самые быстрые универсальные
алгоритмы, известные за решение процессора передачиданных ,основаны на методе
называемом конкрементом индекса. В этом методе создана база данных маленьких
штрихов и их соответствующих логарифмов, в последствии за которой
логарифмыпроизвольных полевых элементов могут быть легко получены. Это
напоминание о методах основы множителя для целочисленной факторизации. По этой
причине, еслиуточнение в алгоритмах для IFP или процессора передачи данных
найдено, то вскоре подобный улучшенный алгоритм может ожидаться, чтобы быть
решеным впользу другай проблемы. С методами разложения на множители, алгоритмы
конкремента индекса могут быть легко параллелизованы. В случае с
разложением на множители, лучшим текущим алгоритмом является процессор
передачиданных - решето поля цифр. Он имеет то же самое асимптотическое текущее
время , как соответствующий алгоритм для целочисленной факторизации. Это может
свободноинтерпретироваться с таким сообщением: что обнаружение логарифмов в
случае k-бита главного модуля p Выполнение дискретных алгоритмов
логарифма отстало от аналогичных усилий для разложения намножители целых чисел.
В 1990 Брайен ЛаМакчия и O.Эндрю использовали вариант метода конкремента
индекса, называемогометодом Комплексного целого числа вычисляемого дискретный
модуль логарифмов 191-разрядный штрих. Раньше Вебер, Дэнни и Зауер (студенты в
Universitaet desSaarlandes, Германия) вычислили дискретный модуль логарифмов
248-разрядный штрих, используя решето поля цифр. Проект,
инициализированный в Университете Waterloo (Канады) пытается улучшать эту
технологию, и в теории и впрактике с целью принятия модуля логарифмов штрих p
длины более 400 битов. Лучшие оценки состоят в том, что эта цель далека от
достижения на нескольколет. Можно сказать, что принятие модуля логарифмов 512-
разрядный штрих p останется труднообрабатываемым в течение следующих трех или
четырех лет. Насравнении, 512-разрядный RSA модуль будет вероятно разложен на
множители в пределах года или около этого. Тем не менее, для долгой
защиты, 1024-разрядный или больший moduli p должен использоваться в
дискретныхсистемах шифрования логарифма. 3.3.Эллиптическаякривая дискретная проблема логарифма
(ECDLP) Эллиптический аналог кривой системного агента
каталога (ECDSA), и эллиптических аналоговкривой Diffie-Hellman ключевой схемы
соглашения, ElGamal кодирования и схем сигнатуры, Schnorr схемы сигнатуры, и
Nyberg-Rueppel схемы сигнатуры. Должно быть подчеркнуто, что эти проблемы
являются труднообрабатываемыми, потому что годы интенсивного изучения
ведущимиматематиками и компьютерными учеными не сумели выдать эффективные
алгоритмы для их решения . Если q - главная мощность, то Fq обозначает
конечное поле, содержащее q элементы. Вприложениях q - обычно мощность 2 (2m)
или вспомогательное простое число (p). Эллиптическая кривая дискретная
проблема логарифма (ECDLP) заключается в следующем: учитываяэллиптическую кривую
E определенную по Fq, точка PОE (Fq) порядка n, и точки QОE (Fq), определяются
целым числом 0,l, 2,..., n - 1, так что Добротность = lP, при условии, что
такое целое число существует. Базируясь на трудности этой проблемы, Нейл
Коблиц и Виктор Миллер независимо друг от друга в1985 предложили использовать
группу точек на эллиптической кривой, определенной по конечному полю, для
осуществления различных дискретных систем шифрованиялогарифма. Один такой
криптогафический протокол, который стандартизируется аккредитованными
организациями стандартов - эллиптический аналог кривойсистемного агента
каталога, называемого ECDSA. Имеется только два главных способа
в методах для решения IFP: квадратичный алгоритм разложения на множители
решета(вместе с его предшественником, алгоритм разложения на множители цепной
дроби), и решето поля цифр. Последний алгоритм возводит в степень некоторую
сложнуюматематику (особенно алгебраическая теория номера), и только полностью
понят маленьким семейством теоретиков. До появления компьютеров, математики не
искалиалгоритмы для IFP, которые были эффективны вручную скорее , чем на больших
сетях компьютеров. Другой факт, который обычно пропускается - то многое
изработы, сделанной на процессоре передачи данных до 1985, также применяется к
ECDLP , так как ECDLP можетпросматриваться как похожий на процессор передачи
данных, но в различной алгебраической установке. Начиная с 1985, на ECDLP обратили значительное внимание
ведущие математики во всеммире. Алгоритм из-за Pohlig и Hellman приводит
определениеl к определениюl модуля каждый из главных множителей n.
Следовательно, чтобы достичь возможномаксимального уровня защиты, n должен быть
главным. Лучший алгоритм, известный до настоящего времени для ECDLP - Pollard
метод ро, где шаг имеетсяэллиптическое сложение кривой. В 1993 Р. Oorschot и
Майкл Винер показали, как Pollard метод ро может бытьпараллелизован так, чтобы,
если r процессоры использовались, то ожидаемое число с каждым процессором перед
одиночным дискретным логарифмом получено - ( ) /r.Наиболее существенно,
алгоритмы типа показателя степени не являются известными из-за
ECDLP ,что касается процессора передачи данных. Поэтой причине, ECDLP является
намного тяжелее или чем IFP или процессор передачи данных . В 1991
Menezes, Okamoto и Vanstone (MOV) показал, как ECDLP может быть сокращен
кпроцессу перпдачи данных в полях Fq, где могут применяться методы конкремента
индекса. Однако, этот MOV алгоритм приведения эффективен только для
оченьспециальной категории кривых ,известных как суперсингулярные кривые.
Имеется простое испытание, чтобы гарантировать, что эллиптическая кривая не
уязвима кэтому разложению. Суперсингулярные кривые специально запрещены во всех
стандартах эллиптических систем кривой типа ИИЭРА P1363, ANSI X9.62, и
ANSIX9.63. Другой жидкий класс эллиптических кривых - так называемые
аномальные кривые - кривые E определенныепо Fq, которые имеют точно q точки.
Разложение на этих кривых было обнаружено Semaev, Smart, и Satoh и Araki , и
обобщено Rьck. Имеется простоеиспытание над суперсингулярными кривыми для того
чтобы гарантировать, что эллиптическая кривая не уязвима; через это испытание,
эти кривые специальнозапрещены во всех стандартах эллиптических систем
кривой. Криптографический алгоритм RSA использует только
один тип вычислений – возведение в степень . Показатель степениопределяет
длительность выполнения процедуры вычеслений. Чтобы обеспечить требуемый
уровень надежности , показательстепени, являющийся секретным ключом , должен
быть достаточно большим , поэтому для вычислений требуется много
времени. Производительность вычислительных устройств с недавнего
времени принято оценивать в MIPS ( MillionInstruction Per Second): 1MIPS=10^6
опер./с. По отношению к
эллиптическим кривым производительность 1 MIPS соответствует примерно
4*10^4операций сложения кривой в секунду, поскольку длина ключа существенно
превышает длину еденицы данных. У стойчивостьалгоритмов криптографии принято
оценивать в MIPS годах . Иначе говоря , устойчивость – это число лет непрерывной
работы , необходимое вычислителю с производительностью 1 MIPS,чтобы взломать
данный шифр.
10^8 132
Таблица
3.1. Сравнение размеров ключей , необходимых для обеспечения
эквивалентныхуровней безопасности. Программные выполнение на
SPARC IPC исполняют 2,000 эллиптических сложений кривой в секунду. Тогда число
эллиптических сложенийкривой, которые могут быть выполнены 1 механизмом MIPS в
одном году: Например,
если 10,000 компьютеров каждый в 1,000 MIPS году доступн, то эллиптическая
кривая дискретного логарифма может быть вычисленачерез 96,000 лет. При установке режимов эллиптической системы
шифрования кривой, имеются три основных пункта, которыедолжны быть
сделаны: 2. Выбор представления для элементов
Fq. 1.
Два наиболее общего выбора в практических приложениях для основного конечного
поля - F2m и Fp (где p -вспомогательный штрих). ECDLP одинаково труден для
образцов, которые используют F2m и для образцов , которые используют Fp, и где
размеры 2m и p полейприблизительно равны. Не имелось никаких математических
открытий до настоящего времени, которые показывают, что ECDLP для эллиптических
кривых по F2m можетбыть проще или тяжелее чем ECDLP для эллиптических кривых по
Fp. 2. Если поле F2m выбрано как основное конечное поле, то
имеются много путей, в которых элементы F2m могут бытьпредставлены. Два наиболее
эффективных пути : оптимальное , нормальное представление основания и
полиномиальное представление основания. Так какэлементы в одном представлении
могут быть эффективно преобразованы к элементам в другом представлении,
используясоответствующую матрицу изменения основания, на ECDLP не воздействует
выбор представления. 4. MOV алгоритм приведения выдает алгоритм для
ECDLP, когда эллиптическая кривая суперсингулярна. В большенстве
случаевэллиптические кривые являются не-суперсингулярными. Кроме того, можно
легко проверить действительно ли MOVалгоритм приведения выполним для данной
эллиптической кривой – следовательно, этого разъедания легко избегают на
практике. Также, можно легко обнаружить является ли данная кривая аномальной.
Разъедания на аномальной кривой легко избегают. При выборене-суперсингулярной
эллиптической кривой, можно выбирать кривую наугад, или можно выбирать кривую
специальными свойствами, которые могут привести быстрее кэллиптической
арифметике кривой. Пример специальной категории кривых, который был предложен -
кривые Koblitz . ECDLP одинаково труден для образцов, которыеиспользуют
беспорядочно сгенерированные кривые, и для тех, которые используют кривые
Koblitz. Не имелось никаких математических открытий до настоящеговремени,
которые показывают, что ECDLP для беспорядочно сгенерированных эллиптических
кривых - проще илитяжелее чем ECDLP для кривых Koblitz. Международная стандартизация систем
засекречивания протоколов - важный процесс, который активно поддержан фирмой
Certicom.Стандартизация имеет три главных выгоды. Сначала, это учитывает
способность к взаимодействию среди аппаратных и программных систем от многих
различныхпродавцов. Во вторых, это возводит в степень критический обзор защиты
систем с криптографической точки зрения. Наконец, это разрешает вход в
конструкциюсистем шифрования от тех, кто должны осуществить их в широких
пределах среды. Эллиптические Кривые - это темаинтенсивного исследования в
математическом семействе много лет и теперь тщательно исследовались в
организациях стандартов в течение более чем трех лет.Это дало инженерам -
конструкторам высокий доверительный коэффициент в их защите, которая не могла
быть достигнута через поддержку только несколькоорганизаций. Извлечение
корня стандартов - критическая партия принятая любой системой
засекречивания.Стандартизация кода с исправлением ошибок поощрила ее принятие
организациями во всем мире. Кроме того, это продвинуло образование многих
шифровальщиков,разработчиков, и проектирует в математическом основании кода с
исправлением ошибок и в его важности в достижения практических, эффективных
общее - ключевыхоснованных систем. ИИЭР P1363 - код с
исправлением ошибок включен в проект ИИЭРА P1363 стандарт (Техническиеусловия
для Шифрования с открытым ключом), который включает кодирование, сигнатуру, и
ключевые механизмы соглашения. Эллиптические кривые могут бытьопределены по
модулю р. или по F2m, поле с 2m элементы, для соответствия со стандартом. ANSI
X9 - код с исправлением ошибок содержится в двух работах, созданных
Американским ИнститутомНациональных эталонов (ANSI) ASC X9 (Службы финансового
довольствия): ANSI X9.62, Эллиптический Алгоритм Цифрового представления Кривой
(ECDSA); и ANSIX9.63, Эллиптическое Соглашение ключа Кривой и Транспортные
Протоколы . ISO/IEC - проект документа ISO/IEC 14888: Цифровое
представление с приложением - Партия3: Свидетельство основанные механизмы
определяют эллиптические аналоги кривой некоторых Elgamal-подобных алгоритмов
сигнатуры. IETF - OAKLEY Ключевой Протокол Определения Internet,
проектирующего Оперативное соединение (IETF),описываетключевой протокол
реализации соглашения, который является вариантом Diffie-Hellman протокола. Это
учитывает ряд групп, которые нужно использовать,включая эллиптические кривые.
Документ делает определенное упоминание об эллиптических группах кривых по полям
F2155 и F2210. Форум ATM - Форум ATM Стадия Технического Комитета я
проект документа Техническихтребований Защиты ATM стремится обеспечивать
механизмы защиты для ATM сетей (Режимов асинхронной передачи). Службы
безопасности обеспечили,конфиденциальность, идентификацию, целостность данных, и
управление доступом. Код с исправлением ошибок - одна из поддержанных
систем. Большинство этих стандартов описывается в алгоритме независимым
способ так, чтобы любойпризнанный общее - ключевой алгоритм мог быть реализован.
Это позволит использовать алгоритмы, типа кода с исправлением ошибок, в средах,
где другиекриптосистемы с ключом общего пользования были бы
непрактичны. Выбор для
кон­крет­ных ИС дол­жен быть ос­но­ван на глу­бо­ком ана­ли­зе сла­бых и
силь­ных сто­рон тех или иных ме­то­дов за­щи­ты. Обос­но­ван­ныйвы­бор той или
иной сис­те­мы за­щи­ты в об­щем-то дол­жен опи­рать­ся на ка­кие-то
. К со­жа­ле­нию, до сих пор не
раз­ра­бо­та­ныпод­хо­дя­щие ме­то­ди­ки оцен­ки эф­фек­тив­но­сти
крип­то­гра­фи­че­ских сис­тем. мощ­ность
мно­же­ст­ва клю­чей(М). . Для ее численной оценки можно использовать также и
сложность раскрытия шифра путемперебора всех ключей. невоз­мож­ность рас­кры­тия
или ос­мыс­лен­ной мо­ди­фи­ка­ции ин­фор­ма­ции на ос­но­ве ана­ли­за ее
струк­ту­ры, ·
минимальная слож­ность реа­ли­за­ции (в ко­ли­че­ст­ве ма­шин­ных опе­ра­ций),
ее стои­мость, Же­ла­тель­но ко­неч­но ис­поль­зо­ва­ние не­ко­то­рых
ин­те­граль­ных по­ка­за­те­лей, учи­ты­ваю­щих ука­зан­ные фак­то­ры. Для
уче­та стои­мо­сти, тру­до­ем­ко­сти и объ­е­ма клю­че­вой ин­фор­ма­ции мож­но
ис­поль­зо­вать удель­ные по­ка­за­те­ли - от­но­ше­ниеука­зан­ных па­ра­мет­ров
к мощ­но­сти мно­же­ст­ва клю­чей шифра. Час­то бо­лее эф­фек­тив­ным при
вы­бо­ре и оцен­ке крип­то­гра­фи­че­ской сис­те­мы яв­ля­ет­ся
ис­поль­зо­ва­ние экс­перт­ныхоце­нок и ими­та­ци­он­ное
мо­де­ли­ро­ва­ние. В лю­бом слу­чае вы­бран­ный ком­плекс
крип­то­гра­фи­че­ских ме­то­дов дол­жен со­че­тать как удоб­ст­во, гиб­кость
иопе­ра­тив­ность ис­поль­зо­ва­ния, так и на­деж­ную за­щи­ту от
зло­умыш­лен­ни­ков цир­ку­ли­рую­щей в ИС ин­фор­ма­ции. Эллиптические
кривые – математические объекты, которые математики интенсивно изучают начиная с
17 – го века. Н.Коблиц и В. Миллернезависимо друг от друга предложили системы
системы криптозащиты с открытым ключом , использующие для шифрованиясвойства
аддитивной группы точек на эллиптической кривой. Эти работы легли в основу
криптографии на основе алгоритмаэллиптических кривых. Множество
исследователей и разработчиков испытывали алгоритм ЕСС на прочность. Сегодня
ЕСС предлагает болеекороткий и быстрый открытый ключ , обеспечивающий практичную
и безопасную технологию , применимую в различных областях . Применение
криптографии наоснове алгоритма ЕСС не требует дополнительной аппаратной
поддержки в виде криптографического сопроцессора . Всё это позволяет уже сейчас
применятькриптографические системы с открытым ключом и для создания недорогих
смарт-карт. В соответствии с законодательством США (соглашение
International Traffic in Arms Peguiation), криптографические устройства ,
включаяпрограммное обеспечение , относится к системам вооружения . Поэтому
при экспорте программной продукции , в которой используется криптография ,
требуетсяразрешение Госдепартамента. Фактически экспорт криптографической
продукции контролирует NSA (NationalSecurity Agency). правительство США очень
неохотно выдаёт подобные лицензии , поскольку это можетнанести ущерб
национальной безопасности США. Вместе с тем совсем недавно компании Newlett –
Packard выдано разрешение на экспорт еёкриптографического комплекса Ver Secure
в Великобританию , Германию, Францию , Данию и Австралию. Теперь Н Р может
эксплуатировать в этистраны системы , использующие 128- битный криптостандарт
Triple DES ,который считается абсолютно надёжным. 1. Герасименко В.А. Защита
информации в автоматизированных системах обработки данных кн.1.-М.:
Энергоатомиздат. -1994.-400с. 3. Диффи У.
Первые десять лет криптографии с открытым ключом //ТИИЭР, т. 76(1988)б Т5б
с.54-74. 4. Герасименко В.А., Скворцов А.А., Харитонов И.Е. Новые
направления применения криптографических методов защиты информации.- М.: Радио
исвязь.-1989.-360с. 6. Галатенко В.А. Информационная
безопасность. –М.: Финансы и статистика, 1997. –158 с. Методы криптоанализа классических шифров.–М.: Наука, 1995. –
208 с. //
Программирование РАН. –1994. -N 5 -С. 17—22. 11. Баричев
С. В. Криптография без секретов. –М.: Наука, 1998. –120 с. текста
в алфавите, расширенном некоторыми дополнительнымизнаками,
сначала – информация, доступная строго
определенному кругу лиц.