Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| |
Re: Владельцу ключа параметры вроде известны :) 21.11.02 15:44 Число просмотров: 2583
Автор: Komlin Статус: Незарегистрированный пользователь
Отредактировано 21.11.02 15:46 Количество правок: 1
|
> > 2) RSA не может применяться для цифровой подписи, т.к.
> > одной и той же подписи могут соответствовать разные
> > документы.
>
> Да, одной и той же подписи могут соответствовать разные
> сообщения, но доля таких ссобщений ничтожно мала, а для
> нахождения нужно знать разложение модуля.
>
> Все это вовсе не мешает использованию RSA как для
> шифрования данных, так и для цифровой подписи.
Двойные подписи нужны только владельцу ключа, чтобы отказаться от подписанного документа. Ему-то параметры подписи известны. Более того он может их выбрать заранее
|
|
<theory>
|
Ошибка в RSA? 15.11.02 11:27
Автор: Komlin Статус: Незарегистрированный пользователь
|
Ошибка в RSA?
Одно из основных утверждений 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=65185),
но вот пример навскидку (дабы не напрягаться запустил перебор в Java) со случайными малыми простыми числами
p=131
q=8191
n=1064700
d=545025
512^d=761764;
32^d=761764;
Я понимаю, что что-то здесь неправильно, но не могу сообразить, что именно
Может с другим компилятором попробовать?
|
| | |
можно без "но" 26.11.02 10:52
Автор: pms Статус: Незарегистрированный пользователь
Отредактировано 26.11.02 10:59 Количество правок: 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 строго и не двусмысленно высказано требование, что подписываться (и проверятся) должно только значение хэш-функции.
В качестве хэш-функции можно использовать, либо SHA-1 (в новых разработках), либо MD5 (для совместимости).
Успехов.
--
"Serguei E. Leontiev"<lse@CryptoPro.ru>
http://www.cryptopro.ru
|
|
Ошибка в RSA? 21.11.02 06:14
Автор: RElf <M> Статус: Member
|
> Ошибка в 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
n = p*q
p и q – простые числа
Успехов.
--
"Serguei E. Leontiev"<lse@CryptoPro.ru>
http://www.cryptopro.ru
|
| | |
вы про какой стандарт? 25.11.02 05:21
Автор: RElf <M> Статус: Member
Отредактировано 25.11.02 05:38 Количество правок: 3
|
> Здравствуйте,
>
> > ...
> > Еще одно: 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)
> n = p*q
> p и q – простые числа
Вот цитата из
ftp://ftp.rsasecurity.com/pub/pkcs/ascii/pkcs-1v2.asc
===
RSASP1 (K, m)
Input:
K RSA private key, where K has one of the following
forms:
-a pair (n, d)
-a quintuple (p, q, dP, dQ, qInv)
m message representative, an integer between 0 and n-1
Output:
s signature representative, an integer between 0 and
n-1, or "message representative out of range"
===
|
| | | |
вы про какой стандарт? 26.11.02 03:06
Автор: Serge3 Статус: Незарегистрированный пользователь
|
Здравствуйте,
> > > ...
> > > Еще одно: 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.
Успехов.
--
"Serguei E. Leontiev"<lse@CryptoPro.ru>
http://www.cryptopro.ru
|
| |
Re: Владельцу ключа параметры вроде известны :) 21.11.02 15:44
Автор: Komlin Статус: Незарегистрированный пользователь
Отредактировано 21.11.02 15:46 Количество правок: 1
|
> > 2) RSA не может применяться для цифровой подписи, т.к.
> > одной и той же подписи могут соответствовать разные
> > документы.
>
> Да, одной и той же подписи могут соответствовать разные
> сообщения, но доля таких ссобщений ничтожно мала, а для
> нахождения нужно знать разложение модуля.
>
> Все это вовсе не мешает использованию RSA как для
> шифрования данных, так и для цифровой подписи.
Двойные подписи нужны только владельцу ключа, чтобы отказаться от подписанного документа. Ему-то параметры подписи известны. Более того он может их выбрать заранее
|
| | |
Re: Владельцу ключа параметры вроде известны :) 21.11.02 16:26
Автор: RElf <M> Статус: Member
|
> Двойные подписи нужны только владельцу ключа, чтобы
> отказаться от подписанного документа. Ему-то параметры
> подписи известны. Более того он может их выбрать заранее
Ну и что? Подпись всего лишь удостоверяет автора документа. Ничего большего от нее не требуется по определению.
То, что два документа подписанные одним лицом имеют одинаковые подписи, ничему не противоречит.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
