Единое окно доступа к образовательным ресурсам

Математические основы криптологии

Голосов: 0

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

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


       В теории чисел, несмотря на ее многолетнюю историю и на очень
интенсивные поиски в течение последних 30 лет, эффективный алгоритм
разложения натуральных чисел на множители так и не найден. Конечно,
можно, перебирая все простые числа до (rB)1/2 , и деля на них rB, найти
требуемое разложение. Но учитывая, что количество простых чисел в
этом промежутке асимптотически равно 2⋅(rB)1/2⋅(ln rB)-1, находим, что при
rB, записываемом 1000 десятичными цифрами, найдется не менее 10497
простых чисел, на которые придется делить rB при разложении его на мно-
жители, что при современных возможностях вычислительной техники за-
тянется на долгие годы.
       Известны и более эффективные алгоритмы разложения целых чи-
сел на множители, чем простой перебор простых делителей, но и они
работают очень медленно.
       Необходимо также отметить, что система RSA обладает мульти-
пликативным свойством. Поясним сказанное. Пусть m1 и m2 - 2 различных
открытых текста, а c1 и с2 - соответствующие им шифртексты. Заметим,
что
                     (m1m2)α= m1αm2α= c1c2(mod n).
       Другими словами, шифртекст открытого текста m=m1m2 есть c=
c1c2(mod n). Это свойство, называемое также гомоморфным свойством
RSA, позволяет осуществить атаку по выбранному шифртексту. Его нуж-
но учитывать при совмещении схем шифрования на основе RSA и цифро-
вой подписи RSA.
       Кроме того, известно еще несколько атак на RSA. Рассмотрим из
них две.
       Первая из них называется ”Метод безключевого чтения RSA”. Суть
заключается в следующем.
       Криптоаналитику известны открытый ключ (a, n) и шифротекст С.
Тогда он подбирает такое число k, для которого выполняется следующее
соотношение: Сak(mod n)=C. Т.е. криптоаналитик просто проводит k раз
зашифрование на открытом ключе перехваченного шифротекста. Это вы-
глядит следующим образом: (((Сa)a)a…)a=Сak=Сϕ(n)-1=С(mod n). Найдя та-
кое k, криптоаналитик вычисляет Сk=mak=mϕ(n)-1=m(mod n), т.е. получает
открытый текст m.
       Пример 67. Пусть абонент А хочет послать сообщение m=193263
абоненту В. А знает n=212887 и открытый ключ a=3061. Он зашифровы-
вает сообщение открытым ключом, т.е. ma=1932633061=С= 35947 и посыла-
ет это число в открытый канал связи. Таким образом, криптоаналитику
становится известно сообщение С, модуль n и a. Далее криптоаналитик
вычисляет Сa(mod n)=359473061(mod 212887). Затем он находит такое k,
чтобы выполнялось Сak=359473061k=35947=С. Получили k=1084. И, нако-
нец, вычисляем Сk=359471084=193263. ♦
       Следующая атака осуществляется на базе общего модуля. Основ-
ные предпосылки для ее осуществления заключаются в следующем.


82


          При реализации RSA можно раздать всем абонентам криптосети
одинаковый модуль n, но каждому свои значения аi(открытый ключ) и αI
(секретный ключ). При этом наиболее очевидная проблема заключается в
том, что если одно и то же сообщение когда-нибудь шифровалось разны-
ми аi и аk, причем НОД(аi,аk)=1 (как обычно и бывает), то открытый текст
может быть раскрыт даже при неизвестных αi и αk.
          Таким образом, пусть заданы: m – сообщение, а и b – два открытых
ключа шифрования, n – модуль. Тогда щифротекстами являются c1=
mа(mod n) и c2=mb(mod n). Криптоаналитику известны: n, а, b, c1 и c2. Да-
лее, так как а и b взаимно – простые числа, то воспользовавшись результа-
тами главы 4, можно найти такие целые числа x и y, что аx +by =1. Тогда,
возведя c1 в степень x, а c2 – в степень y, получим: c1xc2y=(mа)x(mb)y= mаx+by
=m1=m.
          Пример 68. Пусть абонент А хочет послать сообщение m=237135
