> Двойные подписи нужны только владельцу ключа, чтобы > отказаться от подписанного документа. Ему-то параметры > подписи известны. Более того он может их выбрать заранее
Ну и что? Подпись всего лишь удостоверяет автора документа. Ничего большего от нее не требуется по определению.
То, что два документа подписанные одним лицом имеют одинаковые подписи, ничему не противоречит.
Одно из основных утверждений RSA – утверждение о существовании и единственности решения
m^e == c (mod (n)) n=pq
и
c^d == e (mod (n)) n=pq
при условии простоты p,q и взаимной простоты e и функии Эйлера (p-1)(q-1)
К сожалению это не совсем так.
Рассмотрим выражение a mod n
Его можно представить как a mod pq == a mod p + (([a / p]) mod q) *p
[a/p] означает целую часть от деления a/p
Из него следуют выводы:
xq^p mod n = xq
xq^(yp) mod n = xq^y
xq ^ (x(p-1)) mod p = const т.е. постоянен вне зависимости от значений x,y.
Из последних утверждений следует также
(q-1)^(p-1) mod n =1
(q+1)^(p-1) mod n =1
или
(m(q+-1))^(p-1) mod n = m^(p-1) mod n
Отсюда следует, что выражения m^d mod n сводимые к a*(q+-1)^(p-1) будут иметь общие решения с a^d mod n(Напрямую использовать p-1 в качестве ключа нельзя). Способов получить такие выражения довольно много.
Пример.
Пусть есть простое q=i^t+-1
Тогда при d=t и z=(i)^(p-1)
c^d mod n = (cm)^d mod n.
Практические последствия этой формулы достаточно просты.
1) Возможен такой выбор параметров, что RSA будет работать неправильно и приведёт к потере данных
2) RSA не может применяться для цифровой подписи, т.к. одной и той же подписи могут соответствовать разные документы.
попытка закрыть тему: коллизий не бывает26.11.02 06:44 Автор: RElf <M> Статус: Member Отредактировано 26.11.02 07:31 Количество правок: 1
Будем отталкиваться от необходимых требований стандарта 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.
Вывод: двух различных документов с одинаковыми подписями не бывает ни при каком выборе параметров, удовлетворяющих основным требованиям.
вроде всё правильно, но26.11.02 08:45 Автор: Komlin Статус: Незарегистрированный пользователь Отредактировано 26.11.02 08:50 Количество правок: 1
> Вроде всё в Ваших выводах правильно, по сути и без них > понятно, что решение a^d mod n=b должно быть единственным > (см. мой постинг > http://www.bugtraq.ru/cgi-bin/forum.cgi?type=sb&b=15&m=6518 > 5), > > но вот пример навскидку (дабы не напрягаться запустил > перебор в Java) со случайными малыми простыми числами > p=131 > q=8191 > n=1064700 > > d=545025 > 512^d=761764; > 32^d=761764; > > Я понимаю, что что-то здесь неправильно, но не могу > сообразить, что именно
Не выполняется условие взаимной простоты d с phi(n)=130*8190.
> Может с другим компилятором попробовать?
у меня получились такие же значения, так что не стоит-)
Спасибо всем. Не работал поиск НОД.26.11.02 12:31 Автор: Komlin Статус: Незарегистрированный пользователь
Спасибо всем. Как выяснилось в программе некорректно работал поиск НОД, поэтому проходили недопустимые значения сбивая меня и окружающих с толку.
Экспериментально проверил очень длинный ряд простых получаемых из степенных функций .
p=a^t+-1
Всегда p и t имеют НОД >1
Интуитивно об этом догадывался, но верил программе :(
Тема закрыта. Коллизий быть не может. Топик ошибочен.
Как вы думаете стоит его удалять или пусть одной глупостью будет больше?
Александр.
Ошибка в RSA?24.11.02 08:07 Автор: Serge3 Статус: Незарегистрированный пользователь
> Ошибка в RSA? > > Одно из основных утверждений RSA – утверждение о > существовании и единственности решения > m^e == c (mod (n)) n=pq > и > c^d == e (mod (n)) n=pq > при условии простоты p,q и взаимной простоты e и функии > Эйлера (p-1)(q-1)
Еще одно: m должно быть взаимно просто с n.
Так как вероятность того, что это не так, близка к 0, то это условие обычно не упоминают.
В своих выкладках вы как раз используете такие "плохие" основания.
[...]
> Практические последствия этой формулы достаточно просты.
Посылки верные, а выводы нет.
> 1) Возможен такой выбор параметров, что RSA будет > работать неправильно и приведёт к потере данных
Это не зависит от выбора параметров. Для любых параметров есть такие сообщения, которые будут не правильно шифроваться/расшифровываться. Но их доля ничтожна мала, а нахождение хотя бы одного такого сообщения равносильно взлому RSA.
Тот, кто знает секретный ключ (разложение модуля), может найти такие сообщения без труда.
> 2) RSA не может применяться для цифровой подписи, т.к. > одной и той же подписи могут соответствовать разные > документы.
Да, одной и той же подписи могут соответствовать разные сообщения, но доля таких ссобщений ничтожно мала, а для нахождения нужно знать разложение модуля.
Все это вовсе не мешает использованию RSA как для шифрования данных, так и для цифровой подписи.
Ошибка в RSA?24.11.02 08:00 Автор: Serge3 Статус: Незарегистрированный пользователь
> Здравствуйте, > > > ... > > Еще одно: m должно быть взаимно просто с n. > > Так как вероятность того, что это не так, близка к 0, > то > > это условие обычно не упоминают. > > Если мне не изменяет память, она СТРОГО РАВНА 0, т.к. > m < p > m < q
Это где такие требования?
В RSA PKCS#1 требование m<n (см. ниже). Соответственно, вероятность попасть на "плохое" m примерно равна:
1 - phi(n)/n = 1 - (p-1)(q-1)/pq = (p+q-1)/pq ~= 2/sqrt(n)
Здравствуйте,
> > > ... > > > Еще одно: m должно быть взаимно просто с n. > > > Так как вероятность того, что это не так, близка > к 0, > > то > > > это условие обычно не упоминают. > > > > Если мне не изменяет память, она СТРОГО РАВНА 0, т.к. > > m < p > > m < q
Извините, ошибся.
Согласно стандартам на ЭЦП с RSA (rfc 3279, DSS и т.п.) MD = SHA-1(message) или MD = MD5(message).
При этом эти стандарты накладывают существенные ограничения на возможный диапазон m. На пример, в случае 1024 битных ключей RSA и SHA-1:
01 00 115*FF 00 10*00 < m < 01 00 115*FF 00 10*FF
В "псевдо-шестнадцатеричной" записи, где 10*FF это 160 бит "1".
Соответственно вероятность того, что m не является взаимно простым с n, действительно отлична от 0.
> > 2) RSA не может применяться для цифровой подписи, т.к. > > одной и той же подписи могут соответствовать разные > > документы. > > Да, одной и той же подписи могут соответствовать разные > сообщения, но доля таких ссобщений ничтожно мала, а для > нахождения нужно знать разложение модуля. > > Все это вовсе не мешает использованию RSA как для > шифрования данных, так и для цифровой подписи.
Двойные подписи нужны только владельцу ключа, чтобы отказаться от подписанного документа. Ему-то параметры подписи известны. Более того он может их выбрать заранее
Re: Владельцу ключа параметры вроде известны :)21.11.02 16:26 Автор: RElf <M> Статус: Member
> Двойные подписи нужны только владельцу ключа, чтобы > отказаться от подписанного документа. Ему-то параметры > подписи известны. Более того он может их выбрать заранее
Ну и что? Подпись всего лишь удостоверяет автора документа. Ничего большего от нее не требуется по определению.
То, что два документа подписанные одним лицом имеют одинаковые подписи, ничему не противоречит.
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
