Раскрываем подпись прошивки, поиск простых сомножителей ключа. Поделиться Опции

[Demm]

Походу только у меня она не пашет :( .Я заметил, что у меня еще некоторые приложения(досовские)Не запускаются, сразу сворачиваются!Что делать?

[dimichxp]

Belmatik,
Almazka,
Demm,

Не пошет потому что уже разложили.

Marvel,

А где исходник?

[Marvel]

Кое-что поправил, кажется еще быстрее считать стало ,
хотя скорее всего меня уже глючит...

Теперь с исходником.

З.Ы. Разложилось за 37 сек. Атлон ХР 2500+, 512 мозгов.

[dimichxp]

Marvel,

for (i=2; i <= d; i++)

Как все запущено... for (i=3; i<=d; i+=2) не устраивает?

А теперь вопрос: у тебя все быстро из-за встроенных типов long, А теперь впихни туда 308-значное число и посмотрим. как ты разложишь.

[Trog]

давайте чтоль ещё какоенить число разложим?? а то скучно както..
а начинать с моточислом работать, мне кажется рановато... слишком сырой софт

[Demm]

dimichxp, не у меня она просто не запускается!В окошке пишет "программа не умещается в памяти" и закрывается!Из-за чего сея фигня?

[dimichxp]

Marvel,

37 секунд... У меня 16
dimichxp ~ # cat 2.cpp
#include <stdio.h>
#include <cmath>
int main( int argc, char* argv[] )
{
long long a = 292061912;
long long b = 900755579;
long long g;
long d;
g = a*1000000000+b;
d = (long)sqrt( g );
for ( long int c = 3; c <= d; c+=2 )
if ( c % 3 ) if ( g % c == 0 ) printf( "%i\n" , c) ;
}
dimichxp ~ # g++ 2.cpp
dimichxp ~ # time ./a.out
515977963

real 0m15.987s
user 0m14.000s
sys 0m0.074s
dimichxp ~ #

А теперь с оптимизацией.

dimichxp ~ # g++ 2.cpp -O3 -march=pentium4
dimichxp ~ # time ./a.out
515977963

real 0m11.022s
user 0m10.547s
sys 0m0.007s
dimichxp ~ #

[dion]

Первое число - 515 977 963.
Второе, соответственно, 292 061 912 900 755 579 / 515 977 963 = 566 035 633. :)
Кто хочет проверить - пакет с диапазоном от прост_сомн-1 до прост_сомн+1 прилагаю.
А можно и просто на калькуляторе посчитать :D

За какое время я его разложил? За 40 секунд... на одном своем компьютере!!!

Прога написана на яве, ее я тоже прилагаю.
Считает по-честному - от 2 до корень из 292 061 ...

dimichxp уже говорил.

2dimichxp: поздравляю. На сколько я понимаю, число разложил ты.

[dimichxp]

dion,

Компильни последнего клиента. Там оптимизация под винду.

[Marvel]

Marvel,

for (i=2; i <= d; i++)

Как все запущено... for (i=3; i<=d; i+=2) не устраивает?

Да, эт я стормозил, а че вы хотели - все-таки моя первая программа. :)

Теперь 19 сек.

dion,

Компильни последнего клиента. Там оптимизация под винду.

Ура, наконец-то и о нас, мастдайщиках, позаботились.

З.Ы. Может теперь посложнее число разложим?

З.З.Ы. Спасибо. :)

Сообщение отредактировал Marvel - 26.5.2005, 9:59

[KQ_44]

Есть ИДЕЯ:
Программа в основном уже выполняет свою функцию.
Если dion и dimichxp небудут сильно возражать, можно начать помаленьку работать.
Выбирать себе коротенький диапазон чисел на день-два кричать в форум, что забили - и проверять. Потом можно ручками проверенное забить на сервере.
Что на это скажут dion и dimichxp???

[dimichxp]

KQ_44,

В принципе можно уже наинать работу в нормальном режиме.

[hobbit19]

и когда начнем??

[Trog]

и тишина...

[Alma.zik]

Хотелось бы узнать а сколько участников уже зарегилось. А то бесполезно будет, если хотя б 20000 компов нет.

[BeZnOg]

Нужна какаянибудь статистика,вроде бы dimichxp собирался прикрутить... :)

[KQ_44]

Пока что на данный момент это единственный метод для изменения подписи. Так что РАНЬШЕ СЯДЕМ - ТОЛЩЕ БУДЕМ. Если у кого есть время и желание и кто помнит про индусов, так у меня есть книга
"О. Н. ВАСИЛЕНКО ТЕОРЕТИКО-ЧИСЛОВЫЕ АЛГОРИТМЫ В КРИПТОГРАФИИ" и там есть это

