Методы и средства криптографической защиты информации

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

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

Если А и В не доверяют алгоритмам друг друга, они могут использовать их последовательно. Для потоковых алгоритмов их порядок не имеет значения. При использовании блочных алгоритмов А может сначала использовать алгоритм А, а затем алгоритм В. В, который больше доверяет алгоритму В, может использовать алгоритм В перед алгоритмом А. Между алгоритмами они могут вставить хороший потоковый шифр. Это не причинит вреда и может значительно повысить безопасность.

Ключи для каждого алгоритма последовательности должны быть независимыми . Если алгоритм А использует 64-битовый ключ, а алгоритм В - 128-битовый ключ, то получившаяся последовательность должна использовать 192-битовый ключ. При использовании зависимых ключей у пессимистов гораздо больше шансов оказаться правыми.

Объединение нескольких блочных алгоритмов

Вот другой способ объединить несколько блочных алгоритмов, безопасность которого гарантировано будет, по крайней мере, не меньше, чем безопасность обоих алгоритмов. Попытка, на наш взгляд, достаточно успешная, прояснить этот вопрос предпринята в статье [18] А.М. Кукарцевым с соавторами. Для двух алгоритмов (и двух независимых ключей):

(1) Генерируется строка случайных битов R того же размера, что и сообщение М.

(2) R шифруется первым алгоритмом.

(3) МR шифруется вторым алгоритмом.

(4) Шифротекст является объединением результатов этапов (2) и (3).

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

Этот метод можно расширить для нескольких алгоритмов, но добавление каждого алгоритма увеличивает шифротекст.

2.7 Алгоритмы с открытыми ключами

Концепция криптографии с открытыми ключами была выдвинута Уитфилдом Диффи (Whitfield Diffie) и Мартином Хеллманом (Martin Hellman), и независимо Ральфом Мерклом (Ralph Merkle). Их вкладом в криптографию было убеждение, что ключи можно использовать парами - ключ шифрования и ключ дешифрирования - и что может быть невозможно получить один ключ из другого. Диффи и Хеллман впервые представили эту идею на Национальной компьютерной конференции (National Computer Conference) 1976 года, через несколько месяцев была опубликована их основополагающая работа "New Directions in Cryptography" ("Новые направления в криптографии"). (Из-за бесстрастного процесса публикации первый вклад Меркла в эту область появился только в 1978 году.)

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

Немногие алгоритмы являются и безопасными, и практичными. Обычно эти алгоритмы основаны на одной из трудных проблем. Некоторые из этих безопасных и практичных алгоритмов подходят только для распределения ключей. Другие подходят для шифрования (и для распределения ключей). Третьи полезны только для цифровых подписей. Только три алгоритма хорошо работают как при шифровании, так и для цифровой подписи: RSA, EIGamal и Rabin. Все эти алгоритмы медленны. Они шифруют и дешифрируют данные намного медленнее, чем симметричные алгоритмы. Обычно их скорость недостаточна для шифрования больших объемов данных.

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

Так как у криптоаналитика есть доступ к открытому ключу, он всегда может выбрать для шифрования любое сообщение. Это означает, что криптоаналитик при заданном С=Е_K(Р) может попробовать угадать значение Р и легко проверить свою догадку. Это является серьезной проблемой, если количество возможных открытых текстов настолько мало, что делает возможным исчерпывающий поиск, но эту проблему легко можно решить, дополняя сообщения строкой случайных битов. Это приводит к тому, что идентичным открытым текстам соответствуют различные шифротексты.

Это особенно важно, если алгоритм с открытым ключом используется для шифрования сеансового ключа. Ева может создать базу данных всех возможных сеансовых ключей, зашифрованных открытым ключом Боба . Конечно, это потребует много времени и памяти, но взлом грубой силой разрешенного к экспорту 40-битового ключа или 56-битового ключа DES потребует намного больше времени и памяти. Как только Ева создаст такую базу данных, она получит ключ Боба и сможет читать его почту.

Алгоритмы с открытыми ключами спроектированы так, чтобы противостоять вскрытиям с выбранным открытым текстом. Их безопасность основана как на трудности получения секретного ключа по открытому, так и на трудности получить открытый текст по шифротексту. Однако большинство алгоритмов с открытым ключом особенно чувствительны к вскрытию с выбранным шифротекстом.

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

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

2.7.1 Алгоритмы рюкзака

Первым алгоритмом для обобщенного шифрования с открытым ключом стал алгоритм рюкзака, разработанный Ральфом Мерклом и Мартином Хеллманом. Он мог быть использован только для шифрования, хотя позднее Ади Шамир адаптировал систему для цифровой подписи. Безопасность алгоритмов рюкзака опирается на проблему рюкзака, NP-полную проблему. Хотя позже было обнаружено, что этот алгоритм небезопасен, его стоит изучить, так как он демонстрирует возможность применения NP-полной проблемы в криптографии с открытыми ключами.

Проблема рюкзака несложна. Дана куча предметов различной массы, можно ли положить некоторые из этих предметов в рюкзак так, чтобы масса рюкзака стала равна определенному значению? Более формально, дан набор значений M₁, М₂,. . ., М_n и сумма S, вычислить значения b_i, такие что

