Difference between revisions of "Математические основы асимметричной криптографии"

From CryptoWiki
Jump to: navigation, search
(Решение линейных сравнений)
(Сравнения второй степени)
Line 167: Line 167:
 
Определение
 
Определение
  
  Число a называется квадратичным вычетом по mod p, если сравнение x^2[[File:Con.png]]a(mod p),  
+
  Число a называется квадратичным вычетом по mod p, если сравнение x<sup>2</sup>[[File:Con.png]]a(mod p),  
 
  (2,p)=1 имеет решение. Иначе число a называется квадратичным невычетом по mod p.
 
  (2,p)=1 имеет решение. Иначе число a называется квадратичным невычетом по mod p.
 
При этом принадлежность числа a к квадратичным вычетам по модулю p обозначается как [[File:Asim19.png]], а принадлежность к квадратичным невычетам по модулю p обозначается как [[File:Asim20.png]]
 
При этом принадлежность числа a к квадратичным вычетам по модулю p обозначается как [[File:Asim19.png]], а принадлежность к квадратичным невычетам по модулю p обозначается как [[File:Asim20.png]]
Line 173: Line 173:
 
'''Теорема. Критерий Эйлера.'''
 
'''Теорема. Критерий Эйлера.'''
  
  Если (a,p) = 1, то сравнение x^2[[File:Con.png]]a(mod p) имеет или 2 решения или ни одного в зависимости от значения числа [[File:Asim21.png]].
+
  Если (a,p) = 1, то сравнение x<sup>2</sup>[[File:Con.png]]a(mod p) имеет или 2 решения или ни одного в зависимости от значения числа [[File:Asim21.png]].
 
  Если  [[File:Asim21.png]][[File:Con.png]]1(mod p), то исходное сравнение имеет два решения, и ни одного если [[File:Asim21.png]][[File:Con.png]]-1(mod p).
 
  Если  [[File:Asim21.png]][[File:Con.png]]1(mod p), то исходное сравнение имеет два решения, и ни одного если [[File:Asim21.png]][[File:Con.png]]-1(mod p).
 
Доказательство
 
Доказательство

Revision as of 11:04, 22 November 2013

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

Contents

Основные задачи асимметричной криптографии. Методы их решения.(Security challenge)

Идеи и принципы асимметричной криптографии

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

Проблема распределения ключей

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

Проблема доверия

Даже если секретные ключи распределены заранее, возникает еще одна проблема. Суть ее состоит в том, что невозможно различить двух корреспондентов, обладающих одинаковыми ключами. При отсутствии доверия между сторонами схема бесполезна. Также может возникнуть проблема, если корреспондент «поделится» с кем-то ключом, не ставя вас в известность.

Сложность управления ключами в большой сети.

Проблема связана с квадратичным возрастанием числа пар ключей, которые надо генерировать, передавать, хранить и уничтожать в сети. Для сети в 10 абонентов требуется 45 ключей, для 100 уже 4950, для 1000 — 499500 и т. д.


Идеи асимметричной криптографии

Идея состоит в замене секретного ключа парой математически связанных ключей, один из которых будет открытым, а второй – закрытым, доступным только тому, кто сгенерировал пару. Преимущества: Нет необходимости в заблаговременном распределении ключей Тайну ключа обеспечивает только одна сторона Не встает проблема доверия к другой стороне


Принцип построения асимметричных криптосистем

Некоторый участник T, который хочет получать шифрованные сообщения, выбирает однонаправленную функцию с секретом Fk:X → Y с секретом k, публикует алгоритм вычисления значений функции Fk, а k оставляет в секрете. Любой пользователь A, желающий послать B секретное сообщение x ∈ X, вычисляет y = Fk (x) и посылает y по незащищенному каналу связи. Из определения однонаправленной функции с секретом следует, что только пользователь B может по y легко вычислить x, так как только T знает секрет k. Кроме того, по открытому ключу Fk вычислительно можно восстановить k, так как, если бы это было не так, то можно было бы по Fk узнать k и эффективно обратить функцию Fk, что невозможно по определению.

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

Среди математических проблем, на которых основываются криптоалгоритмы с открытым ключом: 1. проблема факторизации; 2. проблема дискретного логарифмирования; 3. проблема укладки рюкзака; 4. проблема решения систем нелинейных уравнений над конечным полем; 5. проблема вычисления коротких векторов целочисленных решеток; 6. проблема декодирования линейного кода, не имеющего видимой алгебраической, комбинаторной или иной структуры. Большинство наиболее используемых алгоритмов основываются на первых двух проблемах. Перечислим наиболее известные системы асимметричной криптографии: RSA, Меркля, DSA, ElGamal, ECC, Схема Шнорра, ГОСТ 34.10, ECDSA, ECDH, NTRU. Алгоритмы базируются, в основном, на результатах теории чисел.

Преимущества и недостатки использования систем асимметричной криптографии

Преимущества асимметричных шифров перед симметричными:

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

Недостатки алгоритма несимметричного шифрования в сравнении с симметричным:

  • В алгоритм сложнее внести изменения.
  • Хотя сообщения надежно шифруются, но получатель и отправитель самим фактом пересылки шифрованного сообщения «засвечиваются».
  • Более длинные ключи.
  • Шифрование-расшифрование с использованием пары ключей проходит на два-три порядка медленнее, чем шифрование-расшифрование того же текста симметричным алгоритмом.
  • Требуются существенно бо́льшие вычислительные ресурсы, поэтому на практике асимметричные криптосистемы используются в сочетании с другими алгоритмами

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

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

Основы теории чисел

Теория делимости

Основные понятия

Теория чисел занимается изучением свойств целых чисел.

В случае, когда частное от деления a на b - целое, обозначая его  буквой q, имеем a=bq, то есть a равно произведению b на целое q. 

При этом а назовем кратным числа b, а b - делителем числа a.


Наибольший общий делитель

Любое целое число, делящее одновременно целые a,b,c, ... , l , называется их общим делителем. 
Наибольший из общих делителей называется наибольшим общим делителем и обозначается символом (a,b, ... , l).
 Если (a,b, ... , l) = 1, то числа a,b, ... , l называются взаимно простыми.
 Если каждое из этих чисел взаимно просто с каждым  другим, тогда они называются взаимно попарно простыми. 

Теорема делимости с остатком

Для любых двух целых a,b найдутся такие q,r, где r > b, что  представляется виде  a = qb + r .
В терминологии кванторов это утверждение будет выглядеть следующим образом: Asim2.png 

Общий делитель – всякое целое, делящее одновременно целые a,b, …, t. Наибольший общий делитель (НОД) – наибольший из общих делителей. Обозначается НОД(a,b, …, t), GCD(a,b, …, t) или просто (a,b, … , t).

Теорема

Для любых r целых чисел существует  наибольший общий делитель.

Алгоритм Евклида

Для нахождения наибольшего общего делителя, а также вывода его важнейших свойств применяется алгоритм Евклида. Последний состоит в нижеследующем [Виноградов]. Пусть a и b – положительные целые числа. Согласно с теоремой делимости находим ряд равенств:

Asim3.png

Этот ряд равенств заканчивается, когда получается некоторое rn+1 = 0. Последнее неизбежно, так как ряд b,r2,r3 как ряд убывающих целых, который не может содержать более чем b положительных.

Простые числа. Основная теорема алгебры

Определение.

Число p > 1 называется простым, если оно не обладает положительными делителями, кроме 1 и p. 

Основная теорема алгебры: Любое положительное целое число m представимо в виде произведения степеней простых чисел. Asim4.png

Функция Эйлера. Сравнения в кольце целых чисел

Функция Эйлера Функция Эйлера Asim5.png определяется для всех целых положительных a и представляет собой количество чисел ряда 0,1, … , a-1, взаимно простых с a.

Сравнение в кольце целых чисел

Определение. Пусть m, a, b – целые числа, m Asim6.png 0, тогда говорят, что число a сравнимо с числом b по модулю m (обозначается Asim7.png , если

1) m делит разность a и b. m|(a-b)

2) a и b делятся на m с одинаковым остатком. a=mqa + r, b=mqb + r

3) Asim8.png

Сравнимость – бинарное отношение, причем Отношение эквивалентности.

Приведенная система вычетов

