Дискретная математика. Теория чисел. Ерош И.Л. - 24 стр.

UptoLike

Составители:

Рубрика:

2. ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ ТЕОРИИ

2.1. Использование теории чисел при открытом

распределении секретных ключей

Пусть два абонента A и B обмениваются информацией по открыто-

му каналу. Для защиты передаваемой информации может быть исполь-

зован ключ K, который должен быть как у абонента A, так и у абонента

B и больше ни у кого.

Абонент A, передавая сообщение S (двоичная последовательность ко-

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

образом: вместо того, чтобы передавать открытое сообщение S передаст

сообщение S ⊕ K, где ⊕ – булева операция сложения по модулю 2. Не зная

ключа K, очень трудно расшифровать сообщение S. Если же ключ K изве-

стен, то расшифрование производится очень просто: достаточно к получен-

ному сообщению (S ⊕ K ) прибавить по модулю 2 значение ключа K. Одна-

ко мы же сталкиваемся с другой проблемой: как снабдить абонентов A и B

секретным ключом K? Отправить курьера – дорого и опасно, поскольку

курьера можно перехватить, отобрать секретный ключ или просто его ку-

пить. В связи с этим соображением в криптографии предполагается, что

перехватчику информации известно все: и машины для шифрования, и коды.

Неизвестным может быть только то, что очень хорошо охраняется (а это

дорого) или что еще не успели украсть или купить.

Одна из идей криптографии с открытым ключом основана на труд-

ностях логарифмирования сравнений. Так, если имеется равенство

=b,

где a и b известно и требуется найти x, то значение x находится элементарно

x = logb/logа.

Если же имеется сравнение:

≡ b mod p,

где известны a, b и p, то для нахождения неизвестного x часто требует-

ся произвести полный перебор.