S = b₁М₁ + b₂М₂ +...+ b_пМ_п

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

Например, массы предметов могут иметь значения 1, 5, 6, 11, 14 и 20. Вы можете упаковать рюкзак так, чтобы его масса стала равна 22, использовав массы 5, 6 и 11. Невозможно упаковать рюкзак так, чтобы его масса была равна 24. В общем случае время, необходимое для решения этой проблемы, с ростом количества предметов в куче растет экспоненциально.

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

Открытый текст	111001	010110	000000	011000
Рюкзак	1 5 6 11 14 20	1 5 6 11 14 20	1 5 6 11 14 20	1 5 6 11 14 20
Шифротекст	1+5+6+20=32	5+11+14=30	0=0	5+6=11

Рис. 13 Шифрование с рюкзаками

Фокус в том, что на самом деле существуют две различные проблемы рюкзака, одна решается за линейное время, а другая, как считается, - нет. Легкую проблему можно превратить в трудную. Открытый ключ представляет собой трудную проблему, которую легко использовать для шифрования, но невозможно для дешифрирования сообщений. Закрытый ключ является легкой проблемой, давая простой способ дешифрировать сообщения. Тому, кто не знает закрытый ключ, придется попытаться решить трудную проблему рюкзака .

Сверхвозрастающие рюкзаки

Что такое легкая проблема рюкзака? Если перечень масс представляет собой сверхвозрастающую последовательность, то полученную проблему рюкзака легко решить. Сверхвозрастающая последовательность - это последовательность, в которой каждой член больше суммы всех предыдущих членов. Например, последовательность {1,3,6,13,27,52} является сверхвозрастающей, а {1,3,4,9, 15,25} - нет.

Решение сверхвозрастающего рюкзака найти легко. Возьмите полный вес и сравните его с самым большим числом последовательности. Если полный вес меньше, чем это число, то его не кладут в рюкзак. Если полный вес больше или равен этому числу, то оно кладется в рюкзак. Уменьшим массу рюкзака на это значение и перейдем к следующему по величине числу последовательности. Будем повторять, пока процесс не закончится. Если полный вес уменьшится до нуля, то решение найдено. В противном случае нет.

Например, пусть полный вес рюкзака - 70, а последовательность весов {2,3,6, 13,27,52}. Самый большой вес, 52, меньше 70, поэтому кладем 52 в рюкзак. Вычитая 52 из 70, получаем 18. Следующий вес, 27, больше 18, поэтому 27 в рюкзак не кладется, вес, 13,меньше 18, поэтому кладем 13 в рюкзак. Вычитая 13 из 18, получаем 5. Следующий вес, 6, больше 5, поэтому 6 не кладется в рюкзак. Продолжение этого процесса покажет, что и 2, и 3 кладутся в рюкзак, и полный вес уменьшается до 0, что сообщает о найденном решении. Если бы это был блок шифрования методом рюкзака Меркла-Хеллмана, открытый текст, полученный из значения шифротекста 70, был бы равен 110101.

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

Алгоритм Меркла-Хеллмана основан на этом свойстве. Закрытый ключ является последовательностью весов проблемы сверхвозрастающего рюкзака. Открытый ключ - это последовательность весов проблемы нормального рюкзака с тем же решением. Меркл и Хеллман, используя модульную арифметику, разработали способ преобразования проблемы сверхвозрастающего рюкзака в проблему нормального рюкзака.

Создание открытого ключа из закрытого

Рассмотрим работу алгоритма, не углубляясь в теорию чисел: чтобы получить нормальную последовательность рюкзака, возьмем сверхвозрастающую последовательность рюкзака, например, {2,3,6,13,27,52}, и умножим по модулю т все значения на число п. Значение модуля должно быть больше суммы всех чисел последовательности, например, 105. Множитель должен быть взаимно простым числом с модулем, например, 31. Нормальной последовательностью рюкзака будет

2*31 mod 105 = 62

3*31 mod 105 = 93

6*31 mod 105 = 81

13*31 mod 105 = 88

27*31 mod 105 = 102

52*31 mod 105 = 37

Итого- {62,93,81,88,102,37}.

Сверхвозрастающая последовательность рюкзака является закрытым ключом, а нормальная последовательность рюкзака - открытым.

Шифрование

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

Например, если сообщение в бинарном виде выглядит как 011000110101101110, шифрование, использующее предыдущую последовательность рюкзака, будет происходить следующим образом:

сообщение = 011000 110101 101110

011000 соответствует 93 + 81 = 174

110101 соответствует 62 + 93 + 88 + 37 = 280

101110 соответствует 62 + 81 + 88 + 102 = 333

Шифротекстом будет последовательность 174,280,333

Дешифрирование

Законный получатель данного сообщения знает закрытый ключ: оригинальную сверхвозрастающую поcледовательность, а также значения п и т, использованные для превращения ее в нормальную последовательность рюкзака. Для дешифрирования сообщения получатель должен сначала определить n^-1, такое что n(n^-1)l (mod т). Каждое значение щифротекста умножается на п^-1 mod m, а затем разделяется с помощью закрытого ключа, чтобы получить значения открытого текста.

В нашем примере сверхвозрастающая последовательность - {2,3,6,13,27,52}, т равно 105, а и - 31. Шифротекстом служит 174,280,333. В этом случае п^-1 равно 61, поэтому значения шифротекста должны быть умножены на 61 mod 105.

174*61 mod 105 = 9 = 3 + 6, что соответствует 011000

280*61 mod 105 = 70 = 2 + 3 + 13 + 52, что соответствует 110101

333*61 mod 105 = 48 = 2 + 6 + 13 + 27, что соответствует 101110

Расшифрованным открытым текстом является 011000 110101 101110.

Практические реализации

Для последовательности из шести элементов нетрудно решить задачу рюкзака, даже если последовательность не является сверхвозрастающей. Реальные рюкзаки должны содержать не менее 250 элементов. Длина каждого члена сверхвозрастающей последовательности должна быть где-то между 200 и 400 битами, а длина модуля должна быть от 100 до 200 битов. Для получения этих значений практические реализации используют генераторы случайной последовательности.

Вскрывать подобные рюкзаки при помощи грубой силы бесполезно. Если компьютер может проверять миллион вариантов в секунду, проверка всех возможных вариантов рюкзака потребует свыше 10^4б лет. Даже миллион машин, работающих параллельно, не успеет решить эту задачу до превращения солнца в сверхновую звезду.

Безопасность метода рюкзака

Взломали криптосистему, основанную на проблеме рюкзака, не миллион машин, а пара криптографов. Сначала был раскрыт единственный бит открытого текста. Затем Шамир показал, что в определенных обстоятельствах рюкзак может быть взломан. Были и другие достижения - но никто не мог взломать систему Мартина-Хеллмана в общем случае. Наконец Шамир и Циппел (Zippel), обнаружили слабые места в преобразовании, что позволило им восстановить сверхвозрастающую последовательность рюкзака по нормальной. На конференции, где докладывались эти результаты, вскрытие было продемонстрировано по стадиям на компьютере Apple II.

Варианты рюкзака

После вскрытия оригинальной схемы Меркла-Хеллмана было предложено множество других систем на принципе рюкзака: несколько последовательных рюкзаков, рюкзаки Грэм-Шамира (Graham-Shamir), и другие. Все они были проанализированы и взломаны, как правило, с использованием одних и тех же криптографических методов.

Были предложены и другие алгоритмы, использующие похожие идеи, но все они тоже были взломаны. Криптосистема Lu-Lee была взломана, ее модификация также оказалась небезопасной. Вскрытия. Криптосистема Pieprzyk была взломана аналогичным образом.

Хотя вариант алгоритма рюкзака в настоящее время безопасен - алгоритм рюкзака Char-Rivest, несмотря на "специализированное вскрытие" - количество необходимых вычислений делает его намного менее полезным, чем другие рассмотренные здесь алгоритмы. Вариант, названный Powerline System (система электропитания) небезопасен. Более того, учитывая легкость с которой пали все остальные варианты, доверять устоявшим пока вариантом, по видимому, неосторожно.

2.7.2 Алгоритм RSA

Концепция криптографии с открытым ключом была предложена Уитфилдом Диффи (Whitfield Diffie) и Мартином Хелллманом (Martin Hellman), и, независимо, Ральфом Мерклом (Ralph Merkle) Основная идея: использовать ключи парами, состоящими из ключа зашифрования и ключа расшифрования, которые невозможно вычислить один из другого. В 1976 году вышла основополагающая работа [19]. С 1976 г. Было создано много алгоритмов, использующих концепцию открытых ключей. Алгоритм является общедоступным, нет необходимости в секретных каналах связи. Общая схема выглядит следующим образом:

1. Каждый пользователь генерирует пару ключей: один для шифрования и один для дешифрования.

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

3. Если пользователь A собирается послать сообщение пользователю B, он шифрует сообщение открытым ключом пользователя B.

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

Описание алгоритма RSA

В 1978 г. Появилась работа [20], в которой Рон Райвест(Ron Rivest), Ади Шамир(Adi Shamir) и Лен Адлеман(Len Adleman) предложили алгоритм с открытым ключом. Схема Райвеста-Шамира-Адлемана (RSA) получила широкое распространение.

Опишем процесс шифрования. Исходный текст должен быть переведен в числовую форму. Метод преобразования текста в числовую форму считается известным. В результате текст представляется в виде одного большого числа. Затем полученное число разбивается на части (блоки) так, чтобы каждая из них была числом в промежутке [0,N-1], о выборе N -- см. ниже. Процесс шифрования одинаков для каждого блока. Поэтому мы можем считать, что блок исходного текста представлен числом x, .

