"/home/yossef/notes/Su/security/study_security_l7.md"

path: Su/security/study_security_l7.md

- **fileName**: study_security_l7
- **Created on**: 2025-06-02 21:26:49

RSA Cryptography Explained

Core Concepts

• Public-key algorithm by Rivest, Shamir, Adleman (1977)
• Used for encryption, signatures, and key exchange
• Security relies on difficulty of factoring large primes
• Key components:
  • n: Product of two primes (p × q)
  • φ(n): Euler's totient (p-1)(q-1)
  • e: Public exponent (coprime to φ(n))
  • d: Private exponent (e⁻¹ mod φ(n))

RSA Workflow

Key Generation

1. Choose primes p=17, q=11
2. Calculate n = 17 × 11 = 187
3. Compute φ(n) = 16 × 10 = 160
4. Select e=7 (gcd(7,160)=1)
5. Find d=23 (7×23 mod 160=1)
6. Public key: PU = {7, 187}
7. Private key: PR = {23, 187}

Encryption (M=88)

C = 88⁷ mod 187 = 11

Decryption

M = 11²³ mod 187 = 88

Solved Exercises

Problem 2 (From Lecture)

Encrypt M=2 with p=3, q=11:

1. n = 3×11 = 33
2. φ(n) = 2×10 = 20
3. Choose e=7 (coprime to 20)
4. Find d=3 (7×3 mod 20=1)
5. Encrypt: 2⁷ mod 33 = 29
6. Decrypt: 29³ mod 33 = 2

Assignment Problem 2

Encrypt M=20 with p=13, q=17:

1. n = 13×17 = 221
2. φ(n) = 12×16 = 192
3. Choose e=5 (gcd(5,192)=1)
4. Find d=77 (5×77 mod 192=1)
5. Encrypt: 20⁵ mod 221 = 141
6. Decrypt: 141⁷⁷ mod 221 = 20

Assignment Problem 3

Encrypt M=70 with p=3, q=7:

1. n = 3×7 = 21
2. φ(n) = 2×6 = 12
3. Choose e=5 (gcd(5,12)=1)
4. Find d=5 (5×5 mod 12=1)
5. Encrypt: 70⁵ mod 21 = 7 (Note: 70 mod 21=7)
6. Decrypt: 7⁵ mod 21 = 7 (Original M < n)

Security Considerations

• Brute force: Infeasible for large n (2048+ bits)
• Mathematical attacks: Equivalent to factoring n
• Timing attacks: Constant-time implementations needed
• Best practice: Use OAEP padding, not raw RSA

Applications

1. Secure web traffic (HTTPS/SSL)
2. Digital signatures (PKCS#1)
3. Encrypting symmetric keys (Hybrid systems)

Key Formulas

• Key generation:
  d ≡ e⁻¹ mod φ(n)
• Encryption:
  C ≡ Mᵉ mod n
• Decryption:
  M ≡ Cᵈ mod n

continue:./study_security_l8.md
before:./study_security_l6.md