§ 1.9. Заключение. Детерминированный полиномиальный алгоритм проверки простоты чисел
К тому моменту, когда больша я часть этой книги уже была написана, появилась замечательная работа индийских математиков Агравала, Кайала и Саксены [50] , в которой получен детерминированный алгоритм проверки простоты натуральных чисел, имеющий сложность O(log12 n(log log n)c) арифметических операций (n — проверяемое напрост оту число, c — некоторая абсолютная константа).
Далее мы приводим описание и обоснование этого алгоритма.
Алгоритм работы [50] основан на следующей теореме.
Теорема 1.71. Пусть p—нечетное натуральное число, a ∈ Z,
(a, p) = 1. Число p является простым тогда и толькотогда, когда
(x −a)p ≡ xp −a (mod p) (1.3)
(соотношение (1.3) означает, что коэффициенты многочленов
сравнимы по модулю p).

[Archy]

вот вот :) З.ы. неплохо бы толкового математика подтянуть, да и на асме написать алго, кот непосредственно считает.
Второе можно попросить у ребят с Пирамида - там уже давно всякое считают-раскладывают...
pyramidmagsat.honsat.ru

[dimichka]

Ребята как только начнете это делать напишите письма всем пользователям с просьбой помочь... Например возьмите пользователей у которых количество сообщений больше 20-30. нгапример я уже забыл что вы тут подпись ломаете случайно забрел, а вы тут уже протестили... Или рекламку замутите...

[Alma.zik]

А давайте, будем тестить путём подбора SHA-1. Подобрав, добавим в прошиву хотя б зпись видео на первое время, а потом уже за RSA примемся, ломать то его долго, пока хоть видео поснимаем.

[hobbit19]

SHA-1.
взламывать сколько по времени???
успеем ли??
ведь главное RSA!!!

[Alma.zik]

Если 512 ломали 6-7 мес., то 128 сломается, думаю максимум через месяц, но ведь в худшем случае. Поправьте меня, если я ошибаюсь. Но зато будет чем занятся, пока будем RSA ломать, я не хочу 20 лет ждать не имея ъёмки видео. :D :D :D

[Random]

Если 512 ломали 6-7 мес., то  128 сломается, думаю максимум через месяц, но ведь в худшем случае. Поправьте меня, если я ошибаюсь. Но зато будет чем занятся, пока будем RSA ломать, я не хочу 20 лет ждать не имея ъёмки видео.  :D  :D  :D

Время экспоненциально будет уменьшаться... Т.е. при таком же количестые машин уменьшится не в 4 раза,
а в 2^4 (кажется так).
Ну компов столько еще набрать надо.
Так что месяц как раз и выйдет наверное.

[puper]

Всё не то - ломали 512 бит - а у нас 128 байт (т.е. 1024 бита) - время увеличивается,

Как говорил Vilko, подписью RSA подписывается SHA-1, т.е не вся кодовая часть прошивки, а её хэш, так вот надо подобрать на уже изменённую прошивку такой набор байт, чтобы при подсчёте SHA-1 получалось тоже число, что и в оригинале, тода RSA подпись менять не надо.

[dmat]

хм, я почему то 2 дня несмотря на упорные попытки попасть на мотофан, никак немог этого сделать (писало как обычно "запрошеный url...") думал что сайт упал, или уронили.
странно что тема зоглохла...Dion, Dimichxp вы где ?

[dion]

странно что тема зоглохла...Dion, Dimichxp вы где ?

я тут.

Как говорил Vilko, подписью RSA подписывается SHA-1, т.е не вся кодовая часть прошивки, а её хэш, так вот надо подобрать на уже изменённую прошивку такой набор байт, чтобы при подсчёте SHA-1 получалось тоже число, что и в оригинале, тода RSA подпись менять не надо.

Нужно как бы менять прошивку таким образом, чтобы SHA не менялся. Т.е если подбирать SHA то это нужно делать для каждого изменения в прошивке. А подобрав 1 раз RSA мы решаем все проблемвы.

[KQ_44]

Несколько слов по поводу, ЧТО ЛОМАТЬ - RSA или SHA-1.

В прошивке 3 RSA ключа - 1 прошит в железе(ПЗУ) и 2 в зоне подписи.
С помощью тех 2-х что в зоне подписи и проверяют прошивку.
А вот тем, что в железе(ПЗУ) проверяют подписи для предыдущих 2-х ключей.
Подпись после расшифровки RSA - это 0х01, 0х00, далее много 0хFF,
далее некая сигнатура (она ДОЛЖНА быть аналогична зашитой в железе(ПЗУ)),
а далее уже хеш SHA-1.

