# Calculate if a digital signature is valid

In the book An Introduction to Mathematical Cryptography, it mentions a section on digital signatures and a theoretical example. I am having difficulty understanding the book and I was wondering if someone could better explain how you would be able to deduce if a signature is valid rather than finding what the signature is.

For example, $N = 1562501$ and the public key is $e = 87953$, the document $m = 161153$, and the signature is $d = 870099$. Is there a technique to find if it's a valid signature?

• Possible duplicate of How does RSA signature verification work? Apr 11 '16 at 17:51
• While the question was about signatures methods in general, the actual example given is a toy implementation of RSA. Perhaps if you reviewed the crypto.stackexchange.com/questions/9896/… answer, it may address some of your questions (unless you need something more basic; don't worry, we won't be offended by basic questions...) Apr 11 '16 at 17:53
• Fact: $870099^{87953}\bmod1562501$ is easy to compute, and is $161153$; but computing $870099$ from the other three values is harder, and requires factoring $1562501$, or comparable effort [revised].
– fgrieu
Apr 11 '16 at 18:55

Basically RSA signatures work just like encryption but with the keys exchanged. If somebody tells you $m^{sk}$ you can easily test if $$(m^{sk})^{pk} \equiv m\ (mod\ N)$$ but you cannot calculate $m^{sk}$ yourself.

The problem/trick is the usual, exponentiation is easy but logarithm is hard.

(I like using $sk$/$pk$ for secret-/public-key rather than $d$/$e$ for decryption-/encryption-key as it makes more sense for signatures.)

• The RSA private key operation is not a logarithm; RSA is not: exponentiation is easy but logarithm is hard.
– fgrieu
Apr 11 '16 at 20:04
• I don't understand your comment so let me rephrase: Calculating the discrete logarithm of $m^{sk}$ to base $m$ aka the secret key is hard while taking $m^{sk}$ to the power $pk$ and thus verifying the signature is easy. Apr 11 '16 at 20:17
• @Erwin: a logarithm would be "given $a, b, n$ compute $x$ such that $a^x = b \pmod n$. Instead, the RSA problem is the $e$-th root; that is, given $b, e, n$ compute $x$ such that $x^e = b \pmod n$ Apr 11 '16 at 20:24
• But in case of signatures the message $m$ is given as is $m^{sk}$. So calculating $sk$ would be calculating the discrete log of $m^{sk}$ to the base $m$. Apr 11 '16 at 20:30
• However, breaking RSA doesn't require us to recover the value of $sk$; recovering $m$ given $m^e$ would suffice to break both RSA public key encryption and RSA signatures (and there's no known proof that performing $e$-th roots (for odd $e$) can allow us to compute $sk$) Apr 12 '16 at 0:53