1
$\begingroup$

To clarify, I'm talking about digital-signatures, not public key encryption.

When I encrypt something with a private key, then it should be decryptable with a public key, as I've understood how asymetric cryptography works.

So, if 654 * 987 * 123 = 79.396.254, there are countless sums that could lead to that 79 million answer, that explains private key encryption to me, and can be applied to superficially explain how digital signing works.

But how do you verify with a public key, that it was signed with their private key?

I'm looking for the simplest mathematical way to explain this, perhaps using a similar mathematical analogy.

I'm not looking for a super in-depth explanation, but a superficial analogy for it.

$\endgroup$

migrated from security.stackexchange.com Jul 25 '16 at 12:26

This question came from our site for information security professionals.

  • $\begingroup$ Not sure if I grasp this. You “clarify” that you’re talking about digital signatures, not public key encryption… yet then you describe public key encryption, asking if there’s a way to verify if something was encrypted with a public key. How (or where) do “digital signatures” fit into that picture? $\endgroup$ – e-sushi Jul 25 '16 at 12:47
  • $\begingroup$ @e-sushi: he's under the impression that all signature algorithms work like RSA; I'd write an answer, but I can't think of a 'signature scheme' that's simple, representative (Lamport is simple, but rather unlike traditional signature methods) and not easily broken (even if you assume things like computing inverses 'too hard') $\endgroup$ – poncho Jul 25 '16 at 12:55
  • $\begingroup$ @poncho Ah, failed to adapt my brain to look at things from that angle. Got it now, thanks. (As he/she only expects a “simplest mathematical way” demo, a toy-construction should already satisfy his/her needs…) $\endgroup$ – e-sushi Jul 25 '16 at 12:56
  • $\begingroup$ @e-sushi, I'm using the simplest ELI5 explanation of why private key encryption works and is not easily reversed. I'm describing how the public key is used to verify the ownership so to say. But now I'm really curious for your toy-construction analogy... $\endgroup$ – BlockChange Jul 25 '16 at 13:41
  • 1
    $\begingroup$ @BlockChange Confusion vanished. ;) Re: toy construction analogy… toy constructions are “boiled down” versions. They tend to have less cryptographic security (if any), but they’re nice to demonstrate or analyze the core of something; especially with new constructions. One of many examples is “Bivium” as toy version of stream cipher “Trivium”. But toy constructions can also be as simple as in the answer to How would you encrypt-then-MAC when using pen-and-paper and a Caesar cipher? $\endgroup$ – e-sushi Jul 25 '16 at 14:00
2
$\begingroup$

Ok, here's a toy example (which really doesn't work) of a simple signature scheme, which you can use as an analogy of a real system:

Suppose the signer Alice picks three integers $b, c, p$, and computes $a = b \times c \bmod p$. She then publishes $a, b, p$ as her public key, and keeps $c, p$ as her private key.

Then, when Alice wants to sign a message $M$, she computes $S = c \times M \bmod p$, and publishes $S$ as the signature.

So, when verifier Bob gets the message $M$, the signature $S$, and Alice's public key, he verifies whether $a \times M \bmod p$ and $b \times S \bmod p$ are the same; if the signature is valid, then $a \times M \bmod p = (b \times c) \times M \bmod p = b \times (c \times M) \bmod p= b \times S \bmod p\ $, and so equality would hold.

The points I am hoping to make in this analogy:

  • The signature is not necessarily an 'encoding' of the message

  • Instead, the signature and the message satisfy some relationship (in concert with the public key)

  • It's not obvious how to create a signature for a given message with only the public key (actually, my example falls down a bit here)

  • The private key contains the 'secret sauce' that makes generating such signatures easy

Now, this doesn't work as an actual signature scheme, even with large numbers, because we know how to compute $a \times b^{-1} \bmod p$, which is $c$, however the method isn't immediately obvious to someone new to the field.

$\endgroup$
1
$\begingroup$

To decode from a public-key encoded message, you need the secret private key. Anyone else cannot do it. For the mathematical details how this is possible, you need to analyse the respective asymmetric cryptographic algorithms.

There are several different asymmetrical encryption algorithms, including RSA and ElGamal, see the Wikipedia links for an explanation of the algorithms behind them.

