Suppose Oscar sees Alices RSA signature on m1and on m2 that

Suppose Oscar sees Alice\'s RSA signature on m₁and on m₂ (that is, he sees m₁^d mod n and m₂^d mod n). How does Oscar compute the signature on each of m₁^j mod n (for positive integer j), m₁^-1 mod n, m₁*m₂ mod n, and in general m₁^j * m₂^k mod n (for arbitrary integers j and k)?

Solution

When we say Oscar see RSA on m1 and m2 which means Oscar see m1^d mod n and m^2d mod n. Now we can solve the problem as below. Signature of m1^i mod n where i is any +integer could be calculated by formula (m1^d)^i mod n = (m1^i)^d mod n. Signature of m1^(-1) is (m1^(-1))^(d) mod n = (m1^(-d)) mod n = (m1^d)^(-1) mod n. This could be computed by multiplicative inverse of m1^d mod n using Eucildean Algorithm. If we want to compute signature of m1*m2 then it could be calculated like (m1*m2)^d mod n = ((m1)^d mod n) *(m2^d modn) mod n.