информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Страшный баг в WindowsСетевые кракеры и правда о деле Левина
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 С наступающим 
 Серьезная уязвимость в Apache Log4j 
 Крупный взлом GoDaddy 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Re: Владельцу ключа параметры вроде известны :) 21.11.02 16:26  Число просмотров: 2465
Автор: RElf <M> Статус: Member
<"чистая" ссылка>
> Двойные подписи нужны только владельцу ключа, чтобы
> отказаться от подписанного документа. Ему-то параметры
> подписи известны. Более того он может их выбрать заранее

Ну и что? Подпись всего лишь удостоверяет автора документа. Ничего большего от нее не требуется по определению.
То, что два документа подписанные одним лицом имеют одинаковые подписи, ничему не противоречит.
<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
<"чистая" ссылка>
> Двойные подписи нужны только владельцу ключа, чтобы
> отказаться от подписанного документа. Ему-то параметры
> подписи известны. Более того он может их выбрать заранее

Ну и что? Подпись всего лишь удостоверяет автора документа. Ничего большего от нее не требуется по определению.
То, что два документа подписанные одним лицом имеют одинаковые подписи, ничему не противоречит.
1






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2022 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach