24 Oct 2025
asymmetric key cryptography
asymmetric key crypto
This allows us to do some really creative stuff where one of the keys is public, which allows for even more use-cases like non-repudiation, signing etc. These can't be fulfilled by symmetric key cryptography
RSA encryption
- 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\).
Elgamal encryption
- 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\).
