RSA

 RSA cryptosystem The algorithm of RSA The speed of RSA algorithm Breaking the RSA cryptosystem The current applications of RSA cryptosystem

 RSA cryptosystem The RSA cryptosystem is a public-key cryptosystem. It offers encryption and digital signatures (authentication). It was developed Ronald Rivest, Adi Shamir, and Leonard Adleman  in 1977.The security of the RSA system is based on the hard problem of factoring a large integer.

 The algorithm of RSA In the RSA algorithm, it needs to take two large primes (p and q), then produce n = pq (n is called the modulus). Choose a number, e, which less than n and relatively prime to (p-1)(q-1), which means e and (p-1)(q-1) have no common factors except 1. Find another number d such that (ed - 1) is divisible by (p-1)(q-1). The values e and d are called the public and private exponents respectively. The public key is the pair (n, e); the private key is (n, d). The factors p and q may be destroyed or kept with the private key, because people can break RSA cryptosystem with p and q. It is difficult to find the private key d with the public key (n, e). But if someone could factor the large integer n into p and q, then the private key d will be found. Hence, the security of the RSA system is based on the hard problem of factoring a large integer. Encryption In this case, Alan wants to encrypt a message m and send it to Bobby: Alan creates the ciphertext c: c = me mod n, where e and n are Bobby's public key. Alan sends c to Bob. To decrypt the ciphertext c, Bobby use his private key d to find the plaintext m: m = cd mod n. Since only Bobby knows d, only Bobby can decrypt and read this message. Digital Signature In this case, Alan wants to send a message m to Bobby in such a way that Bobby is assured the message is from Alice: Allan creates a digital signature s that: s = md mod n, where d and n are Alan's private key. Alan sends m and s to Bobby. Bobby, received the message (m) and signature (s), decrypts the signature with Alan's public key (n,e) to recover the message (m), as m = se mod n. Bobby compares the result to the message gets by decrypted the signature (s) and the original message (m). If they are exactly equal, the signature has been successfully verified and Bobby can be sure the message that comes from Alan. If they are not equal, then the message is not originated by Alan or was altered, and he rejects the message.

 The speed of RSA algorithm By comparison, the other block ciphers are much faster than the RSA algorithm. DES is generally at least 100 times as fast in software and between 1,000 and 10,000 times as fast in hardware now.

 Breaking the RSA cryptosystem There are a few possible methods of "breaking'' the RSA cryptosystem. An attacker would discover the private key corresponding to a given public key; this would enable the attacker both to read all messages encrypted  and to make signatures. It needs to factor the public modulus, n, into its two prime factors, p and q. From p, q, and e, the public exponent, the attacker can easily get d, then the attacker will get the private key. The hard part is factoring n; the security of RSA depends on the hard problem of factoring the large integer n. It should be noted that hardware improvements alone will not weaken the RSA cryptosystem, as long as appropriate key lengths are used. Another way to break the RSA cryptosystem is to find a technique to compute eth roots mod n. Since c = me mod n, the eth root of c mod n is the message m. The attacker can recover encrypted messages and make signatures even without finding the private key. This attack is not known to be equivalent to factoring. No general methods are currently known that attempt to break the RSA cryptosystem in this way. However, in special cases where multiple related messages are encrypted with the same small exponent, it may be possible to recover the messages.

 The current applications of RSA cryptosystem The RSA cryptosystem is currently used in a wide variety of products, platforms, and industries around the world. It is found in many commercial software products and is planned to be in many more. In hardware, the RSA algorithm can be found in secure telephones, on ethernet network cards, and on smart cards. In addition, the algorithm is incorporated into all of the major protocols for secure Internet communications, including S/MIME, SSL, and S/WAN. It is also used internally in many institutions, including branches of the U.S. government, major corporations, national laboratories, and universities.