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

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.Дискретная проблема логарифма (процессор передачи данных): 3.2.1 Описание задачи

Алгоритм цифрового представления Американского правительства (системный  агент каталога), 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 принадлежит

 al (mod p). Целое число l называется дискретным логарифмом b к основе a.

Базируясь на трудности этой проблемы, Диффи и Хеллман  предложили известную Diffie-Hellman ключевую схему соглашения в 1976. С тех пор были предложены многочисленные другие криптогафические протоколы, чья защита зависит от процессора передачи данных, включая: Американский правительственный алгоритм цифрового представления (системный агент каталога), ElGamal кодирование и схемы сигнатуры, Schnorr схема сигнатуры, и Nyberg-Rueppel схема сигнатуры.С должным интересом  процессор передачи данных экстенсивно изучился математиками в течение прошлых 20 лет.

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

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

Самые быстрые универсальные алгоритмы, известные за решение процессора передачи данных ,основаны на методе называемом конкрементом индекса. В этом методе создана база данных маленьких штрихов и их соответствующих логарифмов,  в последствии за которой логарифмы произвольных полевых элементов могут быть легко получены. Это напоминание о методах основы множителя для целочисленной факторизации. По этой причине, если уточнение в алгоритмах для IFP или процессора передачи данных найдено, то вскоре подобный улучшенный алгоритм может ожидаться, чтобы быть решеным в пользу другай проблемы. С методами разложения на множители, алгоритмы конкремента индекса могут быть легко параллелизованы.

В случае с разложением на множители, лучшим текущим алгоритмом является процессор передачи данных - решето поля цифр. Он имеет то же самое асимптотическое текущее время , как соответствующий алгоритм для целочисленной факторизации. Это может свободно интерпретироваться с  таким сообщением: что обнаружение логарифмов в случае 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. Стандартизация имеет три главных выгоды. Сначала, это учитывает способность к

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: