RSA Alogorithm

The RSA algorithm is an example of asymmetric cryptography, which is widely used in worldwide for securing sensitive while sending insecure medium like the internet.

RSA was first described in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman of the Massachusetts Institute of Technology. Two types of keys are used, public and private. Private is secrete key used by the owner or receiver. Data can be encrypted using a public or private key, but decryption can be done only with the private key.


The RSA algorithm is fully based on mathematical process, steps are followed

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

• Choose two very large (100+ digit) prime numbers. Denote these numbers as p and q.
• Set n equal to p * q.
• Choose any large integer, d, such that GCD(d, ((p-1) * (q-1))) = 1
• Find e such that e * d = 1 (mod ((p-1) * (q-1)))

Example :

Choose p = 7 and q = 13

Compute n = p * q = 7* 13 = 91

Compute φ(n) = (p - 1) * (q - 1) = 6* 12 = 72

Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 11

Compute a value for d such that (d * e) % φ(n) = 1. One solution is d = 7 [(7 * 11) % 72 = 4]

Public key is (e, n) => (11, 91)

Private key is (d, n) => (7, 91)

The encryption of m = 2 is c = 3⁷ % 91 = 37

The decryption of c = 37 is m = 37⁷ % 91 = 2

Advantage

RSA's biggest advantage is that it uses Public Key encryption. This means that your text will be encrypted with someone's Public Key (which everyone knows about). However, only the person it is intended for can read it, by using their private key (which only they know about). Attempting to use the Public Key to decrypt the message would not work. RSA can also be used to "sign" a message, meaning that the recipient can verify that it was sent by the person they think it was sent by.

Disadvantage

In cryptography, the RSA problem summarizes the task of performing an RSA private-key operation given only the public key. The RSA algorithm raises a message to an exponent, modulo a composite number N whose factors are not known. Thus, the task can be neatly described as finding the eth roots of an arbitrary number, modulo N. For large RSA key sizes (in excess of 1024 bits), no efficient method for solving this problem is known; if an efficient method is ever developed, it would threaten the current or eventual security of RSA-based cryptosystems—both for public-key encryption and digital signatures.

The most efficient method known to solve the RSA problem is by first factoring the modulus N. A task believed to be impractical, if N is sufficiently large (see integer factorization). The RSA key setup routine already turns the public exponent e, with this prime factorization, into the private exponent d, and so exactly the same algorithm allows anyone who factors N to obtain the private key. Any C can then be decrypted with the private key.

Next Topic