Обсуждение Алгоритмов Дешифрации Ключа, Нужны свежие идеи - нельзя долго копать Поделиться Опции

[Envelope]

Уверен, что не один я устал от метода "слепого перебора" зашифрованных пакетов.
Нет, идея, с перебором, конечно, классная, вот только реализация: типа клюквой пробить бетонный забор, короче, если все на форуме подключатся, то этот процесс (при условии обработки одного пакета в день одним пользователем) займет (грубо) 6*10^280 лет как вам такое положение вещей в пространстве?

Обладая, нашими сегодняшними технологиями, на дешифрацию 1024 битного ключа мы потратим энергию, равносильною появлению Сверхновой. Как думаете, есть у нас такие запасы на планете? <_<

Либы для клиента перебора написаны итак в большей степени на асме.
Но одного асма недостаточно. Нужен толковый алгоритм - это основное. Тогда, впринципе, хыть на Vb клиента напиши, все равно перебор быстрее идти будет.
Эта тема создана для поиска более эффективного алгоритма дешифрации, основанного на знаниях в области Высшей математики.

Я ПРОСТО НАСТАИВАЮ, ЧТОБЫ ВСЕ, КТО СЕЙЧАС ЗАНИМАЕТ СВОЮ ГОЛОВУ ТЕМ, КОГДА ЖЕ ЕГО МОНСТР-КОМП ОБРАБОТАЕТ ОЧЕРЕДНОЙ ПАКЕТ, ЗАНЯЛИ СЕБЯ ПОИСКОМ ИНФЫ В ИНЕТЕ И УЗУЧЕНИЕМ ВОПРОСА!!!

Народ, подключайте, всех, кого знаете, особенно, если у кого-то есть в знакомых преподы по Вышке. Объясните им, что вдруг заинтересовались криптографией - мол, прогу секьюрную пишете. Они только скакать от счастья будут - это именно то, о чем они мечтали всю свою преподавательскую деятельность - чтобы их трудами, наконец, кто-то заинтересовался, чтоб кому-то эта хрень стала интересна.

Короче, что я еще могу сказать... Дерзайте, тогда раскроем РСА!!! starwars_draka;

Зыы... Исходники клиента приложены в конце сообщения

[Envelope]

Итак (в особой степени обращаю этот пост dimichxp), вот и оптимизация алгоритма. clap;applo

Так что вперед и за работу, господа программеры starwars_draka;

[dion]

Envelope, я об этом методе думал, но не подходит он для больших чисел.. Т.к чтобы проверять число скажем 2^50 - 1 на простоту, нам нужны все простые числа от 2 до 2^50-1. Соответственно оперативки нужно до черта. + распаралелить на кучу компов не возможно.

[Envelope]

Что значит невозможно? Ты имеешь в виду сложно? Ну а кто сказал, что это задача для маленького ребенка?

[dimichxp]

Что значит невозможно? Ты имеешь в виду сложно? Ну а кто сказал, что это задача для маленького ребенка?

Згначит что времени нужно несравнимо больше чем сейчас.

[dion]

Что значит невозможно? Ты имеешь в виду сложно? Ну а кто сказал, что это задача для маленького ребенка?

Невозможно означает невозможно. Для этого алгоритма каждому клиенту нужен весь диапазон простых чисел.
Т.е если у нас диапазон от 1..20 и 2 клиента. 1 получит 1..10 а второй 11..20
Если 1 будет искать числа 1..10 то второму придется от 1..20. Т.е второй дублирует работу первого.
А пересылать все простые числа нереально (траффик).

[Envelope]

Невозможно означает невозможно. Для этого алгоритма каждому клиенту нужен весь диапазон простых чисел.
Т.е если у нас диапазон от 1..20 и 2 клиента. 1 получит 1..10 а второй 11..20
Если 1 будет искать числа 1..10 то второму придется от 1..20. Т.е второй дублирует работу первого.
А пересылать все простые числа нереально (траффик).

Dion, ну ты и приколист . А что, так сложно переслать диапазон, а не таблицу и заставить клиента сгенерить на месте? drink_drunks;

