Лекции по криптографии. М.: Мцнмо, . -е изд., стереотип. с. Брошюра издана по материалам лекций по криптографии, прочи
жүктеу/скачать 460.25 Kb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Пример
| Пример . Вычислим d по заданным m, p, q, e.
В этом примере в качестве шифрующей «односторонней функции с секретом» используется степенная функция y = x e mod m при кон- кретном значении параметра m = 91 и ключа шифрования e = 29, а в качестве «секретного свойства» этой функции использовалось знание разложения параметра m на простые множители (m = p · q), или в конкретном примере 91 = 7 · 13. Значение функции Эйлера ϕ(m) = (p − 1)(q − 1) = 6 · 12 = 72. Число e = 29 не имеет общих делителей ни с 91, ни с 72, значит, годится в качестве ключа шифрования. 20 1. Основные понятия и математическая формализация Найдем d по алгоритму Евклида. Этот алгоритм используется для отыскания наибольшего общего делителя двух целых чисел: 72 = 2 · 29 + 14; 29 = 2 · 14 + 1; 1 = 29 − 2 · 14 = 29 − 2 · (72 − 2 · 29) = 5 · 29 − 2 · 72; 5 · 29 = 1 mod 72. Ответ: d = 5. Пример (исторический). Приведем, в прямом смысле слова, ис- торический пример, который сыграл огромную роль в распростране- нии схемы RSA. Для иллюстрации своего метода Ривест, Шамир и Ад- леман зашифровали с помощью предложенного ими метода англий- скую фразу: «The magic words are squeamish ossifrage» (при этом, по- видимому, авторы не слишком старались придать шифруемому тексту какой-либо содержательный смысл). Сначала этот текст стандартным образом (см. п. ...) был пере- кодирован в целое число x. При этом, естественно, получилось целое число, содержащее 78 десятичных цифр: x = 200805001301070903002315180419000118050019172105011309 190800151919090618010705. Затем к этому числу была применена процедура шифрования RSA f (x) = x e mod m при значении e = 9007 и 129-значном (!) значении m = 114381625757888867669325779976146612010218296721242362 562561842935706935245733897830597123563958705058989075147 599290026879543541. Полученный в результате зашифрованный текст f (x) = 9686961375462206147714092225435588290575999112457431 987469512093081629822514570835693147662288398962801339199 0551829945157815154 был опубликован вместе с указанными значениями использованных параметров e и m. Дополнительно сообщалось, что m = pq, где p и q — некоторые простые числа, записываемые соответственно 64 и 65 де- сятичными знаками. Первому, кто дешифрует соответствующее сооб- щение, была обещана награда в 100 долларов. 1.3. Математическая формализация 21 Эта история завершилась спустя 16 лет в 1994 г., когда D. Atkins, M. Graff, A. K. Lenstra и P. C. Leyland сообщили о дешифровке фразы, предложенной выше. Соответствующие числа p и q оказались равными p = 349052951084765094914784961990389813341776463849338784 3990820577, q = 327691329932667095499619881908344614131776429679929425 39798288533. Выполнение вычислений потребовало колоссальных ресурсов. В ра- боте, возглавлявшейся четырьмя авторами проекта и продолжав- шейся после предварительной теоретической подготовки примерно 220 дней, на добровольных началах участвовало около 600 чело- век и примерно 1600 компьютеров, объединенных сетью Internet. Понятно, что основной трудностью всего проекта, которую удалось преодолеть его участникам, было именно разложение 129-значного числа на простые множители. Детали вычислений опубликованы в статье, в заголовок которой авторы вынесли зашифрованную за шестнадцать лет до этой публикации и расшифрованную ими англий- скую фразу. Честным трудом заработанные 100 долларов участники этого грандиозного проекта передали в фонд развития программного обеспечения. Описанная выше схема RSA используется во всем мире чрезвычай- но широко и во многих приложениях. Вместе с тем ее использование ставит ряд вопросов. Главный из них: существуют ли другие способы решения сравнения ()? Ведь если можно найти решение (), не разлагая число m на простые сомножители, да еще сделать это до- статочно быстро, вся система RSA разваливается. Между тем, вопрос этот чрезвычайно важен. Ведь схема RSA положена в основу защи- ты многих информационных систем, хранящих и государственные и коммерческие тайны. Косвенным, но все же достаточно убедитель- ным, подтверждением стойкости системы RSA является тот факт, что за 16 лет никто так и не объявил, что смог дешифровать предложен- ную авторами RSA фразу. Не довольствуясь этим, специалисты по информационной безопасности принимают дополнительные меры для защиты своих систем, например, периодически с интервалом заведомо меньшим, чем возможное время, требуемое для взлома шифра, проводится смена ключей шифрования и новое «перешиф- рование» защищаемых текстов. И все-таки, если когда-либо кому-нибудь из математиков удастся найти алгоритм, дешифрирующий схему RSA за приемлемое время 22 1. Основные понятия и математическая формализация без знания секретного ключа d, почти наверняка этот заведомо вы- дающийся математический результат будет не опубликован, а засек- речен, ибо битва за шифры продолжается. 1.3.3. Открытый и закрытый ключи Как уже отмечалось, понятие ключа появилось еще в древности вместе с возникновением первых систем шифрования. Вместе с тем, описанный в предыдущих разделах математический аппарат позволя- ет формализовать это важнейшее понятие теории шифрования. Схема асимметричного шифрования, основанная на использова- нии понятия функции с секретом, предполагает с одной стороны из- вестный всем участникам схемы (другими словами, открытый) ал- горитм шифрования, а с другой стороны, известный только «закон- ным участникам» (другими словами, закрытый) алгоритм расшиф- рования, использующий «секретное свойство» шифрующей функции. При этом каждый математический алгоритм, в том числе и любой алгоритм шифрования, сформулированный в общем виде, содержит какое-то количество параметров, которым для реальной работы этого алгоритма должны быть присвоены конкретные значения. Таким образом, мы получаем два определения. Открытым ключом схемы шифрования, использующей функцию с секретом, является совокупность конкретных значений параметров, обеспечивающих работу открытого алгоритма шифрования с помо- щью этой функции. Закрытым ключом схемы шифрования, использующей функцию с секретом, является совокупность конкретных значений параметров, обеспечивающих работу алгоритма расшифрования с использовани- ем «секретного свойства» шифрующей функции. По установившейся традиции для открытых и закрытых ключей в криптографии используются обозначения K1 и K2 соответственно. Поясним сказанное на конкретном примере. жүктеу/скачать 460.25 Kb. Достарыңызбен бөлісу:
|