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





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
вы про какой стандарт? 25.11.02 05:21  Число просмотров: 2840
Автор: 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"
===
<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-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach