There are several ways to have a short key size.
1. With RSA
The RSA public key consists of a large number n (a “module”) and a (usually small) number e (a public indicator). e can be like 3, but in a private setting (where you control key generation) you can force to use regular e, the same for everyone. The typical size for n is 1024 bits (i.e. 128 bytes).
n is the product of two primes (n = p * q). Knowing p and q is enough to rebuild the private key (nominally d, which is multiplicative, inverting e modulo p-1 and q-1). Assuming n is known, it is enough to know only p (if you know n and p, you can calculate q using simple division). For proper protection, p and q must be the same size, so even if you take the smaller one, you still need to store about 512 bits or so - it's 64 bytes).
It was also suggested to choose a small d ("private exponent"). But this makes e substantially random, hence large; you can no longer use the usual small value for e. This basically doubles the size of the public key. Also, forcing a small d can make the key weak (it has been shown that d does not exceed 29% of size n, but this in no way proves that declaring 30% size n is safe). This is usually considered a bad idea.
2. With DSA / Diffie-Hellman
DSA is a digital signature algorithm. Diffie-Hellman is a key exchange algorithm. Both are "asymmetric cryptographic algorithms" and you will use one or the other, or both, depending on your needs. In both cases, there is a generally accessible mathematical group (numbers modulo a large prime number p for basic DSA and DH, variants of an elliptic curve use an elliptic curve as a group); the public key is an element of the group, and the private key is the discrete logarithm of this element relative to a conventional generator. In other words, given a prime p and a number g modulo p (they can be shared by all key holders, even); the private key is the number x corresponding to the public key y = g x mod p. The private key is selected modulo small prime q. q is known and must be large enough to defeat the general discrete logarithm algorithms; in practice, we want 160-bit or more q.
This means that the private key holds about 20 bytes. These are not 20 decimal digits, but closer.
3. With ANY cryptographic algorithm
When you create a key pair, you do this with:
- deterministic procedure;
- source of random bits.
For example, using RSA, you create p and q, creating random odd numbers of the correct size and cyclically until a prime number is found. For a given random source, the whole process is deterministic: with the same random bits, it will find the same primes p and q.
Therefore, you can develop a PRNG sown with the secret key K and use it as a random source for the key generation process. Whenever you need a secret key, you start the key generation process again, using K as an input. And voila! Your private key that you need to save is now K.
With RSA, this makes using a private key quite expensive (generating RSA keys is not easy). However, with DSA / Diffie-Hellman this would be very inexpensive: a private key is only a random number modulo q (group order), which can be generated at a much lower cost than using a private key for digital signing or asymmetric key exchange.
This leads to the following procedure:
- The "private key" as stored is K.
- Group parameters for DSA / Diffie-Hellman are hard-coded in the application; everyone uses the same group, and this is not a problem. The group order is q, a known number of at least 160 bits. If you use a variant of an elliptic curve, then q is a property of the curve, therefore, given.
- When you need to sign or perform a key exchange (key exchange is used to emulate asymmetric encryption), you calculate SHA-512 (K), which gives a 512-bit sequence. You take the first half (256 bits), interpret it as a number (with an agreement with a high or medium level, if you wish, provided that you always use the same agreement) and reduce it modulo q to get a private DSA key. Likewise, you use the other half of the SHA-512 output to get the DH private key.
The key generation is very weakly biased, but this does not mean a big security problem. Note that if you need a DSA key and a DH key, you can use the same group, but you should not use the same private key (therefore, using both halves of the SHA-512 output).
How big should K be? Using a hash function such as SHA-512, K can be any arbitrary sequence of bits. However, K must be wide enough to defeat an exhaustive search. A 1024-bit RSA key or a 1024-bit DSA module (p module for DSA) provides a level of security that is very roughly equivalent to an 80-bit symmetric key. Similarly, the 160-bit group order for DSA / DH provides the same level. 80 bits is not so much; you cannot go below if you want to be taken seriously. This means that K should be selected from the space of at least 2 80 possible keys; in other words, if K is chosen as uniformly random bytes, then it must be at least 10 bytes. With decimal digits you need at least 24 digits. Anything below this is essentially weak and inevitable.
Standard warning: if any of the above is not obvious or crystal clear for you, then do not even think about implementing it. The implementation of the cryptographic algorithm is complicated, especially since the most deadly errors cannot be tested (this is not because the program works and works normally, because it does not contain security flaws).