We present a simple method for generating random-based signatures when random number generators are either unavailable or of suspected quality (malicious or accidental). In opposition to all past state-machine models, we assume that the signer is a memoryless automaton that starts from some internal state, receives a message, outputs its signature and returns precisely to the same initial state; therefore, the new technique formally converts randomized signatures into deterministic ones. Finally, we show how to translate the random oracle concept required in security proofs into a realistic set of tamper-resistance assumptions