We show that computing the most significant bits of the secret key in a Diffie-Hellman key-exchange protocol from the public keys of the participants is as hard as computing the secret key itself. This is done by studying the following {em hidden number problem}: Given an oracle $O_{alpha,eta}(x)$ that on input $x$ computes the $k$ most significant bits of $alpha g^x + eta mod p $, find $alpha, eta mod p$. We present many other applications of this problem including: (1) MSB's in El-Gamal encryptions, Shamir Message passing scheme etc. are hard to compute. (2) Factoring with hints. Our results lead us to suggest a new variant of Diffie-Hellman key exchange, for which we prove the most significant bit is hard to compute.