RSA Attack
Ok, i've been doing a little (lot) of thinking lately.
This is what i've been thinking about.
Ci^D mod n = Mi
Ci^D = Mi + XiN
D = log(Mi + xiN) / log(ci)
Now we have multiple i, multiple c, and multiple m. There are also multiple unknowns (x's) and one static unknown (d). It should be possible to recover d using that information.
We also know e, and that
DE is divisible by (p-1)(q-1)
So, D should be divisible by ((p-1)(q-1)) / E
and that
Ci^D is equal to N mod N.
For ALL C
There is a relationship. its just hard to find.
Ok, thought.
Find two c's so that log(ci) is = 2(log(cj))
That then means that the log of Mj + xjN must half the value log mi + xiN.
Are these ok, interesting, or have i gone insane [grin]?
From,
Nice coder
[Edited by - Nice Coder on December 2, 2004 5:31:48 AM]
Quote:Original post by Nice Coder
Find two c's so that log(ci) is = 2(log(cj))
That then means that the log of Mj + xjN must half the value log mi + xiM + xNn.
log(ci)=2*log(cj)
==> ci=cj^2
Winograd:
Thanks for that.
Does that mean that mj + xjn is the sqr of mi + xin (lousy typos...)
From,
Nice coder
Thanks for that.
Does that mean that mj + xjn is the sqr of mi + xin (lousy typos...)
From,
Nice coder
I just read this over quickly, because I'm in a hurry, but it seems what you did was reduce the problem down to a log function.
The problem is now, you have to calculate the log of that mercilessly giant number :) Which means that you've substituted one nearly impossible problem for another.
Granted, that's the way mathematics works. Gotta keep trying new stuff.
The problem is now, you have to calculate the log of that mercilessly giant number :) Which means that you've substituted one nearly impossible problem for another.
Granted, that's the way mathematics works. Gotta keep trying new stuff.
Ok. (ther post got eaten... GRRR)
How exactly are logorithms calculated? What is the fastest way?
log(Mi + xiN) / log(ci) = log(Mj + yjN) / log(cj)
Ok, so
(Log(mi + xi) + log(n)) / log(ci) = (log(mj + yj) + log(n)) / log(cj)
So now
log(mi + xi) / log(ci) + log(n) / log(ci) = log(mj + yj) / log(cj) + log(n) / log(cj)
Ok ,lets do a few things
first
A = log(n) / log(ci) and
B = log(n) / log(cj)
Both a and b are known. (because we have the c's and n).
So now
Log(mi + xi) / log(ci) + A = log(mj + yj) / log(cj) + B
ok, we have two unknown (x & y) in this. But they are ralated.
ok, this is for two numbers, ci and cj. we can make as many numbers as wer need to.
Now, this problem is getting simpler and harder (from my pov).
X & y have been taken away form n.(simpler for bruteforcing), but its harder (lots of logs AHHH! I need to know more about them...).
How could i seperate log(mi + xi)?
Edit:
Ok, logs are good, logs are great.
When log(z) goes up 1, z gets 10
For eg. the log of a 64 bit number is about 44. and log(2^80) is 55. so, it should be simple to work these out. (i don't know about the log of 2^1024 tho...)
The log of 2^512 is only about 354. so [grin].
Perhaps a guess, check and refine method would work?
Guess some x, form that, use the equasion to find y. if y isn't an integer, find another x.
if it is,
Calculate C^D (Value of either side of equasion)
Z = C^D - M (for message/cyphertext combo)
Z = Z / N
You then use that Z for another X. Keep working until you've found an answer that works.
Is this method pretty good?
How can it be improved?
From,
Nice coder
[Edited by - Nice Coder on December 2, 2004 11:19:39 PM]
How exactly are logorithms calculated? What is the fastest way?
log(Mi + xiN) / log(ci) = log(Mj + yjN) / log(cj)
Ok, so
(Log(mi + xi) + log(n)) / log(ci) = (log(mj + yj) + log(n)) / log(cj)
So now
log(mi + xi) / log(ci) + log(n) / log(ci) = log(mj + yj) / log(cj) + log(n) / log(cj)
Ok ,lets do a few things
first
A = log(n) / log(ci) and
B = log(n) / log(cj)
Both a and b are known. (because we have the c's and n).
So now
Log(mi + xi) / log(ci) + A = log(mj + yj) / log(cj) + B
ok, we have two unknown (x & y) in this. But they are ralated.
ok, this is for two numbers, ci and cj. we can make as many numbers as wer need to.
Now, this problem is getting simpler and harder (from my pov).
X & y have been taken away form n.(simpler for bruteforcing), but its harder (lots of logs AHHH! I need to know more about them...).
How could i seperate log(mi + xi)?
Edit:
Ok, logs are good, logs are great.
When log(z) goes up 1, z gets 10
For eg. the log of a 64 bit number is about 44. and log(2^80) is 55. so, it should be simple to work these out. (i don't know about the log of 2^1024 tho...)
The log of 2^512 is only about 354. so [grin].
Perhaps a guess, check and refine method would work?
Guess some x, form that, use the equasion to find y. if y isn't an integer, find another x.
if it is,
Calculate C^D (Value of either side of equasion)
Z = C^D - M (for message/cyphertext combo)
Z = Z / N
You then use that Z for another X. Keep working until you've found an answer that works.
Is this method pretty good?
How can it be improved?
From,
Nice coder
[Edited by - Nice Coder on December 2, 2004 11:19:39 PM]
As far as I remember, both problems (RSA reversing and discrete log) are equivalently hard, as already stated.
Quote:Original post by Charles B
As far as I remember, both problems (RSA reversing and discrete log) are equivalently hard, as already stated.
Now, don't quote me on this, but the discrete log is an even harder problem than rsa reversal. That's why ElGamal and the newer discrete log algorithms work well.
I'm trying to reverse rsa to get the message out of a given cyphertext. (for when you can't just go an do a table lookup of the values, ie. when there encrypting 64 or 128 bits at once.)
Ok, i seem to get what the descrete logorithm is, but i don't see how it effects this. What i read
Ok.
Log(mi + xi) / log(ci) + A = log(mj + yj) / log(cj) + B
So, if i have x, and i want y, how would i go about it?
i know log(mi + xi) and log(ci) and A.
As well as log(cj) and b
So, would
yj = 10^((D - b) * log(cj)) - mj
bw ok?
Where D is the value of the rhs (once we guessed xi). (which is D, the decryption key.)
?
So, for any x, we can find the decryption key, by finding some integer value of yj, for all j.
I think...
From,
Nice coder
Ok, i seem to get what the descrete logorithm is, but i don't see how it effects this. What i read
Ok.
Log(mi + xi) / log(ci) + A = log(mj + yj) / log(cj) + B
So, if i have x, and i want y, how would i go about it?
i know log(mi + xi) and log(ci) and A.
As well as log(cj) and b
So, would
yj = 10^((D - b) * log(cj)) - mj
bw ok?
Where D is the value of the rhs (once we guessed xi). (which is D, the decryption key.)
?
So, for any x, we can find the decryption key, by finding some integer value of yj, for all j.
I think...
From,
Nice coder
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement