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

From CryptoWiki
Jump to: navigation, search
(Сравнения второй степени)
(Сравнения второй степени)
Line 124: Line 124:
 
Определение
 
Определение
  
Число a называется квадратичным вычетом по mod p, если сравнение x^2[[File:Con.png]]a(mod p), (2,p)=1 имеет решение. Иначе, число a называется квадратичным невычетом по mod p.
+
Число a называется квадратичным вычетом по mod p, если сравнение  
 +
x^2[[File:Con.png]]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]]
  

Revision as of 10:37, 5 November 2013

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

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


Contents

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

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

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

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

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

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

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

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

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


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

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

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

RSA, DSA, ElGamal, ECC, ... Алгоритмы базируются, в основном, на результатах теории чисел.

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


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

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


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

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

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

Теория чисел занимается изучением свойств целых чисел. В случае, когда частное от деления 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=mq¬¬a + r, b=mq¬¬b + 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, если сравнение 

x^2Con.pnga(mod p), (2,p)=1 имеет решение. Иначе, число a называется квадратичным невычетом по mod p. При этом принадлежность числа a к квадратичным вычетам по модулю p обозначается как Asim19.png, а принадлежность к квадратичным невычетам по модулю p обозначается как Asim20.png

Основные криптографические конструкции и их стойкость (Cryptographic primitives and/or protocols)

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

Menezes A.J., van Oorschot P.C., Vanstone S.A. Handbook of Applied Cryptography [1]

Stinson D.R. Cryptography: Theory and Practice [2]

Van Tilborg H.C.A., Jajodia S. (Eds.) Encyclopedia of Cryptography and Security [3]

Mao W. Modern Cryptography: Theory and Practice (2003) [4]

См. также другие источники по списку: [5]

Практические применения криптографических конструкций, особенности их реализации (Practical issues)

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

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

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

и т.д.

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

Перейти к списку литературы или базе данных публикаций по разделу "Наименование вашего раздела".

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

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