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

--PAGE_BREAK-- 1.Симметричные криптосистемы 1.1. Классификация крип­то­гра­фи­че­ских ме­то­дов


Все мно­го­об­ра­зие су­ще­ст­вую­щих крип­то­гра­фи­че­ских ме­то­дов мож­но све­сти к сле­дующим клас­сам пре­об­ра­зо­ва­ний:
<img width=«477» height=«157» src=«ref-1_735501463-3095.coolpic» v:shapes="_x0000_s1041 _x0000_s1040 _x0000_s1039">



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

<img width=«174» height=«57» src=«ref-1_735504558-1052.coolpic» alt=«Скругленный прямоугольник: Перестановки» v:shapes="_x0000_s1043"> <img width=«174» height=«57» src=«ref-1_735505610-1057.coolpic» alt=«Скругленный прямоугольник: Блочные шифры» v:shapes="_x0000_s1042">



Рис.1.1.Классы преобразований симметричных криптосистем.


Многоалфавитная подстановка — наи­бо­лее про­стой вид пре­об­ра­зо­ва­ний, за­клю­чаю­щий­ся в за­ме­не сим­во­лов ис­ход­но­го тек­ста на другие (того же алфавита) по бо­лее или ме­нее слож­но­му пра­ви­лу. Для обес­пе­че­ния вы­со­кой крип­то­стой­ко­сти тре­бу­ет­ся ис­поль­зо­ва­ние боль­ших клю­чей.

Пе­ре­ста­нов­ки -не­слож­ный ме­тод крип­то­гра­фи­че­ско­го пре­об­ра­зо­ва­ния. Ис­поль­зу­ет­ся как пра­ви­ло в со­че­та­нии с дру­ги­ми ме­то­да­ми.

Гам­ми­ро­ва­ние — этот ме­тод за­клю­ча­ет­ся в на­ло­же­нии на ис­ход­ный текст не­ко­то­рой псев­до­слу­чай­ной по­сле­до­ва­тель­но­сти, ге­не­ри­руе­мой на ос­но­ве клю­ча. 

Блочные шифры  со­бой по­сле­до­ва­тель­ность (с воз­мож­ным по­вто­ре­ни­ем и че­ре­до­ва­ни­ем) ос­нов­ных ме­то­дов пре­об­ра­зо­ва­ния, при­ме­няе­мую к блоку (части) шиф­руе­мого­ тек­ста. Блочные шифры на прак­ти­ке встре­ча­ют­ся ча­ще, чем “чис­тые” пре­об­ра­зо­ва­ния то­го или ино­го клас­са в си­лу их бо­лее вы­со­кой крип­то­стой­ко­сти. Рос­сий­ский и аме­ри­кан­ский стан­дар­ты шиф­ро­ва­ния ос­но­ва­ны имен­но на этом классе шифров.

   Перестановкойsнабора целых чисел (0,1,...,N-1) называется его переупорядочение. Для того чтобы показать, что целое i пере­мещено из позиции i в позицию s(i), где 0 £(i) <n, будем использовать запись

s=(s(0), s(1),..., s(N-1)).

Число перестановок из (0,1,...,N-1) равноn!=1*2*...*(N-1)*N. Введем обозначение sдля взаимно-однозначного отображения (гомо­морфизма) набора S={s,s1, ...,sN-1}, состоящего изnэлементов, на себя.

s: S ®S

s: si®ss(i), 0 £i<n

Будем говорить, что в этом смысле sявляется перестановкой элементов S. И, наоборот, автоморфизм S соответствует пере­становке целых чисел (0,1,2,..,n-1).

Криптографическим преобразованиемT для алфавита Zmназывается последовательность автоморфизмов: T={T(n):1£n<¥}

T(n): Zm,n®Zm,n, 1£n<¥

Каждое T(n)является, таким образом, перестановкойn-грамм из Zm,n.

Поскольку T(i)и T(j) могут быть определены независимо  при i¹j, число криптографических преобразований исходного текста размерностиnравно (mn)![i]. Оно возрастает непропорционально при увеличенииmиn: так, приm=33 иn=2 число различных криптографических преобразований равно 1089!.. Отсюда следует, что потенциально существует большое число отображений исходного текста в шифрованный.

Практическая реализация криптогра­фических систем требует, чтобы преобразо­вания {Tk: kÎK} были определены алгоритмами, зависящими от относительно небольшого числа параметров (ключей).
    продолжение
--PAGE_BREAK--1.2. Сис­те­мы под­ста­но­вок
ОпределениеПодстановкойpна алфавите Zmназывается автоморфизм Zm, при котором буквы исходного текста t замещены буквами шифрованного текста p(t):

ZmàZm; p: tàp(t).

Набор всех подстановокназывается симметрической группой Zmи будет в дальнейшем обозначаться какSYM(Zm).

УтверждениеSYM(Zm) cоперацией произведения является группой, т.е. операцией, обладающей следующими свойствами:

     Замкнутость: произведение подстановок p1p2является подста­новкой:

p:tàp1(p2(t)).

     Ассоциативность: результат произведения p1p2p3не зависит от порядка расстановки скобок:

(p1p2)p3=p1(p2p3)

    Существование нейтрального элемента: постановка i, опре­деляемая как i(t)=t, 0£t<m, является нейтральным элементом SYM(Zm) по операции умножения: ip=pi для "pÎSYM(Zm).

     Существование обратного: для любой подстановки pсуществует единственная обратная подстановка p-1, удовлетворя­ющая условию

