Asymmetric cryptographic algorithms

In 1976, Whitfield Diffie and Martin E. Hellman described the idea of developing an encryption algorithm based on two different keys [Diffie 76]. One of these keys was to be public, the other secret or ‘private’. This would allow persons to encrypt a message using the public key, with only the owner of the private key being able to decrypt it. This in turn would eliminate the problems associated with exchanging and distributing secret symmetric keys. In addition, it would for the first time make certain other processes possible, such as generating digital signatures that can be verified by everyone.

The RSA algorithm

Two years later, Ronald L. Rivest, Adi Shamir and Leonard Adleman presented an algorithm that met the above-mentioned criteria [Rivest 78]. This algorithm, which is called the RSA algorithm after the initials of its inventors, is the best-known and most versatile asymmetric encryption algorithm presently in use. Its very simple operating principle is based on the arithmetic of large integers. The two keys are generated from two large prime numbers. The encryption and decryption processes can be expressed mathematically as follows:

encryption: y = xe mod n

decryption: x = yd mod n

where x = plaintext

y = ciphertext

e = public key

d = private key

n = public modulus = p · q

p, q = secret prime numbers

Before being encoded, the plaintext block must be padded to the appropriate block size, which varies in the RSA algorithm according to the length of the key used. Encryption itself is performed by exponentiation of the plaintext followed by a modulo operation. The result of this process is the ciphertext. This can only be decoded if the private key is known. The decryption process is analogous to the encryption process. The security of the algorithm is thus based on the difficulty of factoring large numbers. It is quite easy to compute the public modulus from the two prime numbers by multiplication, but it is very difficult to decompose the modulus into its two prime factors, since there is no effective algorithm for this operation. The RAM capacity of smart cards is not sufficient for performing exponential operations on large numbers as required for encryption and decryption, since the numbers become very large before being subjected to the modulo operation. For this reason, modular exponentiation is used, which means that the intermediate result of the calculation never exceeds the value of the modulus. For example, if the value of x2 mod n must be calculated, the expression (x·x) mod n is not evaluated directly, since the intermediate result (x · x) would be excessively large before being reduced by the modulo operation. Instead, the expression ((x mod n) · (x mod n)) mod n is evaluated, which yields the same mathematical result. The advantage of this is that it requires significantly fewer calculations and less memory, since the intermediate results are immediately reduced in size. Anadditionalway to increase the speed of theRSAalgorithm is to use the Chinese remainder theorem for the calculations.7 Of course, a prerequisite for using the Chinese remainder theorem is that both of the secret prime numbers p and q are known, which means that it can only be used for decryption (which means for signing).

The private key should be as long as possible, since this impedes attempts to break the code. Public and private keys may have different lengths, and in fact this is usually the case, since the time required to verify a digital signature can be considerably reduced by making the public key as short as possible. The fourth Fermat number is frequently used as a public key. This prime number has the value of 216 + 1 = 65537, and due to its small size it is very well suited to quickly verifying digital signatures. The numbers 7 and 17 are likewise used. If an attacker succeeds in factoring the public modulus into its two prime components, he could then reproduce the entire encryption process. With a small value, such as 33, it is easy to factor the modulus, but there is presently no fast algorithm that can be used to factor large numbers. If the values of both prime factors can be found, the system is thereby broken, since the private key is then known. Consequently, a requirement for RSA keys is that they are sufficiently long. A length of

512 bits (64 bytes) is presently considered to be the lower limit. In any case, keys with a length of 768 bits (96 bytes) and 1024 bits (128 bytes) are presently used. In the coming years, the first 2048-bit (256-byte) key will come into use. The amount of computational effort needed for encryption and decryption increases with the key length. This increase is not linear, but instead approximately exponential. Smart card microcontrollers, with their 8-bit CPUs, are normally not capable of performing an RSA computation in less than a few minutes. However, there are now microcontrollers with arithmetic coprocessors that have been specially developed for fast exponentiation.With such coprocessors, it is possible to perform RSA computations in an acceptable length of time with reasonable software overhead. The size of the code for a hardware-supported 512-bit RSA algorithm is around 300 bytes. Around 1 kB of assembler code in the smart card is needed for 768-bit and 1024-bit keys. As can be seen from Table 4.12, even with a 512-bit key the number of possible prime numbers is so large that collisions between two different key pairs will never occur.

However, one of the strengths of the RSA algorithm is that it is not limited to a particular key length, in contrast to algorithms such as DES. If increased security is needed, longer keys can be used without modifying the algorithm. The RSA algorithm is thus scaleable. However, computation time and amount of memory space needed must be kept in mind, since even 768-bit keys are presently still considered to be secure. With current factoring algorithms, a good rule of thumb is that increasing the key length by 15 bits doubles the effort of computing the factors.10 Andrew Odlyzko [Odlyzko 95] provides an excellent summary of the internationally available and required processing capacity for factoring integers. Although the RSA algorithm is very secure, it is rarely used to encrypt data, due to its long computation time. It is primarily used in the realm of digital signatures, where the benefits of an asymmetric procedure can be fully realized. The greatest drawback of the RSA algorithm with regard to smart cards is the amount of memory space required for the key. The complexity of the key generation process also causes problems in certain cases. Widespread use of the RSA algorithm is restricted by patent claims that have been made in several countries and by major import and export restrictions imposed on equipment that employs this algorithm. Smart cards with RSA coprocessors fall under these restrictions, which considerably hinders their use internationally.