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





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Какой-то он (алгоритм) "слишком" вероятностный... 15.07.04 13:14  Число просмотров: 3447
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
<"чистая" ссылка>
А для одной пары p и q секретный ключ единственный или их может быть много?
Любое ли небольшое простое число может быть открытым ключем?
<theory>
Секретный ключ RSA 14.07.04 14:12  
Автор: -=ut=- Статус: Незарегистрированный пользователь
<"чистая" ссылка>
Пара вопросов знатокам RSA, plz.

В книге Б. Шнайера "Прикладная криптография" описан алгоритм RSA и затем сказано, что в RSA зашифровать сообщение можно открытым ключом(расшифровывать - секретным) а можно также поступить наоборот, т.е. зашифровать секретным ключом, а расшифровать открытым.
Сущестует ли дополнительные атаки(кроме описанных в книге) на схему RSA в случае, если сообщение зашифровывается секретным ключом, а расшифровывается открытым?

И еще один вопрос. Возможно ли зная секретный ключ и модуль n=p*q восстановить открытый ключ или эта задача сводится к задаче нахождения секретного ключа по заданному открытому и заданному модулю n?
К слову, секретный ключ не используется для шифрования... 14.07.04 23:10  
Автор: RElf <M> Статус: Member
<"чистая" ссылка>
> Сущестует ли дополнительные атаки(кроме описанных в книге)
> на схему RSA в случае, если сообщение зашифровывается
> секретным ключом, а расшифровывается открытым?

К слову, секретный ключ не используется для шифрования сообщений. Шифрование секретным ключом в основном используется в схемах цифровой подписи, где шифруется как правило только хэш от сообщения.
Не совсем так 15.07.04 04:53  
Автор: Ktirf <Æ Rusakov> Статус: Elderman
<"чистая" ссылка>
Секретный ключ может использоваться для шифрования сообщений, равно как и в качестве цифровой подписи. Это просто два различных варианта его использования, в равной степени применимых.
Можно и микроскопом гвозди забивать, и из пушки палить по... 15.07.04 08:17  
Автор: RElf <M> Статус: Member
<"чистая" ссылка>
> Секретный ключ может использоваться для шифрования сообщений, равно как и в качестве цифровой подписи. Это
> просто два различных варианта его использования, в равной степени применимых.

Можно и микроскопом гвозди забивать, и из пушки палить по воробьям, но вот практического смысла в этом мало. Как и в шифровании сообщений с помощью секретного ключа RSA.
Ключи не просто так называются "секретный" и "открытый"... 14.07.04 22:55  
Автор: RElf <M> Статус: Member
Отредактировано 14.07.04 23:03  Количество правок: 2
<"чистая" ссылка>
> Возможно ли зная секретный ключ и модуль
> n=p*q восстановить открытый ключ или эта задача сводится к
> задаче нахождения секретного ключа по заданному открытому и
> заданному модулю n?

Ключи не просто так называются "секретный" и "открытый". Первый держится в секрете, второй - известен всем. Поэтому восстановление открытого ключа не имеет практического смысла - он и так известен.
Если же за названиями "секретный"/"открытый" у вас ничего не стоит, то ключи (и задачи восстановления одного по другому) полностью симметричны. Но опять же с практической точки зрения "открытая" экспонента часто выбирается неким маленьким простым числом, например, 17 или 65537. В этом случае "восстановить" ее можно просто перебором популярных значений.
Следует сделать акцент на слове КЛЮЧ 15.07.04 10:58  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
> Ключи не просто так называются "секретный" и "открытый".
> Первый держится в секрете, второй - известен всем. Поэтому
Отличия не только в доступности, но и, как я уже написал, в количестве данных, закладываемых в ключ. Вот определения ключей из одной из реализаций RSA (чья не нашел - никаких копирайтов в файле нет):

/* RSA public and private key. */
typedef struct {
	unsigned int bits;			/* length in bits of modulus */
	unsigned char modulus[MAX_RSA_MODULUS_LEN];	/* modulus */
	unsigned char exponent[MAX_RSA_MODULUS_LEN];	/* public exponent */
} R_RSA_PUBLIC_KEY;