Вот тебе и процессы распараллелены уже. И статистика не нужна, она есть. Какой суммарный диапазон сделан, столько и процентов.

Но дело не в статистике, дело в алгоритмах.

НАРОД, ВЫ НАМ БОЛЬШЕ НУЖНЫ НЕ В КАЧЕСТВЕ МЯСА, ПЕРЕБИРАЮЩЕГО НА СВОИХ КОМПАХ НЕДОСТАТОЧНО СОВЕРШЕННЫЕ АЛГОРИТМЫ. НАМ НУЖНЫ ВАШИ СВЕТЛЫЕ ГОЛОВЫ. ЛОМАЙТЕ ИХ НАД БОЛЕЕ СОВЕРШЕННЫМИ АЛГОРИТМАМИ, А НЕ ВАШИ ТАЧКИ НАД ЭТОЙ КУЧЕЙ ЦИФР

Что так и будем сидеть, перебирать пакеты и молча ждать результатов? А ну быстро все на подмогу dimichxp, хватит только на нем одном выезжать!!!!!

[AndrewSOAD]

Неужели ни у кого нет среди знакомых профессора математики, или профессионального криптолога?
А специализированные сайты или форумы есть у криптологов?

Не всегда стоит ломиться в парадный вход, обязательно есть черная дверь которая открыта (с)перто

Мне кажется что все на свете можно обмануть =)

Давайте подумаем об обходных путях!

[wert]

Envelope,
AndrewSOAD, Вы такие оптимисты, неужели вы думате что RSA придумали такие дураки которые могли оставили ход который позволит достаточно значительно сократить время подбора ключа (тем более такой длины), я думаю что даже если получется оптимизировать алгоритм то на взлом все равно уйдет много времени и мощности компьютеров(вот еслибы подключить к такому процессу настоящий суперкомпьютер вот это было бы круто).

[Exebyte]

Envelope,
AndrewSOAD, Вы такие оптимисты, неужели вы думате что RSA придумали такие дураки которые могли оставили ход который позволит достаточно значительно сократить время подбора ключа (тем более такой длины), я думаю что даже если получется оптимизировать алгоритм то на взлом все равно уйдет много времени и мощности компьютеров(вот еслибы подключить к такому процессу настоящий суперкомпьютер вот это было бы круто).

Ну... Возможно RSA не так уж надежна!...

Почитайте это:
PGP в России - Литература

[AndrewSOAD]

Интересная вещь по теме, кто знает английский дерзайте
http://psifertex.com/download/twirl.pdf

Что то о компьютере, способном подбирать RSA ... насколько я понял =)

[x3m]

Я не сильно дуплю в С++, да и вообще...
Но есть небольшое предлложение по оптимизации существующего алгоритма:
- все понимают, что нет смысла проверять четные.
- также нет смысла проверять и другие кратные 3,5:
-- покажу на примере 30(2*3*5), реализовать лучше для 210 или 2310:
--- находим первое число, кратное 30 (допустим, 60)
--- от 60 до 90 есть смысл проверять, являются ли простыми: 61,67,71,73,77,79,83,89 - 8 чисел вместо 15 (30), для 210 и 2310(2*3*5*7*11) результаты еще лучше
--- итак, алгоритм:
---- находим кратное, добавляем 1
---- запускаем цикл (проверяем, простое ли, прибавляем 6, проверяем, прибавляем 4, проверяем, прибавляем 2, проверяем, прибавляем 4, проверяем, прибавляем 2, проверяем, прибавляем 4, проверяем, прибавляем 6, проверяем, прибавляем 2)
Вот вам и ускорение :) хоть и немного, хоть и тупое, но все же...

[wert]

Exebyte, Интересная статейка тока все равно надо быть нехилым математиком чтобы разработать хитрый способ разложения ключа.

[KQ_44]