Каждый абонент вырабатывает свою пару ключей. Для этого он генерирует два больших простых числа p и q, вычисляет произведение . Затем он вырабатывает случайное число e, взаимно простое со значением функцией Эйлера от числа N, и находит число d из условия . Так как , то такое число d существует и единственно. Пару (N,e) он объявляет открытым ключом и помещает в открытый доступ. Пара (N,d) является секретным ключом. Для расшифрования достаточно знать секретный ключ. Числа p, q, в дальнейшем не нужны, поэтому их можно уничтожить.

Пользователь A, отправляющий сообщение x абоненту B, выбирает из открытого каталога пару (N,e) абонента B и вычисляет шифрованное сообщение . Чтобы получить исходный текст, абонент B вычисляет . Так как , т.е. , k -- целое, то применяя теорему Эйлера получим:

.

Пример 1. Пусть p = 7, q = 17. Тогда N = 7•17 = 119, . Выбираем e такое, что: . Пусть в нашем случае e = 5. Находим d: . Получаем d = 77, т.к. 77•5 = 4•96+1. Открытый ключ: (119,5). Личный ключ: (119,77). Пусть, например, X = 19. Для зашифрования число 19 возводим в степень 5 по модулю 119. Имеем: 19⁵ = 2476099, и остаток от деления 2476099 на 119 равен 66. Итак, y = 19⁵ mod 119 = 66. Расшифрование: x=66⁷mod119=19.

О вычислениях

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

О стойкости RSA

Безопасность алгоритма RSA основана на трудоемкости разложения на множители больших чисел. Современное состояние технических средств разложения на множители таково, что число, содержащее 193 десятичных знака, факторизовано в 2005 году. Следовательно, выбираемое N должно быть больше. Большинство общепринятых алгоритмов вычисления простых чисел p и q носят вероятностный характер.

О выборе чисел p и q.

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

Кроме разрядности p и q, к ним предъявляются следующие дополнительные требования:

1. Числа не должны содержаться в списках известных больших простых чисел.

2. Они не должны быть близкими, так как иначе можно воспользоваться для факторизации N методом Ферма и решить уравнение .

3. В алгоритме RSA всегда есть эквивалентные по расшифрованию показатели степеней, например d и . При этом эквивалентных решений тем больше, чем больше (p-1,q-1). В лучшем случае (p-1,q-1) = 2, p = 2t+1, q = 2s+1, где s,t -- нечетные числа с условием (s,t) = 1.

Чтобы исключить возможность применения методов факторизации накладывают следующее ограничение. Числа p-1, p+1, q-1, q+1 не должны разлагаться в произведение маленьких простых множителей, должны содержать в качестве сомножителя хотя бы одно большое простое число. В 1978 г. Райвест сформулировал наиболее сильные требования. Числа должны быть простыми, причем p₁-1 и q₁-1не должны разлагаться в произведение маленьких простых.

О выборе параметров e и d

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

Однако, выбор малых параметров е или d представляется небезопасным по ряду соображений. Если малым является секретный параметр d, то можно применить метод перебора малых значений до получения искомого числа d.

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

Другая аналогичная ситуация может сложиться, когда у нескольких абонентов используется одинаковая экспонента е. Тогда становится возможна атака на основе китайской теореме об остатках (см. ниже).

Подготовка текста к шифрованию

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

Пример 2. Для простоты предположим, что текст сообщения содержит только слова, записанные только заглавными буквами. Первый шаг состоит в замене каждой буквы сообщения числом. Пусть наша таблица замен имеет вид:

Табл. 14. Таблица замен

А	Б	В	Г	Д	Е	Ж	З	И	Й	К	Л	М	Н	О	П	Р	С	Т	У	Ф
10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30

Х	Ц	Ч	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я
31	32	33	34	35	36	37	38	39	40	41

Пробел между словами будем заменять числом 99.

Например, пусть открытый текст -- это девиз "ПОЗНАЙ СЕБЯ". Тогда его цифровое представление имеет вид: 2524172310199927151141

Пусть в нашем примере p = 149, q = 157, тогда N = 23393. Поэтому цифровое представление открытого текста нужно разбить на блоки, меньшие, чем 23393. Одно из таких разбиений: 2524 - 1723 - 10199 - 9271 - 511 - 41

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

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

Обратите внимание на то, что в этом примере мы каждую букву кодируем двузначным числом. Это сделано для предотвращения неоднозначности. Если бы мы пронумеровали буквы не по порядку, начиная с 1, т.е. А соответствует 1, Б -- 2 и.т.д., то мы не смогли бы сказать, блок 12 обозначает пару букв АБ или букву Л, двенадцатую букву алфавита. Конечно, для кодирования можно использовать любые однозначные соответствия между буквами и числами, например, ASCII-кодировку, что чаще всего и делается.

Продолжим наш пример. Мы выбираем p = 149, q = 157, вычисляем . Теперь нужно выбрать число e, взаимно простое с . Наименьшее простое, не делящее , равно5. Положим e = 5. Зашифруем первый блок сообщения. Вычисляем 2524⁵ mod 23393 = 22752. Далее, 1723⁵ mod 23393 = 6198

10199⁵ mod 23393 = 14204,

9271⁵ mod 23393 = 23191,

