1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Possible duplicate of How does RSA signature verification work? $\endgroup$ – poncho Apr 11 '16 at 17:51
  • $\begingroup$ 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...) $\endgroup$ – poncho Apr 11 '16 at 17:53
  • $\begingroup$ 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]. $\endgroup$ – fgrieu Apr 11 '16 at 18:55
1
$\begingroup$

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.)

| improve this answer | |
$\endgroup$
  • $\begingroup$ The RSA private key operation is not a logarithm; RSA is not: exponentiation is easy but logarithm is hard. $\endgroup$ – fgrieu Apr 11 '16 at 20:04
  • $\begingroup$ 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. $\endgroup$ – Erwin Apr 11 '16 at 20:17
  • 1
    $\begingroup$ @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$ $\endgroup$ – poncho Apr 11 '16 at 20:24
  • $\begingroup$ 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$. $\endgroup$ – Erwin Apr 11 '16 at 20:30
  • 1
    $\begingroup$ 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$) $\endgroup$ – poncho Apr 12 '16 at 0:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.