id: Гость   вход   регистрация
текущее время 18:34 29/03/2024
Владелец: SATtva (создано 14/09/2006 22:50), редакция от 17/12/2007 19:55 (автор: SATtva) Печать
Категории: криптография, софт, pgp, алгоритмы, шифрование с открытым ключом, сайт проекта, статьи, эцп
создать
просмотр
редакции
ссылки

Алгоритмы с открытым ключом


Алгоритмы с открытым ключом, или PK-алгоритмы, это такие, где ключи существуют в парах: один из ключей называется открытым, и его можно передавать кому угодно. Другой ключ из пары – закрытый. Эти ключи обратны друг другу: открытый может "обратить" действие закрытого (т.е. сверить подпись), а закрытый ключ – обратить операцию открытого (расшифровать данные). Еще одно свойство асимметричных ключей в том, что из открытого ключа нельзя вычислить закрытый.


Хороших алгоритмов с открытым ключом не так много. Этот факт может показаться странным, ведь информатике известно множество NP-полных задач, и каждая из них должна быть применима для фундамента своего алгоритма. К несчастью, на практике большинство этих трудных задач имеют ряд более простых частных случаев, и вы не захотите рисковать своим секретным ключом, основывая его на задаче с возможным легким решением.


На сегодня существует две проблемы, стойко выдержавших все испытания: разложение на множители (факторизация) и вычисление дискретных логарифмов. Алгоритм RSA основан на проблеме факторизации. Известно несколько вариантов RSA, но есть один изначальный, который и реализован в PGP.


Проблема дискретных логарифмов более интересна. Она заключается в нахождении такого x при данных p, g и y, что gx = y (mod p). В схемах с открытым ключом на дискретных логарифмах y является открытым ключом, а x – секретным, но осуществлять шифрование с помощью этих чисел можно несколькими путями. Кроме того, проблема вычисления дискретных логарифмов распространяется и на отличные от Ζp∗ (мультипликативной) группы, например, на многочлены и объекты вроде эллиптических кривых. Трудно сказать, являются ли все они разными алгоритмами с открытым ключом или просто вариациями одного PK-алгоритма. Первой системой, основанной на дискретных логарифмах, был интерактивный протокол, разработанный Диффи и Хеллманом. ElGamel является общим названием целого класса дискретно-логарифмических систем, но в PGP предпочитают название Diffie-Hellman. Они выбрали это название из-за его большей известности, из-за того, что Cylink просил об этом, когда разработчики программы спрашивали разрешения на включение DH в PGP, и из-за того, что разница между системами, созданными Диффи и Хеллманом и Эльгамалем не столь велика.

RSA


RSA – наиболее известный алгоритм с открытым ключом. Он применялся еще в первой версии PGP. RSA основан на теории чисел: он использует большие простые числа. Его изобрели Рональд Райвест, Ади Шамир и Леонард Адлман и впервые опубликовали в апреле 1977 года. Алгоритм получил популярность даже несмотря на проблемы с патентом.

Генерация ключа


Ключ всегда создается определенного размера. Больший ключ будет более медленным, но также и более защищенным от разложения на множители. Так как методы факторизации постоянно улучшаются, то и рекомендации к длине ключей слегка возрастают. В настоящее время они составляют 1024 бита. Длина ключа – это размер числа n, представленный в битах. Чтобы сгенерировать ключ, пользователь случайным образом выбирает


  • p, большое простое число, вполовину меньшее n (скажем, 512 бит). p выбирается как первое простое число, следующее за произвольно выбранным числом, и начинающееся с битов 11 для обеспечения размера n. Выбирается не обязательно первое попавшееся простое число, а перебирается 256 элементов от стартовой точки, дабы снизить шанс выбора простого числа, следующего за большим промежутком без простых чисел.
  • q, другое простое число (тоже 512 бит). В PGP q выбирается не слишком близко к p и так, чтобы q было больше p (если не менять числа местами). Оно также начинается с битов 11.
  • e, любое удобное число, взаимно простое с (p-1)(q-1). Небольшие числа с малым весом Хемминга обсчитываются быстрее, поэтому наиболее распространенные значения – это 3, 17 и 65537. 3 – весьма рискованное число, смотрите ниже раздел об атаках на малую экспоненту, так что новые версии используют 65537. Если избранное e не взаимно простое с (p-1)(q-1), выберите другие значения для p и q.

