РегистрацияЭЦП на базе проблемы вычисления дискретных логарифмов
Большинство современных алгоритмов ЭЦП основаны на трудности вычисления дискретных логарифмов. Все они очень чувствительны к выбору некого случайного числа k, которое необходимо выберать заново при каждой подписи. Две разные подписи с одним и тем же значением k — и ваш закрытый ключ взломан (НИКОГДА не записывайте на бэкап файл random seed!). То же самое, если злоумышленник сможет каким-то образом узнать значение k использoванное при одной из подписей.
Мой вопрос состоит вот в чем: что если k вычислять как H(H(M), K), где H — хеш функция, M — сообщение, K — закрытый ключ? Таким образом, владелец ключа всегда может убедиться в том, что ему не "подсунули" реализацию с предсказуемым k, и что для разных сообщений будет использованы разные k.
Единственное предостережение, что хеш функция должна быть та же самая, что используется для хеширования сообщения, чтобы в случае коллизий они происходили вместе: то есть k1 и k2 для разных сообщений M1 и M2 при том же самом ключе равны если H(M1) и H(М2) тоже равны, и в этом случае не раскрывается закрытый ключ, хотя, конечно подпись проверяется и с тем и с другим сообщением.
Есть в таком подходе к выбору k подводные камни, которые я не заметил?
Единственное неоспоримое приймущество подписи RSA перед схемами на базе д. л. — это гарантия того, что при одном и том же сообщении и закрытом ключе вычисляется одна и та же подпись. Хотелось бы того же добиться от DSA, Schnorr, ElGamal или ГОСТ 34.10.
комментариев: 9796 документов: 488 редакций: 5664
Мне еще не нравится, что противник всегда может подбирать какие-то хитрые значения M на подпись и вообще выставлять хэш закрытого ключа ("подсоленный" сообщением вероятного противника) на всеобщее обозрение как-то не принято. Точно не могу назвать причины, но думаю это не просто так.
О проблеме выбора случайного числа известно давно для DSA и других, если бы ее можно было так легко решить, то наверное так бы и сделали.
В свое время так пытались избавится от вектора IV для CBC, когда получатель расшифровывает все блоки, кроме первого, от них считает хэш, а этот хэш использует для расшифровки первого блока. Не надо лишний блок тратить под IV. Но не помню почему, этот метод тоже не используют.
Посмотрю, подумаю, если что-то в голову конкретное придет – обсудим.
комментариев: 9796 документов: 488 редакций: 5664
Тогда для секретного сеансового параметра k Боб считает:
k = PRNG(M, K) = H(H(M), K)
Но если Алиса будет отправлять M=M+1 (счетчик со сдвигом битов), то Боб будет
считать:
k=PRNG(Counter, K)=H(H(Counter), K),
а этой плохой PRNG. Стойкие PRNG из хэшей так делать не рекомендуют (подобное возможно только для блочных шифров), например PRNG в SSL использует более сложную итеративную структуру из HMAC, а не простой счетчик.
Правда я не знаю, что останется от выходя этого PRNG после всех вычислений и модулярных возведений в степень, но если Алиса может формировать какие-то сообщения на подпись Бобу, она может придумать какой-нибудь способ отыскать k и вычислить его секретный ключ.
Может быть Алиса будет генерировать пары сообщений с какими-то дифференциальными свойствами или использует еще какой-то трюк для взлома функции хэширования. Поэтому, наверное для универсальности принято использовать независимое случайное число.
Тут противник не имеет доступа к результатам вычисления. По-этому если хэш-функция удовлетворяет однонаправленость (даже стойкость к коллизиям не нужна!), то простой H(M, K) вполне подходит. Q. E. D.
В вашем примере Алиса может овладеть ключем Боба. (вообще-то его зовут Трент, если уже использовать классический кастинг)
Делаем выводы. В своей консультантской практике я придерживаюсь следующему правилу при выборе алгоритма для ЭЦП:
Предлагаемый метод имеит смысл только во втором сучае; Трент пусть доверяет сам себе и своим случайным числам. Но ожидать этого же от Алисы — несправедливо. Для нее это неоправданно дорого.
Конечно то, что я предлагаю, тоже хуже, чем RSA, так как только Алиса (и никто другой) может убедиться в том, что все в порядке. Так что скорее всего рекомендации остаются в силе: для сервера — DSA (со случайным k), для человека — RSA.
комментариев: 9796 документов: 488 редакций: 5664
Трента вводят, когда Алиса и Боб уже есть, а он нотариус между ними. Я просто упростил. Надо было подробнее описывать протокол – ввести двух участников и сервер между ними. Я третьего участника оставил за скобками. А когда Алиса пытается одна кого-то обмануть его тоже можно назвать Бобом, а не Трентом. (Это не я придумал) К тому же Боб – по-русски какое-то глупое имя. Как раз подходит, чтобы его оставить в дураках.
В целом, я с Вашими рассуждениями пока согласен, мне кажется, когда принимали стандарт его пытались сделать универсальным и предложенный Вами метод никому не пришло в голову рассматривать.
А Вы видимо создаете протокол под свое облегченное решение походных ключей, о чем раньше никто всерьез не думал.
Именно поэтому я не рекомендую использовать DSA для индивидуальных пользователей. Слишком легко совершить фатальную ошибку и слишком трудно ее заметить.