# RSA the difficulty in getting private key at very first place

I've just learnt about RSA, there's one concept I find very confusing. The reason RSA is very secure is that given public keys {e, n} , it's very hard for people to calculate the private keys {d, n}. But isn't it the same situation when they get the private keys at the first place, since it's so difficult, why is Alice able to calculate the private key and tell Bob?

## Answers

The idea is that Alice *chooses* a private key, then tells Bob her *public* key. Bob can only use the key to encrypt, and it's very hard to get the private key *based on the public key*. If you are picking (or creating) a new private key out of thin air, that's easy; all you have to do is pick a couple prime numbers that satisfy a few requirements. It's calculating the private key *based on the public key* that is (and needs to be) difficult. RSA wiki page.

I thought it's very hard to calculate ax + by = 1 but it's simply log(n) complexity. And the hard part is actually calculating φ(n) because they don't know n = pq! Alice knows p and q, that's why it's much much simpler for her. Problem solved, thanks for helping guys!