If you look on the scottish births section of the LDS sitehttps://www.familysearch.org/search/collection/show#uri=http...
you will find several Catherine JOHNSTONs (of variuos spellings which you should not discount as they are interchangeable ) born to an Alexander at that time.
To get the proper birth cert go to www.scotlandspeople.gov.uk
to download it for about £2 .
However , as there are so many likely candidates it might be better to go for her marriage or death certificates which, if the events took place in Scotland , would have her mother's name