Так как сравнение является отношение эквивалентности, то все числа делятся на классы, называемые классами вычетов. Все числа, дающие одинаковые остатки относительно модуля m, сравнимы, а значит, входят в общий класс вычетов по модулю m. Взяв от каждого такого класса по одному представителю (то есть, составив трансверсал [Дискретная математика]), получим приведенную систему вычетов по модулю m. Обычно приведенную систему вычетов выделяют из наименьших неотрицательных вычетов: 0,1, … , m-1.

Теорема о количестве вычетов

Так как среди чисел приведенной системы вычетов по модулю m, а конкретно чисел 0,1, … , m-1 число взаимно простых с m есть  ,то
число чисел приведенной системы равно как и число классов, содержащих эти числа, взаимно простые с модулем, есть  .  .  

Пример. Приведенная система вычетов по модулю 42 будет 1 ,5 ,11 ,13 ,17 ,19 ,23 ,25 ,29 ,31 ,37 ,41. Свойства функции Эйлера:

Asim9.JPG

Теорема Эйлера

Пусть m – натуральное число. Тогда для Asim10.png  следует Asim11.png

Теорема Ферма

Если p-простое число, (r,p)=1,  p не делит r, то Asim12.png.

Решение линейных сравнений

Сравнения первой степени имеют вид Asim13.png . Перенеся свободный член в правую часть сравнения, и меняя обозначения коэффициентов, получим Asim14.png (№2)

При решении таких сравнений рассматривают два случая: (a,m)=1 и (a,m)=d>1 .

Если (a,m)=1 , то сравнение (№2) имеет единственное решение.

Доказательство. Сравнение может иметь не более m решений, в соответствии с количеством чисел в приведенной системе вычетов. Если x пробегает приведенную систему вычетов, то и линейная форма ax-b также пробегает приведенную систему вычетов. При этом один раз линейная форма примет то значение, которое сравнимо с нулем, так как нуль есть один из вычетов приведенной системе вычетов.

Если (a,m)=d>1 и число b не делится на d , то сравнение Asim14.png не имеет решений. Доказательство проводится методом от противного, с использованием свойств делимости.

Если (a,m)=d>1 и число b делится на d , то сравнение (№2) имеет d решений. Доказательство. Пусть a=a1d,b=b1d,m=m1d. Тогда сокращая (№2) на d , получим сравнение Asim15.png , которое равносильное сравнению (№2). Поскольку (a1,m1)=1, то последнее сравнение по предыдущей теореме имеет единственное решение - Asim16.png, то есть Asim17.png. Рассмотрим последовательность классов

Asim18.png

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

Сравнения второй степени

Определение

Число a называется квадратичным вычетом по mod p, если сравнение x2Con.pnga(mod p), 
(2,p)=1 имеет решение. Иначе число a называется квадратичным невычетом по mod p.

При этом принадлежность числа a к квадратичным вычетам по модулю p обозначается как Asim19.png, а принадлежность к квадратичным невычетам по модулю p обозначается как Asim20.png

Теорема. Критерий Эйлера.

Если (a,p) = 1, то сравнение x2Con.pnga(mod p) имеет или 2 решения или ни одного в зависимости от значения числа Asim21.png.
Если  Asim21.pngCon.png1(mod p), то исходное сравнение имеет два решения, и ни одного если Asim21.pngCon.png-1(mod p).

Доказательство

Если a возвести в степень p-1, то по теореме Ферма Asim22.png => Asim23.png. Так как произведение Asim24.png сравнимо с нулем по модулю p, значит один из множителей делится на p.

Покажем, что оба не могут одновременно делится на p.

Asim25.png, следовательно aCon.png0 (mod p). Поэтому имеет место лишь одно из сравнений. Но всякий квадратичный вычет a удовлетворяет при некотором x сравнению x^2Con.pnga(mod p) и, следовательно, удовлетворяют также и сравнению Asim22.png, которое можно получить почленным возведением в степень p-1/2 , оно не может иметь более чем p-1/2 решений. Поэтому квадратичные невычеты удовлетворяют сравнению Asim21.pngCon.png-1(mod p). Доказано

Теорема Эйлера

Произведение двух квадратичных вычетов или двух невычетов есть вычет, произведение вычета на невычет есть невычет.

Символ Лежандра

Символ Лежандра определяется следующим образом:

Asim26.png

Ввиду критерия Эйлера очевидно, что Asim27.png.

Далее мы приведем важнейшие свойства символа Лежандра, которые позволяют быстро вычислять этот символ, а следовательно решать вопрос о решении сравнения x^2Con.pnga(mod p).