pp‑1=p‑1p=i.

Число возможных подстановок в симметрической группе Zmназывается порядкомSYM(Zm) и равноm! .

Определение.
Ключомподстановки kдля Zmназывается последовательность элементов симметрической группы Zm:

k=(p0,p1,...,pn-1,...), pnÎSYM(Zm), 0£n<¥

Подстановка, определяемая ключом k, является крипто­гра­фи­ческим преобразованием Tk, при помощи которого осуществляется преоб­разованиеn-граммы исходного текста (x,x1 ,..,xn-1) вn-грамму шифрованного текста (y,y1 ,...,yn-1):

yi=p(xi),   £i<n

гдеn– произвольное (n=1,2,..). Tkназывается моноалфавитной под­ста­новкой, если pнеизменно при любом i, i=0,1,..., в  противном случае Tkназывается многоалфавитной подстановкой.

Примечание. К наиболее существенным особенностям подста­новки Tkотносятся следующие:

1. Исходный текст шифруется посимвольно. Шифрованияn-граммы (x,x1 ,..,xn-1) и ее префикса (x,x1 ,..,xs-1) связаны соотношениями

Tk(x0,x1 ,..,xn-1)=(y0,y1 ,...,yn-1)

Tk(x0,x1 ,..,xs-1)=(y0,y1 ,...,ys-1)

2. Буква шифрованного текста y
i
является функцией только i-й компоненты ключа p
i
  и i-й буквы исходного текста xi.
    продолжение
--PAGE_BREAK--1.3. Подстановка Цезаря
Подстановка Цезаря является самым простым вариантом подстановки. Она относится к группе моноалфавитных подстановок.

Определение. Подмножество Cm={Ck: 0£k<m} симметрической группы SYM(Zm), содержащееmподстановок

Ck: j®(j+k) (modm), 0£k<m,

называется подстановкой Цезаря.

Умножение коммутативно, CkCj=CjCk=Cj+k, C0– идентичная подстановка, а обратной к Cк является Ck-1=Cm-k, где 0<k<m. Семейство подстановок Цезаря названо по имени римского императора Гая Юлия Цезаря, который поручал Марку Туллию Цицерону составлять послания с использованием 50-буквенного алфавита и подстановки C3.

Подстановка определяется по таблице замещения, содержащей пары соответствующих букв “исходный текст – шифрованный текст”. Для C3подстановки приведены в Табл. 1. Стрелка (à) означает, что буква исходного текста (слева) шифруется при помощи C3в букву шифрованного текста (справа).

Определение.Системой Цезаряназывается моноалфа­витная подстановка, преобразующаяn-грамму исходного текста (x,x1 ,..,xn-1) вn‑грамму шифрованного текста (y,y1 ,...,yn-1) в соответствии с правилом

yi=Ck(xi), 0£i<n.

Например, ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯ посредством подстановки C3преобразуется в еюыолхиврсеюивцнгкгрлб.

Аàг

Йàм

Тàх

Ыàю

Бàд

Кàн

Уàц

Ьàя

Вàе

Лàо

Фàч

Эà_

Гàж

Мàп

Хàш

Юàа

Дàз

Нàр

Цàщ

Яàб

Еàи

Оàс

Чàъ

_àв

Жàй

Пàт

Шàы



Зàк

Рàу

Щàь



Иàл

Сàф

Ъàэ





Таблица 1.1: Применение подстановки Цезвря.

При своей несложности система легко уязвима. Если злоумышленник имеет

1) шифрованный и соответ­ствующий исходный текст или

2) шифрованный текст выбранного злоумыш­ленником исходного текста,

то определение ключа и дешифрование исходного текста тривиальны.

Более эффективны обобщения подстановки Цезаря — шифр Хилла и шифр Плэйфера. Они основаны на подстановке не отдельных символов, а 2-грамм (шифр Плэйфера) илиn-грамм[ii] (шифр Хилла). При более высокой криптостойкости они значительно сложнее для реализации и требуют достаточно большого количества ключевой информации.
    продолжение
--PAGE_BREAK--1.4.Многоалфавитные системы. Системы одноразового использования
Слабая криптостойкость моноалфавитных подстановок преодолевается с применением подстановок многоалфавитных.


Многоалфавитная подстановкаопределяется ключом p=(p1,
p2, ...), содержащим не менее двух различных подстановок. В начале рассмотрим многоалфавитные системы подстановок с нулевым начальным смещением. Пусть {Ki: 0£i<n} – независимые случайные переменные с одинаковым распределением вероятностей,

принимающие значения на множестве Zm

Pкл{(K, K1, ..., Kn-1)=(k, k1, ..., kn-1)}=(1/m)n

Система одноразового использованияпреобразует исходный текст

X=(X0,x1, ...,xn-1)

в шифрованный текст

Y=(Y0,y1, ...,yn-1)

при помощи подстановки Цезаря

Yi=CKi(xi)=(Ki+Xi) (modm)   i=0...n-1                            (1)

Для такой системы подстановки используют также термин “одноразовая лента” и “одноразовый блокнот”. Пространство ключей К системы одноразовой подстановки является вектором рангов (K, K1, ..., Kn-1) и содержитmnточек.

Рассмотрим небольшой пример шифрования с бесконечным ключом. В качестве ключа примем текст

 “БЕСКОНЕЧНЫЙ_КЛЮЧ....”.

