Engineering Code Lecture Notes on RSA Algorithm Calculation of D

Introduction

• Topic: Calculation of D in RSA Algorithm
• Importance: One of the toughest and main parts of RSA
• Audience: Requested by a subscriber to be explained in English

Steps to Calculate D

Step 1: Calculate Phi(n)

• Formula: ( \phi(n) = (p - 1)(q - 1) )
• Example 1:
  • Given values: ( P = 5, Q = 11 )
  • Calculation: ( \phi(n) = (5 - 1)(11 - 1) = 4 \times 10 = 40 )

Step 2: Solve for D

• Equation: ( D \cdot E \equiv 1 \mod \phi(n) )
• Substitute values:
  • For example: ( 3D \equiv 1 \mod 40 ) (using E = 3)
• Create a table of multiples of ( \phi(n) ):
  • Values: 40, 80, 120...
  • Add 1 to each: 41, 81, 121...
• Check divisibility with E:
  • Example: 81 is divisible by 3
• Calculate D:
  • Make equation equivalent to 81: ( 27 \times 3 = 81 )
  • Final equation: ( 27 ,mod , 40 )
  • Result: When the modulus is 1, D is found.

Example 2

• New values: ( P = 3, Q = 11, E = 7 )

Step 1: Calculate Phi(n)

• Calculation:
  • ( \phi(n) = (3 - 1)(11 - 1) = 2 , \times , 10 = 20 )

Step 2: Solve for D

• Equation: ( D \cdot 7 \equiv 1 \mod 20 )
• Create a table:
  • Values: 20, 40, 60...
  • Add 1: 21, 41, 61...
• Check divisibility with E:
  • Example: 21 is divisible by 7
• Calculate D:
  • Make equation equivalent to 21: ( 3 \times 7 = 21 )
  • Final equation: ( 3 ,mod , 20 )
  • Result: D = 3 when modulus is 1.

Conclusion

• The process of calculating D in RSA is straightforward and involves two main steps.
• Understanding these calculations is crucial for implementing RSA effectively.
• Thank you for attending the lecture!