Свойства символа Лежандра:

Asim28.JPG

Показатели. Первообразные корни

Определение (Виноградов).

 Показателем, которому a принадлежит по модулю m называется минимальное  j, такое что a^jCon.png1(mod m)  .

Определение (Бухштаб).

 Показателем a по модулю m называется  минимальное j, такое что a^jCon.png1(mod m) .

Определение (Айерлэнд).

 Число a имеет порядок j по модулю m, если j – наименьшее из чисел, такое что a^jCon.png1(mod m) . Обозначается   Asim29.png.

Определение.

 Первообразным корнем по модулю m называется такое число a, порядок которого равен значению функции Эйлера по данному модулю, то есть Asim30.png

Утверждение №1

Asim31.png

Доказательство.

Пусть Asim32.png Тогда Asim33.png1(mod m). Противоречие. Аналогично рассматривается случай Asim34.png Доказано.

Утверждение №2

Рассмотрим последовательность {Asim35.png}, где Asim36.png . Тогда Asim37.png , при Asim38.png.

Доказательство.

Пусть Asim39.png. Так как (a,m)=1, в кольце вычетов по модулю m существует элемент обратный к a, то есть a^(-1) . Тогда сравнение можно умножить справа на a^(-k). Получаем Asim40.png , что противоречит начальным условиям. Доказано.

Утверждение №3

Если Asim36.png , то Asim41.png выполняется тогда и только тогда, когда j сравнимо c j1 по модулю Delta.png. Частным случаем будет Asim42.png .

Доказательство.

Докажем необходимость. Asim43.PNG , где Asim44.png Asim45.png . Учитывая то, что Asim46.png, получаем Asim47.png, то есть Asim48.png.

Докажем достаточность.

Asim49.pngAsim50.png

Доказано.

Следствие: Asim51.png

Доказательство

Asim52.png Доказано.

Теорема Гаусса

Первообразные корни существуют только для  m = 2,4,Asim53.png,  этих корней ровно Asim54.png.

Если a – первообразный корень модулю m, то все первообразные имеют вид Asim55.png

Индексы (дискретные логарифмы) и их свойства

Пусть g – первообразный корень по mod p. Для любого a, такого что (a,p)=1 выполняется g^j = a (mod p), 0<=j<=p-2.

Определение.

Любой j, такой что a = g^j  (mod p), 0<=j<=p-2 называется 
индексом a по модулю p. Обозначается ind a или  Asim57.png для обозначения того, 
что индекс по модулю p . Иными словами  выполняется сравнение Asim56.png.
Отметим, что  Asim58.png  выполняется, тогда и только тогда, когда j=j1(mod (p-1)). Следует из утверждения (№3).

Свойства индексов:

Asim59.png

Применение индексов для решения сравнений.

Пусть дано сравнение Asim60.png. При взятии индекса от этого выражения получаем Asim61.png , а после переноса известных в правую часть сравнения Asim62.png , что является сравнением первой степени относительно ind x. По приведенным выше правилам решения сравнений:

1. (n,p-1) = 1, значит сравнение имеет одно решение

2. (n,p-1) = d>1

a. d не делит (ind a – ind b), значит решений нет

b. d | (ind b – ind a)

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

Проблема дискретного логарифмирования

Сформулируем проблему дискретного логарифмирования (discrete logariphm problem - DLP). Пусть имеем конечную мультиаппликативную группу G с операцией *. Обозначим a*a*a* ... *a = b как Asim64.png . Тогда можно обозначить две следующие проблемы:

1) Рассмотрим Asim65.png. Существует ли такой, что Asim64.png

2) Необходимо найти такой n, что Asim64.png, если известно,что он существует.

Для аддитивных групп обозначения меняются вместе со сменой обозначения операции: Asim67.png => Asim66.png

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

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

Метод Полига-Хеллмана нахождения дискретного логарифма

Метод эффективен, если известно разложение Asim68.png .

Трудоемкость метода: Asim69.png.

Описание метода.

Шаг 1. Asim70.png, строим таблицу: Asim71.png.

Шаг 2. Asim72.png находим Asim73.png с использованием таблиц, построенных на шаге 1. Пусть Asim74.png, Asim75.png.

