Открытое распространение ключей
Можете ли Вы найти другие корни 4-ой степени из 16 по модулю 21 ? Найдите целое число х, которое не имеет корней 4-ой степени по модулю 21.
В том случае, когда экспонента m и модуль n фиксированы, мы уже приводили эффективный алгоритм вычисления g[m,n](a) для любого основания a.
В противоположность задаче дискретного логарифмирования, тем не менее, известно, что существует также и эффективный алгоритм взятия корня m-ой степени их х по модулю n (или выяснения, что его не существует) для любого заданного х. Любопытный феномен заключается в том, что неизвестно, как эффективно построить этот эффективный алгоритм при заданных лишь m и n. Другими словами, функция g[m,n] в действительности не является однонаправленной, поскольку мы знаем, что она может быть эффективно обращена, но несмотря на этот факт мы не знаем, как это сделать!
Тем не менее, легко построить эффективный алгоритм вычисления m-ого корня по модулю n при условии, что известно разложение n на простые множители. Именно по этой причине g[m,n] и является кандидатом на однонаправленную функцию с потайным ходом, для которой m и n используются как открытая информация, тогда как разложение служит в качестве секретного потайного хода.
Мы еще увидим, каким образом это может быть использовано, когда будем изучать знаменитую криптосистему RSA(раздел 1.4).
Важный специальный случай модульного возведения в степень имеет место, когда экспонента равна 2 и когда модуль является числом специального вида. Для понимания этого второго примера кандидата на однонаправленную функцию с потайным ходом необходимы дополнительные сведения из теории чисел.
Если p и q два различных больших простых числа примерно равного размера, и если оба p и q сравнимы с 3 по модулю 4, то мы будем говорить, что их произведение n = p*q является целым числом Блюма. Определим Zn* как множество целых между 1 n-1, которые не делятся ни на p ни на q. Наконец, определим QRn как подмножество Zn*, состоящее из чисел, которые являются совершенными квадратами по модулю n. Элементы QRn известны как квадратичные вычеты по модулю n.
В качестве небольшого примера рассмотрим p = 19 и q = 23, таким образом n=437. В этом случае 135 является элементом Zn*, в то время как 133 нет(поскольку 133 = 19*7).
Кроме того 135 не является квадратичным вычетом по модулю 437, так как не существует целого числа а такого, что ал2 = 135 (mod 437), тогда как 139 является квадратичным вычетом, так как 24Л2 = = 576 = 139 (mod437).
Сформулируем без доказательства несколько необходимых для понимания дальнейшего теорем.
Число элементов в Zn* равно (p-1)*(q-1), и ровно одну четвертую часть из них составляют квадратичные вычеты. Каждый квадратичный вычет допускает в точности четыре различных квадратичных корня в Zn*, из которых лишь один единственный сам является квадратичным вычетом.
Этот особый корень мы назовем главным квадратичным корнем.
В нашем примере 24 это главный квадратичный корень из 139 по модулю 437, а другими тремя корнями являются 185,252 и 413. Имеющий криптографическое значение факт заключается в том, что способность определять квадратические корни по модулю n оказывается вычислительно эквивалентной умению раскладывать n на множители. Иначе говоря, тот кто знает разложение n на множители может эффективно вычислять главные квадратичные корни по модулю n, тогда как такие вычисления столь же трудны сколь и факторизация n для того, кто этого разложения еще не знает.
Наш второй кандидат на однонаправленную функцию с потайным ходом теперь должен быть очевиден. Вы случайно выбираете p и q и вычисляете n = p*q, которые открыто объявляете.
После этого любой может эффективно вычислить квадраты по модулю n, но только ваш друг может эффективно обратить эту операцию (в предположении, что факторизация трудна).
В этом примере открытой информацией является число n, а секретным потайным ходом опять служит его разложение на множители.
Для более основополагающих сведений по вычислительной теории чисел мы отсылаем к [165].
Открытое распространение ключей
Одна из основных трудностей в больших многопользовательских криптосистемах, которую необходимо отметить, заключается в том, что каждая пара пользователей должна обмениваться секретными ключами. Предположим, что два каких-то конкретных пользователя пока еще не делились друг с другом заранее никакой секретной информацией, и что они неожиданно захотели установить секретную связь между собой.
Общепринятым решением для них было бы где-то встретиться, чтобы передать друг другу секретный ключ, или использовать нечто вроде доверительного курьера. Оба этих решения являются очень медленными и дорогими, и к тому же они не могут быть абсолютно надежными.
Предназначение системы с открытым распространением ключей заключается в том, чтобы она позволяла двум таким пользователям выработать секретный ключ в результате переговоров по несекретному каналу связи таким образом, чтобы возможный подлушиватель не смог разгадать этот ключ даже после прослушивания полностью всех этих переговоров.
Точнее, хотелось бы иметь такой протокол, с помощью которого А и В обменивались бы сообщениями m1(от А к B), m2(от B к A), ..., до тех пор пока А и В окончательно не условятся о некотором ключе k таким образом, чтобы определить k из знания только m1, m2,... было бы практически невозможно. Подчеркнем еще раз, что этого необходимо добиться даже несмотря на то что А и В заранее не обмениваются никакой информацией, которая не была бы известна подслушивателю.
Первый протокол, который достигает этой кажущейся невозможной цели, был предложен Диффи (W. Diffie) и Хеллманом (M.E. Hellman)[101] в 1976 году. Он основывается на задаче дискретного логарифмирования, рассмотренной в разделе 1.1.
Пусть n некоторое большое целое число, и пусть g другое целое, лежащее строго между 1 и n-1. В качестве первого щага протокола Диффи-Хеллмана A и B уславливаются об n и g посредством несекретного канала связи (альтернативно n и g могли бы быть стандартными параметрами, применяемыми всеми пользователями системы).
Затем А выбирает некоторое большое целое число x и вычисляет X = gAx mod(n). Соответственно, В выбирает у и вычисляет Y = gAy mod(n). После этого А и В обмениваются X и Y по тому же несекретному каналу связи, храня при этом в секрете x и у ( x знает только А, а у - только В). Наконец, А вычисляет YAx mod(n); соответственно, В вычисляет XAy mod(n).
Оба эти значения равны между собой, так как каждое из них равно gA(x*y) mod(n). Это и есть именно тот ключ k, который они хотели совместно выработать.
Нарушитель сталкивается с задачей вычисления k из информации, пересылаемой по несекретному каналу: g, n, X, Y. Очевидным подходом для нарушителя было бы вычислить x из g, n и X (или, по крайней мере, некоторое такое x', что gAx' mod(n)=X, так как любое такое x' дает YAx' mod(n) = k). Однако, это в точности задача определения дискретного логарифма, которая считается практически невыполнимой. Еще никто не придумал способа вычислять k эффективно из g, n, X, Y, но и никто не смог доказать, что это невозможно, или хотя бы, что не существует лучшего способа сделать это, чем вычислить сначала дискретный логарифм.
Поэтому, вообще говоря, правомерно предполагать, что вычисление k может быть осуществлено эффективно, даже если задача дискретного логарифмирования действительно оказалась бы практически невыполнимой.
Выбор g и n может оказывать существенное влияние на эффективность и надежность представленного выше проекта системы. Для того чтобы сократить размер возможных окончательных значений k, важно чтобы функция модульного возведения в степень f[g,n]: Zn - Zn (как она определена в разделе 1.1.) была настолько почти взаимнооднозначной, насколько это возможно. В том случае, когда n является простым числом, всегда существует такое g, что gAx mod(n) принимает каждое из значений в промежутке от 1 до n-1, когда x пробегает значения из того же интервала. Такие g, известные как генераторы циклической группы Zn и были бы искомыми.
В этом случае надежнее выбрать n таким образом, чтобы (n-1)/2 также было простым [191]. Кроме того можно было бы все указанные операции проводить в полях Галуа GF(2Ak), методы вычисления в которых выходят далеко за рамки этого обзора [28]. Они предоставляют возможность намного более эффективно осуществлять умножение (а следовательно и возведение в степень), так как позволяют избежать при вычислениях необходимости переносов и приведений по модулю.
Размер ключа в этом случае будет, однако, существенно длинее.
Несмотря на то, что очень большие дискретные логарифмы возможно и являются трудновычислимыми, хотелось бы предупредить читателя, что для их вычисления существуют алгоритмы намного лучшие, чем исчерпывающий поиск. Самые лучшие из известных в настоящее время алгоритмов, когда n является простым числом, описаны в [80], или в [186] при вычислениях в GF(2Ak). Но такие поля должны тщательно анализироваться при выборе размера ключа.
Злополучная аппаратная реализация была однажды разработана в Hewlitt-Packard, используя GF(2A127) [247]. И ключи в ней были быстро раскрыты с помощью [29].
В предположении, что n и g являются стандартными параметрами, интересной альтернативой описанному ранее интерактивному протоколу заключается в учреждении и использовании для распространения некоторого единого для всех справочника. Каждый пользователь записывает в этот справочник свой собственный X, вычисленный как gAx mod(n) для своего случайно выбранного секретного х. Это позволяет двум пользователям сформировать их совместный секретный ключ даже до того как они поговорят друг с другом с самого начала.
Основной недостаток такого доступа к справочнику состоит в том, что он не поддерживает пользователей в изменении своих секретных ключей достаточно часто. Мы намереваемся вернуться к этой теме в разделе 1.7.
Другим подходом к проблеме распространения ключей является предложенная Беннетом (C.H.Bennet) и Брассардом (G.Brassard) квантовая криптография. Ее надежность не зависит от недоказанных предположений о вычислительной сложности, основанных на трудности вычислений каких бы то ни было функций.
Она остается таковой даже тогда, когда нарушитель имеет неограниченные вычислительные ресурсы, или если все-таки P = NP [17,18,19,20,21].
Криптосистемы с открытым ключом. Теория.
Система открытого распространения ключей, так как она описана в разделе 1.2, позволяет двум сторонам сформировать совместную часть некоторой распределенной секретной информации. Однако, ни одна из сторон не имеет никакого непосредственного влияния на то, какой окажется эта информация.
Если бы А захотел передать В единственное специальное сообщение, то за использованием системы открытого распространения ключей должно было бы последовать использование криптосистемы с открытым ключом, в которой первоначальная совместно сформированая информация сохранялась бы в качестве секретного ключа.
Криптосистемы с открытым ключом используются непосредственно для передачи исключительно важных сообщений. Во многом подобные криптосистемам с секретным ключом криптосистемы с открытым ключом состоят из: пространства ключей K, а для каждого k из K, из пространств открытых сообщений Mk, пространств шифртекстов Ck и пар функций Ek: Mk - Ck и Dk: Ck - Mk, таких что Dk(Ek(m)) = m для любого открытого текста m из Mk.
Снова, как и в криптосистемах с секретным ключом, эффективные алгоритмы для вычисления как Ek, так и Dk, должны легко получаться для каждого ключа k. Мы будем называть алгоритмы, полученные таким образом, естественными алгоритмами. Важной новой отличительной особенностью является то, что Ek должна быть однонаправленной функцией с потайным ходом: необходимо, чтобы было практически невозможно построить никакого эффективного алгоритма для вычисления Dk (но только естественного алгоритма), зная описание естественного алгоритма для вычисления Ek.
В частности, это означает, что k не должно появляться в явном виде в естественном алгоритме шифрования.
Криптографические системы с открытым ключом используются следующим образом. Каждый пользователь раз и навсегда выбирает некоторый случайный ключ k из K. Он использует этот ключ для получения обоих естественных алгоритмов Ek и Dk.
Затем он делает публично доступным свой алгоритм шифрования Ek, возможно посредством использования при этом некоторого справочника, но хранит в тайне свой алгоритм дешифрования Dk.
В том случае если другой пользователь захочет послать ему некоторое сообщение, то он найдет в справочнике его открытый алгоритм шифрования и использует его для того чтобы зашифровать свое сообщение. Тогда, используя собственный секретный ключ, только законный получатель сможет расшифровать это сообщение.
В противоположность криптосистемам с секретным ключом, заметим, что если пользователь А, закодировав некоторое сообщение m для пользователя В, сохранил шифртекст С, но потерял открытый текст (или забыл все, что в нем содержалось), то он не будет иметь никаких преимуществ перед нарушителем в раскрытии m из С.
Также в противоположность криптосхемам с секретным ключом, если нарушитель перехватывает шифртекст и знает для кого он был зашифрован, то он может использовать открытый алгоритм шифрования для проверки любого конкретного предположения о том, каким может быть соответствующий открытый текст. Возможность формировать шифртексты из открытых текстовых сообщений по своему выбору является причиной сокращения числа классических уровней атаки, которые обсуждались в связи с криптосистемами с секретным ключом (раздел 3.1). Однако следующая важная атака может иногда применяться:
* Атака на основе выбранного шифртекста : против определенного пользователя, чьи функции суть Ek и Dk, криптоаналитик задается выбранными шифрованными сообщениями С1, С2, ..., Ci и подбирает соответствующие m[1] = Dk(C1), m[2] = = Dk(C2),..., m[i] = Dk(Ci), при условии, что они существуют. Он хочет определить k, или какой-нибудь эффективный алгоритм вычисления Dk, или(за неимением такой возможности), пытается найти m[i+1] из некоторого нового шифртекста С[і+1] = Ek(m[i+1]).
Криптосистемы с открытым ключом могут существовать только, если вообще существуют как однонаправленные функции, так и однонаправленные функции с потайным ходом. В самом деле функции шифрования должны быть однонаправленными функциями с потайным ходом, а процесс, который по ключу обеспечивает естественный алгоритм шифрования, должен реализовывать однонаправленную функцию.
В результате получается, что мы не знаем, как доказать существование криптосистем с открытым ключом. Это может быть не более, чем причудливый способ поговорить о пустом множестве, даже несмотря на то, что возможная осуществимость этого понятия была уже формально продемонстрирована в относительных утверждениях [49,46,47].
Поэтому точно так же, как это было в случае однонаправленных функций (с потайным ходом), мы должны быть удовлетворены кандидатами на криптосистемы с открытым ключом. Два наилучших из известных таких кандидата были спроектированы вскоре после того, как Диффи и Хеллман ввели понятие криптографии с открытым ключом [100,101].
Одна из них, так называемая ранцевая криптосистема Меркля^.С. Merkle) и Хеллмана [180,147], была вскоре раскрыта [99,104,209,3,59,166,60]. И хотя существуют еще не раскрытые варианты первоначальной схемы, им, по видимому, не стоит доверять. Брикель^^.
Brickell) написал очень детальную историю криптоанализа ранцевой криптографической системы [61].
Другая, наилучшая из известных криптосистем с открытым ключом, все еще остается несокрушимой, и мы сейчас опишем ее в некоторых деталях. Были предложены и другие системы, такие как системы Макэлиса^Х McEliece) [177] и ЭльГамаля(Т.
ElGamal) [105]. Мы не будем обсуждать их здесь.
По поводу исчерпывающего обзора криптографии с открытым ключом обращайтесь к [167].
Криптосистема RSA
Самой первой криптосистемой с открытым ключом из вообще предложенных в открытой литературе была система Райвеста (R.L.Rivest), Шамира (A.Shamir) и Эдльмана (L.M.Adleman)[205]. Она стала известна под названием RSA или MIT криптосистемы. Основана она на вере в то, что модульное возведение в степень при фиксированных экспоненте и модуле является однонаправленной функцией с потайным ходом (см. раздел 4.1).
Для первоначального ознакомления с этой криптосистемой обращайтесь к [120].
Пусть p и q - два больших различных простых числа, и пусть n = p*q и e некоторое целое, взаимно простое с (p-1)*(q-1). Тогда каждая такая тройка k = объявляется личным(секретным) ключом для криптосистемы RSA.
Оба соответствующих пространства открытых текстов Mk и зашифрованных сообщений Ck суть Zn - множество неотрицательных целых, меньших n. Если подлинное сообщение окажется слишком длинным, чтобы принадлежать Zn, его необходимо разбить на части и зашифровать, используя режим шифрования со сцеплением блоков, описанный в разделе3.5.
Соответствующая ключу k функция шифрования Ek: Mk - Ck определяется как Ek(m) = mAe mod(n). Для того, чтобы полностью определить естественный алгоритм ее вычисления достаточно записать e и n в открытый справочник. Такая пара называется открытым ключом, который легко вычисляется с помощью личного ключа .
Вспомним из раздела 1.1, что Ek является кандидатом на однонаправленную функцию с потайным ходом, и хотя существует эффективный алгоритм вычисления обратной ей функции Dk, мы не знаем, как получить его эффективно, задаваясь только естественным алгоритмом вычисления Ek (т.е. только для заданных n и e).
Однако эффективный алгоритм вычисления Dk легко получить, задав дополнительную секретную информацию p и q. С этой целью, используя обобщенью алгоритмы Евклида для нахождения наибольшего общего делителя, чтобы вычислить целое число d, такое что e*d = 1 mod ф(п), где ф(п) = (p-1)*(q-1). По известной теореме Эйлера mA(e*d) = m mod(n) для каждого целого числа m и, следовательно, (mAe)Ad mod(n) = m, при условии что 0 = m п, что обеспечивается, когда m принадлежит Mk.
Функция дешифрования Dk: Ck - Mk в связи с этим определяется как Dk(c) = mAd mod(n), и эффективный алгоритм для модульного возведения в степень также может быть использован и для ее вычисления. (Для заданных p и q существует даже более эффективный алгоритм вычисления Dk, основанный на китайской теореме об остатках [193]).
Суммируя все сказанное, тогда каждый пользователь криптосистемы RSA должен раз и навсегда выбрать случайно подходящие целые числа p, q и e и вычислить с их помощью d. После чего он делает свой открытый ключ доступным в пользовательском справочнике, тогда как d сохраняет в секрете. Это дает возможность любому другому пользователю шифровать посылаемые ему сообщения, которые только он и может расшифровать. Для того чтобы эта идея была реализована практически, решающим является удовлетворение требование, чтобы генерация больших случайных простых чисел и вычисление d были легкоосуществимы. К счастью, проверка чисел на простоту оказывается действительно легче их разложения на множители, благодаря вероятностным алгоритмам СоловеяШтрассена (R.
Solovay - V. Strassen)[223] и Рабина (M.O. Rabin)[197].
По поводу более связанного с криптографией вопроса генерации простых чисел (а не проверки на простоту) обращайтесь к [81,13]. Относительно описания расширенного алгоритма Евклида для вычисления d смотрите [4,94] (если же вы предпочитаете переоткрыть расширенный алгоритм Евклида самостоятельно, то можете найти полезными те указания, которые даны к задаче 8.5.12b [52]).
В качестве небольшого примера, пусть p = 19 и q = 23, так что n = 437 и ф(п) = 396. Пусть также e = 13, и поэтому d = 61, так как 13*61 = 793 = 2ф(п)+1.
Тогда сообщение в открытом текте m = 123 будет зашифровано как c = 123A13 mod(437) = 386.
Действительно, 386A61 mod(437) = 123. Особо отметим ситуацию, когда криптоаналитик, перехвативший шифртекст c = Ek(m), посланный известному пользователю, знает естественный алгоритм шифрования Ek, используемый отправителем для вычисления с. Это предположение имеет два важных следствия.
Если бы нарушитель угадал в точности открытый текст сообщения m, то он смог бы вычислить Ek(m) точно так же, как и получатель, и сравнить полученный результат с c, чтобы проверить свое предположение. Такая угроза является опасной, если число возможных открытых текстов сравнительно невелико, учитывая возможность исчерпывающего поиска.
Эта трудность может быть до некоторой степени преодолена путем разбавления коротких сообщений случайными битами, однако использование вероятностного шифрования (раздел 4.6) является более приемлемым решением. Смотрите также [206].
Другое следствие из знания нарушителем открытого алгоритма шифрования более специфично для криптосистемы RSA. Он знает, что с = mAe mod(n) для известных значений c, e и n (но не знает m). Если бы он мог разложить n (раскрыв таким образом личный секретный ключ законного получателя с), то он мог бы получить ф(п) = (p-1)*(q-1) и, применив расширенный алгоритм Евклида, вычислить d, а затем и m = cAd mod(n).
К счастью, неизвестно алгоритма, который смог бы разложить на множители двухсотзначное десятичное число за приемлемое время, и, таким образом, считается абсолютно надежным выбирать и p и q длиной примерно в сто знаков.
При выборе p и q необходима особая тщательность для того, чтобы не предоставить никаких зацепок известным алгоритмам факторизации. В частности, наибольший общий делитель p-1 и q-1 должен быть небольшим, а оба p-1 и q-1 должны иметь большие простые делители.
Блэкли (G.R. Blakley) и Борош (I. Borosh) предлагают выбирать p и q так, чтобы (p-1)/2 и (q-1)/2 были бы простыми [31].
Для более широкого обсуждения этих вопросов рекомендуем [94]. Гордон (J.A.
Gordon) предлагает эффективные способы выбора подходящих сильных простых чисел [139].
Даже если факторизация и трудна, неизвестно является ли столь же трудным и раскрытие RSA. Возможно, что d может быть вычислено из открытой информации e и n, вообще, без разложения n на множители.
Возможно также и то, что значение d (а,следовательно, и значения множителей числа n) действительно практически трудновычислимы из e и n, даже если существует иной эффективный алгоритм раскрытия m из e, n и шЛе mod(n). Были предложены другие криптосистемы с открытым ключом, для которых было доказано, что раскрытие открытого текста из доступной нарушителю информации в них, столь же трудно, сколь и разложение на множители больших чисел [196,240], но такие криптосистемы тотчас же раскрываются при атаке на основе выбранного шифртекста.
Наконец, даже если ш и в самом деле практически трудно вычисляется из той информации, которая доступна нарушителю, вероятно еще остается возможность легко получить эффективно некоторую частичную информацию, такую как половина битов m. Вероятностное шифрование решает все эти возможные слабости при простом предположении, что разложение на множители является действительно трудной задачей.
Пользователи RSA должны быть осведомлены о том, что эта криптосхема является слабой при некоторых видах атак на основе выбранного шифртекста [86,95]. Предположим, например, что нарушитель перехватил некоторое c = шЛе mod(n), где e и n открытая информация.
Ему хотелось бы определить ш. При атаке на основе выбранного шифртекста, ему предоставляется возможность передать некоторое с' законному получателю с тем, чтобы получить в ответ соответствующее ш', такое, что с'= ш'Ле mod(n). Разумно ожидать, что получатель может уклониться от ответа, если нарушитель попытается использовать непосредственно c'= c (в противном случае никакая криптосистема, вероятно, не может быть надежной).
Однако, нарушитель может замаскировать свой вопрос, выбрав случайно некоторое x из Zn* и вычислив с'= (хЛе)*с mod(n).
Исходный открытый текст ш может быть тогда получен эффективно (используя обобщенный алгоритм Евклида), поскольку ш = ш'*хЛ(-1) mod(n). Неизвестно, может ли более хитроумная атака на основе выбранного шифртекста действительно раскрыть RSA в том смысле, что позволит нарушителю вычислить множители n или, хотя бы, секретную экспоненту дешифрования d.
Если бы это было так, то последующие шифртексты можно было бы расшифровывать без необходимости обращения к законному получателю.
