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