Вставлю и свои 5 копеек.
Судить о том насколько надежен RSA мы не можем.
НО если у вас в одежде дыра - вы не будете орать об этом
на каждом углу. И попытаетесь оттянуть время ее обнаружения
как можно дальше. И даже если кто-либо из математиков
нашел решение, то (ЕСЛИ ОН УМНЫЙ) не будет орать об этом
на каждом углу. Он свяжется с RSA или спец-службами
и будет получать дивиденты!!! А устроить обвал во многих
сферах деятельности, где юзается RSA - как-то по детски.
Плюс - могут и посадить...
Многие задачи можно решать интуитивно - как пример таже теорема Ферма.
И еще раз повторюсь: многие алгоритмы - это общие решения, у нас же конкретное.

И не надо дергать Dionа и Dimichа-xp. Они сделали то, что не сделал никто из нас.
ОНИ ЗАПУСТИЛИ ПРОЦЕСС!!!

ПРЕДЛОЖЕНИЕ: Пока идет счет, можно попытатся оптимизировать алгоритм.
И реализовать!!! Если новое творение окажется более ...(что-либо) - то очевидное
стимулирует народ к переходу на это творение. НО к этому времени часть
диапазона будет ОБРАБОТАНА.

И теперь в 3-й раз повторюсь. Наше число Р=а*с, где P,c,а=>xn*10^n+...+x0*10^0.
Если расписать, то P0=a0*c0 и P1=(c0*a1+a0*c1)*10 и т.п. Зная Р0 по таблице умножения можно найти значения a0 и c0, произведение которых дает Р0.
По аналогии для а1 и с1. Для какого-то n - возможные значения аn и сn будут
от 1 до 9. Далее раскладывать не имеет смысла, но можно исключать все сгенерированные простые числа, для которых первые n-чисел не совпадают с
найдеными диапазонами для а0..аn-1 и с0..сn-1.
Для проверки такого типа полезно реализовать персональную процедуру для
работы с большими числами, иначе выиграш в скорости будет не очень большой.
Причем, если некое аn=1..4 и 6..9, то и ежику понятно, что проще делять проверку
на 5, а не на весь остальной диапазон.

[Sl_1]

Порылся я по сети и нашёл кое-что посмотрите и скажите что это
"Прога лидера группы TMG, предназначена полученя Приватной Екпоненты (D), из Module (N) и Pablic Exponent (E), эта версия поддерживает ключ размером 4096, если ключ больше 256 то это займет много времени и оперативной памяти." RSA-Tool 2
Затем калькулятор для работы с большими числами и поддержкой RSA-Tool
И наконец Factorizer - программа, чтобы найти факториалы чисел до 2 147 483 646 и находить неделимые простые числа, их пары. Или более подробно, Factorizer может использоваться: (1), чтобы получить главное разложение числа на простейшие, (2), чтобы получить все факториалы единственного числа или все факториалы всех чисел в диапазоне, (3), чтобы найти только главные числа в диапазоне чисел, (4), чтобы найти пары главных чисел (например 107 и 109) в некотором диапазон, (5), чтобы считать (не показывая) главные числа в диапазоне чисел. (6), чтобы найти Fermat и Mersenne primes <2 147 483 647 (7), чтобы найти Palmen цвет числа или цветов диапазона чисел и для других целей, которые вам могут понадобится при изучении ассиметричной криптографии RSA или DSA.
Если есть какие-то мысли напишите.

rsatool2v17.rar   ( 57.46 килобайт ) Кол-во скачиваний: 601

bigintcalcpro_v12.rar   ( 63.84 килобайт ) Кол-во скачиваний: 527

factorizer831.rar   ( 1.66 мегабайт ) Кол-во скачиваний: 1144

[BlackHack]

Люди! www.intuit.ru - мне кажется здесь мона найти инфу по алгоритмам шифрования.

P.S. А может в журнал ][akep написать? Лидей грамотных много.

[wRAR]

P.S. А может в журнал ][akep написать? Лидей грамотных много.

Нету в ксакепе грамотных людей.

[Tails]

Взлом такого ключа в принципе невозможен. Проводили эксперимент: по всему миру сотни тысяч компов брутфорсили 56-битный ключ. Правильная комбинация была подобрана черех 5 лет. Сейчас начался взлом 78-битного. По предварительным оценкам- 75 лет. Есть другое решение: почему бы не написать прошивку не ASMе с нуля? Или похакать Моторолу :) !

