Description
Public-key cryptosystem. Key generation: choose primes p,q; n=pq; φ=(p-1)(q-1); choose e coprime to φ; compute d ≡ e⁻¹ (mod φ). Public key (e,n), private (d,n). Encrypt: c = m^e mod n. Decrypt: m = c^d mod n. Security relies on hardness of factoring n. Uses modular exponentiation (square-and-multiply). Time O(k³) for k-bit keys.
Source: Wikipedia
Algorithm Flowchart
graph TD
A1["Primes p q\nor message m, keys e n or d n"]
D1{"Key gen\nor Encrypt\nor Decrypt?"}
B1["Key gen: n=pq, phi\nchoose e, d = inv e mod phi"]
B2["Encrypt: c = m^e mod n"]
B3["Decrypt: m = c^d mod n"]
F1["Return keys\nor ciphertext c\nor plaintext m"]
A1 --> D1
D1 -->|Key gen| B1
D1 -->|Encrypt| B2
D1 -->|Decrypt| B3
B1 --> F1
B2 --> F1
B3 --> F1
classDef red fill:#ff6b6b,color:#fff,stroke:#c0392b
classDef yellow fill:#ffd43b,color:#000,stroke:#f59f00
classDef green fill:#51cf66,color:#fff,stroke:#40c057
classDef lightblue fill:#74c0fc,color:#fff,stroke:#4dabf7
classDef violet fill:#b197fc,color:#fff,stroke:#9775fa
classDef lavender fill:#e6e6fa,color:#333,stroke:#b19cd9
class A1 red
class B1,B2,B3 green
class F1 violet
class D1 lavender
Color Scheme (GLMP 6-Color)
Red
Triggers & Inputs
Triggers & Inputs
Yellow
Structures & Objects
Structures & Objects
Green
Processing & Operations
Processing & Operations
Light Blue
Intermediates & States
Intermediates & States
Violet
Products & Outputs
Products & Outputs
Lavender
Decision diamonds
Decision diamonds
Process Statistics
- Nodes: 6
- Edges: 7
- OR gates: 1
- Loops: 0
- AND gates: 0
- Complexity: O(k³) for k-bit keys
Keywords
- RSA
- public-key cryptography
- modular exponentiation
- encryption