View Full Version : RSA implementation

LaptoniC

November 6th, 2004, 09:03

I am working on some RSA protected app.It serial scheme is different to regular RSA implemantation so that it decrypts serial with d.I guess I have found the n and d however when I feed this values to my bignumber lib it didnt worked

original program

n=79E7FF0C76D6A4F704DBB6F60674D7AD36CF4616A0DC7D0225A5AF4F7471BFAD

d=2A844C090804BD42A260A4BC01AF1A5181769F16E7BE8A289ACCAF3406C184E7

so I calculated

p=B046688D67641C9BC2697D40879BE175

q=B10A9FC3E2EF4912860338DBA2852659

e=E17

Maybe I should first try to brutefrorce e instead of factorig and geting it

I know one valid serial though

name: user600

code: qBaILQ9eHfqaHZw+Ld+gyfBusxmMLOq7CJOBgfHbU2I=

Serial is converted to base64.I am new to RSA thing could you check this values and tell me my values are correct or not for this implementation ?

Thanks

mike

November 7th, 2004, 17:18

you've got your numbers right: p*q=n, d*e=1 mod phi(n). What's 'code' as a number? (too lazy to figure it out myself)

KSA

November 8th, 2004, 08:09

Hi LaptoniC

May I ask you How you obtain the p and q (factoring) ?

Which program you are used to factor this 256 bits RSA number ?

KSA

LaptoniC

November 8th, 2004, 10:55

mike code is as

hex A816882D0F5E1DFA9A1D9C3E2DDFA0C9F06EB3198C2CEABB08938181F1DB5362

dec

76028369049733043146806201961894077383848836998720579113190947617082709857122

for factorizing I used http://www.asahi-net.or.jp/%7EKC2H-MSM/cn/ it is faster than RSA-tool and allows you to save and resume.I factored I guess after 1.5 hour dont remember exactly.

mike

November 8th, 2004, 17:42

I get code^d mod n =

dec: 32203605056077899989696486620583417132870039787602000620061715128083153892901

hex: 473298337bae3413c451da2685c6c0198f473af75521f5b66904cc7c439f3625

and code^e mod n =

dec: 25633554524463369197540132814160836968933790088022549341000866828215553752435

hex: 38ac13e50fab65f6f3a1d21d4356a5b511039facf5d6d3bf8d3da1c51d7dfd73

http://www.alpertron.com.ar/ECM.HTM is a java factoring applet that's pretty good

LaptoniC

November 8th, 2004, 19:24

That means I skipped something I will dig it more thanks for your time.

volodya

November 10th, 2004, 14:52

*http://www.alpertron.com.ar/ECM.HTM is a java factoring applet that's pretty good*

Not bad indeed. Two-stage ECM with the weeker B-smoothness limitation... Hmm... But it is Java. Therefore, the speed is horrible.

Better use this one:

http://www.loria.fr/~zimmerma/records/ecmnet.html

This one is using GMP engine. Once again, I'm too lasy to check if this guy has implemented FFT-multiplication, but, anyhow...

mike

November 10th, 2004, 22:39

Java doesn't necessarily imply horrible speed: JIT compilers do a really good job these days, and it's all math calls which are native anyway. Why doesn't someone do a comparison and let us know?

volodya

November 10th, 2004, 22:52

The keyword here is "JIT compilers"

As to the speed comparison - m-m-m... Nice idea. Slightly later. Pretty busy now

friedo

December 18th, 2004, 21:47

Is there any known attack if (in addition to modulus N and exponent E) C and M is available?

So i have crypted and plaintext "message" and the modulus and exponent and want to determine my private exponent d. what possibilities do i have without getting my big math bible...?

volodya

December 20th, 2004, 15:44

Without the math, there is nothing you can do at all. You have to know A LOT. As to your specific problem go read

http://www.hackemate.com.ar/ezines/tic/TIC3.txt/TIC3.txt

There is a very easy description there of the various attacks on RSA that do not involve factoring N and allow you to recover M. But I'm not sure about D...

Since d = e^-1(mod((p-1)*(q-1))) you have to know p and q... Though I must admit, I don't know algebra good enough yet to say it for sure

friedo

December 21st, 2004, 05:37

Quote:

*[Originally Posted by volodya]Without the math, there is nothing you can do at all. You * |

I fear thatīs true... ;-)

Anyway, there are lots of Attacks. I played a little with RSATool (2.17).. is there somewhere the source of that nice thing? because i miss some functions and not lucky to write all for new...

(So whatīs with "factorizing" d instead n, furthermore it shuts down without any error calculating bigger keys..)

volodya

December 21st, 2004, 15:32

The newest possible version is on my wasm.

http://wasm.ru/toollist.php?list=23

But why do you need it for?

To factor N you should use specific tools parallelized on many machines (like NFS implementation). RSA Tool is build using Miracl and suites for the numbers that are less then 80 digits, say. You can calculate these on your personal PC.

mike

December 28th, 2004, 16:53

See "Twenty years of attacks on the RSA cryptosystem" by Dan Boneh

http://crypto.stanford.edu/~dabo/abstracts/RSAattack-survey.html

Powered by vBulletin® Version 4.2.2 Copyright © 2019 vBulletin Solutions, Inc. All rights reserved.