0% found this document useful (0 votes)
11 views11 pages

RSA Algorithm

The document explains the RSA algorithm, a public-key cryptography method developed by Rivest, Shamir, and Adleman in 1977, which utilizes two keys: a public key for encryption and a private key for decryption. It outlines the steps for generating these keys, the mathematical principles behind RSA, and provides examples of encryption and decryption processes. RSA ensures confidentiality and is based on the difficulty of factoring large integers into their prime components.

Uploaded by

hashimuabdul864
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
11 views11 pages

RSA Algorithm

The document explains the RSA algorithm, a public-key cryptography method developed by Rivest, Shamir, and Adleman in 1977, which utilizes two keys: a public key for encryption and a private key for decryption. It outlines the steps for generating these keys, the mathematical principles behind RSA, and provides examples of encryption and decryption processes. RSA ensures confidentiality and is based on the difficulty of factoring large integers into their prime components.

Uploaded by

hashimuabdul864
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 11

Public-Key Cryptography: RSA (Rivest, Shamir, Adleman)

 Sender uses a public key


» Advertised to everyone
 Receiver uses a private key
Plaintext Plaintext

Encrypt with Internet Decrypt with


public key private key
Ciphertext
Asymmetric Encryption

 Gives 'one-way' security.


 Two keys generated, one used with decryption
algorithm (private key) and one with encryption
algorithm (public key).
 Generation of private key, given public key is
computationally hard.
 Does not need secure key transmission
mechanism for key distribution.
The RSA Algorithm

 Based on the idea that factorization of integers


into their prime factors is hard.
★ n=p . q, where p and q are distinct primes
 Proposed by Rivest, Shamir, and Adleman
in 1977 and a paper was published in The
Communications of ACM in 1978
 A public-key cryptosystem
RSA Algorithm

 Bob chooses two primes p,q and compute


n=pq
 Bob chooses e with gcd(e,(p-1)(q-1))=
gcd(e, ψ(n))=1
 Bob solves de≡1 (mod ψ(n))
 Bob makes (e,n) public and (p,q,d) secret
 Alice encrypts M as C≡Me (mod n)
 Bob decrypts by computing M≡Cd (mod n)
RSA Algorithm

Generating the private and public key


requires four steps:
Choose two very large prime numbers, p and q
Compute n = p x q and z = (p – 1) x (q – 1)
Choose a number d that is relatively prime to z
Compute the number e such that e x d = 1 mod z
Generating Public and Private Keys

 Public key consist of pair (n, e)


 Private key consists of pair (n, d)
RSA Encryption and Decryption
 Encryption of message block m:
» c = me mod n

 Decryption of ciphertext c:
» m = cd mod n
Example (1/2)

 Choose p = 7 and q = 11  n = p*q = 77

 Compute encryption key e: (p-1)*(q-1) = 6*10


= 60  chose e = 13 (13 and 60 are
relatively prime numbers)

 Compute decryption key d such that 13*d = 1


mod 60  d = 37 (37*13 = 481)
Example (2/2)
 n = 77; e = 13; d = 37

 Send message block m = 7

 Encryption: c = me mod n = 713 mod 77 = 35

 Decryption: m = cd mod n = 3537 mod 77 = 7


Properties

 Confidentiality
 A receiver B computes n, e, d, and sends out (n, e)
» Everyone who wants to send a message to A uses (n,
e) to encrypt it
 How difficult is to recover d ? (Someone that can do
this can decrypt any message sent to B!)
 Recall that
d is relatively prime to (p-1)*(q-1)
 So to find d, you need to find prime factors p and q
» This is provably very difficult
Example

 Perform encryption and decryption using the RSA


algorithm, for the following:
a) p=3; q=11; e=7; M=5
b) p=5; q=11; e=3; M=9
c) p=7; q=11; e=17; M=8

You might also like