Затем пользователь вычисляет


  • n = p∗q. Длина n – это длина ключа. Она будет равна размеру p плюс размер q, потому как в PGP они оба начинаются с 11.
  • φ(n) = (p-1)∗(q-1). Это значит, что mφ(n)mod(n) = m для каждого m. Если вы посмотрите исходный код PGP, вы увидите, что вместо (p-1)∗(q-1) они используют φ(n) = lcm(p-1,q-1). Из-за того, что здесь число меньше, вычисление происходит немного быстрее, к тому же оно дает такое же d, так что это не принципиально.
  • d = e-1 mod φ(n).
  • u = p-1 mod q.

Открытый ключ состоит из (n, e). Закрытый ключ – из (n, e, d, p, q, u).

Применение


  • зашифрование короткого сообщения x: преобразуйте x в большое число m такое, что 1<m<n, и рассчитайте шифртекст C = me mod n.
  • подписание хэш-значения h: преобразуйте h в большое число m такое, что 1<m<n, и рассчитайте подпись S = md mod n.
  • расшифрование: вычислите m = Cd mod n.
  • сличение подписи: проверьте, что m = Se mod n.

Вычисления наподобие S = md mod n можно выполнить быстрее, если, обладая закрытым ключом, первоначально рассчитать s1 = md mod p и s2 = md mod q. Это будет быстрее потому, что p и q меньше, чем n. Теперь у нас есть S = s1 + p ∗ u ∗ (s2 – s1) mod n. В литературе это называется применением китайской теоремы об остатках.


Это описание RSA немного длиннее, чем то, которое приводится в большинстве книг, потому что включает в себя ряд особенностей реализации из потрохов PGP (в частности, дополнительные переменные в закрытом ключе).


Есть несколько способов преобразовать сообщение x в большое число, но не все из них одинаково хороши. Метод, используемый в PGP, описан в параграфе "Дополнение".

Проблемы RSA


Считается, что RSA очень надежен. Еще никто не продемонстрировал полный взлом алгоритма, как было, например, с другими ранними криптосистемами, основанными на проблеме укладки ранца. Рекомендованный размер ключа очень сильно возрос из-за совершенствования методов факторизации. С помощью сегодняшних технологий возможно разложить на множители 512-битовое число, поэтому ключи короче 768 бит находятся на краю безопасности, а рекомендуется использовать 1024-битовые и более крупные ключи. Также существует ряд атак на особые случаи RSA. Следующий список приводит [некоторые] способы взлома.

Факторизация ключа

Самый агрессивный способ взлома RSA – попытаться факторизовать n. Если вы найдете один из сомножителей n, то сможете вычислить закрытый ключ. Для этих целей был разработан ряд хороших методик. Квадратичное решето (QS), описанное в [20], глава 14, является простым методом. Чтобы факторизовать n, оно ищет пару чисел, таких, что x2 = y2 mod n. Если это удается, тогда, для некоторого k, (x-y)(x+y) = k∗n, и велика вероятность, что НОД(x-y,n) либо НОД(x+y,n) является множителем n. Чтобы найти подобную пару собирается множество соотношений z = k2 mod n, для таких z, которые можно разложить на малые простые сомножители. Эти соотношения можно объединить: если v = l2 mod n и w = m2 mod n, то vw = (lm)2 mod n. Используя линейную арифметику, можно среди комбинаций соотношений отыскать такие, где каждый из малых простых сомножителей встречается среднее количество раз. Если это удастся, тогда z = i pi 2ei = (i pi ei) 2, и мы получаем пару квадратов.


QS выполняется за субэкспоненциальное время, его вариант отметился в 1994 году разложением на множители 428-битового числа. А решето числового поля – еще более быстрый алгоритм.

Атака на предсказуемое сообщение

Если с помощью RSA вы отправляете короткое сообщение из возможной небольшой группы сообщений и при этом не дополняете сообщение особым образом, а просто вставляете в его начало нули (то, что считается обычным способом дополнения), взломщик может попытаться зашифровать все возможные сообщения, пока не найдет совпадающее с вашим. Для предотвращения подобной атаки всегда используйте преобразование сообщения в число, при котором к его началу добавляется по меньше мере 80 случайных битов.

Атака 1 на малую экспоненту

Зачастую реализации используют значение e = 3, поскольку столь малое значение делает процесс шифрования и проверки подписей быстрее. Если при этом сообщение оказывается короче одной третьей длины n, то раскрыть сообщение становится очень просто. Зашифрованный текст C = m3 mod n = m3, потому что me<n. В таком случае оппонент может найти значение C, используя метод двоичного поиска. Эта атака возможна только для детских реализаций RSA. В этом же одна из причин применения сложных схем дополнения.