другим абонентам. В. Абоненту А даны n=399799 и открытый ключ
a=4397. Он зашифровывает сообщение открытым ключом, т.е. ma=c1=
2371354397=268100(mod 399799) и посылает это число в открытый канал
связи. Абонент В хочет также послать сообщение m=237135 другим або-
нентам. Для В даны n=399799 и открытый ключ b=7517. Он зашифровы-
вает сообщение открытым ключом, т.е. mb=c2=2371357517=263851 (mod
399799) и также посылает это число в открытый канал связи. Таким обра-
зом, криптоаналитику известно: зашифрованные сообщения c1 и c2, мо-
дуль n, открытые ключи a и b. Далее криптоаналитик решает уравнение
аx+by=1=4397x+7517y и получает x=−1607 и y=940. Затем он возводит c1 в
степень |x|, т.е. c1|x|=d1=2681001607=12105(mod 399799), а c2 в степень |y|,
т.е. c2|y|=d2=263851940=362154(mod 399799). Так как x<0, то находится (d1)-1
=12105-1=39501(mod 399799). (При y<0 искали бы (d2)-1). Далее, перем-
ножая (d1)-1∗d2=39501∗362154=237135(mod 399799)=m, т.е. получили
открытый текст. ♦

6.5. ПРОБЛЕМЫ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ RSA

       В настоящее время алгоритм RSA активно реализуется как в виде
самостоятельных криптографических продуктов, так и в качестве встроен-
ных средств в популярных приложениях.
       Важнейшей проблемой практической реализации - генерация боль-
ших простых чисел. Решение задачи «в лоб» - генерация случайного боль-
шого числа n (нечетного) и проверка его делимости на множители от 3
вплоть до n0.5. В случае неуспеха следует взять n+2 и так далее1.
       В принципе в качестве p и q можно использовать «почти» простые
числа, то есть числа для которых вероятность того, что они простые, стре-
мится к 1. Но в случае, если использовано составное число, а не простое,
1
    В теории чисел показано, что вероятность того, что число порядка n будет простым составляет 1/ln n


                                                                         83


криптостойкость RSA падает. Имеются неплохие алгоритмы, которые по-
зволяют генерировать «почти» простые числа с уровнем доверия 2-100.
        Поскольку простые числа должны выбираться таким образом, что-
бы факторизовать их произведение было вычислительно невозможно, ре-
комендуется брать их очень большими и одинаковой длины. Так, для n =
pq длины 1024 бита, p и q должны быть длиной 512 бит.
        Разность чисел p и q (p-q) также не должна быть маленькой,
поскольку в этом случае p~q и, следовательно, p~(n)1/2. Таким образом,
разложение n может быть найдено простым делением на все числа поряд-
ка (n)1/2.
        Кроме того, числа p и q должны быть также "устойчивыми" прос-
тыми числами.
        Число p является устойчивым (strong), если оно удовлетворяет
трем условиям:
     1. p-1 имеет большой простой делитель, обозначим его как r (т.е.
        p≡1(mod r ));
     2. p+1 имеет большой простой делитель, обозначим как s (т.е. p≡s-
        1(mod s ));
     3. r-1 имеет большой простой делитель, обозначим его как t (т.е.
        r=1(mod t )).
        Условие 1 не позволит успешно факторизовать n (p-1) методом
Полларда, который позволяет быстро разложить число n на множители,
если его делитель p имеет небольшие (скажем, меньше миллиона) простые
делители. Условие 2 позволит избежать p+1 метода Ульямса, позволяю-
щего разложить n при условии, что p+1 имеет небольшие делители.
Условие 3 позволит избежать метода безключевого чтения RSA (цикли-
ческой атаки). Если p выбирается случайно и имеет довольно большой
размер, то, как правило, p-1 и p+1 будут иметь большие простые делители.
Однако выбор устойчивых простых чисел не защищает систему от атаки
алгоритмом факторизации на основе эллиптических кривых.
        Получить устойчивые простые числа можно следующим способом.
Генерируем большие простые числа s и t. Затем получаем такое простое
число r, что r-1 делится на t (для этого рассматриваем нечетные числа
вида r=kt+1, где k - последовательные натуральные числа, и проверяем их
на простоту, пока не найдем простое). Теперь, имея простые r и s, строим
новое простое p. Для этого вычисляем p=((sr-1-rs-1) mod rs)+xrs, где x – не-
которое целое число и проверяя p на простоту, находим устойчивое
простое число p.
        Следующая проблема - какой длины ключи следует использовать?
        Для практической реализации алгоритмов RSA полезно знать оцен-
ки трудоемкости разложения простых чисел различной длины, сделанные
Шроппелем.


84


     lg n         Число операций                                Примечания
      50             1.4*1010              Раскрываем на суперкомпьютерах
     100             2.3*1015              На пределе современных технологий
     200             1.2*1023              За пределами современных технологий
     400             2.7*1034              Требует существенных изменений в технологии
     800             1.3*1051              Не раскрываем

       В конце 1995 года удалось практически реализовать раскрытие
шифра RSA для 500-значного ключа. Для этого с помощью сети Интернет
было задействовано 1600 компьютеров.
       Сами авторы RSA рекомендуют использовать следующие размеры
модуля n:
  • 768 бит - для частных лиц;
  • 1024 бит - для коммерческой информации;
  • 2048 бит - для секретной информации1.
       Третий немаловажный аспект реализации RSA - вычислительный,
приходится использовать аппарат длинной арифметики. Если использует-
ся ключ длиной k бит, то для операций по открытому ключу требуется
О(k2) операций, по закрытому ключу - О(k3) операций, а для генерации но-
вых ключей требуется О(k4) операций.
       По сравнению с тем же алгоритмом DES, RSA требует в тысячи и
десятки тысяч раз большее время.

6.6. КРИПТОСИСТЕМА БЕЗ ПЕРЕДАЧИ КЛЮЧЕЙ

       Пусть абоненты А, В, С, ... условились организовать секретную пе-
реписку между собой. Для этой цели они выбирают достаточно большое
простое число р и такое, что р-1 хорошо разлагается на не очень большие
простые множители. Если среди множителей такого числа кратных нет, то
число р-1 называют евклидовым. Каждый из абонентов независимо один
от другого выбирает случайное число, натуральное, взаимно простое с
числом р-1: А, В, С, ... – абоненты; а, b, c, ... – выбранные ими случайные
числа. Далее, абонент А находит число α из условия
                         а⋅α≡1(mod ϕ(p)), 0 < α <р-1;                    (8)
абонент В находит число β из условия
                         b⋅β≡1(mod ϕ(p)), 0 < β <р-1,                    (9)
где ϕ(p) – функция Эйлера, а, α – секретные ключи абонента А; b, β –
секретные ключи абонента В и т.д.
       Пусть абонент А решает послать сообщение m абоненту В. Можно
предполагать, что 0 < m < р-1. Тогда он сначала зашифровывает это сооб-
щение своим первым секретным ключом, находит:
                       m1≡mа(mod p), 0 < m1 < р                        (10)
1
    Данные оценки сделаны с учетом развития вычислительной техники вплоть до 2004 года.


                                                                     85


и отправляет абоненту В. Абонент В, в свою очередь, зашифровывает
вновь это сообщение также своим первым ключом:
                      m2≡m1b(mod p), 0 < m2 < р                   (11)
и пересылает его обратно абоненту А. Абонент А, получив обратно свое
дважды зашифрованное сообщение, шифрует его же в третий раз своим
вторым ключом:
                      m3≡m2α(mod p), 0 < m3 < р                   (12)
и вновь отправляет его абоненту В. Последний расшифровывает эту шиф-
ротелеграмму при помощи своего второго ключа:
                        m4≡m3β(mod p), 0 < m4 < р.
       В самом деле, из сравнений (10) – (12) имеем:
                             m4≡mk(mod p),
где k≡a⋅α⋅b⋅β(mod р-1).
       В силу (8) и (9) k≡1(mod ϕ(p)). Поэтому m4≡m(mod p), а так как
каждое из них положительно и меньше p, то m4=m.
       Пример 69. Пусть абоненты A и B решили установить между со-
бой скрытую связь без передачи ключей. Они выбрали для этого простое
число p = 9551. Тогда p-1=9550.
       Абонент A выбирает случайное число a=8159, а абонент B –
b=7159. Абонент A решает сравнение: 8159⋅α≡1(mod ϕ(9551)), 0<α< 9550
и находит α= 6639, а абонент B решает сравнение: 7159⋅β≡1(mod ϕ(9551)),
0<β<9550 и находит β= 6139.
       Абонент A решает послать секретное сообщение абоненту B
m=7032. Тогда он сначала шифрует сообщение своим первым ключом:
m1≡mа(mod p)= 703281593(mod 9551)= 153.
       Абонент B, получив это сообщение, шифрует его своим первым
ключом: m2≡m1b(mod p)= 1537159(mod 9551)= 4896, и пересылает его або-
ненту А, который, получив зашифрованное сообщение, шифрует его же в
третий раз своим вторым ключом: m3≡m2α(mod p) =48966639(mod 9551)=
7577 и отправляет его абоненту В, который расшифровывает эту шифро-
телеграмму при помощи своего второго ключа: m4≡m3β(mod p)= 757
76139(mod 9551)= 7032.♦
       Пример 70. А теперь рассмотрим похожий пример, но с большими
