RSA Cryptography

An important reason that public key encryption is so much slower than shared key encryption is that RSA public key asymmetric encryption/decryption is based on the mathematics of modular exponentiation . In simple terms, this means that this algorithm takes each input value, raises it to a power (requiring a large number of multiplications), and then performs the modulo operation (a form of division). On the other hand, shared key symmetric algorithms are based on much faster logical operations on bit arrays. On average, public-private key operations are 13 times slower than symmetric key operations. Furthermore, the private key has a much larger exponent than the public key, so private key operations take substantially longer in asymmetric encryption than do public key operations. In confidentiality applications (that is, message encryption) where the public key is used for encryption, decryption takes substantially longer than encryption. In integrity applications (that is, integrity as in digital signature) where the private key is used for encryption, it is the other way around. This imbalance would be a problem when applied to large messages, but it is not an issue when applied only to small messages such as the 200-bit symmetric encryption key when this algorithm is used for key transport.

Choosing RSA Key Pairs

The RSA algorithm for choosing key pairs is as follows :

1. Choose two large prime numbers , p and q , of equal length. Now compute the product:

   n = p * q

   n will be the modulus used later.

2. Choose two more numbers: the public exponent e and the private exponent d .

   Choose e to be less than n and relatively prime to ( p “ 1) * ( q “ 1). This means that ( p “ 1) and ( q “ 1) and e have no common factors other than 1.

   Choose d such that ( e * d “ 1) is divisible by ( p “ 1) ( q “ 1). In other words,

   e * d = 1 mod ( p “ 1) * ( q “ 1)

   which means after you choose e , you know d to be

   d = e ^“1 mod (( p “ 1) * ( q “ 1))

The two key values so produced are actually each a pair of values:

public key = ( n, e )

private key = ( n, d )

Padding

The input to RSA encryption operations is interpreted as a number, so special padding is required to make the input totally consistent. The total length of the data must be a multiple of the modulus size , and the data must be numerically less than the modulus. A 1,024-bit RSA key has a 128-byte modulus. Therefore, data must be encrypted in blocks of 128 bytes. Each input number must be padded with zeros until its numerical value is less than that of the modulus. XML Encryption specifies the use of PKCS#1 Block 02 padding. This padding places a critical restriction on the size of data that RSA can encrypt. This is why RSA is never used to encrypt the entire plaintext message but encrypts only the shared key being exchanged between communicating parties or the fixed-size message digest in digital signature.

RSA Encryption

The intended recipient's public key is used for message encryption. As stated previously, you must divide the message m into numerical blocks smaller than the modulus n . So if p and q are 100-digit primes, then n will be less than 200 digits, which will be the upper limit for message blocks to be encrypted. This upper limit works well for sending encrypted shared keys because they will fit into this block size limitation. The encryption formula to take an input plaintext message block m and create an output ciphertext message block c is then as follows:

c = m ^e mod n

RSA Decryption

The recipient uses his or her private key for decryption. Decryption takes each encrypted block c and computes

m = c ^d mod n

to create a plaintext message block m .

The number theory behind this algorithm proves that it does not matter which key you use first; its pair used in the corresponding formula will reverse the initial operation. This is great because it means you can use the sender's private key to encrypt when you want to prove identity and non- repudiation to anyone with the sender's public key, and you can use the recipient's public key to encrypt when you want to prove confidentiality to the only one recipient who possesses the matching private key.