Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | | | |
Секретный ключ определяется p,q _и_ открытым ключом. Для... 15.07.04 13:26 Число просмотров: 3550
Автор: 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.
|
<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 в институте, так что не обессудьте. Главное, что я хотел сказать, ключ может содержать что угодно. И закрытый от открытого отличается не столько экспонентами, сколько количеством данных, которые в него засовывают
|
|
|