числами, а именно пусть абоненты A и B выбирают случайное число p =3
6185027886661311069865932815214971204146870208012676262330495002
47285301313. Далее абонент A выбирает случайное число a=32910091146
42412084309938365114701009965471731267159726697218119, а абонент B
– b=72133456729194312009114642445656781208430934647938365165454
65843. Абонент A решает сравнение: 3291009114642412084309938365114
701009965471731267159726697218119⋅α≡1(mod ϕ(3618502788666131106
986593281521497120414687020801267626233049500247285301313)), 0 < α
< 36185027886661311069865932815214971204146870208012676262330495
00247285301312 и находит α=7182890946724276712267540712060414209


86


95758405828622569613369504272231654775, а абонент B решает сравне-
ние: 721334567291943120091146424456567812084309346479383651654546
5843⋅β ≡1(mod ϕ(119726214130147567059245861496117904970213993920
59391)), 0 < β < 1197262141301475670592458614961179049702139939205
9390 и находит β= 20507850089479826167721544736489099017840580106
89679595249365486507640220987.
         Абонент A решает послать секретное сообщение абоненту B
m=16439530856237023359734047455621923453212389086. Тогда он снача-
ла шифрует сообщение своим первым ключом: m1≡mа(mod p)= 164395308
562370233597340474556219234532123890863291009114642412084309938365114701009965
471731267159726697218119
                        (mod 3618502788666131106986593281521497120414687
020801267626233049500247285301313)=2340488471726089607124556756
26416933820229094970133 5616973062664572414115995.
         Абонент B, получив это сообщение, шифрует его своим первым
ключом: m2≡m1b(mod p)= 23404884717260896071245567562641693382022
9094970133561697306266457241411599572133456729194312009114642445656781208430934
64793836516545465843
                     (mod 361850278866613110698659328152149712041468702
0801267626233049500247285301313) =200847152309106133691890020899
3851807662985672512619192514870979350742436070, и пересылает его
абоненту А. Абонент А, получив зашифрованное сообщение, шифрует его
же в третий раз своим вторым ключом: m3≡m2α(mod p) =200847152309106
13369189002089938518076629856725126191925148709793507424360707182
89094672427671226754071206041420995758405828622569613369504272231654775
                                                                       (mod 3618502788666
131106986593281521497120414687020801267626233049500247285301313)
= 33742679560664044914439639213562036497523303647522251966113925
36160948437196 и отправляет его абоненту В, который расшифровывает
эту шифротелеграмму при помощи своего второго ключа: m4≡m3β(mod p)=
3374267956066404491443963921356203649752330364752225196611392536
1609484371962050785008947982616772154473648909901784058010689679595249365486507640220987(
mоd 36185027886661311069865932815214971204146870208012676262330
49500247285301313)=164395308562370233597340474556219234532123890
86♦
6.7. АЛГОРИТМ ЭЛЬ-ГАМАЛЯ

       Поиски более эффективных систем открытого шифрования при-
вели к тому, что в 1985 году Т.Эль-Гамаль (США) предложил алгоритм на
основе возведения в степень по модулю большого простого числа p.
Криптоалгоритм не запатентован, но попадал под действие патента на
метод ключевого обмена Диффи-Хеллмана.
       В отличие от RSA, метод Эль-Гамаля основан на проблеме дис-
кретного логарифма. Этим он и похож на алгоритм Диффи-Хелмана. Если
возводить число в степень в конечном поле достаточно легко, то восста-
новить аргумент по значению (то есть найти логарифм) довольно трудно.


                                                                     87


       Рассмотрим схему алгоритма.
       Основу системы составляют параметры p и n - числа, первое из
которых - простое, а второе - целое.
       Абонент А генерирует секретный ключ α и вычисляет открытый
ключ y = nα mod p. Если абонент Б хочет послать А сообщение m, то он
выбирает случайное число k, меньшее p и вычисляет:
                               y1 = nk mod p и
                               y2 = m ⊕ yk,
где ⊕ - побитовое сложение по модулю 2.
       Затем Б посылает (y1,y2) А.
       А, получив зашифрованное сообщение, восстанавливает его:
                               m = (y1α mod p) ⊕ y2.
       Известен вариант схемы, когда операция ⊕ заменяется на умноже-
