What I learned today:
RSA
Alice has two large (150+ digit) prime numbers: pA , qA .
She then computes:
nA = pA * qA and mA = Φ(nA) = (pA-1)(qA-1)
Then she finds a number eA such that gcd (eA, mA) = 1.
And computes dA such that dA * eA = 1 (mod mA).
She then publishes nA and eA as her public keys, destroying all copies of pA, qA and mA, keeping dA a secret.
A “phone book” of key-pairs is published:
Alice - (nA , eA)
Bob - (nB , eB)
Carol - (nC , eC)
For Alice to send a message (M) to Bob, she looks up his public key pair, and then computes: C = MeB (mod nB) and sends this to Bob.
Bob looks up his private key and computes:
CdB = MeBdB (mod nB).
Note that dB * eB = 1 (mod Φ(nB)) = 1 + k Φ(nB) and that gcd (M, nB) = 1, hence:
MΦ(nB) = 1 (mod nB).
CdB = M 1 + k Φ(nB) (mod nB)
= M * MΦ(nB) * k (mod nB)
= M * (1)k (mod nB)
= M
That is to say: e B and d B are inversely related functions, and by using this relationship, it is possible to decrypt text encrypted by raising it to the e B power by raising it to the d B power.
Message Signing
Suppose Alice wants to send a message and prove that it comes from the person who knows the inverse key to eA (who should only be her).
She computes:
C1 = M dA (mod nA).
C2 = C1eB (mod nB)
and sends C2 to Bob.
Bob then computes:
C1 = C2 dB (mod nB) and then M = C1 eA (mod nA).
This results in the original message, M, which states that the message is signed by Alice, and this signature is verified since she’s the only one who knows her private key (the inverse to eA - the public key) used to encrypt it.
Alice has two large (150+ digit) prime numbers: pA , qA .
She then computes:
nA = pA * qA and mA = Φ(nA) = (pA-1)(qA-1)
Then she finds a number eA such that gcd (eA, mA) = 1.
And computes dA such that dA * eA = 1 (mod mA).
She then publishes nA and eA as her public keys, destroying all copies of pA, qA and mA, keeping dA a secret.
A “phone book” of key-pairs is published:
Alice - (nA , eA)
Bob - (nB , eB)
Carol - (nC , eC)
For Alice to send a message (M) to Bob, she looks up his public key pair, and then computes: C = MeB (mod nB) and sends this to Bob.
Bob looks up his private key and computes:
CdB = MeBdB (mod nB).
Note that dB * eB = 1 (mod Φ(nB)) = 1 + k Φ(nB) and that gcd (M, nB) = 1, hence:
MΦ(nB) = 1 (mod nB).
CdB = M 1 + k Φ(nB) (mod nB)
= M * MΦ(nB) * k (mod nB)
= M * (1)k (mod nB)
= M
That is to say: e B and d B are inversely related functions, and by using this relationship, it is possible to decrypt text encrypted by raising it to the e B power by raising it to the d B power.
Message Signing
Suppose Alice wants to send a message and prove that it comes from the person who knows the inverse key to eA (who should only be her).
She computes:
C1 = M dA (mod nA).
C2 = C1eB (mod nB)
and sends C2 to Bob.
Bob then computes:
C1 = C2 dB (mod nB) and then M = C1 eA (mod nA).
This results in the original message, M, which states that the message is signed by Alice, and this signature is verified since she’s the only one who knows her private key (the inverse to eA - the public key) used to encrypt it.