511⁵ mod 23393 = 10723,

41⁵ mod 23393 = 14065.

Теперь шифрованный текст имеет вид:

22752619814204231911072314065

В нашем примере N = 23393, e = 5. Применив алгоритм Эвклида к числам и e=5, найдем . Значит, для расшифровки блоков шифртекста мы должны возвести этот блок в степень 13583 по модулю 23393. В примере первый блок шифртекста -- число 22752. Вычисляем: 22752¹³⁸⁵³ mod 23393 = 2524.

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

Атаки на RSA

Для дешифрации необходимо по известным N, e и шифртексту y найти такое , что .

Можно попытаться решить сравнение при конкретных y, затем использовать гомоморфность отображения D(x).

Один из возможных способов следующий. Пусть имеется набор пар с условием . Пусть 1<y<N, (y,N) = 1. Если каким-либо образом удалось представить y в виде: с целыми s_k, то будет решением сравнения .

Пример 3. У нас есть в наличии открытый ключ N = 31459, e = 5 и набор пар соответствующих друг другу исходных и зашифрованных сообщений: (23,18707), (755,26871), (631,6384). Требуется расшифровать шифртекст y = 11638. Для этого представим y в виде . Отсюда легко вычислить исходное сообщение: .

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

Взлом RSA при неудачном выборе параметров криптосистемы

Само по себе использование RSA не обеспечивает безопасности. Дело ещё в деталях реализации. Приведём ряд примеров. Для простоты вычислений будем работать с небольшими числами. Наша цель -- показать особенности, не зависящие от размера.

Пример 4. Пусть пользователь выбрал N = 2047, e = 179, d = 411. Так как 2047 = 23•89, а имеют наименьшее общее кратное 88, то любой обратный к 179 по модулю 88, например, 59, будет действовать как d.

Пример 5. Число N = 536813567 является произведением простого числа Мерсенна 8191 и простого числа Ферма 65537. Это очень плохой выбор.

Пример 6. Число 23360947609 является очень плохим выбором для N из-за того, что два его простых делителя слишком близки к друг другу. Действительно, пусть p>q, имеем: . Обозначим: . Так как S мало, то t -- целое число, лишь немного большее , причем t² - N является полным квадратом. Проверяем подряд целые числа . В нашем примере: t₁ = 152843, t₂ = 152844, t₃ = 152845, и , тогда . Таким образом мы с третьей попытки нашли p и q. Количество попыток, необходимых для факторизации N, можно при известных p и q вычислить по следующей формуле: , где [x] -- операция округления x до ближайшего целого числа.

Атака повторным шифрованием

Строим последовательность: . Итак, , а так как , то существует такое натуральное число m, что . Но тогда , отсюда следует: , значит, y_m-1 -- решение сравнения .

Пример 7. Пусть у нас имеется открытый ключ N =84517 , e = 397 и зашифрованное им сообщение y = 8646. Необходимо найти исходный текст x. Возведем y в степень e и получим y₂ = 37043. Будем повторять операцию до тех пор, пока не получим y_n = y. y_n-1 -- искомое сообщение: y₃ = 5569, y₄ = 61833, y₅ = 83891, y₆ = 16137, y₇ = 8646. y₆ является решением сравнения , а, следовательно, искомым сообщением x.

Замечание. Анализ метода повторного шифрования хорошо показывает необходимость соблюдения требований на выбор p и q для обеспечения стойкости. В данном примере d = 82225. Неудачный выбор криптосистемы привел к тому, что атака методом повторного шифрования дала результат почти сразу, тогда как нахождение d потребовало бы на порядок больших вычислений.

Атака на основе Китайской теоремы об остатках.

Как отмечалось ранее, системы шифрования с открытыми ключами работают сравнительно медленно. Для повышения скорости шифрования RSA на практике используют малую экспоненту зашифрования.

Если выбрать число е небольшим или таким, чтобы в его двоичной записи было мало единиц, то процедуру шифрования можно значительно ускорить. Например, выбрав е - 3 (при этом ни р -- 1, ни q -- 1 не должны делиться на 3), мы сможем реализовать шифрование с помощью одного возведения в квадрат по модулю N и одного перемножения. Выбрав 65537 -- число, двоичная запись которого содержит только две 1, мы сможем реализовать шифрование с помощью 16 возведений в квадрат по модулю N и одного перемножения. Если экспонента е выбирается случайно, то реализация шифрования по алгоритму RSA потребует s возведений в квадрат по модулю N и в среднем s/2 умножений по тому же модулю, где 5 длина двоичной записи числа N . Вместе с тем выбор небольшой экспоненты е может привести к негативным последствиям. Дело в том, что у нескольких корреспондентов могут оказаться одинаковые экспоненты е.

Пусть, например, три корреспондента имеют попарно взаимно простые модули N₁, N₂, N₃ и общую экспоненту е = 3. Если еще один пользователь посылает им некое циркулярное сообщение x, то криптоаналитик противника может получить в свое распоряжение три шифрованных текста . Далее он может найти решение системы сравнений