[DEADDY]

http://alglib.sources.ru/numbers/erat.php

[wRAR]

почему бы не написать прошивку не ASMе с нуля?

Потому что ее нельзя будет залить.

[dmat]

Tails,
да, и к тому же про 56-битный ключ ты немного не вкурсе.... уже поломаны и более длинные ключи, вплоть до 512 (если мне не изменяет память).
ЗЫ. брутфорсить - не всегда оптимальный вариант

[wRAR]

Ключи на 56 и ключи на 512 - абсолютно разные вещи. 56 - коротюсенький симметричный ключ. 512 - асимметричный, как и у нас.

[Tails]

Хорошо, вот ещё идейка.
В микроконтроллерах есть такая фигня, как бит-защита.если её врубить, прошивка нормально выполняется, но считать её корректнымы методами невозможно. Так вот, если кому-то очень надо иметь прошивку, есть спец. конторы, которые этим занимаются.иИх метод состоит в том, что они срезают микроконтроллер...эээ...напильником :) слой за слоем и фотографируют каждый в электронный микроскоп. Потом из фоток получают прошивку. Так вот: если RSA где-то хранится, нельзя ли что-то подобное сделать и здесь?
ЗЫ: вроде это стоит огромных денег...

[wRAR]

если RSA где-то хранится

Учите матчасть || читайте прошлые темы.
Закрытый ключ в телефоне не хранится.

[algal]

Эгей, господа! Пишу уже второй раз (правда в другой топик, предыдущий потерял :( )!
Совершенно непонятно обстоит дело с ключом! Т.е. что это - в сети написано. Зачем - тоже объяснили. В то же время неоднократно появлялись оценки сколько нужно времени на его подбор. Это НЕРЕАЛЬНО :( .
Поэтому возникает мысля (у меня - далеко не первого!!!!) - чем просто подбирать, может ПОДУМАТЬ!!!
Однако что делать если мозгов немного есть, а инфы в обрез! Меня уже посылали на этом форуме на фак и т.д., прочел множество веток, однако во первых ни одного конструктивного направления не видел, во вторых не нашел достойного описания положения на сегодняшний день. Т.е. может надо ковырнуть железо, может надо посмотреть в микроскоп, может еще чего - никто не делится знаниями об основах, соответственно придумать тут нечего. А разгадывать ключи непосредственно, имхо, занятие бестолковое - это мы тут экс - советские граждане толпой гадаем, а буржуи на таких вещах деньги огромные делают - уж если у них не вышло - это только китайцам под силу - их много :)
ВЫВОД: давайте подведем итог - что известно про эту маленькую железочку под кодовым названием тело?
Может есть другие подходы? Может надо купить человека из СЦ? ДАВАЙТЕ НАЧНЕМ С НАЧАЛА И НЕ БУДЕМ ОТБРАСЫВАТЬ НИКАКИХ ВАРИАНТОВ!!!

P.S. Уж если затраты энергии на расшифровку сравнивают с рождением сверхновой, то по "гнусной теории Эйнштейна" - это хренова туча материи (не указано какой, по умолчанию пусть будет золото, или цветмет на худой конец ) - так ведь этого хватит на покупку всей компании Motorola с ее гребаным ключом!!!!
P.P.S. off_topic; И еще мысля : если мотофанов 40000 - по скольку надо скинуться чтобы купить Мотор? :P

[Envelope]

algal, ну ты прям выпендрился! :P

1) Это тема как раз и создана для поиска алгоритмов, а не для обсужедения, кто скока за седня ключей прокапал
2) Про проц итак уже узнано все, что можно было узнать, а именно известно число RSA и открытый ключ, никаких микроскопов не надо
3) Компанию моторола никто покупать не собирается, для этого форум-то в общем то и незачем, здесь все построено тока на интеллекте и знаниях участников
4) Как показывает практика, у экс-советских людей-то как раз ломать получается лучше остальных bigsmile;

