Семантическая стойкость. 
Криптографические методы защиты информации

В заключение мы приведем еще одно свойство схемы RSA, которое влияет на ее стойкость.

Определение 10.4. Мы будем говорить, что схема шифрования RSA является семантически стойкой, если для любых значений открытого текста s, шифртекста с и также секретного и открытого ключей d, е схемы RSA не существует полиномиального алгоритма, позволяющего с вероятностью большей ^ отделить открытый текст s от случайного двоичного вектора той же длины по известным открытым параметрам сит.

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

Для схемы RSA условие семантической стойкости не выполняется. Так как НОД (е, ip{m)) = 1 и ip (m) = (р — 1 )(q — 1), то е нечетно. Тогда для любого шифртекста с выполнено равенство.

где символ () обозначает символ Якоби, см. [3].

Следовательно, для каждого сообщения г такого, что.

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