32. Система шифрования с открытым ключом. Понятие односторонней функции с секретом.

Криптографическая система с открытым ключом (или Асимметричное шифрование, Асимметричный шифр) — система шифрования, при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу, и используется для шифрования сообщения. Для расшифровки сообщения используется секретный ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и SSL.

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

Но сама односторонняя функция бесполезна в применении: ею можно зашифровать сообщение, но расшифровать нельзя. Но есть такой y, что зная f(x) и y, можно вычислить x.

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

Пусть 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→ У, обладающая двумя свойствами:

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

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

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

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

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

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

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

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

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

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

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