The Legendre signature of an integer x modulo a prime p with respect to offsets \(\textbf{a} = (a_1, \dots , a_\ell )\) is the string of Legendre symbols \((\frac{x+a_1}{p}), \dots , (\frac{x+a_\ell }{p})\) . Under the quadratic-residuosity assumption, we show that the function that maps the pair (x, p) to the Legendre signature of x modulo p, with respect to public random offsets \(\textbf{a}\) , is a pseudorandom generator. Our result applies to cryptographic settings in which the prime modulus p is secret; the result does not extend to the case—common in applications—in which the modulus p is public. At the same time, this paper is the first to relate the pseudorandomness of Legendre symbols to any pre-existing cryptographic assumption.