RSA Algorithm and its implementation in C++.pptx

This ppt is showing details of RSA and implementation of RSA in C++.

1. RSA Algorithm: Pseudocode and Implementation in C++ Name: Anees ur Rehman Reg#: BCB242011 Design And Analysis Of Algorithm

2. Introduction What is RSA? RSA (Rivest-Shamir-Adleman) is a widely used public-key cryptosystem for secure data transmission. It is based on the mathematical properties of large prime numbers. Key Concepts: Public Key: Used for encryption. Private Key: Used for decryption. Applications: Secure communication (e.g., HTTPS, SSL/TLS). Digital signatures. Data encryption.

3. Common Problems Related to RSA Key Generation Challenges: Finding large prime numbers. Ensuring the security of the private key. Computational Complexity: Modular exponentiation is computationally expensive. Security Concerns: Vulnerable to brute-force attacks if key size is small. Vulnerable to quantum computing attacks (Shor’s algorithm). Implementation Issues: Handling large integers in programming languages.

4. RSA Algorithm Overview Steps in RSA: Key Generation: Choose two large prime numbers, p p  and q q . Compute . Choose public key e e  such that   and  . Compute private key  . Encryption: , where  M  is the plaintext message. Decryption: , where  C  is the ciphertext.  

5. 1. Generate two large prime numbers, p and q. 2. Compute n = p * q. 3. Compute φ( n) = (p-1) * (q-1). 4. Choose e such that 1 < e < φ( n) and gcd (e, φ( n)) = 1. 5. Compute d such that d ≡ e^(-1) mod φ( n). 6. Public Key: (e, n). 7. Private Key: (d, n). Pseudocode for RSA Key Generation

6. 1. Input: Plaintext message M, Public Key (e, n). 2. Compute ciphertext C = M^e mod n. 3. Output: Ciphertext C. Pseudocode for RSA Encryption

7. 1. Input: Plaintext message M, Public Key (e, n). 2. Compute ciphertext C = M^e mod n. 3. Output: Ciphertext C. Pseudocode for RSA Encryption

8. 1. Input: Ciphertext C, Private Key (d, n). 2. Compute plaintext M = C^d mod n. 3. Output: Plaintext M. Pseudocode for RSA Decryption

9. Working Example of RSA Step 1: Key Generation   Step 2: Encryption Let  M=65 . Compute    Step 3: Decryption Compute   

10. Time and Space Complexity Key Generation: Time Complexity:  , where  k  is the number of bits in  n . Encryption/Decryption: Time Complexity:   for modular exponentiation. Space Complexity: O(k) O ( k )  for storing keys and intermediate results.  

11. Implementation in C++

12. Implementation in C++

13. Implementation in C++

14. Summary RSA is a robust public-key cryptosystem based on the difficulty of factoring large prime numbers. It involves key generation, encryption, and decryption using modular arithmetic. Proper implementation requires handling large integers and ensuring security through appropriate key sizes. Applications include secure communication and digital signatures.

15. References Books: "Introduction to Algorithms" by Cormen , Leiserson , Rivest, and Stein. "Applied Cryptography" by Bruce Schneier. Online Resources: Wikipedia: RSA Algorithm GeeksforGeeks : RSA Algorithm

16. Thank you Anees ur Rehman Reg #: BCB242011