Отправлено SМ 11 февраля 2004 г. 01:04

Ау! Алекс Юстасу! Надо вот ключик для RSA сгенерить. Для этого надо нарыть число случайное, но при этом простое, длиной бит эдак 200, а то и 300. Причем ажно 2 штуки. Несложные тесты на проверку простоты числа могут дать ответ, что число либо составное, либо "а хрен его знает". Другие тесты, отвечающие на данный вопрос "чиста канкретна" требуют разложения на множители числа, на 1 меньшего проверяемого, для того, что-бы оценить, является ли оно порядком группы обратимых по модулю проверяемого числа чисел. Принцип проверки понятен от и до, но совершенно не ясно, как раскладывать на множители... Ведь на сложности разложения всё в RSA и держится. Или выбирать только из известных простых, порядки U(p) которых легко разложимы? Или что еще придумали на эту тему?

• Кстати тебе нужны готовые ключи или нужно самому генерить их? если самому генерить то под какой железкой? — anvolk   (12.02.2004 11:24, пустое)
  • Самому. Железка роли не играет. Интересует алгоритм, а не реализация. — SМ   (12.02.2004 16:29, пустое)
• Как отличить составное число от простого — anvolk   (11.02.2004 14:51, 4 байт, ссылка)
  • Это все вероятностные алгоритмы. Тест Миллера не дает 100% ответа. — SM   (11.02.2004 15:00, пустое)
    • 100% алгоритм найдёшь отличный от простого перебора - Нобилевская Премия (хотя по математике её не дают). Вероятностный единственный путь. Вероятность то ошибки мала. В спортлото легче выиграть. — anvolk   (11.02.2004 16:16, пустое)
      • Кстати, недавно в новостях было... — Oleg_0515   (11.02.2004 16:44, пустое, ссылка)
        • А что, и нам также нужно. SM пусть выложит число, а весь форум раскладывает его на множители. — shenon   (12.02.2004 10:17, пустое)
          • :) шутки - шутками, но anvolk прав: чем дольше алгоритм будет париться с проверкой постоты, тем больше уверенности, что хакеру потребуется указанный выше метод распределенных вычислений... — Oleg_0515   (12.02.2004 17:23, пустое)
      • Хе. А если я ключ сгенерю, и попаду в это спортлото? Потом могут и органы пообрывать ценные :) — SM   (11.02.2004 16:38, пустое)
        • 100% быстрый алгоритм - крах криптографии основанной на простых числах. Надо смириться - мы живём в мире где правит её величиство СЛУЧАЙНОСТЬ:) суть проверок заключается в том чем меньше вы хотите ошибиться тем больше надо сделать проверок — anvolk   (11.02.2004 17:40, пустое)
          • Ну это я знаю. И тест Миллера знаю. Больше интересовали тесты Люка-Лемера и подобное что-нить... — SM   (11.02.2004 18:48, пустое)
        • Судьба такой, значит-) — ВН   (11.02.2004 17:20, пустое)
          • У меня в планах нету такой судьбы :) — SM   (11.02.2004 17:28, пустое)
• Проблема имеет место быть... — Oleg_0515   (11.02.2004 14:10, 786 байт)
  • Ну (+) — SM   (11.02.2004 14:28, 121 байт)
    • Ответ: А насколько быстр Ваш алгоритм, если не секрет. — PY   (12.02.2004 11:41, 253 байт)
      • У нас результаты скромнее :) ... — Oleg_0515   (12.02.2004 18:01, 656 байт)
        • Ага. 2185 скорее всего выиграет. — ВН   (12.02.2004 19:09, 708 байт)
          • Так у меня и делается, только ничего запоминать не нужно ибо разложение делается не со стороны младшего бита, а со стороны старшего... — Oleg_0515   (13.02.2004 17:49, 992 байт)
            • Ответ: — ВН   (13.02.2004 18:42, 1116 байт)
              • Спасибо, понял... — Oleg_0515   (13.02.2004 19:39, 143 байт)
      • Да - это явно не быстро - :) ... — делавший    (12.02.2004 13:14, 416 байт)
        • Прошу прощения, у Вас возведение в степень 0.18 сек? или все-таки умножение? — Oleg_0515   (12.02.2004 18:05, пустое)
          • Именно возведение в соотвествии с СТБ 1176.2-99 ... — делавший    (13.02.2004 02:44, 128 байт)
        • Ответ: — PY   (12.02.2004 14:00, 142 байт)
          • Ответ: ... — делавший    (12.02.2004 14:25, 491 байт)
            • Для особо сообразительных поясняю - АЛГОРИТМОВ деления ВН не раздавал. До него раздали. В школе. — ВН   (12.02.2004 14:47, пустое)
              • ну хорошо - раздавал реализации - но все равно это был ВН :) — делавший    (13.02.2004 02:29, пустое)
            • До кучи ... — делавший    (12.02.2004 14:37, 623 байт)
• () — Fat Robot   (11.02.2004 10:41, 6 байт, ссылка)
• Чем RSA хуже Д-Х .... — предполагающий   (11.02.2004 02:47, 1093 байт)
  • За алгоритмы спасибо (СТБ), а про остальное и так знаем :) — SМ   (11.02.2004 08:25, пустое)
    • Кстати, а где эти стандарты дают? — SM   (11.02.2004 14:22, пустое)
      • Ответ: — Oleg_0515   (11.02.2004 17:04, 41 байт)
        • Спасибо! Выкачал. — SM   (11.02.2004 17:27, пустое)
• А CiteSeer не поможет? Хотя Вы, наверное, смотрели. — svf   (11.02.2004 01:41, пустое, ссылка, картинка)
  • Угу. Надыбыванье той литературы у меня начинается, когда ничто другое уже не помогает :) — SМ   (11.02.2004 08:26, пустое)
• А — svf   (11.02.2004 01:39, пустое, ссылка, картинка)