Прошу совета у знатоков криптографии и RSA в частности.

Пусть Range_out = {45,175}.



Всё равно непонятно. А где взять то этот диапазон ?

Исходные данные - это только Public key. Ну допустим

программа написана в 2003-2004 году. И всё.

 

А вот на этом:

mul edx

mov eax, edx

у меня отшибло крышу.



Здесь получается , что в eax или 0 или старшая часть

результата умножения.

 

RandSeed определён как int RandSeed.



Что интересно, и Delphi, и BCB компилируя пример генерируют знаковое умножение, даже если RandSeed определён как unsigned int.

 

По-моему, я слегка ошибся с формулой.

Range_in нам ведь тоже известен... Так что нужно решить только одно уравнение...



Всё равно непонятно. А где взять то этот диапазон ?





Бряку поставить в айсе. И на цифирки посмотреть

Помнишь, я говорил (если имеется доступ к выходу RandomInt) - дык вот, если этот PRNG от тебя не спрятан за какой-нибудь фигней, если у тебя есть непосредственный доступ к входным и выходным значениям функции, то seed восстанавливается по уравнениям. В противном случае seed восстанавливается полным перебором состояний RandSeed - их всего 2^32.

 

Значит остаётся полный перебор. Времени уйдёт уйма ,

но всё равно значительно меньше , чем на факторизацию.

 

не уйма. Если randseed действительно зависит от даты то получится меньше чем 2^32 и вполне так решаемо.

 

Получается randseed зависит от GetTickCount, т.е. двордового счетчика, который стартует с момента загрузки ОС, и делает полный оборот за 49.7 дней

Но! Многие ли не выключают комп такой период? имхо обычно машина работает до суток



added: trsa я компилил в 6-м дельфи, там в randomize используется GetSystemTime

Код (Text):

1. rtl60.System::Randomize 4>/ PUSH    EBP
2. 40003679                  | MOV     EBP, ESP
3. 4000367B                  | ADD     ESP, -18
4. 4000367E                  | LEA     EAX, DWORD PTR [EBP-18]
5. 40003681                  | PUSH    EAX
6. 40003682                  | CALL    <JMP.&kernel32.GetSystemTime>
7. 40003687                  | MOVZX   EAX, WORD PTR [EBP-10]
8. 4000368B                  | IMUL    EAX, EAX, 3C
9. 4000368E                  | ADD     AX, WORD PTR [EBP-E]
10. 40003692                  | IMUL    EAX, EAX, 3C
11. 40003695                  | XOR     EDX, EDX
12. 40003697                  | MOV     DX, WORD PTR [EBP-C]
13. 4000369B                  | ADD     EAX, EDX
14. 4000369D                  | IMUL    EAX, EAX, 3E8
15. 400036A3                  | MOV     DX, WORD PTR [EBP-A]
16. 400036A7                  | ADD     EAX, EDX
17. 400036A9                  | MOV     DWORD PTR [System::RandSeed], EAX
18. 400036AE                  | MOV     ESP, EBP
19. 400036B0                  | POP     EBP
20. 400036B1                  \ RET
21. rtl60.System::RandInt 4>  / PUSH    EBX
22. 40004125                  | XOR     EBX, EBX
23. 40004127                  | IMUL    EDX, DWORD PTR [EBX+System::RandSeed],8088405
24. 40004131                  | INC     EDX
25. 40004132                  | MOV     DWORD PTR [EBX+System::RandSeed], EDX
26. 40004138                  | MUL     EDX
27. 4000413A                  | MOV     EAX, EDX
28. 4000413C                  | POP     EBX
29. 4000413D                  \ RET

В этом случае, если предположить, что ключи генерировались автоматически в момент компиляции (сборки) проекта, то это (почти точное) время известно по PE.TimeDateStamp

 

Каков принцип:

Берем начальное значение RandSeed, как в проге генерим 2 простых числа (P и Q), перемножаем и сравниваем с твоим modulus, если не совпало - значит повторяем пока RandSeed<>FFFFFFFF



Как происходит генерация P и Q в этом примере:

Нажимаем "CreateKey" и vcl60.Controls::TControl::Click запускает процедуру.

