A random PSK modulated signal generated with an optical waveguide phase modulator is used to obtain an error signal and lock the frequency of an AlGaAs semiconductor laser to the Rb-87 D2 line. The measured error signal is similar to that obtained with sinusoidal phase modulation under the same conditions. The technique could be applied to longer wavelength lasers and other types of laser that cannot be directly modulated such as fibre lasers.