Hi folks,
Today we are going to see how we can calculate the private key of RSA.
Inputs
Random prime numbers p and q
Public key (n, e)
Procedure
1. Compute n (Random modulus)
n = p * q
2. Compute e (Derived Number)
e = (p - 1) * (q - 1)
3. Form the public key
GCD(pubkey, e) should be 1
pubkey = 1 mod e
4. Private key
prikey = (1 + k * e) / pubkey
0 < k < e - Iterate until we get a number without fraction
Real example
Inputs
p = 7, q = 17, pubkey = 11
1. n = 7 * 17 = 119
2. e = (7-1) * (17-1) = 96
3. pubkey = 11
GCD (11, 96) = 1
4. prikey computation
k=0, (1 + 0 * 96) / 11 = 0.09
k=1, (1 + 1 * 96) / 11 = 8.81
k=2, (1 + 2 * 96) / 11 = 17.5
k=3, (1 + 3 * 96) / 11 = 26.27
k=4, (1 + 4 * 96) / 11 = 35
prikey = 35
Hoping that this blog will be useful in understanding the RSA private key computation.
Send your valuable feedback and comments to psrdotcom@gmail.com
No comments:
Post a Comment