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

From CryptoWiki
Revision as of 15:45, 3 November 2013 by 13-03-DushaIF (Talk | contribs)

Jump to: navigation, search

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

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


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.

Основные криптографические конструкции и их стойкость (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