[AndrewSOAD]

У меня полностью разобранная, в корень убитая моторолкак с380=)

Если кому надо это убитое существо, для тестов, или порыться там в поисках РСА - пожалуйста!

[ReBoons]

AndrewSOAD
а у меня 650 валяется, правда не совсем убитая

[Envelope]

Итак, Господа, вот вам, как говорится, пища для ума.
Нам нафик не нужен RSA, нам нужно найти d-закрытый показатель. Вот полюбуйтесь на прикрепленную картинку. Инфа подготовлена мной на базе этой статьи. Проверьте. Если это и правда так, то мы сможем подделать подпись, разве не это нам надо? ;)

-Приношу свои извинения, ошибки в формуле. Пока в разработке- :)

[DjSens]

взято с http://www.mmonline.ru/news.php?mid=2084&topic=131

До последнего времени наиболее совершенным устройством для быстрого разложения чисел на множители была оптоэлектронная система TWINKLE. Она состояла из подложки, разбитой на множество вычислительных ячеек, каждая из которых работала с собственной числовой последовательностью. TWINKLE последовательно перебирает различные области числового сита в соответствии с сигналами от тактового генератора. Поскольку в TWINKLE применяются оптические компоненты, полупроводниковой основой устройства служит дорогой арсенид галлия.

Устройство TWIRL, разработанное Шамиром и Тромером, использует близкий к TWINKLE подход к реализации алгоритма разложения чисел на множители. Однако новое устройство может параллельно рассматривать тысячи участков числового сита, а схема устройства не содержит оптических элементов. По сути, TWIRL представляет собой специализированную сверхбольшую интегральную схему (СБИС), работающую на частоте 1 ГГц, выполненную по 0,13-микронной технологии.

Пока исследователи разработали лишь схему TWIRL и не реализовали ее на практике, хотя предварительная оценка показывает, что с помощью TWIRL взлом шифров с ключами длиннее 512 бит становится возможным. Например, для вскрытия 1024-битного шифра понадобится специальный компьютер на основе TWIRL стоимостью около 10 млн. долл. США. Для взлома шифра такой машине понадобится около года. 512-битный шифр RSA TWIRL-компьютер стоимостью в 10000 долларов США вскроет менее чем за десять минут.

[Archy]

А как вам метод быстрого поиска, описанный в соседней теме?

[c_a]

http://www.cryptology.ru/
... может здесь найдете полезную инфу по алгоритмам ...

[Evgeney]

Привет всем, кое-что нашел. http://artificial.progmeistars.lv/goods/index.htm внизу страницы.
Там можно скачать PDFку http://artificial.progmeistars.lv/goods/primality.zip

[ScyRnest]

Всем привет, мне самому интересно все это, но жалко помочь врятли смогу со своим вторым пнем:))))
Вот свежая идейка, почитайте, мож наведет на мысли какие
http://web.ru/db/msg.html?mid=1161209

[angel_n_flesh]

