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

Да , внимательней надо мне было help читать.

И я никак не думал , что программеры компонента

выдумают свой ряд для base 64. Ламернулся

Bogrus Ты же скачал компонент , как я понял ,

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

конвертации - он вроде бы лежит в функции MakeKeyPair ?

И действительно дело в кодировке , потому что для проверки

простоты числа разработчики использовали тесты

Миллера-Рабина и Соловея-Штрассера и скорей всего никакой

лажи не допустили.

Спасибо всем за помощь.

 

Хе, скачать то скачал RSA_free.zip, но эта х. не обнаружила у меня борландовских продуктов и ничего кроме хелпа не поставила

 

Накидал программу для перевода из их кодировки в каноническую Вот 16-ричный код -



34BD4FE379A60DA747815CDBCD9BD12F11C8F4074143F658D391CF4

3A0239DBD38A150FE01B492F245B4C25EA48C95A5A8F5B068A6B475

5AE38C64159759C4B



Всё равно RSATool раскладывает число на 3 простых.

 

Приведенные тобой и те и эти числа недотягивают до 512 бит, в хексе должно быть 64 (40h) байт (128 символов)

Лучше ищи в отладчике (судя по хелпу рой в сторону EConvertError), там должно быть ясно какая экспонента и какой modulus после конвертации, хотя... врядли это чем-то поможет разложить RSA512

 

2 Bogrus

Согласен , я привёл ключ из реальной программы

(для фотографов) , но если взять ключ из Examples

установленного компонента , то там 100 пудов 512-битный ключ.Если скомпилируешь этот Example , то программа тоже генерирует ключи. И в обоих случаях ключи 512-битные ,но

опять же они факторизуются на 3 и более простых числа.

Я менял порядок байтов на инверсный ,но RSATool факторизует предлагаемый modulus на раз. В конце концов речь ведь не о 45 баксовой программе , а конкретно об этом компоненте и о возможно ошибочной реализации RSA.

И главное о том , какие выводы (в первую очередь) можно сделать и какие "дивиденты" из этого можно поиметь.

Скомпилируй и убеди меня , что это не кривые руки

программеров , а мои кривые мозги

С уважением ,

man0war.

 

Блин, у меня полтора часа ушло поставить дельфи, научится компилировать в нем маленькие exe'шки

Вот архивчик по TRSA, надо будет поразбираться в ихнем BASE64 и BigNum, может завтра ...

Код (Text):

1. procedure TfrmRSATest.btnCreateKeyClick(Sender: TObject);
2. var
3.      SeedP: BigNum;         // holds the seed for the random search of Prime1
4.      SeedQ: BigNum;         // holds the seed for the random search of Prime2
5.      PrimeLength: Integer;  // holds the number of significant 32 bit words
6.      i: integer;            // loop counter
7. begin
8.      {** get a random seed for the search - your routine
9.          should use a high quality RNG to fill this seed **}
10.      // get the number of words in the BigNum for the currently selected key length
11. PrimeLength := RSA1.GetPrecision;
12.      // fill the random numbers which will seed the search engine
13. for i := 0 to PrimeLength do
14.     begin
15.         SeedP.Contents[i] := Random($FFFFFFFF);
16.         SeedQ.Contents[i] := Random($FFFFFFFF);
17.     end;
18. RSA1.MakeKeyPair(SeedP, SeedQ);      // create the key pair

_1628218834__trsa.rar

 

Зачем обязательно Delphi ставить , если Pascal не знаешь,

то поставь Builder , это же не принципиально.



Есть вопрос , если modulus раскладывается на 3 и более

множителя , то естественно , что Encrypt/Decrypt работать

не будет и верификация тоже , но в примере у них всё работает. Что-то я совсем запутался.

 

Запутался потому, что надо ихний base64 преобразовать точно так, как это делает прога, иначе неправильный modulus будет разлаживатся не на два простых числа, а на всякую ерунду



Короче я пока сделал так: Ввел в прогу твой public key "++11IE:pGQKLK-NACiKpFfdc-PxcKOZAGeL0HPFm97h-sDIVWHjRC0c1xQYHXZx13o-oX Q2j2xaBjBL-SodBMOSXzIjo+", нажал Set Entered Key, потом бряки-кряки и в отладчике появился такой хекс:



5D1627D5EB305960E91AD596A1FD16A02A31A566D1360997076DB2C82486D483A8E074 EF4E24D70F5D0C7D390437D20136664FBCED0557F39E863529D02FF58F



Переворачиваем:



8FF52FD02935869EF35705EDBC4F663601D23704397D0C5D0FD7244EEF74E0A883D486 24C8B26D07970936D166A5312AA016FDA196D51AE9605930EBD527165D



Меняем number base:



7539679715254555336427901656902588117692097765901830952359442316635707 0830310610697188556473784736230294790299127578758798866606922707100238 72991415703133



Теперь можешь впихнуть это в Cryptool,RSA Tool и ждать ...Ж)

326807967___00D00000.mem

 

C modulus мне всё понятно , янеправильно конверировал , а exponenta какая ?

 

20931



забыл перевернуть хекс, вот 50001

 

Всё просто и понятно. Спасибо. Остался последний вопрос , но уже ,наверное , больше к создателю RSATool -

все ли современные методы факторизации он использовал ?

Да и несколько глюков в программе есть.

А как итог всех постов - будьте внимательней , не как я ,

а как Bogrus, а для программеров - используйте правильные методы защиты , например RSA , выбирая правильную длину ключа.

Bogrus , мой Respect.

 

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



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

Код (Text):

1.      for i := 0 to PrimeLength do
2.      begin
3.           SeedP.Contents[i] := Random($FFFFFFFF);
4.           SeedQ.Contents[i] := Random($FFFFFFFF);
5.      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

Код (Text):

1.  
2. Randomize();
3. rnd_var:= Random($FFFFFFFF);
4. ...
5. ; инициализация [b]RandSeed[/b]
6. Randomize proc near
7.   var_8  = dword ptr -8
8.   add     esp, -8
9.   push    esp             ; lpPerformanceCount
10.   call    QueryPerformanceCounter
11.   test    eax, eax
12.   jz      short loc_TickCount
13.   mov     eax, [esp+8+var_8]
14.   mov     ds:RandSeed, eax
15.   pop     ecx
16.   pop     edx
17. retn
18.  
19. loc_TickCount:
20.   call    GetTickCount
21.   mov     ds:RandSeed, eax
22.   pop     ecx
23.   pop     edx
24.   retn
25. Randomize  endp
26.  
27. ; PRNG
28. ; EAX = Range
29. RandomInt  proc near
30.   push    ebx
31.   xor     ebx, ebx
32.   imul    edx, ds:RandSeed[ebx], 8088405h ; дизассемблер Делфи показывает как [ebx+RandSeed]
33.   inc     edx
34.   mov     ds:RandSeed[ebx], edx
35.   mul     edx
36.   mov     eax, edx
37.   pop     ebx
38.   retn
39. RandomInt endp

 

RandomInt



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

Код (Text):

1.  
2.   imul    edx, ds:RandSeed[ebx], 8088405h
3.   inc     edx
4.   mov     ds:RandSeed[ebx], edx
5.  

сводится к

Код (Text):

1.  
2. RandSeed = 1 + (RandSeed * 0x8088405);
3.  

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

А вот на этом:

Код (Text):

1.  
2.   mul     edx
3.   mov     eax, edx
4.  

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

Код (Text):

1.  
2. Range = RandSeed * Range;
3. return Range;
4.  

но



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



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

Код (Text):

1.  
2. static long RandSeed;
3.  
4. static unsigned long RandomInt(unsigned long Range)
5. {
6.     unsigned long Range_out;
7.     RandSeed = 1 + (RandSeed * 0x8088405);
8.     Range_out = Range * RandSeed;
9.     return Range_out;
10. }
11.  
12. void main ()
13. {
14.     RandomInt(0xFFFFFFFF);
15.     return;
16. }
17.  

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



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

Потом решаем систему уравнений.

Пример от балды.

Код (Text):

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

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

Тогда

Код (Text):

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

Две уравнения - два неизвестных. Все.

infern0 говорил совершенно правильно.

 

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