Asymmetric Cipher and RSA

The most common asymmetric algorithms are RSA and ECC. The idea of "asymmetric" is that unlike "symmetric", it uses two key, one is public key (publicly known & can be exposed) and the other one is private key (should be kept secret). The benefit is to make key exchange less of a hassle.

Public Key Cryptography - Concepts

The idea behind PKC is easy, as illustrated.

💡

Use public key to encrypt, and then use private key to decrypt.

Digital Signature - Concepts

The idea behind the Digital Signature is exactly the reverse of PKC, as illustrated.

Note that digital signatures are not for encryption, it's for validation to know a message is issued by someone who holds the private key.

💡

Use private key to sign, use public key to verify.

RSA (Rivest-Shamir-Adleman)

Math property

RSA uses the property of (m^e)^d = (m^d)^e = m (mod n) for all m in range of [0...n).

You can see m as the message, e as the encryption key and d as the decryption key.

Process

This article or wikipedia explains what RSA is like:

select two large prime number: x, y
- x and y should be kept secret and choose randomly
calculate n = x * y
- n is used as modulus and part of the private/public key
calculate totient(n) = (x-1)(y-1) (usually totient is the least common multiple and may be calculated by euclidean algo)
- totient(n) should be kept secret
select an integer e, so that e is co-prime to totient(n)
- co-prime means two integers' greatest common divisor is 1, i.e. gcd(e, totient(n)) = 1
- 1 < e < totient(n), (n, e) makes up the public key (used for encryption & signature verification)
calculate e*d = 1 mod totient(n)
- d could be found using extended euclidean algorithm, and the pair (n, d) makes up the private key (used for decryption & signing)

Encryption & Decryption

Let's suppose Bob holds the private key, and he made the public key known to everyone else.

💡

Alice wants to write a ciphertext to Bob so that only Bob knows the original message, so she encrypts a plain text P, and derives the ciphertext C with C = P^e mod n to send to Bob

💡

Bob then recievea ciphertext C, only he can decrypt the plain text P with P = C^d mod n

How to apply the keys to Digital Signatures?

First, Bob need to derive the hash h from the message, i.e. h = hash(msg), and need to attach the message with the hash to the public.

💡

Bob wants to sign a message so that Alice and everyone else could know the message is issued by Bob, so he signs a signature S, which is the encrypted h using private key: S = h^d mod n

💡

Alice (and everyone else) is given a signature S, the hash h' could be found using public key h' = S^e mod n

Finally, anyone just have to compare the h' and h, so that they could know if the signature is really signed by the Bob, who hold the private key.

Last updated on November 20, 2022

Symmetric Cipher Elliptic Curve Cipher And ECDSA