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

From CryptoWiki
Revision as of 09:38, 17 October 2013 by 13-03-DushaIF (Talk | contribs)

Jump to: navigation, search

Душа И.Ф.,

Лагутина Е.А.

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

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

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

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

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

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

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

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

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

Означает квадратичное возрастание числа пар ключей, которые надо генерировать, передавать, хранить и уничтожать в сети. Для сети в 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 называются взаимно простыми. Если каждое из этих чисел взаимно просто с каждым другим, тогда они называются взаимно попарно простыми.

Назад