Лекции по криптографии. М.: Мцнмо, . -е изд., стереотип. с. Брошюра издана по материалам лекций по криптографии, прочи
жүктеу/скачать 460.25 Kb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Определение.
| .... Функции с секретом. Односторонние функции, остава-
ясь важнейшим средством исследований в математическом шифро- вании, тем не менее не могут быть непосредственно применимы для шифрования. Дело в том, что трудности дешифрования, связанные с отсутствием эффективного алгоритма вычисления обратной функ- ции, будут испытывать не только противники, пытающиеся взломать шифр, но и законный получатель зашифрованного сообщения. Между тем сама идея шифрования наряду с невозможностью взло- ма шифра противником должна содержать и способ достаточно про- стого расшифрования полученного зашифрованного сообщения за- конным его получателем. В криптографии подобные требования формализуются в виде определения «функции с секретом» или «односторонней функции с секретом». Определение. Функция f (x) называется функцией с секретом, ес- ли она удовлетворяет следующим условиям: ) для любого x из некоторого множества существует эффектив- ный алгоритм вычисления y = f (x); ) функция f (x) обладает некоторым «секретным свойством» (обозначим его k), удовлетворяющим следующим условиям: а) при использовании свойства k можно построить эффективный ал- горитм построения обратной функции f −1 k ( y) = x; б) если свойство k неизвестно, то не существует эффективного алго- ритма построения обратной функции f −1 . Другими словами, если для некоторого пользователя «секретное свойство k» неизвестно (то есть или ему не сообщили об этом свой- стве заранее, или он не смог догадаться о нем в процессе изучения функции f ), то для такого пользователя f (x) — это односторонняя функция, и, используя ее для шифрования, он не может осуществить процесс дешифрования. Если же некоторому пользователю становится известно «свой- ство k», то, используя его, он может построить эффективную обрат- ную функцию, то есть осуществлять процесс расшифрования (или дешифрования, если пользователь незаконный). |