лежащее в интервале 0 < y < N₁•N₂•N₃. По китайской теореме об остатках такое решение единственно, а так как , то y = x³. Само x можно найти, вычисляя кубический корень: .

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

Пример 8. Три пользователя имеют модули N₁ = 26549, N₂ = 45901, N₃ = 25351. Все пользователи используют экспоненту e = 3. Всем пользователям было послано некое сообщение x, причем, пользователи получили сообщения y₁ = 5366, y₂ = 814, y₃ = 4454. Найдем M₀ = N₁•N₂•N₃ = 30893378827799. Далее находим

m₁ = N₂•N₃ = 1163636251

m₂ = N₁•N₃ = 673043699

m₃ = N₁•N₂ = 1218625649

n₁ = m₁^-1 mod N₁ = 13533

n₂ = m₂^-1 mod N₂ = 27930

n₃ = m₃^-1 mod N₃ = 22354

S = y₁•n₁•m₁ + y₂•n₂•m₂ + y₃•n₃•m₃ = 84501028038745578 + 15301661957638980 + 121332116653000684 = 221134806649385242

S mod M₀ = 1000000000

x = (S mod M₀)^1/3 = 1000 -- исходное сообщение, отправленное пользователям.

Бесключевое чтение

Пусть два пользователя выбрали одинаковый модуль N и разные экспоненты e1 и e₂. Если один пользователь посылает им некое циркулярное сообщение x, то криптоаналитик противника может получить в свое распоряжение два шифрованных текста и . В таком случае криптоаналитик может получить исходное сообщение, используя расширенный алгоритм Евклида, находим такие, что . Отсюда получаем:

Пример 9. Два пользователя используют общий модуль N = 137759, но разные взаимно простые экспоненты e₁ = 191 и e₂ = 233. Пользователи получили шифртексты y₁ = 60197 и y₂ = 63656, которые содержат одно и то же сообщение. Найдем исходное сообщение методом бесключевого чтения. Т.к. e₁ и e₂ взаимно просты, найдем такие r и s, что . С помощью расширенного алгоритма Евклида находим r = 61, s = -50. Искомое сообщение

Выводы

Как видно из приведенных выше примеров (а также из примеров выполнения заданий лабораторных работ) выбор параметров криптосистемы является ответственной задачей. Параметры необходимо выбирать в строгом соответствии с требованиями. Существующими в настоящими время методами (и при использовании существующих в настоящее время вычислительных мощностей) атака на алгоритм и/или криптосистему возможна лишь при неудачном выборе параметров. В процессе выполнения заданий лабораторных работ вы убедитесь в обоснованности перечисленных требований к параметрам криптосистемы. В частности, необходимо обеспечить каждому пользователю уникальные значения p, q и уникальное значение e, удовлетворяющие требованиям.

Для тренировки в использовании алгоритма авторы рекомендуют пользоваться учебно-методическим изданием [21].

2.7.3 Алгоритм Pohlig-Hellman

Схема шифрования Pohlig-Hellman похожа на RSA. Это не симметричный алгоритм, так как для шифрования и дешифрирования используются различные ключи. Это не схема с открытым ключом, потому что ключи легко получаются один из другого, и ключ шифрования, и ключ дешифрирования должны храниться в секрете. Как и в RSA,

С = P^e mod n

P=C^dmodn

Где ed 1 (mod какое-нибудь составное число)

В отличие от RSA n не определяется с помощью двух простых чисел и остается частью закрытого ключа. Если у кого-нибудь есть е и п, он может вычислить d. He зная е или d, противник будет вынужден вычислить

е = log_pC mod n, а это является трудной проблемой.

2.7.4. Алгоритм Rabin

Безопасность схемы Рабина (Rabin) опирается на сложность поиска квадратных корней по модулю составного числа. Эта проблема аналогична разложению на множители. Вот одна из реализаций этой схемы.

Сначала выбираются два простых числа р и q, конгруэнтных 3 mod 4. Эти простые числа являются закрытым ключом, а их произведение п =pq - открытым ключом.

Для шифрования сообщения М(М должно быть меньше n), просто вычисляется С = М² mod n

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

m₁ = C^(p+l)/4 mod p

т₂ = (р - C^(p+1)/4) mod p

т₃ = C^(q+1)/4 mod q

m₄ = (q- C^(q+1)/4) mod q

Затем выбирается целые числа а = q(q^-1 mod p) и b = p(p^-1 mod q). Четырьмя возможными решениями являются:

M₁ = (am₁ + bm₃) mod n M₂ = (am₁ + bm₄) mod n M₃ = (ат₂ + bm₃) mod n M₄ = (am₂ + bm₄) mod n

Один из четырех результатов M₁, M₂, М₃ и М₄, равно М. Если сообщение написано по английски, выбрать правильное М, нетрудно. С другой стороны, если сообщение является потоком случайных битов (скажем, для генерации ключей или цифровой подписи), способа определить, какое М_i - правильное, нет. Одним из способов решить эту проблему служит добавление к сообщению перед шифрованием известного заголовка.

