взломщикам RSA на заметку

Привет. Попал на непонятную мне реализацию RSA. Есть дос файлик реализующий как буд-то выход = вход ^ 3 mod k. При специально подставленных малых значениях вроде все работает...В архиве (пароль wasmwasm) здесь:

http://files.onlinesoft.ru/cgi-bin/filex.cgi?ac-go=r.rar

есть и c++ аналог дос файлика. Длина чисел - 192 байта. К ключу вначале есть и не очень понятная константа 77, которая (как я думаю) имеет строго определенное значение в зависимости от младшего байта ключа (b9).

Нуждаюсь в помощи понятия алгоритма (пока даже не смею верить, что возможно найти приватную експоненту)...Спасибо.

 

RSA может использовать двухбитные экспоненты 3,17,257 или 65537, все одно.
Это сделано исключительно для быстродействия, а так все экспоненты одинаковы по стойкости.

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

А ежели прога добавляет-таки в начало мусор - то никак.

 

persicum

Ничего прога не добавляет. В примере есть реальные данные (посмотрите на выходной файл). Могу извлечь несколько "правильных" входных файлов. С модулем К не могу разобраться перед тем как вообще думать об уязвимости...

 

georgel
возьми нормальную реализацию с sourceforge.net

 

UbIvItS

Tы меня не правильно понял - суть сделать свой входной файл для этого алгоритма

 

georgel

Sounds like an 8-bit Montgomery RSA signature implementation. That constant multiplied by the first byte of the modulus should give 0xFF. You have three choices: 1) factor that 1536-bit modulus (most expensive), 2) find a large number of smooth signatures and from them build a table of signatures of all small primes, then build signatures by factoring the data you need to sign, with some luck you'll have a smooth enough meaningful input file (much cheaper) or 3) since it's a simple cube without hashing, you can prepare special kind of files with matching signatures: all-0 or a small number that taken to the power of 3 will give you the right signature (super cheap). You'll just have to convert them to n-residue format. Shamus Miracl library has a function for that. There is not much else you can do.

 

deleted

 

Ruptor
Thank you for your competent directions. Could you tell me what is so specific about this Montgomery implementation that I am unable to achieve the same results while using a big number calculator? I suspect there is something very tricky about the modulus. And sorry for even mentioning it but don't you think I have a chance to find a private exponent by mere bruteforcing (in case it is a relatively low number)?

Option 3) is not an option actually since every byte in the message counts

 

You must convert the input number to n-residue format. Looks like that conversion is missing in the code. The final conversion may also be missing. There is nothing special about the modulus.

And no, you don't have a chance of finding the private exponent. It will not be a low number.

 

Ruptor

Added: I've experimented with the given input (which appears to be in n-residue format) and failed with the big number calculator! Why?

Since the input is prepared by the party that holds the private exponent there is no access to the code that makes this conversion...Although an access to another obfuscated code that makes similar conversion in the field might be possible it would use the same algo and same public exponent =3 but with shorter (and different) key...So I think it is irrelevant to this problem...

No, the output is directly used for checksum and string comparison.

Last hope disappeared. I still wonder (because of my ignorance) how such super large exponents are actually used

 

del

 

georgel

You failed with the big number calculator probably because big number calculators operate with normal numbers, and if they support n-residue format, those are most probably n-residues mod 2^32, and yours is mod 2^8. You may also have to try converting the result back to binary and not converting it to see which one of the two it is, but it should work.

There is plenty of hope. They are exponentiating the input itself, not its hash. You can easily find plenty of smooth cubes to be able to reproduce a signature maybe not for any, but at least for any reasonably smooth input. It's not as hard as factoring the modulus.

 

del

 

Ruptor

The message consists of 12 AES encryptions of constants 0-b with a single key...One of them is partially overwritten with a string. Does it sound you like a reasonably smooth input?

 

Smooth means divisible only by small primes. So yes, it does. It can be. Try factoring it.

 

Ruptor

What's the difference between factoring a 1536 bit modulus and a message of the same length?

 

georgel
RSA modulus doesn't have small factors, it is chosen to resist factoring. Message of same length may have small factors (and it is very likely that it actually has) and may be factored much easily.

 

flankerx
Sorry for incompetence, but what should be done with the factored message? Is there a software that is already made with which I could try to factor a message just too see if it is possible to be done and how long it takes?

 

You can try RSATool (which you can find on this site, http://wasm.ru/baixado.php?mode=tool&id=308)

 

flankerx
I've tried it with the output.bin (in reversed order of bytes, of course). So far it has found the following:
PRIME FACTOR: 2
PRIME FACTOR: 2
PRIME FACTOR: 3
PRIME FACTOR: 6D
PRIME FACTOR: 1183
PRIME FACTOR: 757C4DF2E9D
PRIME FACTOR: 2EB35CB6AD23

What am I supposed to do with these primes?