Quote:Original post by Anonymous Poster

Quote:Original post by Nice Coder
...
It works too!

No it does not, see my fix.
Anyway this 'algorithm' is not _any_ better then just brute force checking of all possible factors less than sqrt(n).

Quote:Original post by Nice Coder
...
I would like to know how this algorithm stands.

I think one would have more chances of just guessing the secret message than successfully exploiting this stuff.

1. it works, after the changes you outlined...... but anyway, i fell rather nice, having worked out the method (minus the sqrt) by myself!
2. You can't guess hashes! What i am trying to do, is get d.

so with c^d mod n = m
You know m, d, n and C

You also know what c^d could be.
c^d must be on + m
where o is some integer, n and m are the key (the product of p and q) and the message respectivly.

so, we check o, and for each o, we find the d so that c^d = on + m.

If we cannot find d, then this o must be the wrong one, so you increment o and try again.

we then check the other known c/m pairs (ciphertext/plaintext).
if (for all c/p pairs) ci^d = on + mi then,
we have found d!, we now have the decryption key!
else
we have the wrong o, increment o and try again
end if

i think this should work, but then again, it may not.

Btw, if x^y = z
if i know z and x, how would i find y?

From,
Nice coder

Quote:Original post by Anonymous Poster
NiceCoder,
You'd be better off using Mathematica or Maple than VB for number theory

Or the much cheaper GNU MP big number library.

I'll refrain from ranting about how BS VB is, since C and Java etc won't do big numbers if you stick them in a long either. (This is no excuse to use VB, though.) Just use Windows Calculator (for Win2K or XP) for crying out loud! As if you needed it to tell that
43137655118390846898163374197591 * 2 != 862753102367816937963267483951819444767

It's 86275310236781693796326748395182. And now you've seen Windows Calculator successfully multiply a fairly large number by 2. That's only because this is under 32 bits, of course, which means it's nowhere near the range of a 256 bit RSA key, naturally.

Just so you don't wast any more time on your older method, the original post of the number of comparisons to be made going up by a factor of 10 each time (the 20, 200, 2000, 20000 post) was correct. What you're missing is that just because all numbers that end in 3 and 3 multiplied together end with a 9, does not mean these are the ONLY numbers that will end with a 9. ie, 19 and 1, which are both prime, to boot. True, you will cull out a few numbers, but you've still got an exponential tree of numbers left to check, so unless you work this in as an additional check on a much faster algorithm, it's not going to do anything for you.

Quote:Original post by fractoid
x ^ y = z

Assuming ^ is exponentiation (programmer forum, hence it could be XOR):

log(x^y)   = log(z)y * log(x) = log(z)y          = log(z) / log(x)

Thank you! (it was expentiation, rating+= 10).


I only use vb, because it allows me to write some simple programs quickly, and it was my first language (i also know enough c++, java and python to know what a program does, and code a few simple things in it), and being my first language, it jsut gives me a feeling of ease to work with it.


The only reson i was trying my origional idea, is to try and get p & q from n. That isn't the only way, however.

Currently, knowing what i know now, i can change my method a bit.

instead of:
c^d = on + m
i have

ld = undefinedfor each i in md = log(on + m) / log(c)if d <> ld and ld <> undefined then   o = o + 1   ld = undefined   i = 0end ifnext ioutput d

This (should) output the smallest (i think) decryption key d, where d would validly decrypt the cyphertext (c) into the message (m).

The only problem is, how big will c^d get, in relation to n (since this algorithm uses n sized steps)?

From,
Nice coder

So... i guess this method (finding c^d by using c^d mod n), isn't so good after all. [sad]

From,
Nice coder