Лекции по криптографии. М.: Мцнмо, . -е изд., стереотип. с. Брошюра издана по материалам лекций по криптографии, прочи
жүктеу/скачать 460.25 Kb. Pdf көрінісі
|
| Замечание. Так же, как и в случае с односторонней функцией,
в математической криптографии формулируются строгие определе- ния таких понятий, как существование эффективного алгоритма. Из самого определения функции с секретом ясна ее роль в процес- се шифрования. Шифровать, то есть осуществлять вычисления по схе- ме y = f (x), могут все участники процесса обмена информацией. Что же касается дешифрования, то его могут эффективно осуществлять только участники процесса, владеющие секретным «свойством k». Таким образом, процесс шифрования/расшифрования с использо- ванием функции с секретом осуществляется следующим образом. • Выбирается некоторая функция с секретом и алгоритм вычис- ления y = f (x) сообщается всем заинтересованным участникам процесса обмена информацией (этот алгоритм может быть даже опубликован). Это позволяет всем участникам схемы осуществ- лять шифрование по схеме y = f (x). • Некоторым участникам («законным пользователям») сообщается о секретном «свойстве k». • Получив зашифрованное сообщение y = f (x), «законный» участ- ник может осуществить расшифрование, вычислив исходный текст по формуле x = f −1 k ( y), поскольку такой алгоритм вычисления строится в силу свойства а). • «Незаконный» участник схемы, обладая зашифрованным текс- том y, не может, тем не менее, вычислить исходный текст x, т. е. провести дешифрование, поскольку ему не известно секретное «свойство k» шифрующей функции f , а без его знания вычисление напрямую x = f −1 ( y) невозможно практически. Для иллюстрации сказанного относительно свойств функций с сек- ретом рассмотрим тот же пример шифрующей функции y = x 6 . Мы договорились считать, что в данном примере дешифрование, т. е. вычисление обратной функции x = y 1 /6 , при данном значении y является сложной задачей; по крайней мере, эта задача значительно сложней, чем задача шифрования, т. е. вычисления y = x 6 при задан- ном значении x. Чтобы проиллюстрировать понятие «секрета» функции, заметим, что обратную функцию можно переписать в виде x = ( y 1 /2 ) 1 /3 , () а это позволяет построить алгоритм вычисления обратной функции, который сводится к последовательному извлечению сначала квадрат- ного корня, а затем кубического, что можно осуществить значительно 1.3. Математическая формализация 17 более эффективно, чем однократное извлечение корня шестой степе- ни. Приведенный пример иллюстрирует (конечно, весьма условно) идею применения функций с секретом. Конечно, этот пример плох в том смысле, что распознать приведенный секрет данной схемы шифрования может не только законный ее пользователь. В данном случае секрет, заключающийся в том, что для любого числа a a 1 /6 = ( a 1 /2 ) 1 /3 , вовсе не является таким уж секретом. Однако этот пример иллюстрирует еще одну весьма важную ма- тематическую задачу. Фактически в () использовано разложение исходного показателя степени на простые множители, а именно, 6 = 2 · 3 , и вместо извлечения одного корня шестой степени можно извлечь сначала корень второй степени, а затем корень третьей степени. Опять-таки, разложить на простые множители число 6 — задача, не содержащая секрета. Однако эта же задача, поставленная в общем виде, дает неожиданный результат. Несмотря на колоссальные уси- лия математиков, особенно за последние — лет, до сих пор не найден эффективный алгоритм разложения произвольного числа на простые множители. Именно осознание этого факта позволило по- строить один из самых эффективных и наиболее распространенных алгоритмов шифрования, так называемый алгоритм RSA, описание которого приведено в следующем разделе. 1.3.2. Алгоритм шифрования RSA Алгоритм шифрования RSA был предложен в опубликованной в году работе американскими математиками (Ривест, Шамир и Адлеман) и назван по первым буквам английской транскрипции их фамилий (Rivest R. L., Shamir A., Adleman L.). В настоящее время он является одним из наиболее популярных алгоритмов. Некоторые авторы считают, что RSA — наиболее часто употребляемый алгоритм шифрования вообще. К сожалению, подробное изложение математического обоснова- ния RSA опирается на некоторые результаты теории чисел, изложе- ние которых выходит за пределы данных лекций. Ниже мы приведем необходимые факты без доказательств. Более подробную информа- цию об RSA можно найти в работе []. Приведем основные моменты построения алгоритма. 18 1. Основные понятия и математическая формализация В качестве основной шифрующей функции в схеме RSA принята жүктеу/скачать 460.25 Kb. Достарыңызбен бөлісу:
|