РегистрацияНеправильная реализация схемы DSS
Имеем схему Digital Signature Standart.
По стандарту P выбирается так, что оно должно быть простым числом. В одной программе была обнаружена реализация ЭЦП с выбором P в качестве произведения двух простых множителей (как в RSA).
Зачем P должно быть простым, вполне понятно (чтобы всегда существовал обратный элемент в группе). Но вопрос другой: как эту информацию можно (если, конечно, можно) использовать для атаки на схему?
P от 1024 до 1025 бит
Q 64 бита (тоже является произведением двух простых чисел)
X взято по модулю Q
Y = R ^ X (mod P)
Y, P, R известны
комментариев: 2 документов: 1 редакций: 0
Брут-форс для 64-битного числа? Не думаю, что реально. Поправьте меня, если я не прав. У Q всегда старший бит ненулевой, у X может быть равен нулю (поскольку по модулю берётся).
комментариев: 9796 документов: 488 редакций: 5664
p должнo быть простым числом.
Даже если взять настоящие простые числа, но с подогнанными свойствами, то получается лазейка, что и было кажется в первоначальном варианте DSS от АНБ.
В группе Zp были обнаружены две подгруппы: в которой решение дискретного логарифма сложное и в которой простое.
Чтобы этого не повторилось, были предложены методы генерации простых p, с доказательством пользователям (или третьей стороне), что они получены честным путём и с фиксацией p и q в стандарте.
см. "Minding your p’s and q’s" Ross Anderson, Serge Vaudenay и "Designing and Detecting Trapdoors for Discrete Log Cryptosystems" Daniel M. Gordon.
Можете нагуглить ещё заявку НИСТ с описанием математических основ DSA (там кажется было доказательство на четырёх леммах) и посмотреть, что получится, если нарушить требование простоты p.
Возможно окажется, что это банальный RSA-подобный бэкдор внутри реализации DSA.
Вот, правильные бэкдоры делают в "математике", а не в программном коде!
[/offtop]
комментариев: 32 документов: 0 редакций: 0
http://en.wikipedia.org/wiki/Baby-step_giant-step
Нужно представить X в виде X = H*2^32 + L, где L,H – 32-битные числа. И построить две последовательности по модулю Q:
R, R^2, R^3, ...
Y/R^(2^32), Y/R^(2*2^32), Y/R^(3*2^32), ...
Их общий элемент как и раз и соответствует R^L = Y/R^(H*2^32).
комментариев: 2 документов: 1 редакций: 0
Q неизвестно, это несколько усложняет задачу... И точно ли Q, а не P?