ние по модулю p. Это удобнее в том смысле, что в первом случае текст
необходимо разбивать на блоки той же длины, что и число ykmod p. Во
втором случае этого не требуется. Значит можно обрабатывать блоки
текста заранее заданной фиксированной длины меньшей, чем число p.
Уравнение расшифровки в этом случае будет иметь вид:
                                  m=y2/y1k mod p.
       Пример 71. Пусть абоненты A и B решили установить между
собой скрытую связь с открытым ключом на базе алгоритма Эль-Гамаля.
       Абонент A выбрал простое число р=1125899906842679 и целое
число n = 745819352812378.
       Затем абонент А генерирует секретный ключ α = 725391906243661,
и вычисляет открытый ключ y = nαmod p =745819352812378725391906243661
mod 1125899906842679=1124568734648807 и передает числа p, n и y в от-
крытый канал.
       Пусть абонент Б хочет послать А сообщение m=4567345. Он выби-
рает случайное число k= 51394216073587 меньшее p и вычисляет: y1=
nkmodp =440797012227888, ykmodp = 112456873464880751394216073587=3804 8
8279630195, y2= m⊕yk=380488283459650 и посылает А пару (y1, y2).
Абонент А, получив зашифрованное сообщение, восстанавливает его:
m=(y1α mod p ⊕y2.=(440797012227888725391906243661 mod 1125899906842679
⊕ 380488283459650)= 380488279630195⊕ 380488283459650=4567345.♦
       При использовании метода Эль-Гамаля в системе открытого шиф-
рования с модулем модулем p из 150 знаков достигается та же степень
защиты, что для алгоритма RSA с модулем из 200 знаков. Это позволяет в
5-7 раз увеличить скорость обработки информации. Однако в таком вари-
анте открытого шифрования нет подтверждения подлинности сообщений.
       Однако схема Эль-Гамаля не лишена определенных недостатков.
Среди них можно выделить следующие.
       1.Отсутствие семантической стойкости. Если g – примитивный эле-
мент GF(p), то за полиномиальное время можно определить, является ли


88


некоторое число x квадратичным вычетом, или нет. Это делается возведе-
нием в степень x(p-1)/2mod p. Если результат равен 1, то x - квадратичный
вычет, если –1, то x квадратичный невычет. Затем пассивный противник
проверяет, являются ли gk и gt квадратичными вычетами. gkt будет квадра-
тичными вычетом тогда и только тогда, когда gk и gt являются квадратич-
ными вычетами. Если это так, то y2= mykmod p будет квадратичным выче-
том тогда и только тогда, когда сообщение m будет само квадратичным
вычетом. То есть, пассивный противник будет иметь некоторую информа-
цию об открытом тексте имея лишь шифрованный текст и открытый
ключ.
       2. Делимость шифра. Если дан шифрованный текст (y1,y2), то мож-
но получить другой шифрованный текст, изменив только вторую часть
сообщения. Действительно, умножив y2 на gu (u≠0), мы получим шифро-
текст для другого сообщения m1=mgu.
       Для защиты от подобных атак Шнорром и Якобсоном было пред-
ложено объединить схему шифрования Эль-Гамаля с цифровой подписью
Шнорра. Это позволяет не только шифровать сообщение, но и аутентифи-
цировать его.
       В заключении заметим, что алгоритм цифровой подписи DSA, раз-
работанный NIST (National Institute of Standard and Technology) и являю-
щийся частью стандарта DSS, опирается на рассмотренный метод.

6.8. КРИПТОСИСТЕМЫ НА БАЗЕ ЭЛЛИПТИЧЕСКИХ
КРИВЫХ

        Рассмотренная выше криптосистема Эль-Гамаля, базируется на
том, что задача логарифмирования в конечном поле является достаточно
сложной с вычислительной точки зрения. Однако конечные поля являются
не единственными алгебраическими структурами, в которых может быть
поставлена задача вычисления дискретного логарифма. В 1985 году Коб-
лиц и Миллер (причем независимо друг от друга) предложили использо-
вать для построения криптосистем алгебраические структуры, определен-
ные на множестве точек эллиптической кривой (ЭК). Рассмотрим опреде-
ление ЭК над полями Галуа.
        Пусть p>3 простое число, a,b∈GF(p), такие, что 4a2+27b2≠0.
Эллиптической кривой E над полем GF(p) называется множество решений
(x,y) уравнения:
                            y2 = x3 +ax+b mod(p)                   (13)
над полем GF(p) вместе с дополнительной точкой ∞, называемой точкой в
бесконечности.
        Представление ЭК в виде уравнения (13) носит название эллипти-
ческой кривой в форме Веерштрасса.


                                                                     89


       Если обозначить количество точек на кривой E через NE. Тогда,
согласно теореме Хассе, NE=p+1-t, где |t|≤2(p)0.5.
       NE называется порядком кривой E, а – t следом кривой E.
       Для точек на кривой вводится бинарная операция сложения, кото-
рая играет ту же роль, что и операция умножения в криптосистемах RSA и
Эль-Гамаля:
  1. ∞+∞=∞
  2. Для любых (x,y)∈E, (x,y)+ ∞=(x,y)
  3. Для любых (x,y)∈E, (x,y)+(x,-y)=∞
  4. Для любых (x1,y1)∈E, и (x2,y2)∈E, x1≠x2, (x1,y1)+(x2,y2)=(x3,y3),
     где x3=λ2- x1- x2, y3=λ(x1-x3)-y1, λ= (y2-y1)/(x2-x1).
  5. Для любых (x1,y1)∈E, и y1≠0, (x1,y1)+(x1,y1)=(x3,y3),
     где x3=λ2-2x1, y3=λ(x1-x3)-y1, λ= (3 x12+a)/2y1.
       Множество точек на кривой E, с заданным таким образом бинар-
ной операцией, образует абелеву группу.
       Если NE=p+1,то E называется суперсингулярной.
       Пользуясь операцией сложения точек на кривой, можно естествен-
ным образом ввести операцию умножения точки P∈E на произвольное
целое число k:
                                     kP=P+P+…+P.
       Где операция выполняется k раз.
       Построим теперь одностороннюю функцию, на базе которой будем
строить криптосистему.
       Пусть E – ЭК, точка P∈E. Возьмем k∈Z, причем k<NE. В качестве
прямой функции выберем произведение kP. Для его вычисления по опти-
мальному алгоритму требуется не более 2⋅log2k операций сложения. Об-
ратную задачу определим так: по заданным ЭК, точке P∈E и произведе-
нии kP найти k. В настоящее время такая задача за полиномиальное время
неразрешима.
       Теперь рассмотрим криптографический протокол, аналогичный
протоколу Диффи-Хелмана.
       Для установления секретной связи два пользователя A и B выбира-
ют ЭК E и точку P на ней. Затем A и B генерируют независимо друг от
друга по секретному числу α и β. Затем пользователь A вычисляет произ-
ведение αP и пересылает его B, а пользователь B вычисляет βP и пересы-
лает его A. При этом параметры кривой, координаты точки на ней, значе-
ния произведений являются открытыми и могут передаваться по незащи-
щенным каналам связи. Далее пользователь A умножает присланное зна-
чение βP на α, получив после этого αβP, пользователь B умножает при-
сланное значение αP на β, получая такой же результат – αβP. Таким обра-
зом, оба пользователя получили общее секретное значение (координаты
точки αβP на ЭК), которое они могут использовать для получения сек-
ретного ключа шифрования. Необходимо отметить, что криптоаналитику


90


для восстановления ключа потребуется решить сложную с вычислитель-
ной точки зрения математическую задачу восстановления α и β по из-
вестным E, P, αP и βP.
       Пример 72. Пусть абоненты A и B решили провести передачу со-
общений используя криптосистему на базе ЭК. Для этого они выбрали ЭК
                     E: y2 = x3 +157x+223 mod(743),
 и точку P(117,692) на ней. Затем A генерирует секретное число α = 735.
Пользователь B генерирует секретное число β = 529.
       Затем пользователь A вычисляет произведение αP = (517,488) и пе-
ресылает его B, а пользователь B вычисляет βP = (472,687) и пересылает
его A. Далее пользователь A умножает присланное значение βP на α,
получив после этого αβP=(332,590). Пользователь B умножает прислан-
ное значение αP на β, получая такой же результат – αβP=(332,590). Таким
образом, оба пользователя получили общее секретное значение (коорди-
наты точки αβP на ЭК), которое они будут использовать в качестве обще-
го секретного ключа. ♦
       Переход на "эллиптическую" криптографию позволяет сохранить
приемлемую длину ключа при резком (на порядки) увеличении стойкости
криптосистем. Появление "эллиптической" криптографии и было обуслов-
лено именно этой причиной.



    
Яндекс цитирования Яндекс.Метрика