I've been studying the concept of RSA algorithm today, And this is what i understood.
To generate keypair -
- Two prime numbers (p1 = 53, p2 = 59 for example) are multiplied to generate
n (which will be utilized as the public modulus)
- We use Euler's totient function on our
n variable and define a new variable
- We generate a public exponent
e in condition that it must be small odd number not sharing factor with our
d is generated from this formula:
d = (k * (phi(n)) + 1) / e.
We substitute variables with numbers and get private key:
d = (2 * (3016) + 1) / 3 = 2011
We substitute -
2 (by my knowledge
k must be more than 0 and less than
p1 * p2 = 3127 and since the result is a prime number, We get its phi easily using
phi(n) = (p1-1) * (p2-1))
e the exponent with
3 (Because it does not share any factors with 3016 and it's an odd number)
To use the public key -
Afterwards we can share our
n since computers would take decades to get private key from big
Our communicator encodes message the into the hex and afterwards converts it to base10 integer. Communicator may also add random integer padding for protection.
When message is turned into the number, Modular exponentiation is performed mcdvoice on it:
[![enter image description here]]
So if message in numbers is 89 for example, If we do modular exponentiation on it we would get:
The Question -
If our communicator sends us
1394 which is encrypted
89^3 * mod(59 * 53) = 1394), How do we use our private key to decrypt this message automatically? Is there some specific formula that must be used?
Thank you a lot for reading.