Re: A89: Linux Port for 89/92
[Prev][Next][Index][Thread]
Re: A89: Linux Port for 89/92
> Well, if you know n, then finding p and q is easy, as they are the only
> factors of n.
It is not easy, that's the idea in the algorithm. Factoring large
numbers is *very* hard.
> I know this because it is stated on the RSA site that both p
> and q are prime numbers, and a prime multiplied with another prime will give
> you a number that has only those two primes as factors.
No, you know that because this comes from the definition of prime
numbers and the rules of multiplication :-)
Well, if you have p and q then the rest is easy, especially for you
know either e or d.
> It wouldn't be a major waste of time if I found more than 3 factors (meaning
> that there was a typo) or if one of the factors was less than 2^128 as you
> say.
Usually they choose the numbers in the same league, that is, for an
500 bit n you would have p and q in the 250-bit ballpark.
> Factoring this way might be slow, yes, but I do not have the math knowledge
> to use such algorithms that the RSA site suggests. I do not know a single
Brute force factoring (dividing the result, that is, n with primes)
might take a very very long time indeed. Assuming that you have all
primes up to 250 bits stored in a media, so you don't waste time by
generating them. We know that around a large x every ln(x) -th
randomly chosen number is a prime, so you have to deal with about:
2^250 ~= 10^80 and ln(10^80) ~= 184 => 10^77 numbers. Mind you,
storing them would be a major headache. Now if you have a rather
quick computer which does an 500-bit divisin in every nanosec and
you are lucky and you have to search 1/10 of all the numbers, then
you'd need about 3*10^59 years. Since the Universe is only about
16*10^9 years old yet ...
The various number theory tricks which you can find around would
decrease your computational need drastically. If you send email to
challenge-results@rsa.com, it will send you the results of their
factoring challenge which is about factoring numbers between 300 and
1500 bits long.
Unless the number-theory mathematicians come up with something,
or an NP-complete problem suddenly turns out being in P, factoring
large numbers remains pratically untractable if you have a large
enough number. 512 bit is not that hard these days but only if you can
get hold of a loose network of computers and you use one of the
leading edge methods to factor n. Naive approaches will not lead you
anywhere.
May I suggest the book 'Applied Cryptography' by Bruce Schneier,
ISBN 0-471-11709-9 which is a very thorough book on all sorts of
cryptographic techniques, from primitive cyphers through DES and
primes up to the quantum physical untapable communication links and
using DNA to solve NP problems.
It also gives the necessary math background assuming only basic
knowledge. Wired Magazine wrote about it: "The book the National
Security Agency wanted never to be published..."
> person who has spoken about doing anything near eliptic curves and such that
> are required for those high-level algorithms.
>
> Math comes very easy to me, but I do not consider myself a 'math wiz'
> either...
The above mentioned book gives you a very good introduction to number
theory and other cryptography-related maths. It also contains C code
for various cyphers, lots of algorithms, methonds and all what you
want to know about encoding, decoding and breaking things :-)
Regards,
Zoltan
Follow-Ups:
References: