Why I don't need to specify public key to import paper wallet I created a paper wallet on coinbase and wanted to import it to coinbase.com. It allowed me to import it by specifying private key only. I was surprised that I didn't have to specify public key as well... is it secure?

I am surely missing here something but the analogy that comes to my mind is ability to log in into someone's gmail account by providing only password and not email. I mean, if that would be possible we could specify "P@ssword" and I'm sure someones has this kind of password to their email, that would let us log in to that account.

Similarily, I could specify some random private key and hope that it's associated with some public address... 

Could you please clarify why my reasoning is not correct and why importing bitcoins by specifying private key only is safe?

Thanks!
The analogy that you suggest isn't quite accurate because a private/public key pair have a very exact mathematical relation, whereas a username/password have no real relation (except maybe an entry in a database somewhere). 

A private key is essentially a 256 bit number. Using this private key, and an Elliptic Curve library that supports the use of the secp256k1 curve, you can deterministically calculate what the associated public key is. Since a bitcoin address is a hash of the public key, all you really need is the private key and you can calculate everything else to be able to see what transactions resulted in the address being credited/debited coins. That's why coinbase only has you give your private key.