Криптография

процессор передачи данных - решето поля цифр. Он имеет то же самое

асимптотическое текущее время , как соответствующий алгоритм для

целочисленной факторизации. Это может свободно интерпретироваться с таким

сообщением: что обнаружение логарифмов в случае k-бита главного модуля p

стольже трудно как разложение на множители k-бит составного число n.

Выполнение дискретных алгоритмов логарифма отстало от аналогичных

усилий для разложения на множители целых чисел. В 1990 Брайен ЛаМакчия и

O.Эндрю использовали вариант метода конкремента индекса, называемого

методом Комплексного целого числа вычисляемого дискретный модуль логарифмов

191-разрядный штрих. Раньше Вебер, Дэнни и Зауер (студенты в Universitaet

des Saarlandes, Германия) вычислили дискретный модуль логарифмов 248-

разрядный штрих, используя решето поля цифр.

Проект, инициализированный в Университете Waterloo (Канады)

пытается улучшать эту технологию, и в теории и в практике с целью принятия

модуля логарифмов штрих p длины более 400 битов. Лучшие оценки состоят в

том, что эта цель далека от достижения на несколько лет. Можно сказать, что

принятие модуля логарифмов 512-разрядный штрих p останется

труднообрабатываемым в течение следующих трех или четырех лет. На

сравнении, 512-разрядный RSA модуль будет вероятно разложен на множители в

пределах года или около этого.

Тем не менее, для долгой защиты, 1024-разрядный или больший moduli p

должен использоваться в дискретных системах шифрования логарифма.

3.3.Эллиптическая кривая дискретная проблема логарифма (ECDLP)

3.3.1. Описание задачи