Алгоритм Williams. Хью Вильяме (Hugh Williams) переопределил схему Рабина, чтобы устранить эти недостатки. В его схеме р и q выбираются так, чтобы

р = 3 mod 8

q = 7 mod 8

и

N = pq

Кроме того, используется небольшое целое число, S, для которого J(S,N) = -1. (J - это символ Якоби). N и S опубликовываются. Секретным ключом является k, для которого

k = 1/2 (1/4 (p - 1)(q- 1) +1)

Для шифрования сообщения М вычисляется с₁, такое что J(M,N) =(-1)^c1 . Затем вычисляется М = (S^c1*M) mod N. Как и в схеме Рабина, С = М'² mod N. И c₂ = М' mod 2. Окончательным шифротекстом сообщения является тройка:

(С, c₁, с₂)

Для дешифрирования С, получатель вычисляет М" с помощью

С^k=М" (mod N)

Правильный знак М" определяет c₂. Наконец

М= (S^cl *(-1)^c1 *M") mod N

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

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

2.7.5 Алгоритм EIGamal

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

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

у = g^x modp

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

Шифрование EIGamal

Модификация EIGamal позволяет шифровать сообщения. Для шифрования сообщения М сначала выбирается случайное число k, взаимно простое с р - 1. Затем вычисляются

а = g^k mod p b=y^k M mod p

Пара (a,b) является шифротекстом. Обратите внимание, что шифротекст в два раза длиннее открытого текста. Для дешифрирования (а,b) вычисляется

М= b/a^x mod p

Так как а^х = g^kx (mod p) и b/а^х= у^k M/a^x = g^xk M/g^kx = M (mod p), то все работает . По сути это то же самое, что и обмен ключами Диффи-Хеллмана за исключением того, что у - это часть ключа, а при шифровании сообщение умножается на у^k.

Табл. 15 Шифрование EIGamal

Открытый ключ:
р	простое число (может быть общим для группы пользователей)
g	<p (может быть общим для группы пользователей)
у	=gx modp
Закрытый ключ:
х	<р
Шифрование:
k	выбирается случайным образом, взаимно простое с р-1
а	(шифротекст) =gk modp
b	(шифротекст)= ук М mod p
Дешифрирование:
М (открытый текст) = b/ax mod p

Табл. 16 Скорости EIGamal для различных длин модулей при 160-битовом показателе степени (на SPARC II)

	512 битов	768 битов	1024 битов
Шифрование	0.33с	0.80 с	1.09 с
Дешифрирование	0.24 с	0.58 с	0.77 с
Подпись	0.25 с	0.47 с	0.63 с
Проверка	1.37 с	5.12 с	9.30 с

2.7.6 Алгоритм МсЕLIECE

В 1978 году Роберт МакЭлис (Robert McEliece) разработал криптосистему с открытыми ключами на основе теории алгебраического кодирования. Этот алгоритм использует существование определенного класса исправляющих ошибки кодов, называемых кодами Гоппа (Goppa). Он предлагал создать код Гоппа и замаскировать его как обычный линейный код. Существует быстрый алгоритм декодирования кодов Гоппа, но общая проблема найти слово кода по данному весу в линейном двоичном коде является NP-полной. Ниже приведен только краткий обзор.

Пусть d_H(x,y) обозначает расстояние Хэмминга между х и у. Числа п, k и t служат параметрами системы.

Закрытый ключ состоит из трех частей: G' - это матрица генерации года Гоппа, исправляющего t ошибок. Р -это матрица перестановок размером п*п. S - это nonsingular матрица размером k*k.

Открытым ключом служит матрица G размером k*п: G = SG'P.

Открытый текст сообщений представляет собой строку k битов в виде k-элементного вектора над полем GF(2).

Для шифрования сообщения случайным образом выбирается n-элементный вектор z над полем GF(2), для которого расстояние Хэмминга меньше или равно t.

c=mG+z

Для дешифрирования сообщения сначала вычисляется с'= сР^-1. Затем с помощью декодирующего алгоритма для кодов Гоппа находится т', для которого d_H(m'G,c) меньше или равно t. Наконец вычисляется т = m'S^-1.

В своей оригинальной работе МакЭлис предложил значения п = 1024, t = 50 и k = 524. Это минимальные значения, требуемые для безопасности.

Хотя этот алгоритм был одним из первых алгоритмов с открытыми ключами, и вне появлялось публикаций о его успешном криптоаналитическом вскрытии, он не получил широкого признания в криптографическом соообществе. Схема на два-три порядка быстрее, чем RSA, но у нее есть ряд недостатков. Открытый ключ огромен: 2¹⁹ битов. Сильно увеличивается объем данных - шифротекст в два раза длиннее открытого текста. Ни одна из них не достигла успеха для общего случая, хотя сходство между алгоритмом МакЭлиса и алгоритмом рюкзака немного волнует.

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

Другие алгоритмы, основанные на линейных кодах, исправляющих ошибки

Алгоритм Нидеррейтера (Niederreiter) очень близок к алгоритму МакЭлиса и считает, что открытый ключ - это случайная матрица проверки четности кода, исправляющего ошибки. Закрытым ключом служит эффективный алгоритм декодирования этой матрицы.

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

2.7.7 Алгоритм LUC

Некоторые криптографы разработали обобщенные модификации RSA, которые используют различные перестановочные многочлены вместо возведения в степень. Вариант, называющийся Kravitz-Reed и использующий неприводимые двоичные многочлены, небезопасен. Винфрид Мюллер (Winfried Muller) и Вилфрид Нобауер (Wilfried Nobauer) используют полиномы Диксона (Dickson). Рудольф Лидл (Rudolph Lidl) и Мюллер обобщили этот подход в (этот вариант назван схемой Reidi), и Нобауер проанализировал его безопасность. Несмотря на все предыдущие разработки группе исследователей из Новой Зеландии удалось запатентовать эту схему в 1993 году, назвав ее LUC.

n-ое число Лукаса, V_n(P,1), определяется как V_n(P,1) = PV_n-1(P,1)-V_n-2(P,1)

В любом случае для генерации пары открытый ключ/закрытый ключ сначала выбираются два больших числа p и q. Вычисляется п, произведение p и q. Ключ шифрования е - это случайное число, взаимно простое с р-1, q-1,р+1 и q+1. Существует четыре возможных ключа дешифрирования,

d=e^-1 mod (HOK(p+l), (q+1)))

d=e^-1 mod (HOK(p+l), (q-1)))