Зашифруем с его помощью текст “ШИФР_НЕРАСКРЫВАЕМ”. Шифрование оформим в таблицу:



ШИФРУЕМЫЙ_ТЕКСТ

24

8

20

16

19

5

12

27

9

32

18

5

10

17

18

БЕСКОНЕЧНЫЙ_КЛЮЧ

1

5

17

10

14

13

5

23

13

27

9

32

10

11

30

ЩРДЪАТТССЦЪЫДФЬП

25

13

4

26



18

17

17

22

26

27

4

20

28

15



Исходный текст невозможно восстановить без ключа.

Наложение белого шума в виде бесконечного ключа на исходный текст меняет статистические характеристики языка источника. Системы одноразового использованиятеоретически не расшифруемы[iii], так как не содержат достаточной информации для восстановления текста.

Почему же эти системы неприменимы для обеспечения секретности при обработке информации? Ответ простой — они непрактичны, так как требуют независимого выбора значения ключа для каждой буквы исходного текста. Хотя такое требование может быть и не слишком трудным при передаче по прямому кабелю Москва — Нью-Йорк, но для информационных оно непосильно, поскольку там придется шифровать многие миллионы знаков.

Посмотрим, что получится, если ослабить требование шифровать каждую букву исходного текста отдельным значением ключа.
    продолжение
--PAGE_BREAK--1.5.Системы шифрования Вижинера
Начнем с конечной последовательности ключа

 k = (k0,k1 ,...,kn),

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

k= (k0,k1 ,...,kn), kj = k(jmod r, 0 £j < ¥.

Например, при r= ¥и ключе пользователя 15 8 2 10 11 4 18 рабочий ключ будет периодической последовательностью:

15 8 2 10 11 4 18 15 8 2 10 11 4 18 15 8 2 10 11 4 18 ...




Определение.
Подстановка ВижинераVIGkопределяется как

 VIGk: (x0,x1, ...,xn-1) ®(y0,y1, ...,yn-1) = (x0+k,x1+k,. ..,xn-1+k).

Таким образом:

1) исходный текстxделится на rфрагментов

 
xi= (xi ,xi+r, ...,xi+r(n-1)), 0 £i < r;

2) i-й фрагмент исходного текстаxiшифруется при помощи подстановки Цезаря Ck:

(xi ,xi+r, ...,xi+r(n-1)) ®(yi ,yi+r, ...,yi+r(n-1)),
Вариант системы подстановок Вижинера приm=2 называетсясистемой Вернама (1917 г). В то время ключ k=(k0,k1 ,...,kк-1) записывался на бумажной ленте. Каждая буква исходного переводилась с использованием кода Бодо в пятибитовый символ. К исходному тексту Бодо добавлялся ключ (по модулю 2). Старинный телетайп фирмы AT&T со считывающим устройством Вернама и оборудованием для шифрования, использовался корпусом связи армии США.

Очень распространена плохая с точки зрения секретности практика использовать слово или фразу в качестве ключа для того, чтобы k=(k0,k1 ,...,kк-1) было легко запомнить. В ИС для обеспечения безопасности информации это недопустимо. Для получения ключей должны использоваться программные или аппаратные средства случайной генерации ключей.

Пример. Преобразование текста с помощью подстановки Вижинера (r=4)

Исходный текст (ИТ1):

НЕ_СЛЕДУЕТ_ВЫБИРАТЬ_НЕСЛУЧАЙНЫЙ_КЛЮЧ

Ключ:КЛЮЧ

Разобьем исходный текст на блоки по 4 символа:

НЕ_С ЛЕДУ ЕТ_В ЫБИР АТЬ_ НЕСЛ УЧАЙ НЫЙ_ КЛЮЧ

и наложим на них ключ (используя таблицу Вижинера):

H+К=Ч, Е+Л=Р и т.д.

Получаем зашифрованный (ЗТ1) текст:

ЧРЭЗ ХРБЙ ПЭЭЩ ДМЕЖ КЭЩЦ ЧРОБ ЭБЮ_ ЧЕЖЦ ФЦЫН

Можно выдвинуть и обобщенную систему Вижинера. ЕЕ можно сформулировать не только при помощи подстановки Цезаря.

Пустьx— подмножество симметрической группы SYM(Zm).

Определение. r
-многоалфавитный ключшифрования есть r-набор p= (p, p1, ..., pr-1) с элементами вx.

Обобщенная система Вижинерапреобразует исходный текст (x,x1 ,...,xn-1) в шифрованный текст (y,y1 ,...,yn-1) при помощи ключа p= (p, p1, ..., pr-1) по правилу

VIGk: (x0,x1 ,...,xn-1) ®(y0,y1 ,...,yn-1) = (p(х0), p1(х1), ..., pn-1(xn-1)), где используется условие pi= pimod r. Следует признать, что и многоалфавитные подстановки в принципе доступны криптоаналитическому исследованию. Криптостойкость многоалфавитных систем резко убывает с уменьшением длины ключа.

Тем не менее такая система как шифр Вижинера допускает несложную аппаратную или программную реализацию и при достаточно большой длине ключа может быть использован в современных ИС.
    продолжение
--PAGE_BREAK--1.6. Гам­ми­ро­ва­ние
Гам­ми­ро­ва­ние яв­ля­ет­ся так­же ши­ро­ко при­ме­няе­мым крип­то­гра­фи­че­ским пре­об­ра­зо­ва­ни­ем. На са­мом де­ле гра­ни­ца ме­ж­ду гам­ми­ро­ва­ни­ем и ис­поль­зо­ва­ни­ем бес­ко­неч­ных клю­чей и шиф­ров Ви­жи­не­ра, о ко­то­рых речь шла вы­ше, весь­ма ус­лов­ная.

Прин­цип шифрования гам­ми­ро­ва­ни­ем за­клю­ча­ет­ся в ге­не­ра­ции гам­мы шиф­ра с по­мо­щью дат­чи­ка псев­до­слу­чай­ных чи­сел и на­ло­же­нии по­лу­чен­ной гам­мы на от­кры­тые дан­ные об­ра­ти­мым об­ра­зом (на­при­мер, ис­поль­зуя сло­же­ние по мо­ду­лю 2).

Про­цесс дешифрования дан­ных сво­дит­ся к по­втор­ной ге­не­ра­ции гам­мы шиф­ра при из­вест­ном клю­че и на­ло­же­нии та­кой гам­мы на за­шиф­ро­ван­ные дан­ные.

По­лу­чен­ный за­шиф­ро­ван­ный текст яв­ля­ет­ся дос­та­точ­но труд­ным для рас­кры­тия в том слу­чае, ес­ли гам­ма шиф­ра не со­дер­жит по­вто­ряю­щих­ся би­то­вых по­сле­до­ва­тель­ностей. По су­ти де­ла гам­ма шиф­ра долж­на из­ме­нять­ся слу­чай­ным об­ра­зом для ка­ж­до­го шиф­руе­мо­го сло­ва. Фак­ти­че­ски же, ес­ли пе­ри­од гам­мы пре­вы­ша­ет дли­ну все­го за­шиф­ро­ван­но­го тек­ста и не­из­вест­на ни­ка­кая часть ис­ход­но­го тек­ста, то шифр мож­но рас­крыть толь­ко пря­мым пе­ре­бо­ром (про­бой на ключ). Криптостойкость в этом слу­чае оп­ре­де­ля­ет­ся раз­ме­ром клю­ча.

Ме­тод гам­ми­ро­ва­ния ста­но­вит­ся бес­силь­ным, ес­ли зло­умыш­лен­ни­ку ста­но­вит­ся из­вес­тен фраг­мент ис­ход­но­го тек­ста и со­от­вет­ст­вую­щая ему шиф­ро­грам­ма. Про­стым вы­чи­та­ни­ем по мо­ду­лю по­лу­ча­ет­ся от­ре­зок ПСП и по не­му вос­ста­нав­ли­ва­ет­ся вся по­сле­до­ва­тель­ность.  Зло­умыш­лен­ни­ки мо­жет сде­лать это на ос­но­ве до­га­док о со­дер­жа­нии ис­ход­но­го тек­ста. Так, ес­ли боль­шин­ст­во по­сы­лае­мых со­об­ще­ний на­чи­на­ет­ся со слов “СОВ.СЕК­РЕТ­НО”, то крип­тоа­на­лиз все­го тек­ста зна­чи­тель­но об­лег­ча­ет­ся. Это сле­ду­ет учи­ты­вать при соз­да­нии ре­аль­ных сис­тем ин­фор­ма­ци­он­ной безо­пас­но­сти.

Ниже рассматриваются наиболее распространенные методы генерации гамм, которые могут быть использованы на практике.
1.7. Шифрование с помощью аналитических преобразований
Достаточно надежное закрытие информации может быть обеспечено при  использовании для шифрования некоторых аналитических преобразований. Для этого нужно использовать методы алгебры матриц, например, умножение матрицы на вектор по правилу:

                                   ||  aij||bj  =  cj  =Saijbj

         Если матрицу  ||  aij||  использовать в качестве ключа, а вместо компонента вектора bj  подставить символы текста, то компоненты вектора  cj  будут представлять собой символы зашифрованного текста.

<img width=«2» height=«79» src=«ref-1_735506667-160.coolpic» v:shapes="_x0000_s1044"><img width=«2» height=«79» src=«ref-1_735506827-158.coolpic» v:shapes="_x0000_s1045"><img width=«2» height=«79» src=«ref-1_735506827-158.coolpic» v:shapes="_x0000_s1046"><img width=«2» height=«79» src=«ref-1_735506667-160.coolpic» v:shapes="_x0000_s1047">         Приведем пример, взяв в качестве ключа  квадратную матрицу третьего порядка

            14  8  3

             8    5  2

             3    2  1
           Заменим буквы алфавита цифрами, соответствующими порядковому номеру в алфавите. Тогда отрывку текста  ВАТАЛА соответствует последовательность номеров 3,0,19,0,12,0. По принятому алгоритму шифрования выполним необходимые действия:

<img width=«2» height=«78» src=«ref-1_735507303-155.coolpic» v:shapes="_x0000_s1048"><img width=«2» height=«78» src=«ref-1_735507458-157.coolpic» v:shapes="_x0000_s1049"><img width=«2» height=«78» src=«ref-1_735507303-155.coolpic» v:shapes="_x0000_s1050"><img width=«2» height=«78» src=«ref-1_735507303-155.coolpic» v:shapes="_x0000_s1051"><img width=«2» height=«78» src=«ref-1_735507458-157.coolpic» v:shapes="_x0000_s1052"><img width=«2» height=«78» src=«ref-1_735507458-157.coolpic» v:shapes="_x0000_s1053"><img width=«2» height=«78» src=«ref-1_735507303-155.coolpic» v:shapes="_x0000_s1054"><img width=«2» height=«78» src=«ref-1_735507458-157.coolpic» v:shapes="_x0000_s1055"><img width=«2» height=«78» src=«ref-1_735507303-155.coolpic» v:shapes="_x0000_s1056"><img width=«2» height=«78» src=«ref-1_735507458-157.coolpic» v:shapes="_x0000_s1057"><img width=«2» height=«78» src=«ref-1_735507458-157.coolpic» v:shapes="_x0000_s1058"><img width=«2» height=«78» src=«ref-1_735507458-157.coolpic» v:shapes="_x0000_s1059">14  8   3          3               99                   14   8   3              0               96

 8    5   2   *     0       =     62        ;           8   5   2        *    12      =     60

 3   2   1          19             28                     3   2   1              0               24

          При этом зашифрованый текст будет иметь вид:99,62,28,96,60,24.

Расшифрование осуществляетсяс использованием того же правила умножения матрицы на вектор, только в качестве основы берется матрица, обратная той, с помощью которой осуществляется закрытие, а в качестве вектора-самножителя – соответствующие колличество символов закрытого текста; тогда значениями вектора-результата будут цифровые эквиваленты знаков открытого текста. Обратной к данной называется матрица, полущающая из так называемой присоединенной матрицы делением всех ее элементов на  определитель данной матрицы. В свою очередь присоединенной называется матрица, составленная из алгеброических дополнений А, к элементам данной матрицы, которые вычисляются по формуле:        Aij = (-1)^i+j Dij ,

где Dij– определитель матрицы, получаемый вычеркиванием i-й ее строки и j-го столбца. Определителем же как известно, называется алгеброическая сумма n! членов (для определения n-ого порядка), составленная следующим образом: членами служат всевозможные произведения nэлементов матрицы, взятых по одному в каждой строке и в каждом столбце, причем член суммы берется со знаком ''+'', если его индексы составлят подставку, и со знаком ''-''  -  в противоположном случае. Для матрицы третьего порядка, например, определитель вычисляется по следующей формуле:

D=а11а22а33+а12а23а31+а13а21а32-а11а23а32-а12а21а33-а13а22а31.

Тогда процесс раскрытия выглядит так:

<img width=«2» height=«78» src=«ref-1_735507303-155.coolpic» v:shapes="_x0000_s1060"><img width=«2» height=«78» src=«ref-1_735507303-155.coolpic» v:shapes="_x0000_s1061"><img width=«2» height=«78» src=«ref-1_735507303-155.coolpic» v:shapes="_x0000_s1062"><img width=«2» height=«78» src=«ref-1_735507458-157.coolpic» v:shapes="_x0000_s1063"><img width=«2» height=«78» src=«ref-1_735507458-157.coolpic» v:shapes="_x0000_s1064"><img width=«2» height=«78» src=«ref-1_735507458-157.coolpic» v:shapes="_x0000_s1065"><img width=«2» height=«78» src=«ref-1_735507303-155.coolpic» v:shapes="_x0000_s1066"><img width=«2» height=«78» src=«ref-1_735507303-155.coolpic» v:shapes="_x0000_s1067"> 1   -2    1              99                       1*99-2*62+1*28                     3

-2    5   -4     *      62        =           -2*99+5*62-4*28          =         0

 1  -4    6               28                      1*99-4*62+6*28                     19  

     

<img width=«2» height=«79» src=«ref-1_735510423-161.coolpic» v:shapes="_x0000_s1068"><img width=«2» height=«79» src=«ref-1_735510423-161.coolpic» v:shapes="_x0000_s1069"><img width=«2» height=«78» src=«ref-1_735507303-155.coolpic» v:shapes="_x0000_s1070"><img width=«2» height=«78» src=«ref-1_735507458-157.coolpic» v:shapes="_x0000_s1071"><img width=«2» height=«78» src=«ref-1_735507458-157.coolpic» v:shapes="_x0000_s1072"><img width=«2» height=«78» src=«ref-1_735507458-157.coolpic» v:shapes="_x0000_s1073"><img width=«2» height=«78» src=«ref-1_735507303-155.coolpic» v:shapes="_x0000_s1074"><img width=«2» height=«78» src=«ref-1_735507303-155.coolpic» v:shapes="_x0000_s1075"> 1   -2    1                96                       1*96-2*60+1*24                     0

2    5   -4      *        60        =           -2*96+5*60-4*24          =         12

1  -4    6                 24                      1*96-4*60+6*24                     0  

         

             Таким образом, получили следующюю последовательность знаков раскрытого текста:3,0,19,0,12,0, что соответствует исходному тексту. Этот метод шифрования является формальнным, что позволяет легко реализовать его программными средствами.
    продолжение
--PAGE_BREAK--1.8. Криптосистемы на основе эллиптических уравнений
Эллиптические кривые— математический объект, который может определен над любым полем (конечным, действительным, рациональным или комплексным). В криптографии обычно используются конечные поля. Эллиптическая кривая есть множество точек(
x
,
y
),удовлетворяющее следующему уравнению:

y
2
=
x
3
+
ax
+
b
,

а также бесконечно удаленная точка. Для точек на кривой довольно легко вводится операция сложения, которая играет ту же роль, что и операция умножения в криптосистемах RSAи Эль-Гамаля.

