What is the RSA algorithm (Rivest-Shamir-Adleman)?

The RSA algorithm (Rivest-Shamir-Adleman) is the basis of a cryptosystem -- a suite of

cryptographic algorithms that are used for specific security services or purposes -- which enables
public key encryption and is widely used to secure sensitive data, particularly when it is being sent
over an insecure network such as the internet.
RSA was first publicly described in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman of the
Massachusetts Institute of Technology, though the 1973 creation of a public key algorithm by
British mathematician Clifford Cocks was kept classified by the U.K.'s GCHQ until 1997.
Public key cryptography, also known as asymmetric cryptography, uses two different but
mathematically linked keys -- one public and one private. The public key can be shared with
everyone, whereas the private key must be kept secret.
In RSA cryptography, both the public and the private keys can encrypt a message. The opposite key
from the one used to encrypt a message is used to decrypt it. This attribute is one reason why RSA
has become the most widely used asymmetric algorithm: It provides a method to assure the
confidentiality, integrity, authenticity, and non-repudiation of electronic communications and data
storage.
Many protocols, including Secure Shell (SSH), OpenPGP, S/MIME, and SSL/TLS, rely on RSA for
encryption and digital signature functions. It is also used in software programs -- browsers are an
obvious example, as they need to establish a secure connection over an insecure network, like the
internet, or validate a digital signature. RSA signature verification is one of the most commonly
performed operations in network-connected systems.
Advantages of RSA
• It is very easy to implement RSA algorithm.
• RSA algorithm is safe and secure for transmitting confidential data.
• Cracking RSA algorithm is very difficult as it involves complex mathematics.
• Sharing public key to users is easy.

Disdvantages of Algorithms:

• Alogorithms is Time consuming.

• Difficult to show Branching and Looping in Algorithms.
• Big tasks are difficult to put in Algorithms.

Why is the RSA algorithm used?

RSA derives its security from the difficulty of factoring large integers that are the product of two
large prime numbers. Multiplying these two numbers is easy, but determining the original prime
numbers from the total -- or factoring -- is considered infeasible due to the time it would take using
even today's supercomputers.
The public and private key generation algorithm is the most complex part of RSA cryptography.
Two large prime numbers, p and q, are generated using the Rabin-Miller primality test algorithm. A
modulus, n, is calculated by multiplying p and q. This number is used by both the public and private
keys and provides the link between them. Its length, usually expressed in bits, is called the key
length.
The public key consists of the modulus n and a public exponent, e, which is normally set at 65537,
as it's a prime number that is not too large. The e figure doesn't have to be a secretly selected prime
number, as the public key is shared with everyone.
The private key consists of the modulus n and the private exponent d, which is calculated using the
Extended Euclidean algorithm to find the multiplicative inverse with respect to the totient of n.

What are two applications of RSA algorithm?

The RSA algorithm is widely used and has been applied in various scenarios, including secure
cloud computing environments and wireless networking. It is the most widely used asymmetric
crypto system in the world and is used for securing communication in various domains, from
cellphone communication to online banking.

How does the RSA algorithm work?

Alice generates her RSA keys by selecting two primes: p=11 and q=13. The modulus is n=p×q=143.
The totient is n ϕ(n)=(p−1)x(q−1)=120. She chooses 7 for her RSA public key e and calculates her
RSA private key using the Extended Euclidean algorithm, which gives her 103.
Bob wants to send Alice an encrypted message, M, so he obtains her RSA public key (n, e) which,
in this example, is (143, 7). His plaintext message is just the number 9 and is encrypted into
ciphertext, C, as follows:

Me mod n = 97 mod 143 = 48 = C

When Alice receives Bob's message, she decrypts it by using her RSA private key (d, n) as follows:

Cd mod n = 48103 mod 143 = 9 = M

To use RSA keys to digitally sign a message, Alice would need to create a hash -- a message digest
of her message to Bob -- encrypt the hash value with her RSA private key, and add the key to the
message. Bob can then verify that the message has been sent by Alice and has not been altered by
decrypting the hash value with her public key. If this value matches the hash of the original
message, then only Alice could have sent it -- authentication and non-repudiation -- and the message
is exactly as she wrote it -- integrity.
Alice could, of course, encrypt her message with Bob's RSA public key -- confidentiality -- before
sending it to Bob. A digital certificate contains information that identifies the certificate's owner and
also contains the owner's public key. Certificates are signed by the certificate authority that issues
them, and they can simplify the process of obtaining public keys and verifying the owner.
An RSA key exchange involves multiple steps.

How is RSA secure?

RSA security relies on the computational difficulty of factoring large integers. As computing power
increases and more efficient factoring algorithms are discovered, the ability to factor larger and
larger numbers also increases.
Encryption strength is directly tied to key size. Doubling key length can deliver an exponential
increase in strength, although it does impair performance. RSA keys are typically 1024- or 2048-
bits long, but experts believe that 1024-bit keys are no longer fully secure against all attacks. This is
why the government and some industries are moving to a minimum key length of 2048-bits.
Barring an unforeseen breakthrough in quantum computing, it will be many years before longer
keys are required, but elliptic curve cryptography (ECC) is gaining favor with many security

Related Terms
identity theft
Identity theft, also known as identity fraud, is a crime in which an imposter obtains key pieces
of personally identifiable ... See complete definition
password spraying
Password spraying is a cyberattack tactic that involves a hacker using a single password to try
and break into multiple target ... See complete definition
phishing
Phishing is a fraudulent practice in which an attacker masquerades as a reputable entity or
person in an email or other form of ... See complete definition

Generating Public Key

1. Select two prime no's. Suppose P = 53 and Q = 59.
Now First part of the Public key : n = P*Q = 3127.

2. We also need a small exponent say e :

But e Must be

-An integer.

-Not be a factor of n.

-1 < e < Φ(n) [Φ(n) is discussed below],

 Let us now consider it to be equal to 3.

The public key has been made of n and e

Generating Private Key

1. We need to calculate Φ(n) :

Such that Φ(n) = (P-1)(Q-1)
so, Φ(n) = 3016

2. Now calculate Private Key, d :

d = (k*Φ(n) + 1) / e for some integer k
3. For k = 2, value of d is 2011.

The private key has been made of d

Implementation of RSA Algorithm:

Consider two prime numbers p and q.

1. Compute n = p*q
2. Compute ϕ(n) = (p – 1) * (q – 1)
3. Choose e such gcd(e , ϕ(n) ) = 1
4. Calculate d such e*d mod ϕ(n) = 1
5. Public Key {e,n} Private Key {d,n}
6. Cipher text C = Pe mod n where P = plaintext
7. For Decryption D = Dd mod n where D will refund the plaintext.

Program:

// Java Program to Implement the RSA Algorithm

import [Link].*;
import [Link].*;

class RSA {
public static void main(String args[])
{
int p, q, n, z, d = 0, e, i;

// The number to be encrypted and decrypted

int msg = 12;
double c;
BigInteger msgback;

// 1st prime number p

p = 3;

// 2nd prime number q

q = 11;
n = p * q;
 z = (p - 1) * (q - 1);
[Link]("the value of z = " + z);

for (e = 2; e < z; e++) {

// e is for public key exponent

if (gcd(e, z) == 1) {
break;
}
}
[Link]("the value of e = " + e);
for (i = 0; i <= 9; i++) {
int x = 1 + (i * z);

// d is for private key exponent

if (x % e == 0) {
d = x / e;
break;
}
}
[Link]("the value of d = " + d);
c = ([Link](msg, e)) % n;
[Link]("Encrypted message is : " + c);

// converting int value of n to BigInteger

BigInteger N = [Link](n);

// converting float value of c to BigInteger

BigInteger C = [Link](c).toBigInteger();
msgback = ([Link](d)).mod(N);
[Link]("Decrypted message is : "
+ msgback);
}

static int gcd(int e, int z)

{
if (e == 0)
return z;
else
return gcd(z % e, e);
}
}