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





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Не совсем так 15.07.04 04:53  Число просмотров: 3329
Автор: Ktirf <Æ Rusakov> Статус: Elderman
<"чистая" ссылка>
Секретный ключ может использоваться для шифрования сообщений, равно как и в качестве цифровой подписи. Это просто два различных варианта его использования, в равной степени применимых.
<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