В реальных криптосистемах на базе эллиптических уравнений используется уравнение

y
2
=
x
3
+
ax
+
b
mod
p
,

где р — простое.

Проблема дискретного логарифма на эллиптической кривой состоит в следующем: дана точка Gна эллиптической кривой порядка r(количество точек на кривой) и другая точка Yна этой же кривой. Нужно найти единственную точку xтакую, что Y= xG, то есть Yесть х-я степень G.
2. Эллиптические фунции – реализация метода открытых ключей                                   2.1.Системы с открытым ключом
Как бы ни бы­ли слож­ны и на­деж­ны крип­то­гра­фи­че­ские сис­те­мы — их сла­бое ме­ст при прак­ти­че­ской реа­ли­за­ции — про­блема рас­пре­де­ле­ния клю­чей. Для то­го, что­бы был воз­мо­жен об­мен кон­фи­ден­ци­аль­ной ин­фор­ма­ци­ей ме­ж­ду дву­мя субъ­ек­та­ми ИС, ключ дол­жен быть сге­не­ри­ро­ван од­ним из них, а за­тем ка­ким-то об­ра­зом опять же в кон­фи­ден­ци­аль­ном по­ряд­ке пе­ре­дан дру­го­му. То есть ,  в об­щем слу­чае для пе­ре­да­чи клю­ча опять же тре­бу­ет­ся ис­поль­зо­ва­ние ка­кой-то крип­то­си­сте­мы.

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

Суть их со­сто­ит в том, что ка­ж­дым ад­ре­са­том ИС ге­не­ри­ру­ют­ся два клю­ча, свя­зан­ные ме­ж­ду со­бой по оп­ре­де­лен­но­му пра­ви­лу. Один ключ объ­яв­ля­ет­ся от­кры­тым, а дру­гой за­кры­тым. От­кры­тый ключ пуб­ли­ку­ет­ся и дос­ту­пен лю­бо­му, кто же­ла­ет по­слать со­об­ще­ние ад­ре­са­ту. Секретный ключ сохраняется в тайне.

Ис­ход­ный текст шиф­ру­ет­ся от­кры­тым клю­чом адресата и пе­ре­да­ет­ся ему. За­шиф­ро­ван­ный текст в прин­ци­пе не мо­жет быть рас­шиф­ро­ван тем же от­кры­тым клю­чом. Де­шиф­ро­ва­ние со­об­ще­ние воз­мож­но толь­ко с ис­поль­зо­ва­ни­ем за­кры­то­го клю­ча, ко­то­рый из­вес­тен толь­ко са­мо­му ад­ре­са­ту.

<img width=«563» height=«39» src=«ref-1_735511681-1168.coolpic» v:shapes="_x0000_s1078 _x0000_s1076 _x0000_s1077"> <img width=«108» height=«66» src=«ref-1_735512849-1207.coolpic» v:shapes="_x0000_s1087 _x0000_s1088 _x0000_s1089"> <img width=«108» height=«65» src=«ref-1_735514056-1099.coolpic» v:shapes="_x0000_s1081 _x0000_s1082 _x0000_s1083"> <img width=«257» height=«149» src=«ref-1_735515155-2994.coolpic» v:shapes="_x0000_s1080 _x0000_s1093 _x0000_s1091 _x0000_s1084 _x0000_s1085 _x0000_s1086"> <img width=«102» height=«145» src=«ref-1_735518149-1245.coolpic» v:shapes="_x0000_s1079 _x0000_s1092 _x0000_s1090">


Рис.2.1.Реализация процедуры шифрования с открытым ключом.

Крип­то­гра­фи­че­ские сис­те­мы с от­кры­тым клю­чом ис­поль­зу­ют так называемые  не­об­ра­ти­мые  или од­но­сто­рон­ние функ­ции, ко­то­рые об­ла­да­ют сле­дую­щим свой­ст­вом: при за­дан­ном зна­че­нииxот­но­си­тель­но про­сто вы­чис­лить зна­че­ние f(x),од­на­ко ес­лиy=f(x), то нет про­сто­го пу­ти для вы­чис­ле­ния зна­че­нияx.

Мно­же­ст­во клас­сов не­об­ра­ти­мых функ­ций и по­ро­ж­да­ет все раз­но­об­ра­зие сис­тем с от­кры­тым клю­чом. Од­на­ко не вся­кая не­об­ра­ти­мая функ­ция го­дит­ся для ис­поль­зо­ва­ния в ре­аль­ных ИС.

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

По­это­му что­бы га­ран­ти­ро­вать на­деж­ную за­щи­ту ин­фор­ма­ции, к сис­те­мам с от­кры­тым клю­чом (СОК) предъ­яв­ля­ют­ся два важ­ных и оче­вид­ных тре­бо­ва­ния:

1. Пре­об­ра­зо­ва­ние ис­ход­но­го тек­ста долж­но быть не­об­ра­ти­мым и ис­клю­чать его вос­ста­нов­ле­ние на ос­но­ве от­кры­то­го клю­ча.

2. Оп­ре­де­ле­ние за­кры­то­го клю­ча на ос­но­ве от­кры­то­го так­же долж­но быть не­воз­мож­ным на со­вре­мен­ном тех­но­ло­ги­че­ском уров­не. При этом же­ла­тель­на точ­ная ниж­няя оцен­ка сложности (ко­ли­че­ст­ва опе­ра­ций) рас­кры­тия шиф­ра.

