How do I extract the key(s) from the given base64 encoded data? I have tried several options with openssl treating it is both public and private but no luck yet.

The file command might be of use here.

my struggle continues to find the easy way :)

No Key brute force, but do we have to BF the phone number space ? Or is there some other way to do it ?

No need to brute force the phone number space. You should be able to complete this challenge using the file command, google, and some light coding. There's something special about the properties of the public key that should allow you to recover the private key quickly.