Введение в криптографию
[an error occurred while processing this directive]

Введение


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

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

Пример 1. (Криптосистема с открытым ключом)  

полностью определяется тремя алгоритмами: генерации ключей, шифрования и дешифрования. Алгоритм генерации ключей

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

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




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]