Доброго времени суток... Идеи:
1: Если вариант 1 - у Мотороловских программеров есть закрытый ключ, которым они шифруют прошивку, а в ПСТ открытый, который дешифрует её и ставит на мобилу, то нельзя ли перехватить инфу, которая заливается в мобилу через USB... Просто промониторить эту хрень, в чистом виде, потом послать нах ПСТ и написать свою прошивку и свою прогу для прошивки мобилы... Сам не могу - я её даже прошивать боюсь (C550). И руки кривые... Жалко.
2: Если я тупой, и просто напросто ключ для дешифровки залит в телефон, и через USB в него льётся запароленный софт, а в телефоне он распароливается и ставится, то: вариант лишь один - двинуть науку чтобы похакать телефон, либо... Мож прокатит... В шестнадцатеричном редакторе попробуйте данные расположить в 16 колонок и 10 строк... И пройтись PageDown'ом... Одна строка меняется наподобие счётчика, а вот в свете криптографии что бы это значило хрен его знает. Строку тоже подогнать можно, вставив в начале файла нужное к-во "левых" байт...
3: еси я правильно понял, у вас вообще ничего нету - ни запароливающего ключа (закрытого), ни распароливающего ("открытого", щедро розданного владельцам Motorol'ок внутри телефона)... Какой подход можно изобразить к его взлому тогда?...
4: откуда известно, что ключ 1024-разр... Фиг знает, но цикличность в файле прошивки проявляется на 16*9*8=1152... Битах... ну да, скорее всего 1024 разр...
5: Какая херня в телефоне отвечает за это раскодирование?!!! Вырвать её нах, перепаять всё нах напрямую, послать нах ПСТ и написать свою прошику на асме залив её собственной прогой мимо раскодирования...
6: Блин, фигни я понаписал....
7: Да, и ещё... Если шифрование несимметричное, откуда в файле прошивки эта фигня со строкой - счётчиком?... Чё то не верится в несимметричность...

[angel_n_flesh]

Да и ещё, уцепившись за эту хренову цикличность, вот что настораживает...
1: Почему содержимое файла в ASCII кодировке представлено только шестнадцатеричными цифрами?, т.е. 0,1,2,3,4...E,F... Значит 1 байт вливаемой инфы в файле прошивки представлен двумя байтами... Это ещё раз подталкивает к мысли о том что раскодирование производится ПСТ до перепрошивки мобилы. Иначе на кой хрен вся эта требуха с заменой байта двумя байтами? Чтобы в ПСТ опять сжать и отправить на мобилу? Или чтобы траффик больше был?... Или чтобы в ПСТ лишнюю функцию организовать?... Что то я всё меньше верю в несимметричность шифрования... А при несимметричности алгоритма они наверняка бы стандартными API пользовались, а они (API) такую муть в ASCII кодировке не порождают...
2: К сведению: контроллеры обычно так прошиваются: указывается смещение (может быть номер страницы), и блок данных, которые в эту страницу помещаются... Ну вот судя по всему размер страницы 64 байт (правдоподобно?), строка-счётчик - это номера страниц...

[lester_dev]

Я где-то читал про квантовый компьютер. Так ему вроде бы понадобилось около минуты что б расшифровать самый крутой РСА ключ. Ни у кого случайно нету такого? :D

http://psj.nsu.ru/lector/neizvestniy/
http://www.sciam.ru/2003/3/inform.shtml

[BOBONUS]

Вот здесь есть кое-что интересное и ещё куча всего.

WASM.RU
WASM.RU - Криптография
WASM.RU - Крипторы








E398 SOFT

[thelife]

Почитал весь раздел- инфы много интересной... Мысли сразу поперли: во-первых, чтоб прога-дешифратор работала быстрее(даже при подборе кода), надо, чтоб она перебирала только простые числа. То есть проге надо "дать" базу 512битных простых чисел. Таблица будет весить немало, а следовательно, затормаживать процесс поиска... Идея такая- написать плагин-генератор простых чисел по принципу "от противного"... То есть сначала он будет генерировать все сложные числа, а затем из всех натуральных чисел исключать эти сложные. А сложные можно генерировать так: каждое второе число кратно двум, каждое третье- трем, пятое- пяти, седьмое- семи, ..., 17-е- 17-и, .., и т.д. Ну естественно, целесообразно сразу исключить числа, кратные числам от 2, хотябы до 1000000. И дальнейший подбор производить уже с оставшимися. При подборе чисел уже непосредстванно в код, надо начинать с самых больших, поскольку врядли там есть числа порядка 10^6 (вычислить их не так-то сложно, и упрощение датьнейших действий существенно(10^308 и 10^302).

[Tungsten]

1. Никто уже никуда не идет, насколько я знаю
2. когда-то я писал программу генерации простых чисел решетом. Жрет память в неимоверных количествах.
3. в данном случае все упрется... именно в память. Считай, сколько примерно будет 512-битных чисел, перемножай, смотри, сколько надо памяти... но это если генерировать на лету. Конечно, все пойдет лучше, если генератор будет работать отдельно, но... ему уже памяти не хватит. В общем, упираемся и ?