Секретный ключ может использоваться для шифрования сообщений, равно как и в качестве цифровой подписи. Это просто два различных варианта его использования, в равной степени применимых.
В книге Б. Шнайера "Прикладная криптография" описан алгоритм 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,e15.07.04 12:03 Автор: RElf <M> Статус: Member
А для одной пары 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
> В книге Б. Шнайера "Прикладная криптография" описан > алгоритм RSA и затем сказано, что в RSA зашифровать > сообщение можно открытым ключом(расшифровывать - секретным) > а можно также поступить наоборот, т.е. зашифровать > секретным ключом, а расшифровать открытым.
Полагаю, что Шнайеру можно доверять. И не только с точки зрения математики, но и стойкости.
> И еще один вопрос. Возможно ли зная секретный ключ и модуль > n=p*q восстановить открытый ключ или эта задача сводится к > задаче нахождения секретного ключа по заданному открытому и > заданному модулю n?
Везде читал, что открытый ключ просто выбирается таким, чтоб удовлетворял условию (был взаимно простым секретному). Ну и как тут его восстановить:) Может просто сгенерить новый, они же будут с точки зрения алгоритма равноправны.
Конечно же, они взаимно обратны, а не взаимно просты.14.07.04 22:58 Автор: RElf <M> Статус: Member
> И еще один вопрос. Возможно ли зная секретный ключ и модуль > 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 в институте, так что не обессудьте. Главное, что я хотел сказать, ключ может содержать что угодно. И закрытый от открытого отличается не столько экспонентами, сколько количеством данных, которые в него засовывают