How to calculate the public key (E) of an RSA private key (D)? [duplicate]

Question

This question already has answers here:

c# RSA extract public key from private key (3 answers)

Closed 8 years ago.

I want to create my own RSA Key Pair (Actually I want create pair key with my own Private Key) for some reason but I realized that I should use the keys that RSA Class generates for me cause the public (e) and private (d) keys are mathematically related together.

I kept on researching to find a way to do this and at last found out that it it possible to obtain the public key of a private key.

So I found the solution! Calculate the public key of my own private key.

It's not a traditional work so I think there's not a function for this purpose in any programming language and I should create my own function based on RSA Algorithm that calculate E based on the given D.

Any idea how to do this?

(I prefer C#! But I actually want a solution (event a mathematical formula!), language doesn't matter.)

Answer 1

an rsa keypair consists of the public key (exponent e and modulus N) and the private key (exponent d and modulus N)

in this plain version, it is the same if you'd like to calculate the private key from the public or the other was around ... practically impossible

...however ...

if you happen to have a private key that contains more values for performance reasons (for example like d,dQ,dP,P,Q,N) then you have everything you'll need to calculate the public exponent from that:

calculate phi_n as (P-1)*(Q-1)

run the extended euclidean algorithm to calculate the multiplicative inverse of d mod phi_n ... that is your public exponent ... since N is already known (P*Q) you have the public key

EDIT (to be more precise):

there is no mathematical difference between the exponents e and d ... one is the multiplicative inverse of the other ...

in the most simple way you can look at RSA, one key of a keypair is nothing more than an exponent and a common modulus ... in fact, when you create the keypair and calculate the values e and d, you may exchange them against each other and everything would still work

to calculate a multiplicative modular inverse you need the modulus ... now comes the problematic part: there are two

one modulus is N ... that is the common modulus for both keys ... this value is no secret since it is part of the public key

the second modulus is phi of N (eulers phi function) ... this value IS a secret ... everyone who has this value, can calculate the inverse key ... in case of RSA phi(n) is (P-1)*(Q-1)

P and Q are the two large prime numbers used in RSA ... N = P * Q

now as you can see, to calculate the other key to a given key, you need to know phi(n) ... the only known method to get phi(N) is eulers phi function, and for that, you will need the factors of N ... since N is the product of two large primes, you need those two primes ... so either you have a key which contains P and Q (actually one of them would suffice since you can devide N to get the other...) or you will have to factorize N yourself ...

factorization of large numbers that consist only of two large prime factors is a task that needs time ... thats the security of RSA ... who ever can do that, can break RSA keys

so to get back at your specific problem:

it does not matter if you want to calculate E through D or D through E ... the mathematical problem is the same ... you can solve this IF, AND ONLY IF you have at least one factor of the common modulus N