Asymmetric (public key) cryptosystems RSAalgorithm Euclidean algorithm, Extd. Euclideanalgorithm, gcd, and multiplicative inversemodulo
RSA Algorithm (Rivest-Shamir-Adleman)
It is an asymmetric/public-key cryptography algorithm. The public key is used for encryption and private key is used for decryption.
- Can be used for Key Exchange
- Can be used for Digital Signatures
- Based on the difficulty of Integer Factorisation
Choose two large prime numbers, p and q
Calculate n = p * q
Calculate Φ(n)
Choose e such that 1 < e < Φ(n) and gcd(e, Φ(n)) = 1
Calculate (d * e) ≡ 1 mod Φ(n)
Cipher Text = M ^ e mod(n)
Decrypted Text = C ^ d mod(n)
| Feature | RSA (Asymmetric Transport) | Diffie-Hellman (Shared Secret Formation) |
|---|---|---|
| Mathematical Basis | Integer Factorization. | Discrete Logarithm. |
| Primary Goal | Encryption and Digital Signatures. | Formation of a shared secret key over an insecure channel. |
| How it works | One party selects a key and transmits it to the other using public-key encryption. | Both parties agree on a key by calculating it simultaneously; the key is never sent. |
| Category | Asymmetric Cryptosystem. | Often categorized as a Symmetric key exchange tool because its end goal is a shared symmetric key. |
Extended Euclidean Algorithm
Extended Euclidean algorithm also finds integer coefficients x and y such that: ax + by = gcd(a, b)
eg.
| Step | q (Quotient) | r (Remainder) | T (The Inverse calculation) |
|---|---|---|---|
| Start | — | 26 | 0 |
| Start | — | 11 | 1 |
| 1 | 2 ($26 \div 11$) | 4 ($26 \pmod{11}$) | -2 ($0 - 2 \times 1$) |
| 2 | 2 ($11 \div 4$) | 3 ($11 \pmod{4}$) | 5 ($1 - 2 \times -2$) |
| 3 | 1 ($4 \div 3$) | 1 ($4 \pmod{3}$) | -7 ($-2 - 1 \times 5$) |
| 4 | 3 ($3 \div 1$) | 0 | 26 ($5 - 3 \times -7$) |