Лекция №7 Асимметричное шифрование

key systems) – смысл данных криптосистем состоит в том, что

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

ключом. У пользователя есть два ключа – секретный и открытый.

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

отпадает проблема передачи секретного ключа, как в симметричных системах. Однако,

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

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

натурального числа N является метод пробных делений: для d=2, 3, 4 … мы проверяем выполнение условия (d, N)>1 (здесь (d, N) – наибольший общий делитель чисел d и N). Число операций, требуемых для этого метода, имеет порядок корня из N.

В отличие от таких “детерминированных“ тестов существуют еще “вероятностные“ тесты

проверки простоты. Для исследуемого числа проверяется выполнение некоторых, связанных со случайными числами, условий. Если какое- либо из этих условий не выполнено, то N – составное число. Если же все условия выполнены, то с некоторой вероятностью можно утверждать, что N – простое число. Эта вероятность тем ближе к 1, чем большее количество случайных чисел мы проверим.

для любого положительного числа b, не превосходящего некоторого простого числа

p :

можно выбрать любое положительное целое число b, меньшее r, и

проверить, выполнено ли равенство

быть совершенно уверенным, что r – не простое число. Если

же равенство выполнено, то можно лишь предполагать, что r – простое число и поэтому назвать его “псевдопростым по основанию b“. Вероятность P (x) того, что составное число x окажется псевдопростым по случайному основанию, убывает с ростом x.

числа, которые обладают свойством:

Пример числа Кармайкла
561 = 3*11*17

доля положительных целых чисел, меньших некоторого целого m и являющихся

простыми, близка к 1/(ln m). Например, доля целых чисел, меньших и являющихся простыми, близка к 1/(ln ) = 1/230.

Таким образом, если мы выберем случайно большое целое положительное нечетное число x и будем последовательно проверять на простоту числа x, x+1, x+2, … , то, в среднем, мы впервые встретим простое число на шаге с номером ln x.