typedef struct {
	unsigned int bits;			/* length in bits of modulus */
	unsigned char modulus[MAX_RSA_MODULUS_LEN];	/* modulus */
	unsigned char publicExponent[MAX_RSA_MODULUS_LEN];/* public exponent */
	unsigned char exponent[MAX_RSA_MODULUS_LEN];	/* private exponent */
	unsigned char prime[2][MAX_RSA_PRIME_LEN];	/* prime factors */
	unsigned char primeExponent[2][MAX_RSA_PRIME_LEN];/* exponents for CRT */
	unsigned char coefficient[MAX_RSA_PRIME_LEN];	/* CRT coefficient */
} R_RSA_PRIVATE_KEY;

---

В открытом ключе находится информация ТОЛЬКО для зашифровывания/проверки подписи, а в закрытом хранится полная информация о паре ключей.
Это не имеет особого значения. Зная n,d,e (то есть модуль,... 15.07.04 11:29  
Автор: RElf <M> Статус: Member
Отредактировано 15.07.04 11:53  Количество правок: 3
<"чистая" ссылка>
> В открытом ключе находится информация ТОЛЬКО для
> зашифровывания/проверки подписи, а в закрытом хранится
> полная информация о паре ключей.

Это не имеет особого значения. Зная n,d,e (то есть модуль, секретную и открытую экспоненты), все остальные параметры легко вычислить. Напичкивание в секретный ключ всякой "левоты" может иметь смысл разве что для ускорения вычислений, но никак ни для сохранения каких-то дополнительных "секретов".
JFYI: алгоритм вычисления p и q по n,d,e 15.07.04 12:03  
Автор: RElf <M> Статус: Member
<"чистая" ссылка>
> Это не имеет особого значения. Зная n,d,e (то есть модуль,
> секретную и открытую экспоненты), все остальные параметры
> легко вычислить.

См. http://bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=15&m=70334
Какой-то он (алгоритм) "слишком" вероятностный... 15.07.04 13:14  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
<"чистая" ссылка>
А для одной пары p и q секретный ключ единственный или их может быть много?
Любое ли небольшое простое число может быть открытым ключем?
Секретный ключ определяется p,q _и_ открытым ключом. Для... 15.07.04 13:26  
Автор: RElf <M> Статус: Member
Отредактировано 15.07.04 14:07  Количество правок: 1
<"чистая" ссылка>
> А для одной пары p и q секретный ключ единственный или их
> может быть много?

Секретный ключ определяется p,qиоткрытым ключом. Для одной и той же пары простых чисел p,q можно выбрать пару экспонент e,d многими способами.

> Любое ли небольшое простое число может быть открытым ключем?

Где-то начиная с 17 - да. Для ускорения вычислений часто выбирают открытую экспоненту вида 2^k + 1. Наиболее популярные значений 17=2^4 + 1 и 65537=2^16 + 1.
Я это и имел в виду :-) 15.07.04 11:34  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
> Это не имеет особого значения. Зная p,d,e (то есть модуль,
> секретную и открытую экспоненты), все остальные параметры
> легко вычислить.
Только вместо d и е писал о p и q. В общем закрытый ключ в большинстве реализаций содержит обе экспоненты, а открытый - только одну
Что он там имеет или не имеет никак не влияет на сложность... 15.07.04 11:45  
Автор: RElf <M> Статус: Member
<"чистая" ссылка>
> В общем закрытый ключ в большинстве реализаций содержит обе экспоненты, а открытый - только одну

Что он там имеет или не имеет никак не влияет на сложность взлома RSA (вычисление секретной экспоненты по открытой). А именно эту задачу мы сейчас и обсуждаем.
Все "секретность" сосредоточена в секретной экспоненте. Знаем ее - знаем все.
C этим я полностью согласен 15.07.04 12:21  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
Полагаю, что Шнайеру можно доверять. И не только с точки... 14.07.04 17:43  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
<"чистая" ссылка>
> В книге Б. Шнайера "Прикладная криптография" описан
> алгоритм RSA и затем сказано, что в RSA зашифровать
> сообщение можно открытым ключом(расшифровывать - секретным)
> а можно также поступить наоборот, т.е. зашифровать
> секретным ключом, а расшифровать открытым.

