3 ms·
RSA keys aren't just random strings (unlike symmetric keys, which are short random strings, generally 128 or 256 bits now). You start with two random primes.
by rdl 13y ago
RSA keys aren't just random strings (unlike symmetric keys, which are short random strings, generally 128 or 256 bits now).
You start with two random primes. Generally to generate these what you do is pick a range of numbers in the right size, then test the odd ones with a prime sieve (vs small primes), then do probabilistic primality test on the winners. This doesn't need 4096 bits of randomness.
Once you have the primes, you don't need any more random numbers to generate the key; it's purely deterministic calculation at that point.
- vilda 13y agoTo add: not only you test for primality, but also for common attacks. Not all primes are equally strong http://www.uow.edu.au/~jennie/WEB/WEB99/1999_07.pdf http://www.uow.edu.au/~jennie/WEB/WEB99/1999_07.pdf
- rdl 13y agoPlus technically e could be random (PGP used to do this, now ~everyone uses a fixed value as far as I know).
- pbsd 13y agoFor primes of current acceptable size (>= 1024 bits), you might as well drop those extra checks. The elliptic curve method gives you around 2^512 attempts at doing the exact same thing, each one with the same probability of having a smooth p-1 or p+1. The paper you link to reaches essentially the same conclusion.