modexp

#1
Guest_h4x_*

Posted 28 July 2009 - 02:26 PM

Guests

i have to write rsa enc/dec.

Keys are 100% corrext. Why it doesnt work?

def modexp ( t, u, n ):

   s = 1

   while u:

    	if u & 1:

    	   s = (s * t)%n

    	u >>= 1

    	t = (t * t)%n;

   return s

   

   

   

   

a = 0x61616161616161616161

   

   

a = modexp(a, 65537, 109120132967399429278860960508995541528237502902798129123468757937266291492576446330739696001110603907230888610072655818825358503429057592827629436413108566029093628212635953836686562675849720620786279431090218017681061521755056710823876476444260558147179707119674283982419152118103759076030616683978566631413);

a = modexp(a, 65537, 46730330223584118622160180015036832148732986808519344675210555262940258739805766860224610646919605860206328024326703361630109888417839241959507572247284807035235569619173792292786907845791904955103601652822519121908367187885509270025388641700821735345222087940578381210879116823013776808975766851829020659073);




print(hex(a));

#2
WingedPanther

Posted 29 July 2009 - 07:35 AM

A spammer's worst nightmare

Moderators
16,831 posts

What is it doing? Also, I think your algorithm may be flawed.

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

#3
Guest_h4x_*

Posted 29 July 2009 - 11:37 AM

Guests

its rsa encryption and decryption.
it should print 0x61616161... but instead im betting another value.

where is the flow in my algoritm?
please help me ;/

#4
Guest_h4x_*

Posted 29 July 2009 - 12:03 PM

Guests

pow() and % give also same result (encryption), decryption is so slow that i interrupted test. so i dont think my algo is flawed.

#5
WingedPanther

Posted 29 July 2009 - 12:13 PM

A spammer's worst nightmare

Moderators
16,831 posts

Usually, RSA doesn't require % until AFTER the while loop. Using % at each round of the loop is almost guaranteed to hose your results.

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

#6
Guest_h4x_*

Posted 29 July 2009 - 12:18 PM

Guests

huh?
how does modulo after each round destroy result?

and without modulo i dont think i have enought memory to process that ;)
i managed to finilize pow() method - same result as modexp both enc and dec.

def modexp ( t, u, n ):

   s = 1

   while u:

    	if u & 1:

    	   s = (s * t)

    	u >>= 1

    	t = (t * t)

   return s%n

   

   

   

   

a = 0x6161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161

   

   

a = modexp(a, 65537, 109120132967399429278860960508995541528237502902798129123468757937266291492576446330739696001110603907230888610072655818825358503429057592827629436413108566029093628212635953836686562675849720620786279431090218017681061521755056710823876476444260558147179707119674283982419152118103759076030616683978566631413);

a = modexp(a, 65537, 46730330223584118622160180015036832148732986808519344675210555262940258739805766860224610646919605860206328024326703361630109888417839241959507572247284807035235569619173792292786907845791904955103601652822519121908367187885509270025388641700821735345222087940578381210879116823013776808975766851829020659073);




print(hex(a));

doesnt work, still executing and i doubt it will finish.

#7
WingedPanther

Posted 29 July 2009 - 12:36 PM

A spammer's worst nightmare

Moderators
16,831 posts

I stand corrected on the %. Why are you using a >>= operator, though? You aren't getting the power 65537 in that case.

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

#8
Guest_h4x_*

Posted 29 July 2009 - 12:48 PM

Guests

look: my algo is fine. exactly SAME result if using pow(a, 65537)%4234232....
but bilion times faster
>>= is to properly process only bits wich are 1. next step t*t % n change each step, so if exponent is

101

it will be
*1
*1^3

or smth like that.
if you can please generate your own rsa keys somewere and test it.

i stuck in this for... hmm i think it will be 1 month soon.
HELP :(

#9
Guest_h4x_*

Posted 29 July 2009 - 01:01 PM

Guests

ohdave.com/rsa/

im getting right cipher value, but it seems i cant obtain deciphered bessage after

#10
WingedPanther

Posted 29 July 2009 - 01:33 PM

A spammer's worst nightmare

Moderators
16,831 posts

Your message is:
a = 0x6161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161

You encrypt the message by calling encrypted = message^e mod n
You decrypt the message by calling message = encrypted^d mod n

However, based on what I can see, you are not doing that, you are doing:
You encrypt the message by calling encrypted = message^n mod e
You decrypt the message by calling message = encrypted^n mod d

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

#11
Guest_h4x_*

Posted 29 July 2009 - 03:06 PM

Guests

ok...
thats it!

you can call me noob, i admit it.
as i said i stuck with it for month (well, actually with implementation of DIV in asm) so i forgot how does it work..

solved, now lets go back to div in assembly...