modexp

[h4x]

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));

[WingedPanther]

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

[h4x]

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 ;/

[h4x]

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

[WingedPanther]

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

[h4x]

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.

[WingedPanther]

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

[h4x]

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

[h4x]

ohdave.com/rsa/


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

[WingedPanther]

Your message is:
a = 0x616161616161616161616161616161616161616161616161 61616161616161616161616161616161616161616161616161 61616161616161616161616161616161616161616161616161 61616161616161616161616161616161616161616161616161 61616161616161616161616161616161616161616161616161 61616161

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