Она выделяет 2 буфера (обзовем их "Xp" и "Xq", каждый размером 17*4 байт), потом их заполняет (вызывая rtl60.System::RandInt) случайными значениями. Но (видимо хороший глюк параметр RandSeed пуст, т.к. не вызывалась ф-ция Randomize, и по этому значения эти не случайны, а всегда одинаковы! Буферы "X" это просто константа, с которыми будут ксорится числа.



Теперь уже вызывается Randomize (один раз), после этого выделяется ещё 2 буфера (пусть "P" и "Q", по 8*4 байт=256 бит для RSA512), в них будут числа P и Q. Далее идет заполнение этих буферов, вот тело цикла для числа P:

Код (Text):

1. CALL    <JMP.&rtl60.System::RandInt> ; в eax псевдослучайное число
2. XOR     EAX, DWORD PTR [EDI]         ; в edi буфер "Xp"
3. MOV     DWORD PTR [EDX], EAX         ; в edx буфер "P"

После цикла, чтобы число было простым, видимо делается такая махинация:

Код (Text):

1. OR      [EDX+28],80000000h ; последний дворд P
2. OR      [EDX],1            ; первый дворд P

Дальше P*Q и modulus готов. Всё, выдираем\пишим, оптимизируем алго и ждём заветные P,Q



man0war Как там в твоей (не тестовой) проге х.з.

 

Bogrus

Спасибо . В принципе я это давно понял , просто

думал над тем как уменьшить диапазон для перебора.

 

Вообще я время даже приблизительно не прикидывал, думай, какой там возможен RandSeed в твоей проге...

И потом, ведь ещё можно диапазон RandSeed разбить на части, пропорциональные количеству машин, которые ты можешь задействовать.

 

bogrus

Я привёл листинг Randomize и RandomInt (есть ещё Random, определённый как function Random():Extended; ), их генерирует Borland Delphi Compiler 15.0 (Delphi v7.0.4.453). Так что придётся посмотреть, что в предыдущих версиях (<6.0) и точно определить версию, которой собран целевое приложение.

 

что-то мне подсказывает что исходники VCL, в особенности модуль system, где, скорее всего, находится функция random не меняются уже очень долго между верисями. IMO надо не версию компилятора определить а просто версию делфи (5,6,7) и посмотреть в сырцы соответствующей VCL.

 

Компилятор не Delphi ,а Builder 5 ,

но это в данном случае безразлично.

 

Bogrus

В примере , который идёт с компонентом ,

всё просто , в нём заполнение массивов SeedP и SeedQ идёт

с помощью функции Random($FFFFFFFF) . Ничего подобного

в программе , которую я рассматриваю , не используется.

Разработчик скорей всего воспользовался советом создателей

компонента и применил более "правильный" PRNG ,

что-нибудь типа BBS (Blum-Blum-Shub). Это только моё предположение, так как это не выяснить - никакого кода нет.Ключи сгенерированы отдельной программой.

Программа , которая исследовалась , лежит на

www.ptgui.com

Всё , наверное надо тему закрывать.

 

пропатчи паблик кей - по-моему это наиболее приемлимое решение исходя из вышеизложенного.

 

Спасибо ,infern0 . Это я давно понял , но не хотел

применять "грязный" битхак Всё хотелось сделать

красивей , поэтому и начал эту тему.

 

ЗДРАВСТВУЙТЕ!

Понравилось мне все это и решил написать свою прогу. Всвязи с этим, мне интересно, а если "разбавить" генератор случайных чисел при создании ключей действиями пользователя (т.е. нажатие клавиш, перевод курсора мышки etc), сложнее ли будет расшифровывать.



Второй вопрос.

Вот мы закриптовали и радуемся! А на жестком диске ничего не осталось? То есть, если мы сделали программу, не создающую никаких файлов на жестком диске, то закриптованные все равно придется как-то копировать.

Если их мы положим из памяти в буфер, они могут "перекочевать" в файл подкачки?

 

Не знаю какую для чего, но уже чувствую, будет велосипед

Сложнее

Если сразу радуемся, то осталось.

Откуда и куда положим ... ?

Могут

 

А Вы не знаете, каким образом этого можно избежать?

 

Чтоб на диске не осталось, то стоит содержимое файла перезаписать несколько раз случайными байтами, если чего в своп попадет, то винда со временем сама выкинет оттуда, или ключ есть для очистки свопа после сеанса работы



А ты чего, сам от себя собрался прятать или кроме тебя на компе юзеры есть?



А вообще шифруй себе, удаляй исходный файл, потом WinHex в руки и поиск по физическому, логическим дискам, что там где осталось



з.ы. тут на "ты", и вопросы по конкретней пжл