Course Name:-Advanced Cryptography
Code:BECCS3C007
Course Instructor:
Dr.Bhavna Arora
Associate Professor
Department of CSE
RSA Algorithm
• RSA(Rivest-Shamir-Adleman) Algorithm is
an asymmetric or public-key cryptography algorithm which
means it works on two different keys: Public Key and Private
Key.
• The Public Key is used for encryption and is known to
everyone, while the Private Key is used for decryption and
must be kept secret by the receiver.
• RSA Algorithm is named after Ron Rivest, Adi Shamir and
Leonard Adleman, who published the algorithm in 1977.
Example of Asymmetric Cryptography:
If Person A wants to send a message securely to Person B:
• Person A encrypts the message using Person B’s Public Key.
• Person B decrypts the message using their Private Key.
• RSA Algorithm is based on factorization of large number and modular
arithmetic for encrypting and decrypting data.
It consists of three main stages:
• Key Generation: Creating Public and Private Keys
• Encryption: Sender encrypts the data using Public Key to get cipher
text.
• Decryption: Decrypting the cipher text using Private Key to get the
original data.
• The idea of RSA is based on the fact that it is difficult to
factorize a large integer.
• The public key consists of two numbers where one number is
multiplication of two large prime numbers. And private key is
also derived from the same two prime numbers.
• So if somebody can factorize the large number, the private
key is compromised.
• Therefore encryption strength totally lies on the key size and
if we double or triple the key size, the strength of encryption
increases exponentially.
• RSA keys can be typically 1024 or 2048 bits long, but experts
believe that 1024 bit keys could be broken in the near future.
• But till now it seems to be an infeasible task.
Key Generation in RSA:
• Choose two distinct prime numbers: Let's call them 'p' and
'q'.
• Calculate n: n = p * q (This 'n' is the modulus and is part of
both the public and private keys).
• Calculate the Euler’s totient function (φ(n)):
φ(n) = (p-1) * (q-1).
• Choose an integer 'e': 1 < e < φ(n), and e must be coprime
with φ(n) (meaning their greatest common divisor is 1). 'e' is
part of the public key.
• Calculate 'd': d is the modular multiplicative inverse of 'e' modulo
φ(n).
This means e * d ≡ 1 (mod φ(n)).
Private Key, d : d = (k*Φ(n) + 1) / e for some integer k
'd' is the private key.
• Public Key: The public key is (n, e).
• Private Key: The private key is (n, d).
2. Encryption:
• Sender: The sender obtains the receiver's public key (n, e).
• Encrypt: The sender encrypts the message 'm' (which is a number)
using the formula:
c = m^e mod n, where 'c' is the ciphertext.
3. Decryption:
• Receiver: The receiver uses their private key (n, d).
• Decrypt: The receiver decrypts the ciphertext 'c' using the formula:
m = c^d mod n, where 'm' is the original message.
