Archived

This topic is now archived and is closed to further replies.

Crispy

prime factors for RSA

Recommended Posts

we have a home assignment to write an RSA encryption/decryption utility (actually this was optional since it's more difficult than the comulsory assignments). I understand the algorithm pretty well, but the one thing I'm confused about right now is factoring: RSA uses as big numbers as possible that need to be factored to primes to find the public and private keys. This is the midproduct: P * Q = S * Phi(R) + 1 where P and Q are the sought primes, Phi(R) is known and S is a random number. How do commercial products go about this? Do they have a set of prefactored numbers or do they resort to brute force and use smaller primes? If they use prefactored numbers, could someone please direct me to some site that offers such things for copy-paste (since I can't seem to be able to find any on my own). In the latter case - do I simply follow the divisibility rules until I'm done or is there some simple method to do that (this is just a home assignment - I don't want to catch up with cryptography A-Z just now). Moreover, how big primes would be OK for a school assignement? I'm thinking < 10 million, but I'm not sure. edit: postulated the problem incorrectly :/ [edited by - crispy on May 1, 2003 1:10:49 PM]

Share this post


Link to post
Share on other sites
Umm... You can't factor primes, that's kind of the point of the RSA algorithm,

The RSA algorithm uses large numbers that factor _into_ 2 and only 2 primes.

Here's a decent paper that discusses prime number generation. http://home.olemiss.edu/~aldunn/postdefensethesis.pdf

Cryptographically secure versions of RSA need 1024 bit primes (give or take a few.)

For a school assignment, I'm sure any old size will be fine as long as the algorithm works right.

[edited by - cheesegrater on May 1, 2003 1:09:50 PM]

Share this post


Link to post
Share on other sites
IIRC, cryptography programs don't create large primes with 100% certanity, because that's as time consuming as decrypting (well not quite, as decrypting needs to find the factors of a number that's roughly N^2, as opposed to N). They do a test that proves some large number is a prime with almost 100% certanity (certain enough for practical purposes). I don't remember how this test was done though, maybe CheeseGrater's link has some info.

[edited by - civguy on May 1, 2003 1:16:33 PM]

Share this post


Link to post
Share on other sites
My bad - I know you can't really factor primes - that's why they're called primes. Guess I'm a little tired. Anyway - I fixed the original post.

[edited by - crispy on May 1, 2003 1:16:33 PM]

Share this post


Link to post
Share on other sites