1. A computer-implemented method, comprising: under the control of one or more computer systems configured with executable instructions, receiving a message and a digital signature, the digital signature comprising multiple components comprising a component subject to a uniqueness constraint of a specification of a cryptographic algorithm for generating and verifying digital signatures, wherein performance of the algorithm depends on a set of values for a set of parameters for performing the cryptographic algorithm; using information generated based at least in part on previously received digital signatures to determine whether the component of the digital signature subject to the uniqueness constraint satisfies the uniqueness constraint, wherein the component of the digital signature fails to satisfy the uniqueness constraint as a result of the information generated based at least in part on previously received digital signatures indicates that a value in the component was previously used with the same set of parameters; and as a result of determining that the component of the digital signature subject to the uniqueness constraint fails to satisfy the uniqueness constraint, performing one or more security actions that prevents exploitation of a vulnerability caused by violation of the uniqueness constraint.