Атака 2 на малую экспоненту

Если пользователь шифрует одно сообщение m для нескольких получателей (разными открытыми ключами) при том, что все они используют e = 3, взломщик опять же сможет найти значение m3 по трем разным шифртекстам. Он может прибегнуть к китайской теореме об остатках, чтобы вычислить m из уравнений
c1 = m3 mod n1
(3.4)
c2 = m3 mod n2
(3.5)
c3 = m3 mod n3
(3.6)

Для предотвращения этой атаки никогда не шифруйте одинаковые числа дважды. Всякий раз добавляйте какие-то случайные байты в каждую новую операцию. Эта атака также работает и для других малых значений e, но оппоненту для применения этой методики всегда нужно e зашифрований для e разных ключей, поэтому при e = 65537 атака становится более трудновыполнимой.

Атака 3 на малую экспоненту

Описанную выше атаку на малую экспоненту можно обобщить: если шифруемые сообщения каким-то образом связаны, они образуют набор уравнений, которые могут быть легко решены. В качестве примера подобной атаки допустим, что e = 3, и вы шифруете одно сообщение для семи разных людей. Чтобы предотвратить атаку, вы создаете mi, где за m следует метка времени, уникальная для каждого получателя. Математически, mi = m ∗ 232 + ti. Если злоумышленнику известны значения ti, он может решить систему из этих семи уравнений. Использованная методика была описана в [8]. Для защиты от этой атаки всегда используйте для дополнения секретные случайные биты. Также не стоит использовать e = 3, поскольку оно намного уязвимее для атаки, нежели большие значения.

ElGamal/Diffie-Hellman


Этот алгоритм, называемый DH в PGP, но в литературе именуемый ElGamal, применяется в PGP 5.0 только для шифрования, но не для подписания, поскольку создаваемые им подписи слишком длинны. Подпись по Эльгамалю допустима и безопасна и наверняка будет реализована в будущем, 1 но сама его ЭЦП состоит из двух чисел длиной от 1024 бит, тогда как RSA использует только одно такое число, а DSA – всего лишь два 160-битовых.

Генерация ключа


  • Выбирается простое число p. Длина p определяет длину ключа, и обычно составляет 1024 бита.
  • Находится значение генератора g достаточно большой подгруппы порядка простого числа (т.е. g должен произвести набор чисел gi mod p). Достаточно большая – это по меньшей мере 160 бит. Мы ищем такое g, что 1<g<p, при этом gq mod p = 1 для простого q. Это возможно только для q, делящего p-1.
  • Находится секретное значение x. Размер x выбирается небольшим, поскольку этим можно ускорить вычисления без ущерба для безопасности. Расчеты PGP основаны на работе Майкла Винера: для 2048-битового ключа выбирается 225-битовый x, а полная таблица размеров x приведена в pgpKeyMisc.c. Исходя из расчетов безопасности в документе, его длина должна быть минимум 160 бит.
  • Вычисляется y = gx mod p.

Открытый ключ – это (p, g, y). Закрытый ключ – (p, g, y, x).


Есть несколько способов проделать описанное выше. Можно найти p = 2∗q+1 при простом q. В этом случае подойдет и g = 2. Такое p называется числом Софи Жерман и дает очень стойкий ключ ElGamal, но на его поиск требуется значительное время, поскольку такие простые числа редки. Считается безопасным распределять p и g между группой пользователей, так что PGP может использовать некоторые предрассчитанные значения. Эта возможность называется ускоренной генерацией. Третий способ состоит в том, чтобы взять случайное простое q на несколько бит короче требуемой длины p (скажем, на 10-20 бит). Пробуя ряд значений k, вычисляется такое p, чтобы p = 2∗k∗q+1, после чего проверяется, чтобы 2(p-1)/q не было равно 1. Если это так, то g = 2 – хороший выбор, если же нет, тогда пробуются другие значения k.

Зашифрование


Сообщение m дополняется по правилам PKCS, описанным в [10], чтобы преобразовать его в положительное число, меньшее p. Отправитель выбирает случайное k, чтобы 0<k<(p-1). Наконец, он вычисляет


  • a = gk mod p
  • z = m ∗ yk mod p

Шифртекст сообщения – это (a, z).

Расшифрование


  • m = (ax) -1 ∗ z mod p

Стойкость ElGamal


По-видимому, этот алгоритм очень надежен. Для него нет "атак на малый показатель генератора", так что единственной возможностью взлома представляется решение проблемы дискретных логарифмов. Существует тесная связь между решением ДЛ-проблемы и факторизацией. В действительности, можно сказать, что решить ДЛ-проблему в группе Ζp столь же сложно, как и разложить на множители составное число размера p.


Алгоритмы вычисления дискретных логарифмов можно разделить на теоретико-групповые, которые применимы ко всем вариантам схемы Эльгамаля, даже к работающим в иных группах, а также на специфические для группы Ζp. Специфический алгоритм – это индексное исчисление, являющийся дискретно-логарифмической версией квадратичного решета. Он описан в [20].


Теоретико-групповой алгоритм – это алгоритм Шенка "шаг ребенка – шаг великана" (baby step – giant step). Пусть m = √(верх.предел(x)). Вам нужно узнать x при x = gy в определенной группе. Запишите x = x1 ∗ t – x2 для (x1, x2) ≤ m. Равенство y ∗ gx2 = (gt) x1 справедливо. Создайте таблицу T, содержащую, для всех значений x1, (gt) x1. Затем попытайтесь рассчитать y∗gx2 для всех значений x2 и ищите аналогичные результаты в T. Если обнаружите совпадение, значит, вам известны x1 и x2, а отсюда и x.


Время исполнения этого алгоритма составляет (верх.предел(x)). Это лучшее, что доступно для теоретико-группового алгоритма, таким образом, PGP защищен от подобного рода атак, поскольку их проведение означает выполнение более 280 шагов.


Если же вы хотите решить ДЛ-проблему в группе Ζp и вам известно что-то о факторизации порядка значения g, к примеру, ord(g) = a∗b∗c, вы можете решить дискретный логарифм за время, зависящее от самого крупного сомножителя ord(g). По этой причине всегда необходимо, чтобы ord(g) содержал по крайней мере один крупный сомножитель. Алгоритм для решения этой задачи называется алгоритмом Полига-Хеллмана.

DSA


Алгоритм цифровой подписи Digital Signature Algorithm, являющийся частью Стандарта цифровой подписи (DSS), – это американский стандарт для подписи документов. Он может применяться только для подписания. Его основным преимуществом перед схемами подписи RSA и Эльгамаля является значительно меньшая ЭЦП. Стандарт DSS [15], описывающий DSA, был опубликован в 1994 году.


DSA – это особый вариант схемы Эльгамаля, называемый подгрупповым Эльгамалем. Такая версия Эльгамаля осуществляет расчеты внутри достаточно большой группы, порядка 1024 бит, однако числа для ЭЦП выбираются из меньшей подгруппы (2160 элементов), и разработчики преуспели в создании протокола, в котором для определения этих элементов подгруппы требуется всего лишь 160 бит. Это делает DSA вариантом Эльгамаля, производящим очень компактную подпись: ему требуется только два 160-битовых числа вместо двух 1024-битовых.


Алгоритм создавался Национальным институтом стандартов и технологий США (NIST), но с привлечением помощи из АНБ. После принятия стандарта он подвергся серьезной критике, поскольку люди привыкли к использованию RSA, а тут правительство взялось пересаживать их на DSA. Также высказывались замечания в адрес того, что это лишь стандарт для цифровой подписи, но не для шифрования. Возможно, это и правда, что АНБ не стало бы помогать людям шифровать свои данные, однако DSA как алгоритм подписи не становится от этого хуже.


Стандартизированная длина ключа DSA варьируется от 512 до 1024 бит. Это не очень много: 512 бит определенно недостаточно, и 1024 бита представляются единственным разумным вариантом; стандарт явно не продержится вечно. Объяснение малому размеру ключа состоит в том, что могущественные правительственные взломщики наподобие АНБ будут всегда пытаться раскрывать шифрование, но не подделывать подписи: стоит им начать прибегать к такой возможности, это не останется незамеченным, и для людей больше не будет секретом, что они на это способны. Так что нам нужно опасаться не правительства, а лишь менее значительных врагов. Так или иначе, PGP всегда создает 1024-битовые ключи DSA, что считается достаточно надежным.

Генерация ключа


  • Выберите 160-битовое простое число q.
  • Найдите такое 1024-битовое простое p, чтобы q|(p-1).
  • Найдите такие a и g, что g = a(p-1)/q mod p при g≠1.
  • Выберите случайное число x, чтобы 0<x<q.
  • Рассчитайте y = gx mod p.

Открытый ключ – это (y, p, q, g), закрытый – x.

Генерация подписи


  • Выберите случайное число k, чтобы 0<k<q.
  • Вычислите r = (gk mod p) mod q.
  • Вычислите s = (k–1 ∗ (H(m) + x ∗ r)) mod q, где H(m) – хэш-значение сообщения.

