Объясните мне "неграмотному". Для созданных секретных ключей RSA существуют дубликаты в количестве одного и более штук. Это так и должно быть ??? Так для примера приведенного в Википедии (http://ru.wikipedia.org/wiki/RSA) , для секретного ключа 6111579 , существует "запасной" ключ 1527895 . Это все в порядке вещей ?
Нет никаких дупликатов (можно, конечно, (p-1)(q-1) добавлять, но в этом нет никакого смысла). Откуда ты число 1527895 выкопал?
Если на пальцах, то d вычисляется как e^-1 mod phi следовательно оно зависит от phi есть два метода вычиления phi при генерации ключей 1) phi = (p -1) * (q - 1) 2) phi = LCM ((p -1) * (q - 1)) вторая рекомендуется некоторыми авторами потому как он более чего то там (щас не вспомню) В твоем случае d = 6111579 = 3^(-1) mod ((p -1) * (q - 1)) d = 1527895 = 3^(-1) mod (LCM(p -1) * (q - 1)) Да, оба этих ключа работают одинаково. Нет, не зная P и Q вычислить второй ключ нельзя.
Кроме того, ключeй может быть куда больше: phi = lcm((p-1)*(q-1)); d = (e^(-1) mod phi) + C * phi все эти d будут ключами Например: P : f9849aa93df1894c93a85d747310c7c7 Q : bbcfc7722e46fbc66801787e96182cdd E : 829f phi: 1e826599579453ed662cb53cdd6fbc93bde8ee8abc1f30b96c7603a7c08d9e5c D : 16755cb2091c2c729e1dc96714430df70e556c1429aa4b550235f7c9f8c0dedb D : 34f7c24b60b08060044a7ea3f1b2ca8acc3e5a9ee5c97c0e6eabfb71b94e7d37 D : 537a27e4b844d44d6a7733e0cf22871e8a274929a1e8acc7db21ff1979dc1b93 D : 71fc8d7e0fd9283ad0a3e91dac9243b2481037b45e07dd81479802c13a69b9ef D : 907ef317676d7c2836d09e5a8a02004605f9263f1a270e3ab40e0668faf7584b D : af0158b0bf01d0159cfd53976771bcd9c3e214c9d6463ef420840a10bb84f6a7 -------8<------ added -------8<------ или вот даже для 32бит, чтоб проверять было проще P : 52'291 Q : 53'299 E : 11 phi: 22'118'670 D : 10'053'941 D : 32'172'611 D : 54'291'281 D : 76'409'951 D : 98'528'621 D : 120'647'291 D : 142'765'961 D : 164'884'631 D : 187'003'301 D : 209'121'971 D : 231'240'641 D : 253'359'311 Но есть такие P,Q,E для которых для phi, вычисленных разными методами получается одинаковый D
Во! Нашел где я это читал: Alfred J. Menezes. HANDBOOK of APPLIED CRYPTOGRAPHY 8.5 Note (universal exponent) The number λ = lcm(p−1, q −1), sometimes called the universal exponent of n, may be used instead of φ = (p − 1)(q − 1) in RSA key generation (Algorithm 8.1). Observe that λ is a proper divisor of φ. Using λ can result in a smaller decryption exponent d, which may result in faster decryption (cf. Note 8.9). However, if p and q are chosen at random, then gcd(p−1, q−1) is expected to be small, and consequently φ and λ will be roughly of the same size.
А что тут обосновывать? Если p и q - "сильные" простые числа, то p = 2 * p1 + 1, q = 2 * q1 + 1, где p1 и q1 - тоже простые. Тогда φ(n) = 2 * 2 * p1 * q1
А толку то с того? Ты мне пожалуйста с матобоснованием, что это реально дает. Желательно со ссылкой на авторитетные источники. Пока могу только привести следующие цитаты: Meneses Schneier
>Да, оба этих ключа работают одинаково. >Нет, не зная P и Q вычислить второй ключ нельзя. Отлично ! Ну и подскажите мне пожалуйста , а что обязательно каждый раз вычислять P и Q ? Например секретный ключ d = 1527895 был найден таким способом. Взяли маленькое M , например 2 , возвели его в степень E , т. е. в 3 , а затем разделили на N. В итоге получили 8 , затем 8 поочередно возводили в степень "2,2,4....N" При этом каждый раз делили на N и проверяли остаток. Та степень где остаток был равен 2 как раз и являлась секретным ключом. Да большая выборка , но конечная , тем более что Вы же сами упомянули что первые значения секретных ключей могут быть небольшими.
7aleut Что такое N в твоем примере? Модуль? А откуда ты его берешь в таком случае? P,Q не вычисляются - их выбирают. Вообще с выбора пары простых P,Q начинается генерация ключа и от них зависит стойкость. Где это я упомянул что значение секретного ключа может быть небольшим? Он может быть чуть меньше PQ, но все равно должен быть большим. Не меньше чем примерно 2/3 от PQ. Например 1020бит D при 1024бит PQ это разве небольшое значение? Наверное тебе стоит еще раз внимательно прочитать теорию по RSA - что то ты там пропустил похоже. Рекомендую Шнайера - он есть в сети и на русском. ------------- то, что ты предлагаешь - перебирать тупо все значения степеней - авось какая подойдет - проканает только на небольшом примере. Сгенерируй ключ нормального размера - хотя бы 1024 бита и попробуй подобрать. )
А каковы шансы того, что на практике LCM (наименьшее общее кратное?) будет заметно короче чем (p-1)(q-1) ? Слишком короткий LCM способно указать на слабый ключ? Или при больших случайных числах нарваться на шипко укороченный LCM просто не реально?
persicum При реально случайных P Q нарваться на реально короткий LCM действительно мала. На крайний случай можно проверять размер получившегося D. По грубой оценке D должно быть не менее 1/4 от длины PQ, иначе становится возможна атака Wiener-а, которая такой ключ расковыривает чуть ли не за секунды. Я обычно проверяю чтобы D было не менее 2/3 PQ.
Не понимаю до конца, где идет речь о числе бит в числе, а где о самом этом огромном числе... 1/4 - от числа бит? Если 2/3 это от самого числа, то это же совсем крохи, менее чем на 2 бита короче. ЗАчем заморачиваться? На сколько в среднем бит на практике может быть короче LCM? Если всего лишь на несколько штук, то это вообще фигня, такая оптимизация.
всё про длины. Я тогда спешил, пардон. на практике - самое большое что мне удалось получить для 1024bit PQ - 6 бит разницы ---8<--- Впрочем вру, только что получилось 9 бит
Я тоже сейчас устроил проверочку. Сгенерил три ключа 1024 бит, или три пары простых p и q по 512 бит. Разницы в длинах LCM и (p-1)(q-1) были соответственно 8, 1 и 3 бита. Совсем крохи. И чем первый ключ слабее двух других?
