竹炉山房

Including the time of cooking my dinner. I'm a genius...  😛

However, it is still far from perfect. Besides, the worst part is ECC (Elliptic Curve Cryptography), not RSA. Tmrw I'll meet James in the uni again. Hope we can crack some parts!

What is RSA?

RSA is a public-key cryptosystem for both encryption and authentication;it was invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman. It works as follows: take two large primes, p and q, and find their product n = pq; n is called the modulus. Choose a number, e, less than n and relatively prime to (p-1)(q-1), and find its inverse, d, mod (p-1)(q-1), which means that ed = 1 mod (p-1)(q-1); e and d are called the public and private exponents, respectively. The public key is the pair (n,e); the private key is d. The factors p and q must be kept secret, or destroyed. It is difficult (presumably) to obtain the private key d from the public key (n,e). If one could factor n into p and q, however, then one could obtain the private key d. Thus the entire security of RSA is predicated on the assumption that factoring is difficult; an easy factoring method would "break'' RSA.

Here is how RSA can be used for privacy and authentication (in practice, actual use is slightly different:

RSA privacy (encryption): suppose Alice wants to send a private message, m, to Bob. Alice creates the ciphertext c by exponentiating: c = m^e mod n, where e and n are Bob's public key. To decrypt, Bob also exponentiates: m = c^d mod n, and recovers the original message m; the relationship between e and d ensures that Bob correctly recovers m. Since only Bob knows d, only Bob can decrypt.

RSA authentication: suppose Alice wants to send a signed document m to Bob. Alice creates a digital signature s by exponentiating: s = m^d mod n, where d and n belong to Alice's key pair. She sends s and m to Bob.

To verify the signature, Bob exponentiates and checks that the message m is recovered: m = s^e mod n, where e and n belong to Alice's public key.

Thus encryption and authentication take place without any sharing of private keys: each person uses only other people's public keys and his or her own private key. Anyone can send an encrypted message or verify a signed message, using only public keys, but only someone in possession of the correct private key can decrypt or sign a message.