P.S. I don't think that an analogy can explain this well; just do examples with small numbers by hand to get a feeling of the algorithm and think why it is hard with large numbers.

$\endgroup$
  • $\begingroup$ Actually, he wasn't asking about 'decoding from a public-key encoded message', he was asking about how signatures worked. $\endgroup$ – poncho Jul 25 '16 at 14:06
  • $\begingroup$ @poncho: Sigh, the question is ever morphing. $\endgroup$ – jknappen Jul 25 '16 at 14:08
1
$\begingroup$

An analogy might not be that helpful but an example for example with RSA signatures.

RSA Signatures work like this:

s = m^d mod N

where s is the signature, m the message and d the private key. (See example below.

Verification works like this:

m' = s^e mod N

where s is still the signature and e is the publicly known and trusted public key. If m' = m holds true the signature is valid.

The one who wants to verify the signature needs both the signature and the message (hence m and s). This the nature of the public key is to be publicly available, ideally from a trusted party, one has all three values to verify the signature. The private key should only known by the person who created the signature and therefor he/she is the only person who can create the signature to the given message (assumed the cryptographical primitives are considered secure).

This is a complete example on how this works (with small numbers to understand is, it if obviously not secure in these dimensions) I assume you have know how RSA works, if not search for RSA explained and pick any match.

Party A                                                    Party B
p = 11, q = 3, N = 33
Phi(N) = (11-1)*(3-1) = 20
Choose e = 7
Calculate d = e^-1 = 7^-1 = 3 mod 20

                                       (N=33, e=7)
                                      ------------>        Setup completed
Choose message m = 8
s = m^d = 8^3 = 17

                                       (m=8, s=17)
                                      ------------>
                        (Note here that s can only be calculated by A
                       since only A knows d and the RSA problem is hard)

                                                           m' = s^e = 17^7 = 8 mod 33
                                                           m = m' => Signature is valid

                                                           B knows that m has been send by A
                                                           and only by A (as does everyone
                                                           else who has knowledge about
                                                           m, s, e and N

The crucial part is that every public key e has only one matching d (modulus Phi(N)) for a correct set of RSA Parameter and for sufficient strong bit lengths an attacker would have to guess/calculate the secret d which ought to be sufficient hard that such a guess/calculation is only successfully with a negligible probability.

$\endgroup$
  • 1
    $\begingroup$ Actually, for RSA, there's actually an infinite number of d values that work, in your example, 3, 13, 23, 33, 43, .... What's actually crucial is that the attacker can't guess/calculate any of them... $\endgroup$ – poncho Jul 25 '16 at 15:24
  • $\begingroup$ Yes and no. I updated my answer. There are indeed more numbers, but 13 is none of them. 23 However is. But in modulus 20 3 equals 23 and also 43 and 63 and so on. so there is only one possible value for d which is below the modulus Phi(N) and infinit more greater or lesser Phi(N) but with the same "value" though they are a different "number" $\endgroup$ – JRsz Jul 25 '16 at 16:18
  • 1
    $\begingroup$ 13 is one of them, since it's congruent to 3 mod Lambda(N). ​ ​ $\endgroup$ – user991 Jul 25 '16 at 16:23
  • $\begingroup$ @JRsz: if you claim that 13 doesn't work, that means you claim there's some message $M$ in $[0, 32]$ where $M^{13} \bmod 33$ is not a valid signature for $M$, that is $((M^{13} \bmod 33)^7 \bmod 33) \ne M$. Would you be so kind as to demonstrate such an $M$? There's only 33 possibilities, so it shouldn't be hard to find... $\endgroup$ – poncho Jul 25 '16 at 16:51
  • 1
    $\begingroup$ @JRsz: suffice it to say that $d = 13$ is a valid private key; you can have RSA public/private key pairs with $ed \ne 1 \bmod \phi(N)$ (and actually they're not rare in practice). As for how to format math, stackexchange (or at least this section of it) includes MathJax; you can write an expression in Latex (en.wikipedia.org/wiki/LaTeX) between \$'s, and the formatter will display it as Latex'ized output; so \$ a ^ b \oplus c \$ displays as $a^b \oplus c$. Latex is an amazingly powerful tool for writing mathematical expressions. $\endgroup$ – poncho Jul 26 '16 at 17:58

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.