The RSA Algorithm

	Sign In Sign-Up

The RSA Algorithm

Encryption

A message in its original form (plaintext) is encrypted into an unintelligent form (ciphertext) by a set of procedures known as an encryption algorithm and a variable, called a key; and the ciphertext is transformed (decrypted ) back into plaintext using the decryption algorithm and a key.

Public-key cryptography

Public-key (or two key) cryptography involves the use of two keys:

A public key, which may be known by anybody, and can be used to encrypt messages, and verify signatures.
Aprivate-key, known only to the recipient, used to decrypt messages, and sign (create) signatures.

Public-key encryption process

The essential steps of public-key encryption process are following:

1. Each end system in a network generates a pair of keys to be used for encryption and decryption of messages that it will receive.
2. Each system publishes its encryption key by placing it in a public register or file. This is the public key. The companion key is kept private.
3. If A wishes to send a message to B, it encrypt the message using B's public key.
4. When B receives the message, B decrypt it using B's private key. No other recipients can decrypt the message because only B knows B's private key.

Application for public key cryptosystems

Encryption/decryption: the sender encrypts a message with the recipient's public key.
Digital signature: the sender signs a message with its private key. Signing is achieved by a cryptographic algorithm applied to the message or to a small block of data that is a function of the message.
Key exchange: two sides cooperate to exchange a session key. Several different approaches are possible, involvig the private key(s) of one or both parties.

RSA

RSA - named after Rivest, Shamir and Adleman, the inventors - was the first public key scheme which was capable of signatures as well as encryption.
It is the easiest to understand as well as the most popular to implement.
RSA obtain its security from the difficulty of factoring large numbers.

RSA algorithm

First choose two large prime numbers, p and q, and find their product, n. n is also called modulus in RSA jargon.
Compute z = (p-1)(q-1)
Next choose a number e, relatively prime to z = (p-1)(q-1) - this is the encryption key.
Finally compute d such that the product of e and d is congruent to 1 mod ((p-1)(q-1)). This is the decryption key.
Now e and n together form the public key, while d and n together form the private key.

Encryption with RSA

To encrypt a palintext message block m, compute C = Me mod n
To decrypt the block, compute M = Cd mod n.

RSA Example

p=3
q=11
n = pxq = 33
z = (p-1)(q-1) = 20
the relative primes to 20 are 1,3,7,9,11,13,17,19
e=3
d3=1 mod 20
d=7
C = Pe (mod n)
P = Cd (mod n)
If P = M(M=19) then C = 193 mod 33 = 28
P = 287 mod 33 = 19.

Security of RSA

Brute force: this involves trying all possible private keys.
Mathematical attacks: there are several approaches, all equivalent in effect to factoring the product of two primes
Timing attacks: these depends on running time of the decryption algorithm

The Factoring Problem

Factor n into its two prime factors. This enables calculation of (n) =(p-1)x(q-1), which, in turn, enables determination of d=e-1(mod (n)).
Determine (n) directly, without first determining p and q. again, this enables determination of d=e-1(mod (n)).
Determined d directly, without first determining (n).