всем привет, вообщем такая ситуация, есть rsa, скорее всего только decrypt (т.к. на выходе проверяется текст), известны следующий константы: modulus N (binary!)=CDB921C3EF8FA2A45D9A2885368932C970D4A64E1B0DEE3B83594A61C3A2 B0708B3B168C826CF25B99997BD729B1E57C38EC4E2F188930BCDC1441368D4C69DA D=5 также известен cipher вопрос, что можно/нужно сделать, для того чтобы узнать E, чтобы я мог защифровать нужный мне текст, а потом также успешно расшифровать, чтобы прочитался текст на выходе? ps. http://www.di-mgt.com.au/src/BigDigits.zip - для расшифровки используйтся mpModExp из этого пакета спасибо за помощь
Тебе надо разложить это 512 бит число на множители p,q 1143912924377399574948440683306022083470435622122171233755466205594632 6622267181847115506575792190794376060739775027278829490736783684614146 206263884757453 Видимо на это уйдут годы ...
6622267181847115506575792190794376060739775027278829490736783684614146 206263884757453 это и есть множители? я так думаю посчитать это можно с помощью RSA-Tool?
Да нет, это твое N (перевернуто и в десятичном), в RSA-Tool врядли кто считает 512, есть специальные пакеты и чтоб за месяцы, то нужно параллелить на компах?
Avoidik пара (N, D) является закрытым ключом. Т.е. ты можешь читать зашифрованные сообщения. Для вычисления E тебе нужно найти разложение твоего модуля на простые сомножители p и q. Для чисел такого размера обычно пользуются алгоритмом NFS. На одном компе это займет пару лет...
какие существуют решения для факторизации RSA на нескольких компьютерах / в сети + доступность исходников + эффективность + настраиваемость подходят варианты типа distributed.net но оч. желательно автономные (не привязанные к центр. серверу, либо с возможностью установки локального сервера)
Разговоры о RSA мне напоминают наблюдение за стриптизом. Можно вечно рассуждать как бы я ее и в какой позе, а практически всеголишь ходим вокруг да около и пускаем слюни. Современные алгоритмы факторизации это тупиковый путь. При увеличении ключа сложность взлома растет несоизмеримо быстрее, по сравнению со сложностью рабочих расчетов. Одной и той же прогой можно работать как с 1024, так и с 2048 битами, а сломав 1024 бита пусть даже за неделю, 2048 бита за жизнь не осилим. Реально, чтобы взлом не отставал от рабочих расчетов, алгоритм факторизации должен быть порядка O(c*ln(N)).
volodya, ага Jupiter В сети мало доступных реализаций. Самые нормальные на мой взгляд -- это mpqs4linux (ftp://ftp.math.uni-bonn.de/pub/people/franke/mpqs4linux/) и ggnfs. Зависит прежде всего от /dev/head и минимального знания математики. Факторизовать числа -- это далеко не то же самое что брутфорсить какой-нибудь шифр. Тут все намного сложнее. Некоторые этапы алгоритма распараллеливаются очень хорошо (поиск полинома и просеивание), остальные -- практически не распараллеливаются (фильтр, block lanczos, sqrt). _DEN_ O(c*ln(N))? Это типа факторизация быстрее умножения чтоли? Сейчас NFS имеет асимптотическую сложность exp( x*ln(n)^1/3 * ln(ln(n))^2/3 ), так что если 1024 за неделю, то 2048 немного быстрее чем за жизнь )
flankerx Суть в том, что с ростом производительности тачек разрыв между рабочей и факторизующей машиной будет увеличиваться не пропорционально.
flankerx Ну так блин, не сможет ведь это вечно продолжаться. В один прекрасный день этот алгоритм умрет.
правда? я что-то контрпример придумать не смог... напиши, пожалуйтса, где в криптографии сложность взлома растет медленнее скорости обработки.
flankerx Не медленнее, а пропорционально. Тоесть время взлома можно выразить линейно через время работы. t_h = a * t_w + b. Контрпример - да любой (или почти любой) алгоритм, для которого существует аналитическое решение, а не брутфорс. Ведь современый лом РСА это же самый настоящий брутфорс. Ну может не такой тупой, как делить на все подряд до корня квадратного, но все же брутфорс. А про сложность взлома O(c * ln(N)) я уже тут как-то высказывался. Достаточно научиться за фиксированное время определять знак неравенсива между a и p для любого a из 2 <= a < n. (n = p * q). Пока на сколько я знаю математика ни опровергает ни доказывает существования такого критерия.
_DEN_ ну пропорциональнее так пропорциональнее, а пример-то где? любой алгоритм, для взлома которого найдено аналитическое решения считается нестойким. NFS -- не брутфорс Я могу согласиться что Поллар-ро и ECM с некоторой натяжкой можно назвать брутфорсом, но QS/NFS -- ИМХО далеко не брутфорсовые алгоритмы. Собственно у них и время выполнения зависит не от ращмера наименьшего из множителей, а от размера произведения.
