Random generator matching regexp?

Is there any package that takes a regex as input and returns a random string matching that regex or can you direct me how such a solution can be implemented?

My first thought is to generate random bytes in a loop from /dev/rand and then return one that matches the regex but I think that would be time consuming until I find one such string matching the regex.