Re: A89: Linux Port for 89/92
[Prev][Next][Index][Thread]
Re: A89: Linux Port for 89/92
Aren't there already programs to find if obscenly large numbers are prime or
not (I know I've run across a couple)? Don't these programs accomplish this
task by attempting to find the factors? Would that be a viable method for
finding the factors to the 512 bit excryption key?
-Dan
>
> > 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: