Cryptography: RSA Algorithm

The Issue of Privacy

The growth of the Internet and electronic commerce have brought to the forefront the issue of privacy in electronic communication. Larges volumes of personal and sensitive information are electronically transmitted and stored every day. What guarantees does one have that a message sent to another person is not intercepted and read without their knowledge or consent? Tools to ensure the privacy and confidentiality of paper-based communication have existed for a long time[1]. Similar tools exist in the electronic communications arena.

Encryption is the standard method for making a communication private. Anyone wanting to send a private message to another user encrypts (enciphers) the message before transmitting it. Only the intended recipient knows how to correctly decrypt (decipher) the message. Anyone who was "eavesdropping" on the communication would only see the encrypted message. Because they would not know how to decrypt it successfully, the message would make no sense to them. As such, privacy can be ensured in electronic communication.

Definitions

The following definitions are provided in Advanced Concepts in Operating Systems[2]:
Plaintext(Cleartext)
The intelligible message which will be converted into an unintelligible (encrypted) message
Ciphertext
A message in encrypted form
Encryption
The process of converting a plaintext message into a ciphertext message
Decryption
The process of converting a ciphertext message into a plaintext message
Key
A parameter used in the encryption and decryption process.
Cryptosystem
A system to encrypt and decrypt information
Symmetric Cryptosystem
A cryptosystem that uses the same key to encrypt and decrypt information
Asymmetric Cryptosystem
A cryptosystem that uses one key to encrypt and a different key to decrypt
Cryptography
The use of cryptosystems to maintain the confidentiality of information
Cryptoanalysis
The study of breaking cryptosystems

Overview of Encryption and Public-Key Cryptosystems

Modern cryptosystems are typically classified as either public-key or private-key. Private-key encryption methods, such as the Data Encryption Standard(DES), use the same key to both encrypt and decrypt data. The key must be known only to the parties who are authorized to encrypt and decrypt a particular message. Public-key cryptosystems, on the other hand, use different keys to encrypt and decrypt data. The public-key is globally available. The private-key is kept confidential.

The Key Distribution Problem

Private-key systems suffer from the key distribution problem. In order for a secure communication to occur, the key must first be securely sent to the other party. An unsecure channel such as a data network can not be used. Couriers or other secure means are typically used. Public-key systems do not suffer from this problem because of their use of two different keys. Messages are encrypted with a public key and decrypted with a private key. No keys need to be distributed for a secure communication to occur.

Public-Key Cryptosystems

A user wishing to exchange encrypted messages using a public-key cryptosystem would place their public encryption procedure, E, in a public file. The user's corresponding decryption procedure, D, is kept confidential. Rivest, Shamir, and Adleman provide four properties that the encryption and decryption procedures have[3]:
  1. Deciphering the enciphered form of a message M yields M. That is, D(E(M)) = M
  2. E and D are easy to compute.
  3. Publicly revealing E does not reveal an easy way to compute D. As such, only the user can decrypt messages which were encrypted with E. Likewise, only the user can compute D efficiently.
  4. Deciphering a message M and then enciphering it results in M. That is, E(D(M)) = M
As Rivest, Shamir, and Adleman point out, if a procedure satisfying property (3) is used, it is extremely impractical for another user to try to decipher the message by trying all possible messages until they find one such that E(M) = C.

A function satisfying properties (1) - (3) is called a "trap-door one-way function". It is called "one-way" because it is easy to compute in one direction but not the other. It is called "trap-door" because the inverse functions are easy to compute once certain private, "trap-door" information is known.

The Public-Key Cryptosystem Encryption and Decryption Process

Suppose user A wants to send a private message, M, to user B.

Digital Signatures

Property (4) of public-key cryptosystems allows a user to digitally "sign" a message they send. This digital signature provides proof that the message originated from the designated sender. In order to be effective, digital signature need to be both message-dependent as well as signer-dependent. This would prevent electronic "cutting and pasting" as well as modification of the original message by the recipient.

Suppose user A wanted to send a "digitally-signed" message, M, to user B:

User B cannot alter the original message or use the signature with any other message. To do so would require user B to know how to decrypt a message using A's decryption procedure.

The RSA Algorithm

The Rivest-Shamir-Adleman (RSA) algorithm is one of the most popular and secure public-key encryption methods. The algorithm capitalizes on the fact that there is no efficient way to factor very large (100-200 digit) numbers.

Using an encryption key (e,n), the algorithm is as follows:

  1. Represent the message as an integer between 0 and (n-1). Large messages can be broken up into a number of blocks. Each block would then be represented by an integer in the same range.
  2. Encrypt the message by raising it to the eth power modulo n. The result is a ciphertext message C.
  3. To decrypt ciphertext message C, raise it to another power d modulo n
The encryption key (e,n) is made public. The decryption key (d,n) is kept private by the user.

How to Determine Appropriate Values for e, d, and n

  1. Choose two very large (100+ digit) prime numbers. Denote these numbers as p and q.
  2. Set n equal to p * q.
  3. Choose any large integer, d, such that GCD(d, ((p-1) * (q-1))) = 1
  4. Find e such that e * d = 1 (mod ((p-1) * (q-1)))
Rivest, Shamir, and Adleman provide efficient algorithms for each required operation[4].

How secure is a communication using RSA?

Cryptographic methods cannot be proven secure. Instead, the only test is to see if someone can figure out how to decipher a message without having direct knowledge of the decryption key. The RSA method's security rests on the fact that it is extremely difficult to factor very large numbers. If 100 digit numbers are used for p and q, the resulting n will be approximately 200 digits. The fastest known factoring algorithm would take far too long for an attacker to ever break the code. Other methods for determining d without factoring n are equally as difficult.

Any cryptographic technique which can resist a concerted attack is regarded as secure. At this point in time, the RSA algorithm is considered secure.

Links to Other RSA Information

RSA Data Security Home Page

References

  1. Bidzos, Jim, "Threats to Privacy and Public Keys for Protection", COMPCON Spring '91 Digest of Papers, IEEE Computer Society Press, p. 189-94
  2. Singhal, Mukesh and Shivaratri, Niranjan G., Advanced Concepts in Operating Systems, McGraw-Hill, p. 405
  3. Rivest, R.L., Shamir, A., and Adleman, L., "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM, Vol 21, No. 2, February 1978, p. 120-26
  4. Rivest et. al.