PDA

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