Security Notes for Public-key Algorithms

Any of these algorithms can be trivially broken; for example, RSA can be broken by factoring the modulus n into its two prime factors. This is easily done by the following code:

for i in range(2, n): 
    if (n%i)==0: 
        print i, 'is a factor' 
        break

However, n is usually a few hundred bits long, so this simple program wouldn't find a solution before the universe comes to an end. Smarter algorithms can factor numbers more quickly, but it's still possible to choose keys so large that they can't be broken in a reasonable amount of time. For ElGamal and DSA, discrete logarithms are used instead of factoring, but the principle is the same.

Safe key sizes depend on the current state of number theory and computer technology. At the moment, one can roughly define three levels of security: low-security commercial, high-security commercial, and military-grade. For RSA, these three levels correspond roughly to 768, 1024, and 2048-bit keys.