Будем отталкиваться от необходимых требований стандарта RSA:
p и q - два различных простых числа, n=pq;
d взаимно просто с phi(n)=(p-1)(q-1), более того d*e=1 (mod phi(n)).
Подписью числа x, 0<=x<n, называется число x^d (mod n).
Основная идея оригинального письма в том, что для специально подбранных p и q можно указать такие различные x и y, что их подписи совпадают, т.е. x^d == y^d (mod n).
Мне сначала показалось, что такие x и y всегда существуют, но шансы найти их без знания p и q ничтожно малы. Но мои рассуждения содержали ошибку. Ниже я строго докажу, что сравнение x^d == y^d (mod n) для 0<=x,y<n влечет равенство x=y.
Таким образом, высказанные подозрения цифровой подписи на базе RSA в "дырявости" несостоятельны.
Итак, пусть n,p,q,d,e удовлетворяют требованиям указанным выше, и для x,y, 0<=x,y<n, справедливо сравнение x^d == y^d (mod n).
Рассмотрим два случая:
1) Оба числа x,y взаимно просты с n. Тогда
x == x^(de) == (x^d)^e == (y^d)^e == y^(de) == y (mod n).
Это сравнение вместе с неравенством 0<=x,y<n влечет равенство x=y.
2) Хотя бы одно из чисел x,y имеет нетривиальный общий делитель с n. Без потери общности можно считать, что НОД(x,n)=p.
Сравнение x^d == y^d (mod n) по определению выражает факт делимости (x^d - y^d) на n. Так x делится на p и n делится на p, то y тоже обязано делиться на p.
Итак, пусть x=px', y=py'. Заметим, что из неравенств x<n и y<n следует, что x'<q и y'<q.
Деля сравнение (px')^d == (py')^d (mod n) на p, получаем
p^(d-1) x'^d == p^(d-1) y'^d (mod q).
Так как p и q различные простые числа, то они взаимно просты, а поэтому p^(d-1) взаимно просто с q, и на него можно сократить:
x'^d == y'^d (mod q).
Так как q простое, x'<q и y'<q, то оба числа x' и y' взаимно просты с q. Поэтому
x' == x'^(de) == (x'^d)^e == (y'^d)^e == y'^(de) == y' (mod q).
Это сравнение вкупе с неравенствами x'<q и y'<q влечет равенство x'=y', которое в свою очередь влечет x=y.
Вывод: двух различных документов с одинаковыми подписями не бывает ни при каком выборе параметров, удовлетворяющих основным требованиям.
|
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
