RSA public key recovery from signatures Is it possible (how) to recover public (512 bit long) RSA key from multiple signatures having corresponding plain texts. Padding is not randomized.
I need it to verify any future message comming from the same source.
Suppose you have two message-signature pairs, $(m_1, s_1), (m_2, s_2)$, where $s_i = m_i^d \bmod n$. Suppose we also know the public exponent $e$—it is usually $65537$, $3$, $5$, $17$, or some similar small integer. Then we know that $m_i = s_i^e \bmod n$, or in other words $s_i^e = k_in + m_i$ and it follows that $\gcd(s_1^e - m_1, s_2^e - m_2) = \gcd(k_1, k_2)n$, where $\gcd(k_1, k_2)$ is expected to be small.