Шифрование с открытымключем.

Пусть K — пространство ключей, а e и d — ключи шифрования и расшифрования соответственно. E_e — функция шифрования для произвольного ключа e K, такая что:

E_e (m) = c

Здесь c C, где C — пространство шифротекстов, а m M, где M — пространство сообщений.

D_d — функция расшифрования, с помощью которой можно найти исходное сообщение m, зная шифротекстc

D_d (c) = m

{ E_e: e K } — набор шифрования, а { D_d: d K } — соответствующий набор для расшифрования. Каждая пара (E, D) имеет свойство: зная E_e, невозможно решить уравнение E_e (m) = c, то есть для данного произвольного шифротекста c C, невозможно найти сообщение m M. Это значит, что по данному e невозможно определить соответствующий ключ расшифрования d. E_e является односторонней функцией,

Односторонней называется функция F: X→ У, обладающая двумя свойствами:

a. а) существует полиномиальный алгоритм вычисления значений F(х);

b. б) не существует полиномиального алгоритма инвертирования фун­кции F (т. е. решения уравнения относительно х).

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

Еще одним новым понятием является понятие функции с секретом. Иногда еще употребляется термин функция с ловушкой. Функцией с се­кретом Кназывается функция , зависящая от параметра К и обладающая тремя свойствами:

а) существует полиномиальный алгоритм вычисления значения для любых К и х;

б) не существует полиномиального алгоритма инвертирования при неизвестном К;

в) существует полиномиальный алгоритм инвертирования при известном К.

Применение функций с секретом в криптографии позволяет:

1) организовать обмен шифрованными сообщениями с использова­нием только открытых каналов связи, т. е. отказаться от секретных каналов связи для предварительного обмена ключами;

2) включить в задачу вскрытия шифра трудную математическую задачу и тем самым повысить обоснованность стойкости шифра;

3) решать новые криптографические задачи, отличные от шифро­вания (электронная цифровая подпись и др.).

Дата добавления: 2015-12-01