Полагаю, что Шнайеру можно доверять. И не только с точки зрения математики, но и стойкости.

> И еще один вопрос. Возможно ли зная секретный ключ и модуль
> n=p*q восстановить открытый ключ или эта задача сводится к
> задаче нахождения секретного ключа по заданному открытому и
> заданному модулю n?

Везде читал, что открытый ключ просто выбирается таким, чтоб удовлетворял условию (был взаимно простым секретному). Ну и как тут его восстановить:) Может просто сгенерить новый, они же будут с точки зрения алгоритма равноправны.
Конечно же, они взаимно обратны, а не взаимно просты. 14.07.04 22:58  
Автор: RElf <M> Статус: Member
<"чистая" ссылка>
> Везде читал, что открытый ключ просто выбирается таким,
> чтоб удовлетворял условию (был взаимно простым секретному).

Конечно же, они взаимно обратны, а не взаимно просты.
На самом деле RSA совершенно симметричен в плане p и q 14.07.04 14:18  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
> И еще один вопрос. Возможно ли зная секретный ключ и модуль
> n=p*q восстановить открытый ключ или эта задача сводится к
> задаче нахождения секретного ключа по заданному открытому и
> заданному модулю n?
То есть математически p и q совершенно равнозначны и просто являются агрументами для взаимнообратного преобразования.
Другое дело, что открытый ключ это пара (n, q), а секретный это (n, p, q). При этом для расшифровки q не требуется. Оно хранится просто для архива

Как то так.
Не согласен в корне.. Секретные ключи d и e выбираются из... 14.07.04 19:31  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
Не согласен в корне.. Секретные ключи d и e выбираются из условия de=1(mod n) - так что они полностью симметричны, как относительно p и q (простых множителей), так и относительно e и d. Задачи восстановления открытого ключа по секретному (если имеется n, конечно) - совершенно такая же как и обратная. В принципе это тоже самое, если бы ты переименвал e и d (e->d, d->e). Атаку на этом, соответственно, построить нельзя.
Зря несогласен 15.07.04 10:50  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
> же как и обратная. В принципе это тоже самое, если бы ты
> переименвал e и d (e->d, d->e). Атаку на этом,
> соответственно, построить нельзя.
Я это и написал. Математически p и q совершенно симметричны. Но потом добавил, что в секретный ключ зачастую добавляется информация не только для расшифровки (n и p), но и информация для восстановления открытого ключа (q).
Вы путаете. Открытый ключ - это (n,d), секретный - это... 15.07.04 11:24  
Автор: RElf <M> Статус: Member
Отредактировано 15.07.04 11:30  Количество правок: 1
<"чистая" ссылка>
> > же как и обратная. В принципе это тоже самое, если бы
> ты
> > переименвал e и d (e->d, d->e). Атаку на этом,
> > соответственно, построить нельзя.
> Я это и написал. Математически p и q совершенно
> симметричны. Но потом добавил, что в секретный ключ
> зачастую добавляется информация не только для расшифровки
> (n и p), но и информация для восстановления открытого ключа
> (q).

Вы путаете. Открытый ключ - это (n,d), секретный - это (n,e). Простые числа p и q - это всего лишь параметры, используемые для генерации ключей. О них можно забыть (и, как правило, так и делают) сразу же после генерации ключей.
При желании, зная секретный и открытый ключи, простые числа p и q можно найти. Алгоритм я здесь когда-то постил.
Признаю ошибку 15.07.04 11:32  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
Последний раз сталкивался с RSA в институте, так что не обессудьте. Главное, что я хотел сказать, ключ может содержать что угодно. И закрытый от открытого отличается не столько экспонентами, сколько количеством данных, которые в него засовывают
1  |  2 >>  »  




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


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