Всё просто и понятно. Спасибо. Остался последний вопрос , но уже ,наверное , больше к создателю RSATool -
все ли современные методы факторизации он использовал ?
Да и несколько глюков в программе есть.
А как итог всех постов - будьте внимательней , не как я ,
а как Bogrus, а для программеров - используйте правильные методы защиты , например RSA , выбирая правильную длину ключа.
Bogrus , мой Respect.

Вряд ли для факторизации 512 бит кто-то использует RSATool, тут мощности одной машины недостаточно, нужно распределение

з.ы. ты лучше скажи, как там в паскале, это что PRNG?

     for i := 0 to PrimeLength do
     begin
          SeedP.Contents[i] := Random($FFFFFFFF);
          SeedQ.Contents[i] := Random($FFFFFFFF);
     end;

Интересно как этот Random работает

Что-то понаходил
http://www.merlyn.demon.co.uk/pas-rand.htm
http://www.winsov.ru/delphi002.php

The Turbo/Borland Pascal and Delphi function Random generates pseudo-random sequences by updating a 32-bit variable RandSeed , which is normally initialised by Randomize from the system clock.

Интересно, может ли это помочь, если знать дату генерации ключей ...

у бормана вообще никакой генератор. Если знаешь два последовательных ответа random() можно на ура восстановить состояние генератора. А зная диапазон возможных дат можно значительно ускорить перебор.

генератор лучше взять от майкрософта в сорцах nt4.
искать ф-ю CPGenKey.
там вообще весь криптопровайдер в сорцах лежит :)

2 Bogrus
Интересно как этот Random работает

Так вот и я о том же спросил , как воспользоваться "слабостью" PRNG ? Код Random от Borland ты кстати можешь найти опять же в отладчике или еще проще в Иде.


у бормана вообще никакой генератор. Если знаешь два последовательных ответа random() можно на ура восстановить состояние генератора. А зная диапазон возможных дат можно значительно ускорить перебор.

2 Infern0
Это вообще слабость софтовых генераторов ,
привязанных только к таймеру (как написано в умных книгах, в частности у Шнайера). Но как ею воспользоваться ,что-то я слабо представляю. Не по дате же файлов всё восстанавливать.


генератор лучше взять от майкрософта в сорцах nt4.
искать ф-ю CPGenKey.
там вообще весь криптопровайдер в сорцах лежит :)

А это здесь причём ? Прога написана на Builder. Компонент тоже.PRNG Борландовский. CryptoAPI не используется.
Вы о чём , Max ?

Но как ею воспользоваться ,что-то я слабо представляю.

Решить систему уравнений. Обернуть формулу и по результатам получить внутреннее состояние PRNG.

bogrus
„Интересно как этот Random работает“

Randomize();
rnd_var:= Random($FFFFFFFF);
...
; инициализация RandSeed
Randomize proc near
  var_8  = dword ptr -8
  add     esp, -8
  push    esp             ; lpPerformanceCount
  call    QueryPerformanceCounter
  test    eax, eax
  jz      short loc_TickCount
  mov     eax, [esp+8+var_8]
  mov     ds:RandSeed, eax
  pop     ecx
  pop     edx
retn

loc_TickCount:
  call    GetTickCount
  mov     ds:RandSeed, eax
  pop     ecx
  pop     edx
  retn
Randomize  endp

; PRNG
; EAX = Range
RandomInt  proc near
  push    ebx
  xor     ebx, ebx
  imul    edx, ds:RandSeed[ebx], 8088405h ; дизассемблер Делфи показывает как [ebx+RandSeed]
  inc     edx
  mov     ds:RandSeed[ebx], edx
  mul     edx
  mov     eax, edx
  pop     ebx
  retn
RandomInt endp

RandomInt

Не понимаю я этой функции. Чем больше смотрю - тем хуже становится! Вот это:

  imul    edx, ds:RandSeed[ebx], 8088405h
  inc     edx
  mov     ds:RandSeed[ebx], edx

сводится к

RandSeed = 1 + (RandSeed * 0x8088405);

Между прочим, возникает переполнение при умножении, что сводит такой PRNG на ноль. Кроме того, формула просто офигительная...
А вот на этом:

  mul     edx
  mov     eax, edx

у меня отшибло крышу. Можно бы предположить, что:

Range = RandSeed * Range;
return Range;

но

Умножение беззнаковое - команда mul. В eax, я так понимаю, согласно комментариям, сидит Range. В edx - RandSeed. Т.е. идет перемножение, но вместо пары edx:eax используется только eax. НО. Почему компилятор решил использовать беззнаковое умножение когда один из операндов знаковый - я не понимаю.

Вот моя программка, на которой тестировал. Не запускать. Только дизассемблировать.

static long RandSeed;

static unsigned long RandomInt(unsigned long Range)
{
	unsigned long Range_out;
	RandSeed = 1 + (RandSeed * 0x8088405);
	Range_out = Range * RandSeed;
	return Range_out;
}

void main ()
{
    RandomInt(0xFFFFFFFF);
    return;
}

Поправьте меня, если ошибся на счет формулы и прототипа функции - из листинга выше не совсем это понятно...

Когда устаканим формулу - наша задача - найти RandSeed. Для этого (если имеется доступ к выходу RandomInt) накапливаем выходные значения.
Потом решаем систему уравнений.
Пример от балды.

Range_out = (1 + (RandSeed * 8088405h)) * Range_in;

Пусть Range_out = {45,175}.
Тогда

(1 + (RandSeed * 8088405h)) * Range_in = 45
(1 + (RandSeed * 8088405h)) * Range_in = 175

Две уравнения - два неизвестных. Все.
infern0 говорил совершенно правильно.

P.S. А за такие PRNG убивать надо.

Пусть 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.

„В противном случае seed восстанавливается полным перебором состояний RandSeed - их всего 2^32.“

Значит остаётся полный перебор. Времени уйдёт уйма ,
но всё равно значительно меньше , чем на факторизацию.