Please explain me why we require $2^m$ & $2^{\frac{m}{2}}$ random messages Assume that a one-way Hash function is secure and the best way to attack it is by using the brute force attack. It produces an $m$-bit output. Finding a message that hashes to a given hash value would require hashing $2^m$ random messages. Finding two messages that hash to the same value would only require hashing $2^{\frac{m}{2}}$ random messages.

I know only about birthday paradox involving 23 people. How do I relate the birthday paradox with this attack?
$2^m$ requirement is for the pre-image attack. You have to hash approximately  $2^m$ messages to find the message that has the same value you were looking for if the hash function has pre-image resistance. 

In a collision attack, you are looking for two messages that have the same hash value.

If you look at Wikipedia Birthday Paradox at section Cast as a collision problem, it is also generalized for the arbitrary number of days not just for 365 days. The approximation is given by 

$$n \approx \sqrt{2^m}$$ and we call it generic birthday attack.

Note that: if you find an attack which is faster than generic birthday attack like SHA-1 attack you will be famous.