[2025-11-14 Fri 01:42] <- Digital Signatures [2025-11-14 Fri 01:42] <- S/MIME

• Example of public-private key pair algorithm.
• Text encrypted in blocks of 2048 or 4096 bits.
• Based on exponentiation and modulus arithmetic.
• Select two large primes \(p, q\).
• Calculate \(n = pq\).
• Calculate \(\phi(n) = (p-1)(q-1)\).
• Select integer \(e < \phi(n), \gcd(e, \phi(n)) = 1\)
• Calculate \(d \equiv e^{-1} \mod \phi(n), 1 < d < \phi(n)\)
• Public key is \((e, n)\), private is \((d, n)\)
• Encryption happens as follows: let plaintext be \(P\). Ciphertext is computed as \(C = P^e \mod n\)
• For decryption raise ciphertext to the power of \(d\).

• Public parameters \(q, \alpha\) where the latter is a primitive root of the former and the former is a prime number.
• Key generation works in a similar way, get a \(X_A\) and raise the primitive root to that power, calling it \(Y_A\) and publishing all three as the public key.
• Encryption happens as follows: Calculate \(C_1 = \alpha^k \mod q\), \(K = Y_A^k \mod q\), \(C_2 = KM \mod q\), and transmit \((C_1, C_2)\) to the recipient.
• Decryption happens as follows: Take \(C_1\) and raise it to \(X_A\) and then use it's modular inverse and multiply with \(C_2\).