Эллиптический аналог кривой системного агента каталога (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 может просматриваться как похожий на

процессор передачи данных, но в различной алгебраической установке.

3.3.2. Разложения на множетели

Начиная с 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, и ANSI X9.63.

Другой жидкий класс эллиптических кривых - так называемые аномальные

кривые - кривые E определенные по Fq, которые имеют точно q точки.

Разложение на этих кривых было обнаружено Semaev, Smart, и Satoh и Araki ,

и обобщено Rьck. Имеется простое испытание над суперсингулярными кривыми

для того чтобы гарантировать, что эллиптическая кривая не уязвима; через

это испытание, эти кривые специально запрещены во всех стандартах

эллиптических систем кривой.

3.3.3. Программные разложения фунции на множетели

Криптографический алгоритм RSA использует только один тип

вычислений – возведение в степень . Показатель степени определяет

длительность выполнения процедуры вычеслений. Чтобы обеспечить требуемый

уровень надежности , показатель степени, являющийся секретным ключом ,

должен быть достаточно большим , поэтому для вычислений требуется много

времени.

Производительность вычислительных устройств с недавнего

времени принято оценивать в MIPS ( Million Instruction Per Second):

1MIPS=10^6 опер./с.

MIPS года – такая сложность алгоритма, которая требует годовой

работы компьютера чтобы его вскрыть.

По отношению к эллиптическим кривым производительность 1 MIPS

соответствует примерно 4*10^4 операций сложения кривой в секунду,

поскольку длина ключа существенно превышает длину еденицы данных. У

стойчивость алгоритмов криптографии принято оценивать в MIPS годах . Иначе

говоря , устойчивость – это число лет непрерывной работы , необходимое

вычислителю с производительностью 1 MIPS ,чтобы взломать данный шифр.

|Время на взлом |Размер ключа |Размер ключа |Отношение длин |

|MIPS лет |RSA/DSA |ЕСС |ключей RSA/DSA |

|10^4 |512 |106 |5:1 |

|10^8 |768 |132 |6:1 |

|10^11 |1.024 |160 |7:1 |

|10^20 |2.048 |210 |10:1 |

|10^78 |21 |600 |35:1 |

Таблица 3.1. Сравнение размеров ключей , необходимых для обеспечения

эквивалентных уровней безопасности.

Программные выполнение на SPARC IPC исполняют 2,000 эллиптических

сложений кривой в секунду. Тогда число эллиптических сложений кривой,

которые могут быть выполнены 1 механизмом MIPS в одном году:

(4 x 104) • (60 x 60 x 24 x 365) " 240.

Например, если 10,000 компьютеров каждый в 1,000 MIPS году доступн, то

эллиптическая кривая дискретного логарифма может быть вычислена через

96,000 лет.

3.3.4 Выбор основного поля Fq и эллиптической кривой E

При установке режимов эллиптической системы шифрования кривой, имеются

три основных пункта, которые должны быть сделаны:

1. Выбор основного конечного поля Fq.

2. Выбор представления для элементов Fq.

3. Выбор эллиптической кривой E по 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.

3.3.5.Стандарты кода с исправлением ошибок

Международная стандартизация систем засекречивания протоколов - важный

процесс, который активно поддержан фирмой Certicom. Стандартизация имеет

три главных выгоды. Сначала, это учитывает способность к взаимодействию

среди аппаратных и программных систем от многих различных продавцов. Во

вторых, это возводит в степень критический обзор защиты систем с

криптографической точки зрения. Наконец, это разрешает вход в конструкцию

систем шифрования от тех, кто должны осуществить их в широких пределах

среды. Эллиптические Кривые - это тема интенсивного исследования в

математическом семействе много лет и теперь тщательно исследовались в

организациях стандартов в течение более чем трех лет. Это дало инженерам -

конструкторам высокий доверительный коэффициент в их защите, которая не

могла быть достигнута через поддержку только несколько организаций.

Извлечение корня стандартов - критическая партия принятая любой

системой засекречивания. Стандартизация кода с исправлением ошибок поощрила

ее принятие организациями во всем мире. Кроме того, это продвинуло

образование многих шифровальщиков, разработчиков, и проектирует в

математическом основании кода с исправлением ошибок и в его важности в

достижения практических, эффективных общее - ключевых основанных систем.

Следующие инициативы стандартов кода с исправлением ошибок - в

настоящее время на ходу:

ИИЭР P1363 - код с исправлением ошибок включен в проект ИИЭРА P1363

стандарт (Технические условия для Шифрования с открытым ключом), который

включает кодирование, сигнатуру, и ключевые механизмы соглашения.

Эллиптические кривые могут быть определены по модулю р. или по F2m, поле с

2m элементы, для соответствия со стандартом. ANSI X9 - код с исправлением

ошибок содержится в двух работах, созданных Американским Институтом

Национальных эталонов (ANSI) ASC X9 (Службы финансового довольствия): ANSI

X9.62, Эллиптический Алгоритм Цифрового представления Кривой (ECDSA); и

ANSI X9.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 (National Security Agency).

правительство США очень неохотно выдаёт подобные лицензии , поскольку это

может нанести ущерб национальной безопасности США. Вместе с тем совсем

недавно компании Newlett –Packard выдано разрешение на экспорт её

криптографического комплекса Ver Secure в Великобританию , Германию,

Францию , Данию и Австралию. Теперь Н Р может эксплуатировать в эти страны

системы , использующие 128- битный криптостандарт Triple DES ,который

считается абсолютно надёжным.

Список литературы.

1. Герасименко В.А. Защита информации в автоматизированных системах

обработки данных кн. 1.-М.: Энергоатомиздат. -1994.-400с.

2. Вербицкий О.В.Вступление к криптологии.- Львов.: Издательство науково-

техничной литературы.-1998.-300с.

3. Диффи У. Первые десять лет криптографии с открытым ключом //ТИИЭР, т.

76(1988)б Т5б с. 54-74.

4. Герасименко В.А., Скворцов А.А., Харитонов И.Е. Новые направления

применения криптографических методов защиты информации.- М.: Радио и

связь.-1989.-360с.

5. Миллер В. Использования эллиптических кривых в криптографии .: -1986.-

417-426с.

6. Галатенко В.А. Информационная безопасность. –М.: Финансы и статистика,

1997. –158 с.

7. Грегори С. Смит. Программы шифрования данных // Мир ПК –1997. -№3. -С.58

- 68.

8. Ростовцев А. Г., Михайлова Н. В. Методы криптоанализа классических

шифров. –М.: Наука, 1995. –208 с.

9. Терехов А. Н., Тискин А. В. // Программирование РАН. –1994. -N 5 -С.

17—22.

10. Криптология – наука о тайнописи // Компьютерное обозрение. –1999. -№3.

–С. 10 – 17.

11. Баричев С. В. Криптография без секретов. –М.: Наука, 1998. –120 с.

-----------------------

текста в алфавите, расширенном некоторыми дополнительными знаками, сначала

Конфиденциальность – информация, доступная строго определенному кругу

лиц.

-----------------------

Открытый ключ

Закрытый ключ

Адресат

Отправитель

шифрованный

текст

исходный

текст

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

КЛЮЧ

Гаммирование

Симметричные

криптосистемы

Блочные шифры

Перестановки

исходный

текст

шифрованный

текст

исходный

текст

Система

с открытым ключом

Система

с открытым ключом

Подстановки

Страницы: 1, 2, 3, 4