Лекции по криптографии. М.: Мцнмо, . -е изд., стереотип. с. Брошюра издана по материалам лекций по криптографии, прочи
жүктеу/скачать 460.25 Kb. Pdf көрінісі
|
| Замечание. В математической криптографии сформулированы
строгие определения для односторонней функции, которые дают точный математический смысл понятиям типа «существования или несуществования эффективного алгоритма». Для практического же применения достаточно считать, что п. этого определения означает, что если даже алгоритм вычисления обратной функции найдется, его работа будет занимать столько времени, что после завершения его работы знание исходного текста уже не будет иметь никакого практического значения. Поясним приведенное на очень простом примере. Пусть нужно за- шифровать обычные целые числа 1, 2, …, N. Выберем в качестве шиф- рующей функции обычное возведение в шестую степень: f (x) = x 6 . () Например, число 2 шифруется как 2 6 = 64 , число 3 — как 3 6 = 729 и так далее. Эта функция удовлетворяет условию из определения односторонней функции, так как возведение в шестую степень — это достаточно простая операция (то есть существует эффективный алгоритм шифрования). Посмотрим теперь, как обстоит дело с выполнением условия . Для дешифрования нужно к предъявленному шифру применить функцию, обратную (), то есть извлечь корень шестой степени. Конечно, нельзя сказать, что для этой операции не существует эф- фективных алгоритмов. Но данный пример иллюстрирует примеча- тельный факт: алгоритм применения обратной функции существенно сложнее, чем алгоритм вычисления самой функции. И поэтому, хотя в строгом смысле слова функция y = x 6 не является односторонней, при ее применении для дешифрования приходится применить значи- тельно больше усилий, чем для шифрования. Например, если по каким-либо причинам время и ресурсы на де- шифрирование сильно ограничены, в каких-то случаях вполне мож- но ограничиться такой «слабо односторонней» функцией, как f = x 6 , 1.3. Математическая формализация 15 и противник вполне может и не уложиться в отведенное время, вы- числяя напрямую, например, корни шестой степени из 46656, или 117649 , или 8026. (Первое число в данном случае шифрует 6, второе 7 , а третье вообще ничего не шифрует.) жүктеу/скачать 460.25 Kb. Достарыңызбен бөлісу:
|