Asim76.png

Asim77.png Asim78.png

В таком случае выполнено сравнение:

Asim79.png В общем виде этот этап можно представить следующим образом: Asim80.png

Шаг 3.

Asim81.png

Asim82.png

Далее получившееся сравнение решается с помощью правил решения линейных сравнений.

Криптография на эллиптических кривых

Использование эллиптических кривых

Асимметричная криптография основана на сложности решения некоторых математических задач. Ранние криптосистемы с открытым ключом, такие как алгоритм RSA, безопасны благодаря тому, что сложно разложить составное число на простые множители. При использовании алгоритмов на эллиптических кривых полагается, что не существует субэкспоненциальных алгоритмов для решения задачи дискретного логарифмирования в группах их точек. При этом порядок группы точек эллиптической кривой определяет сложность задачи. Считается, что для достижения такого же уровня безопасности как и в RSA требуются группы меньших порядков, что уменьшает затраты на хранение и передачу информации. Например, на конференции RSA 2005 Агентство национальной безопасности объявила о создании “Suite B”, в котором используются исключительно алгоритмы эллиптической криптографии, причём для защиты информации классифицируемой до “Top Secret” используются всего лишь 384-битные ключи.

Определения

Плоская эллиптическая кривая – множество точек Asim83.png, где f(x,y)=0 – ненулевой многочлен.
Кубическая кривая – плоская алгебраическая кривая, где Asim84.png, для которой максимальное значение i+j=3.
Эллиптическая кривая – гладкая кубическая кривая, которая задается соотношением: Asim85.png


Если характеристика поля F не равна 2,то можно заменить y на Asim86.png. Тогда уравнение №3 приобретает вид Asim87.png.

Теорема Хассе

Теорема Хассе об эллиптических кривых, которая также называется границей Хассе, дает оценку числа точек на эллиптической кривой над конечным полем. Ограничение дается как сверху, так и снизу. Формулировка теоремы:

Количество точек на эллиптической кривой близко к числу элементов конечного поля, а конкретно |EC(Fq)|=q+1-t, где Asim88.png.

Сложение точек эллиптической кривой

Ниже мы приведем правила сложения точек эллиптической кривой, так как это определено в ГОСТ 34.10. Эллиптическая кривая Е – множество чисел, удовлетворяющих тождеству Asim92.png и Asim93.png.

Пары (x, y), удовлетворяющие тождеству (1), называются «точками эллиптической кривой E»; x и у – соответственно х– и у – «координатами точки».

Точка эллиптической кривой обозначается Q(x, y) или просто Q.

Две точки эллиптической кривой равны, если равны их соответствующие координаты х и у.

На множестве всех точек эллиптической кривой Е операцию сложения обозначают знаком «+». Для двух произвольных точек Q1( x1, y1) и Q2(x2 ,y2 ) эллиптической кривой E рассматривают несколько случаев.

Для точек Q1 и Q2, координаты которых удовлетворяют условию: x1 не равен x2, - их суммой называется точка Q3(x3 ,y3 ), координаты которой определяются сравнениями:

Asim94.png

где

Asim95.png

Если выполнены равенства x1 = x2 и y1 = y2 Asim96.png , то координаты определяются следующим образом:

Asim97.png

где

Asim98.png

Если выполнены условия x1 = x2 и y1 = y2 Asim99.png, то сумма точек называется нулевой точной без определения ее координат.

Применение принципов теории чисел

Криптосистема RSA

Утверждение

Если e,d:Asim89.png, тогда выполняется соотношение

Asim90.png

Доказательство

Asim91.png

Глоссарий (Glossary)

Библиографический указатель (Bibliography)

  • Фомичев В. М. Методы дискретной математики и криптологии. – М.: Диалог-МИФИ, 2010. – 424 с.
  • Виноградов И.М. Основы теории чисел, 180 с.
  • Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография. НПО "Профессионал" – 2004, 480 с.
  • Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. – М.: Гелиос АРВ, 2001.
  • Wenbo Mao, Modern Cryptography: Theory and Practice - Издательский дом "Вильямс", 2005, 768 p.
  • Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. Алгоритмические основы эллиптической криптографии. — Москва: МЭИ, 2000, 100 с.

Вернуться к оглавлению

Душа И.Ф., Лагутина Е.А., 2013