Ал­го­рит­мы шиф­ро­ва­ния с от­кры­тым клю­чом по­лу­чи­ли ши­ро­кое рас­про­стра­не­ние в со­вре­мен­ных ин­фор­ма­ци­он­ных сис­те­мах. Так, ал­го­ритм RSA стал ми­ро­вым стан­дар­том де-фак­то для от­кры­тых сис­тем и ре­ко­мен­до­ван МККТТ.

Вообще же все предлагаемые сегодня криптосистемы с открытым ключом опираются на один из следующих типов необратимых преобразований:

1. Разложение больших чисел ан простые множители.

2. Вычисление логарифма в конечном поле.

3. Вычисление корней алгебраических уравнений.

Здесь же  сле­ду­ет от­ме­тить, что ал­го­рит­мы криптосистемы с открытым ключом (СОК) мож­но ис­поль­зо­вать в трех на­зна­че­ни­ях.

1. Как са­мо­стоя­тель­ные сред­ст­ва за­щи­ты пе­ре­да­вае­мых и хра­ни­мых дан­ных.

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

3. Сред­ст­ва ау­тен­ти­фи­ка­ции поль­зо­ва­те­лей. Об этом бу­дет рас­ска­за­но в главе «Электронная подпись».

Ниже рассматриваются наиболее распространенные системы с открытым ключом.

Не­смот­ря на до­воль­но боль­шое чис­ло раз­лич­ных СОК, наиболее популярна — криптосистема RSA, разработанная в 1977 году и по­лу­чив­шая на­зва­ние в честь ее соз­да­те­лей: Рона Ри­ве­ста[iv], Ади Ша­ми­ра и Леонарда Эй­дель­ма­на.

Они вос­поль­зо­ва­лись тем фак­том, что на­хо­ж­де­ние боль­ших про­стых чи­сел в вы­чис­ли­тель­ном от­но­ше­нии осу­ще­ст­в­ля­ет­ся лег­ко, но раз­ло­же­ние на мно­жи­те­ли про­из­ве­де­ния двух та­ких чи­сел прак­ти­че­ски не­вы­пол­ни­мо. До­ка­за­но (тео­ре­ма Ра­би­на), что рас­кры­тие шиф­ра RSA эк­ви­ва­лент­но та­ко­му раз­ло­же­нию. По­это­му для лю­бой дли­ны клю­ча мож­но дать ниж­нюю оцен­ку чис­ла опе­ра­ций для рас­кры­тия шиф­ра, а с уче­том про­из­во­ди­тель­но­сти со­вре­мен­ных ком­пь­ю­те­ров оце­нить и не­об­хо­ди­мое на это вре­мя.

Воз­мож­ность га­ран­ти­ро­ван­но оце­нить за­щи­щен­ность ал­го­рит­ма RSA ста­ла од­ной из при­чин по­пу­ляр­но­сти этой СОК на фо­не де­сят­ков дру­гих схем. По­это­му ал­го­ритм RSA ис­поль­зу­ет­ся в бан­ков­ских ком­пь­ю­тер­ных се­тях, осо­бен­но для ра­бо­ты с уда­лен­ны­ми кли­ен­та­ми (об­слу­жи­ва­ние кре­дит­ных кар­то­чек).

В настоящее время алгоритм RSAиспользуется во многих стандартах, среди которых SSL, S-HHTP, S-MIME, S/WAN, STTи  PCT.
    продолжение
--PAGE_BREAK--2.2.Типы криптографических услуг
Сегодня безопасные  решения используют некоторую комбинацию из пяти  различных криптографических услуг. Эти услуги:

        Проверка пользователя – введением пути в оперативную транзакцию, пользователь подтверждает, что это именно он.

      Идентификация Начала координат Данных— обеспечение источника сообщения.

     Целостность Данных— обеспечение сохранения данных неправомочными сторонами.

     Не отказ -  получатель транзакции способен демонстрировать нейтральному третьему лицу, что требуемый передатчик действительно посылал транзакцию.

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

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

 В системах цифровой лодписи подпись ''накладывается'' с использованием секретного ключа, а снимается с помощью открытого отправителя .  

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

Криптосистемы с ключом общего пользования решают ключевые проблемы управления, связанные с симметрично — ключевым кодированием; однако, шифрование с открытым ключом предлагает способность эффективно осуществить цифровые представления.
2.3.      Цифровые представления
Цифровые представления– это электронный эквивалент традиционных рукописных сигнатур. Рукописные сигнатуры обеспечивают службу безопасности, потому что уникальность почерка личностей делает сигнатуры интенсивными.

В отличие от почерка индивидуума, электронная информация проста для дублирования. Если электронные сигнатуры использовались таким же образом как письменные сигнатуры, защита легко может быть поставлена под угрозу.

