Rsa Cryptosystem

RSA is one of the first practical public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and differs from the decryption key which is kept secret. In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem. RSA is made of the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1977. Clifford Cocks, an English mathematician working for the UK intelligence agency GCHQ, had developed an equivalent system in 1973, but it was not declassified until 1997.

A user of RSA creates and then publishes a public key based on two large prime numbers, along with an auxiliary value. The prime numbers must be kept secret. Anyone can use the public key to encrypt a message, but with currently published methods, if the public key is large enough, only someone with knowledge of the prime numbers can feasibly decode the message. Breaking RSA encryption is known as the RSA problem; whether it is as hard as the factoring problem remains an open question.

RSA is a relatively slow algorithm, and because of this it is less commonly used to directly encrypt user data. More often, RSA passes encrypted shared keys for symmetric key cryptography which in turn can perform bulk encryption-decryption operations at much higher speed.

The idea of an asymmetric public-private key cryptosystem is attributed to Whitfield Diffie and Martin Hellman, who published the concept in 1976. They also introduced digital signatures and attempted to apply number theory; their formulation used a shared secret key created from exponentiation of some number, modulo a prime number. However, they left open the problem of realizing a one-way function, possibly because the difficulty of factoring was not well studied at the time.

Ron Rivest, Adi Shamir, and Leonard Adleman at MIT made several attempts over the course of a year to create a one-way function that is hard to invert. They tried many approaches including "knapsack-based" and "permutation polynomials". For a time they thought it was impossible for what they wanted to achieve due to contradictory requirements. In April 1977, they spent Passover at the house of a student and drank a good deal of Manischewitz wine before returning to their home at around midnight. Rivest, unable to sleep, lay on the couch with a math textbook and started thinking about their one-way function. He spent the rest of the night formalizing his idea and had much of the paper ready by daybreak. The algorithm is now known as RSA – the initials of their surnames in same order as their paper.

Clifford Cocks, an English mathematician who worked for the UK intelligence agency GCHQ, described an equivalent system in an internal document in 1973. However, given the relatively expensive computers needed to implement it at the time, it was mostly considered a curiosity and, as far as is publicly known, was never deployed. His discovery, however, was not revealed until 1997 due to its top-secret classification.

Ex. 10. Make a presentation on one of the following topics:

History of cryptography: ancient times

History of cryptography: modern times

Steganography as a field of cryptography

Rotor cipher machines in the Second World War

RSA cryptosystem: the history of creation

The most known cryptosystems of nowadays

Presentation requirements: format – MS Power Point, number of slides – from 10 to 15, animation (optional, but recommended), presentation plan – from 5 to 10 points, performance time from 5 to 7 minutes.

Unit 7

Ex.1. Read and translate the text: