[ScuzzyTerminator]

In each case the appropriate figure is 2^(B2-B1), where B1 is the number of bits in the smaller key, and B2 is the number of bits in the larger key.

It's actually much less than that. The security of a key against brute force attack is proportional to the number of possible keys, not the size of a key. For RSA keys, most members of the keyspace are not valid keys since RSA keys are based on large prime numbers. An n-bit RSA key is nowhere near as secure as an n-bit conventional cipher key.

[Ichneumon]

It's actually much less than that. The security of a key against brute force attack is proportional to the number of possible keys, not the size of a key. For RSA keys, most members of the keyspace are not valid keys since RSA keys are based on large prime numbers. An n-bit RSA key is nowhere near as secure as an n-bit conventional cipher key.

Ah, good point, thanks for the correction. I was indeed thinking of n-bit conventional keys.

Is the number of valid 516-bit RSA keys known? It would be interesting to figure out how whether it would be feasible to pre-compute all possible keys into a "key dictionary", and then use that to brute-force test encrypted messages.