Цифровые представления могут использоваться, чтобы использовать три  криптогафических услуги: идентификацию, неотказ, и целостность данных.  код с исправлением ошибок может использоваться, чтобы генерировать сильные цифровые представления с  маленьким количеством обработки  энергии.
2.4.      Эллиптическая криптография кривой.
После изобретения шифрования с открытым ключом, были предложены многочисленные общее — ключевые системы засекречивания на ее основе.Криптография с открытым ключом может применяться как для шифрования сообщений, так и для аутентификации (так называемая цифровая подпись).

 Каждая из этих систем полагается на трудную математическую проблему для ее защиты. Они являются труднообрабатываемыми, потому что годы интенсивного изучения ведущими математиками и компьютерными учеными не сумели создать эффективные алгоритмы для их решения, так, чтобы практически, они остались труднообрабатываемыми с текущей вычислительной технологией. Требуется  время, чтобы получить безопасный ключ с лучшим известным алгоритмом для этой проблемы.  Обще — ключевая система шифрования, основана на этой проблеме. Эллиптические кривые — математические конструкции, которые изучились математиками начиная с семнадцатого столетия. В 1985  Нейл Коблиц и Виктор Миллер независимо предложили криптосистемы с ключом общего пользования, использующие группу точек на эллиптической кривой, и эллиптическая криптография кривой (код с исправлением ошибок) была рождена. Начиная с того времени, многочисленные исследователи и разработчики потратили несколько лет, исследуя силу кода с исправлением ошибок и улучшая методы для его выполнения. Сегодня более быстрая криптосистема с ключом общего пользования предлагает практическую и безопасную технологию для наиболее сдерживаемой среды.

Код с исправлением ошибок дает самую высокую силу в любой известной криптосистемы с ключом общего пользования из-за трудности жесткой проблемы, на которой это основано. Эта большая трудность жесткой проблемы эллиптической кривой, дискретной проблемы логарифма (ECDLP) означает что меньший размер ключа выдает эквивалентные уровни защиты. Учитывая лучшие известные алгоритмы к целым числам множителя и вычисляют эллиптические логарифмы кривой, размеры ключа  являются эквивалентной силой, основанной на MIPSгодах, необходимых, чтобы восстановить один ключ.

Трудность проблемы и заканчивающихся размеров ключа эквивалентной силы предоставляет несколько прямых выгод к выполнению электроной платы.
    продолжение
--PAGE_BREAK--2.5.Электронные платы и код с исправлением ошибок
Электроные платы– это маленькие, переносные, устройства противодействия вмешательству, обеспечивающие пользователей с хранением памятью и возможностью обработки. Из-за их уникальной формы, электроные платы предложены для использования в широком разнообразии приложений типа электронной торговли, идентификации, и здравоохранения. Для многих из этих предложенных приложений, требовались бы

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

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

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

Как упомянуто ранее, секретный ключ в общее — ключевой паре должен сохраниться секретным. Для истинного неотказа, секретный ключ должен быть полностью недоступен всем другим сторонам. В приложениях, использующих другие типы используемых в настоящее время криптосистем с ключом общего пользования, платы индивидуализированы  в безопасной среде, чтобы выполнить это требование. Из-за сложности требуемого вычисления,  плата,  неэффективена и обычно непрактичена.

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

При подведении итогов, преимущества размера ключа кода с исправлением ошибок предоставляют много выгод для электроных плат, и превосходящая деятельность, предлагаемая выполнением кода с исправлением ошибок  делает приложения выполнимыми в низких конечных устройствах без специализированных аппаратных средств.
3.Описание алгоритма
Прежде, чем системы засекречивания и соответствующие математические проблемы могут быть обсуждены, должна быть определена трудность проблемы. Алгоритм – это процесс, описывающий проблему, которую нужно решить.

  При поиске математической проблемы,  чтобы базировать криптографическую систему, шифровальщики ищут такую проблему, для которой самый быстрый алгоритм берет показательное время. Чем больше времени требуется, чтобы вычислить лучший алгоритм для этой проблемы, тем более безопасной будет общее — ключевая система шифрования, основанная на той проблеме.

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

1.                       Целочисленная проблема факторизации (IFP): RSA и Rabin-Уильям.

2.                       Дискретная проблема логарифма (ПРОЦЕССОР ПЕРЕДАЧИ ДАННЫХ).

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

Рассмотрим каждую систему в отдельности.
3.1.  Целочисленная проблема факторизации (IFP): RSA и Рабин-Уильям 3.1.1. Описание задачи
Целочисленная проблема факторизации (IFP): находит p и q, учитывая составное число n, который является  произведением двух больших простых чисел p и q.

         Обнаружение больших простых чисел — относительно простая задача, а проблема разложения на множители,  произведение двух таких чисел рассматривается в вычислительном отношении труднообрабатываемым. Базирующиеся на трудности этой проблемы Ривест, Чамир и Адлеман разработали RSA общее — ключевую систему шифрования.

В то время как целочисленная проблема факторизации занимала внимание  известных математиков подобно Фермату и Гауссу  более чем столетия, только в прошлых 20 годах  был сделан прогресс в разрешении этой проблемы. Имеются две главных причины для этого явления. Сначала, изобретение RSA-системы шифрования в 1978 стимулировало много математиков к изучению этой проблему. И быстродействующие ЭВМ стали доступными для выполнения и испытания сложных алгоритмов. Фермат и Гаусс имели небольшой стимул для изобретения алгоритма разложения на множители решета поля цифр, так как этот алгоритм более громоздкий, чем испытательное деление с целью разложения на множители целых чисел  вручную.
3.1.2. Разложения на множетели
Имеются в основном два типа специализированных и универсальных алгоритмов разложения на множители. Специализированные алгоритмы разложения на множители пытаются эксплуатировать специальные особенности номера 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 системе шифрования.
    продолжение
--PAGE_BREAK--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 может просматриваться как  похожий на процессор передачи данных, но в различной алгебраической установке.
    продолжение
--PAGE_BREAK--