Просто испоганить подпись не можем - после RSA пропадет и сигнатура.
Для SHA-1 есть 2 варианта: или мучить прошивку и КАЖДЫЙ раз
подбирать хеш имено для прошивки (зато большой размер - больше вариаций
и больше вероятность подобрать нужный хеш) или, как предлагал Vilko,
подбирать хеш для сертификата ключей, тогда не надо ломать RSA, НО там 0хFF байт
и НЕ ВСЕ их можно менять + обязательны изменения в ключе иначе это не имеет смысла.
Таких сертификата с подписью для ключа 4 штуки.

Итого:
RSA - времени уйдет очень много, но результат гарантирован
SHA-1 - сколько уйдет времени нужно оценить,
возможно намного меньше, но результат НЕ гарантирован.

Если кто захочет поиграть с SHA-1 - все покажу-раскажу. И математик действительно бы не помешал!

[Trog]

господа..
мож всётаки за дело возьмёмся.. а???
я предлагаю начать подбирать множители RSA

[dimichxp]

Trog,

Действительно, пора уж начинать...

(Чего-то заглохла тема... А все так хорошо начиналось) :(

[pahan_tver]

Чего-то заглохла тема... А все так хорошо начиналось

Ничего не заглохло! Просто нужна безглючная версия клиента и люди будут ковыряться. Если текущая версия уже работает, то нужно последнее тестирование и - поехали.

[dimichxp]

Ничего не заглохло! Просто нужна безглючная версия клиента и люди будут ковыряться. Если текущая версия уже работает, то нужно последнее тестирование и - поехали.

Да последняя вроде должна работать хорошо. Только ее никто не скомпилил...

[G.off]

dimichxp,
скорее всего работа и стоит из за отсутствия у разработчика(тобеж тебя) компилятора под винду

[Trog]

dimichxp,

какой тебе компилятор нужен? у мя на работе есть программеры на c++ пишущие..
так что достану

[Alma.zik]

Да... Про SHA-1 я сглупил, взвесив всё, я пришёл к выводу, что если мы подобрав SHA-1 добавим запись видео, то многие откажутся, от дальнейшего подбора RSA, но я сам во что бы то не стало, хочу начать уже подбор RSA, т.к. я знаю, что мой мотор способен на что-то больше. clap;applo

[Romashka0]

Люди давно хочу запустить свой комп на подбор! Нужно составить мануальчик какие проги иметь и что ломать и как это делать!

[Alma.zik]

Мануал, по-моему, уже писали.

[KQ_44]

Almazka:
В твоем предложении нет ничего глупого. Я описал то, что я знаю, но что реальнее - без понятия.
Поскольку ребята RSA уже занялись, возможно попробую поиграться с SHA-1. Но не потому,
что это реальнее - просто интересно.

[Apostol]

Я тут в инете инфу нашел об RSA, может кому что интересно
RSA-кодирование

Исходные тексты на Delphi по реализации алгоритма шифрования RSA как пособие для начинающих программистов. RSA алгоритм относится к ассиметричным алгоритмам шифрования, его главное достоинство - имея открытый ключ и зная алгоритм шифрования невозможно повторить закодированое сообщение, на базе алгоритма RSA работает шифрование PGP, реализуются хэш-функции (элетронно-цифровая подпись). Программа является лениво исполненным интерфейсом для модуля работы с большими числами от Walied Othman (также в этом архиве).

Ссылка http://freesoft.ru/?id=8220

[dion]

Собрал последнего клиента: http://moto.inhex.net/client/client_20050603.zip

Перезапустил сервер. Теперь засунул туда РЕАЛЬНОЕ ЧИСЛО.
Не забудьте заменить файл number!!!!

Вот его содержимое:

Код

11823145941916446514690314500050400455024662194481817715418438557041820322734289
09890011957946150980589602953959112751256719731495098993655713709032459045266537
82569107413713350676232517817181096197654912904839291926811339932095007870787885
454476302964474574702429307332034331743839073902303658693917468638573

Кто нибудь проверьте. Корень из этого числа чему равен?. Я записал (с отбрасыванием дробной части)

Код

10873429055232046031492192397431921672862722538586841594662249849055070405278061
008128997414883027214779472530254046146161597239599829732617709889652045897

Т.е перебор будет идти от него и в сторону убывания пока не найдем.

[WeakMIPS]

Наверное это Firewall у нас на работе тупит. Буду пробывать из дома.