Запасные секретные ключи RSA

Тема в разделе "WASM.CRYPTO", создана пользователем 7aleut, 7 июн 2008.

  1. 7aleut

    7aleut New Member

    Публикаций:
    0
    Регистрация:
    7 июн 2008
    Сообщения:
    2
    Объясните мне "неграмотному". Для созданных секретных ключей RSA существуют дубликаты в количестве одного и более штук. Это так и должно быть ???
    Так для примера приведенного в Википедии (http://ru.wikipedia.org/wiki/RSA) , для секретного ключа 6111579 , существует "запасной" ключ 1527895 .
    Это все в порядке вещей ?
     
  2. halyavin

    halyavin New Member

    Публикаций:
    0
    Регистрация:
    13 май 2005
    Сообщения:
    252
    Адрес:
    Russia
    Нет никаких дупликатов (можно, конечно, (p-1)(q-1) добавлять, но в этом нет никакого смысла). Откуда ты число 1527895 выкопал?
     
  3. CreatorCray

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    Если на пальцах, то 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 вычислить второй ключ нельзя.
     
  4. CreatorCray

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    Кроме того, ключ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
     
  5. CreatorCray

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    Во! Нашел где я это читал:

    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.
     
  6. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.243
    CreatorCray
    фи, в идеале, должно иметь максимум 2 делителя.
     
  7. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.243
    точней 4:))
     
  8. CreatorCray

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    UbIvItS
    Обосновать можешь? Со ссылками.
     
  9. Dmit

    Dmit New Member

    Публикаций:
    0
    Регистрация:
    24 окт 2004
    Сообщения:
    17
    Адрес:
    Russia
    А что тут обосновывать? Если p и q - "сильные" простые числа, то p = 2 * p1 + 1, q = 2 * q1 + 1, где p1 и q1 - тоже простые.
    Тогда φ(n) = 2 * 2 * p1 * q1
     
  10. CreatorCray

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    А толку то с того?
    Ты мне пожалуйста с матобоснованием, что это реально дает. Желательно со ссылкой на авторитетные источники.

    Пока могу только привести следующие цитаты:

    Meneses
    Schneier
     
  11. 7aleut

    7aleut New Member

    Публикаций:
    0
    Регистрация:
    7 июн 2008
    Сообщения:
    2
    >Да, оба этих ключа работают одинаково.
    >Нет, не зная P и Q вычислить второй ключ нельзя.
    Отлично ! Ну и подскажите мне пожалуйста , а что обязательно каждый раз вычислять P и Q ? Например секретный ключ d = 1527895 был найден таким способом. Взяли маленькое M , например 2 , возвели его в степень E , т. е. в 3 , а затем разделили на N.
    В итоге получили 8 , затем 8 поочередно возводили в степень "2,2,4....N" При этом каждый раз делили на N и проверяли остаток. Та степень где остаток был равен 2 как раз и являлась секретным ключом. Да большая выборка , но конечная , тем более что Вы же сами упомянули что первые значения секретных ключей могут быть небольшими.
     
  12. CreatorCray

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    7aleut
    Что такое N в твоем примере? Модуль? А откуда ты его берешь в таком случае?

    P,Q не вычисляются - их выбирают. Вообще с выбора пары простых P,Q начинается генерация ключа и от них зависит стойкость.

    Где это я упомянул что значение секретного ключа может быть небольшим? :)
    Он может быть чуть меньше PQ, но все равно должен быть большим. Не меньше чем примерно 2/3 от PQ. Например 1020бит D при 1024бит PQ это разве небольшое значение?

    Наверное тебе стоит еще раз внимательно прочитать теорию по RSA - что то ты там пропустил похоже. Рекомендую Шнайера - он есть в сети и на русском.

    -------------

    то, что ты предлагаешь - перебирать тупо все значения степеней - авось какая подойдет - проканает только на небольшом примере. Сгенерируй ключ нормального размера - хотя бы 1024 бита и попробуй подобрать. :))
     
  13. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    А каковы шансы того, что на практике LCM (наименьшее общее кратное?) будет заметно короче чем (p-1)(q-1) ? Слишком короткий LCM способно указать на слабый ключ? Или при больших случайных числах нарваться на шипко укороченный LCM просто не реально?
     
  14. CreatorCray

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    persicum
    При реально случайных P Q нарваться на реально короткий LCM действительно мала.
    На крайний случай можно проверять размер получившегося D. По грубой оценке D должно быть не менее 1/4 от длины PQ, иначе становится возможна атака Wiener-а, которая такой ключ расковыривает чуть ли не за секунды.
    Я обычно проверяю чтобы D было не менее 2/3 PQ.
     
  15. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Не понимаю до конца, где идет речь о числе бит в числе, а где о самом этом огромном числе...

    1/4 - от числа бит?
    Если 2/3 это от самого числа, то это же совсем крохи, менее чем на 2 бита короче. ЗАчем заморачиваться?

    На сколько в среднем бит на практике может быть короче LCM?
    Если всего лишь на несколько штук, то это вообще фигня, такая оптимизация.
     
  16. CreatorCray

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    всё про длины. Я тогда спешил, пардон.

    на практике - самое большое что мне удалось получить для 1024bit PQ - 6 бит разницы

    ---8<---
    Впрочем вру, только что получилось 9 бит
     
  17. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Я тоже сейчас устроил проверочку. Сгенерил три ключа 1024 бит, или три пары простых p и q по 512 бит. Разницы в длинах LCM и (p-1)(q-1) были соответственно 8, 1 и 3 бита. Совсем крохи. И чем первый ключ слабее двух других?
     
  18. CreatorCray

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    ничем :)