d=e^-1 mod (HOK(p-l), (q+1)))

d=e^-1 mod (HOK(p-l), (q-1)))

где НОК означает наименьшее общее кратное.

Открытым ключом являются d и и; закрытым ключом - е и п. р и q отбрасываются.

Для шифрования сообщения Р (Р должно быть меньше и) вычисляется

С = V_e(P,l) (mod п)

А для дешифрирования:

Р ⁼ V_d(P, 1) (mod n), с соответствующим d

В лучшем случае LUC не безопаснее RSA. А недавние опубликованные результаты показывают, как взломать LUC по крайней мере в нескольких реализациях.

2.7.8 Криптосистемы на базе конечных автоматов

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

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

О производительности таких систем вкратце можно сказать следующее: они, как и система МсЕliесе, намного быстрее RSA, но требуют использования более длинных ключей. Длина ключа, обеспечивающая, как думают, безопасность, аналогичную 512-битовому RSA, равна 2792 битам, а 1024-битовому RSA - 4152 битам. В первом случае система шифрует данные со скоростью 20869 байт/с и дешифрирует данные со скоростью 17117 байт/с, работая на 80486/33 МГц.

Ренжи опубликовал три алгоритма. Первым был FAPKC0. Эта слабая система использует линейные компоненты и, главным образом, является иллюстративной. Каждая из двух серьезных систем, FAPKC1 и FAPKC2, использует один линейный и один нелинейный компонент. Последняя сложнее, она была разработана для поддержки операции проверки подлинности.

2.8 Криптосистемы на эллиптических кривых

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

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

2.8.1 Эллиптические кривые

В этом параграфе мы предполагаем, что К - поле: либо поле R вещественных чисел, либо поле Q рациональных чисел, либо поле С комплексных чисел, либо поле из q = элементов.

Определение: Пусть К -- поле характеристики, отличной от 2, 3. и (где a, b) -- кубический многочлен без кратных корней. Эллиптическая кривая над К -- это множество точек (х, у) х, у, удовлетворявших уравнению

(1)

вместе с единственным элементом, обозначаемым О и называемым "точка в бесконечности" (о ней подробнее будет сказано ниже).

Если К -- поле характеристики 2, то эллиптическая кривая над К -- это множество точек, удовлетворяющих уравнению либо типа

(2а)

либо типа

(26)

(здесь кубические многочлены в правых частях могут иметь кратные корни), вместе с "точкой в бесконечности" О.

Если К -- поле характеристики 3, то эллиптическая кривая над К -- это множество точек, удовлетворяющих уравнению

(3)

(где кубический многочлен справа не имеет кратных корней), вместе с "точкой в бесконечности" О.

Замечания.

1. Имеется общая форма уравнения эллиптической кривой, которая применима при любом поле: : в случае, когда char , ее можно привести к виду (или к виду. если К > 3). В случае, когда поле К имеет характеристику 2, это уравнение преобразуется либо к виду (2а), либо к виду (26).

2. Если F(x, у) = О -- неявное уравнение, выражающее у как функцию х в (1) (или в (2), (3)),

т. е.

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

Нетрудно показать, что условие отсутствия кратных корней у кубических многочленов в правой части в (1) и (3) эквивалентно требованию, чтобы все точки кривой были неособенными.

Эллиптические кривые над вещественными числами. Перед обсуждением конкретных примеров эллиптических кривых дат. разными полями мы отметим чрезвычайно важное свойство множества точек эллиптической кривой: они образуют абелеву группу. Чтобы объяснить наглядно, как это получается, мы временно будем полагать, что К = R. т.е. что эллиптическая кривая -- обычная плоская кривая ( с добавлением еще одной точки О "в бесконечности").