Which new RSA-signatures can be computed from certain given RSA-signatures? J
Jan‐Hendrik Evertse, E. vanHeijst · Data Archiving and Networked Services (DANS) · 1992
We consider the following problem.A signature authority issues RSAsignatures of certain types to an individual, and the individual tries, by using the signatures he received, to compute an RSA-signature of a type not issued by the authority.Is the individual able to do this?The RSA-signatures are products of rational powers of residue classes modulo the composite number N of the underlying RSA-system, and the residue classes are chosen at random by the signature authority.The rational exponents in the product determine the type of the signature.We prove that computing an RSA-signature of a particular type, from given RSA-signatures of other types, is polynomial time reducible to computing RSAroots x"' (mod N) for random x and some positive integer d.This extends results of Aki and Taylor [1] and Shamir (11] from one variable to arbitrarily many variables.As an application of this, under the assumption that for the individual it is infeasible to compute RSA-roots, we give necessary and sufficient conditions describing whether it is feasible for that individual to compute RSA-signatures of a prescribed type from signatures of other types that he received before from the authority.