(r, s) образуют подпись.

Сверка подписи


  • Убедитесь, что 0<r<q и что 0<s<q.
  • Вычислите t = s–1 mod q.
  • Вычислите u1 = t ∗ H(m) mod q.
  • Вычислите u2 = t ∗ r mod q.
  • Проверьте, чтобы r = (gu1 ∗ yu2 mod p) mod q.

Заметьте, что, в отличие от подписи RSA, вы не можете извлечь из ЭЦП хэш-значение сообщения. Так происходит из-за свойств подгруппового Эльгамаля: данные числа содержат достаточно информации, чтобы провести проверку, но не чтобы воссоздать ввод.


Подпись не определяет, какой алгоритм хэширования применять в вычислениях. Официальный стандарт указывает на использование SHA, однако PGP допускает применение любой 160-битовой хэш-функции. Теоретически, включение в PGP слабой хэш-функции может вызвать проблемы (см. пункт "DSA" в параграфе "Version 3").

Дополнение


Дополнение – это процедура преобразования произвольного сообщения в формат больших чисел, необходимых для алгоритмов RSA и ElGamal. Зачастую данные требуется расширить, поскольку сообщение оказывается короче числа нужной длины. Дополнение является жизненно важным для безопасности – большинство алгоритмов с открытым ключом беззащитны против атак с помощью специально подобранных чисел.


Описанная здесь процедура дополнения была разработана специально для RSA, однако применяется и для алгоритма Эльгамаля. Подробности приведены в [10]. Это документ из серии PKCS, Стандартов для криптографии с открытым ключом (Public Key Cryptography Standards), поддерживаемых компанией RSA Security. Дополнение описано в документе #1, конкретно в его версии 1.5. Этот документ также является и RFC под номером 2313. Есть и его более свежий вариант — RFC 2437.


Строка правильного формата байтов (размерность size(n)/8, округленная в сторону увеличения) формируется путем конкатенации составляющих 00, BT, PS, 00, M. Здесь предполагается шестнадцатеричная нотация, поэтому 00 означает null-байт. Составляющие имеют значения:


  • BT – однобайтовый тип блока. Принимает значение 01 для операции подписания и 02 – для шифрования. Значание 00 также упоминается в RFC, однако оно не рекомендуется и не применяется в PGP.
  • PS – строка дополнения. Имеет произвольную длину и состоит из множества FF-байтов при BT в значении 01 либо из ненулевых случайных байтов, если BT в значении 02. В последнем случае байты дополнения должны быть истинно случайны, не псевдослучайны.
  • M – ваше сообщение. В PGP это сеансовый ключ, дополненный двухбайтовой контрольной суммой, либо хэш-значение с определенным префиксом, идентифицирующим использованный хэш-алгоритм. Контрольная сумма вычисляется путем сложения всех байтов сообщения по модулю 65536.

Приложение должно проверить контрольную сумму, а также FF-байты в строке дополнения. Причина, почему для шифрования используют случайные байты, а для подписи фиксированные, в том, что вы не хотите позволить оппоненту угадать шифруемое число, тогда как для подписи это не важно. При подписании вы не хотите допустить, чтобы получатель сверял разные случайные числа, пока, в конце концов, не получит нечто, похожее на верную подпись: взломщик может воспользоваться этим, чтобы подделывать подпись. В этом случае ему не удастся отобразить заверенный документ, но для каких-то приложений даже такого вида подделки будет довольно.


Одной небольшой потенциальной уязвимостью представляется то, что процедура подписания не содержит случайного дополнения. Если в процессе подписания что-то пойдет не так, взломщик будет точно знать ввод алгоритма и сможет сопоставить числа, чтобы получить некоторые данные о секретном ключе. При использовании такого типа дополнения в PK-алгоритме вроде RSA (где сообщение можно восстановить из подписи), я советую добавлять в сообщение 10 случайных байт. Это поможет предотвратить атаки, описанные в параграфе "RSA".


Назад | Дальше



1 Попытка реализовать цифровую подпись по схеме Эльгамаля предпринималась в GnuPG. К несчастью, в ходе одного из обновлений программного кода в алгоритм была внесена ошибка, благодаря которой стало возможным тривиально взломать любой закрытый ключ, обладающий возможностью подписи по Эльгамалю. В связи с этим инцидентом в стандарте OpenPGP был поставлен запрет на поддержку этого алгоритма подписи из-за тонких нюансов его реализации, – прим. пер.


 
Комментариев нет [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3