8

I'm learning asymmetric encryption in the use case of ssl/tls protocol.

I can understand that the public key (like a padlock) can encrypt (lock)
something and only the private key can decrypt (open) it.

But I just can't understand the other way around.
How can the public key verify digital signatures encrypted by CA's private key?

A lot of material says that a public key can't be used for decryption
(that's fine, if imagine the public key is a padlock, then that's for sure, you're not able to unlock things). Then how can public keys be used to verify digital signatures, given that it can't be used to decrypt?

I can understand that public keys/private keys are used for client server verification.
A server encrypts some secrets and ask the client to decrypt it, and compares
the results, then I can know whether you're the holder of the private key.

But as for digital signatures, it's a different story, because I think in the
digital signature, it doesn't contain the private key of the issuer, right?
Then how can the above verification can be done without private key decrypting?

8

The whole concept of trying to explain signatures with the terminology of encryption is flawed. It simply does not work. So let's unravel the whole thing, and this will require some formalism.


Formally, a cryptographic signature system consists in three algorithms:

  • KeyGen: takes as input a "security parameter" (say, the length of the key we want to obtain), and produces a new public/private key pair (Kp, Ks).

  • Sign: takes as input a message m and a private key Ks; output is a signature s.

  • Verify: takes as input a message m, a signature s and a public key Kp; output is a boolean (true on success, false if the signature is not valid).

The system is said to be sound if the algorithms operate as advertised (Sign produces signatures that Verify accepts, using key pairs produced by KeyGen). The system is said to be cryptographically secure if it is computationally infeasible to make forgeries: given a public key Kp, and without knowing Ks_, it should not be feasible (within the limits of existing technology) to produce a (m, s) pair such that Verify(m, s, Kp) = true. The definition implies, in particular, that the private key should not be computable from the public key alone, because otherwise forgeries would be easy.

None of the above says anything about how the algorithms work. Various systems have been invented, described and standardized.


RSA is a very well-known asymmetric algorithm, but that's wrong, because RSA is not one algorithm. RSA is the name for an internal operation called a trapdoor permutation, from which an asymmetric encryption system and a signature system have been derived. The RSA operation is, roughly, the following:

  • Let n be a big integer such that n = pq, where p and q are two big, distinct primes. Knowledge of p and q is the "private key". Let e be some (usually small) integer, called the "public exponent"; e must be such that it is relatively prime to both p-1 and q-1. Traditional values for e are 3 and 65537.

  • Given an integer x modulo n (an integer in the 0 to n-1 range), the RSA forward operation is computing xe mod n (x is raised to exponent e modulo n). This is easy enough to do. It so happens that this operation is a permutation of integers modulo n (each y modulo n is equal to xe mod m for exactly one x). The "magic" part is that, for some reason, nobody found an efficient way to compute the reverse operation (getting x from xe mod n) without knowing p and q. And that's not for lack of trying; integer factorization has been studied by the finest minds for more than 2500 years. When you know p and q, the RSA reverse operation becomes easy. The knowledge of p and q is thus called the trapdoor.

Now that we have this trapdoor permutation, we can design a signature algorithm which works the following way:

  • KeyGen: given a target length k, produce two random primes p and q of length about k/2 bits, such that p-1 and q-1 are both relatively prime to an a priori chosen e (e.g. e = 3), and n = pq has length k bits. The public key is (n, e), the private key is (p, q, e).

  • Sign: take message m, hash it with some hash function (e.g. SHA-256), and "turn" the hash output (a sequence of 256 bits in the case of SHA-256) into an integer y modulo n. That transform is what the padding is about, because the standard method (as described in PKCS#1) is writing the hash output with some extra bytes, and then interpreting the result as an integer (in big-endian convention in the case of PKCS#1). Once the hashed message has been converted through the padding into an integer y, the private key owner applies the trapdoor (the reverse RSA operation) to compute the x such that xe = y mod n (such a x exists and is unique because the RSA operation is a permutation). The signature s is the encoding into bytes of that integer x.

  • Verify: given a signature s, decode it back into an integer x modulo n, then compute y = xe modulo n. If this value y is equal to what would be the padding of h(m) (hash of message m), then the signature is accepted (returned value is true).

RSA encryption is another, distinct system, that also builds on the RSA trapdoor permutation. Encryption is done by raising an integer x to the exponent e modulo n; decryption is done by reversing that operation thanks to the knowledge of the private key (the p and q factors). Since such a system processes only big integers, and we want to encrypt and decrypt bytes, then there must also be some sort of conversion at some point, so a padding procedure is involved. Crucially, the security requirements for the encryption padding are quite distinct from those for the signature padding. For instance, the encryption padding MUST include a substantial amount of randomness, while the signature padding MUST include a substantial amount of determinism. In practice, the two padding systems are quite different.

When people looked at RSA signatures and RSA encryption, they found it fit to describe signatures as a kind of encryption. If you look at it, the RSA forward operation (raising to the exponent e) is done for RSA encryption, and also for RSA signature verification. Similarly, the reverse operation is done for RSA decryption, and for RSA signature generation. Furthermore, as a stroke of genius if genius was about confusing other people, some noticed that the RSA reverse operation can also be mathematically expressed as "raising an integer to some power modulo n", just like the forward operation (but with a different exponent). Thus they began to call that reverse operation "encryption". At that point, RSA encryption, RSA decryption, RSA signature generation and RSA signature verification are all called "encryption". For some weird psychological reason (I blame the deleterious effects of post-Disco pop music), many people still find it pedagogically sound to try to explain four different operations by first giving them the same name.


We described RSA; let's have a look at another, completely different algorithm called DSA. DSA does not use a trapdoor permutation. In DSA, we do computations modulo a big prime (traditionally called p) and modulo another, smaller prime (called q) which is such that p-1 is a multiple of q. p and q are known to everybody.

There is an operation-that-goes-one-way in DSA. Given an integer g modulo p (strictly speaking, in a specific subset of p called the subgroup of order q) and an integer x modulo q, everybody can compute gx mod p; however, recovering x from gx mod p is computationally infeasible.

While this somehow looks like RSA, there are crucial differences:

  • Here, the operation is raising g to exponent x, where the actual input is x (the exponent), because g is a fixed, conventional value.

  • This is not a permutation, because x is an integer modulo q and gx mod p is an integer modulo p, a quite different set.

  • This is certainly not a trapdoor: there is no "secret knowledge" that allows recovering x, except if you already know that exact value x.

However, a signature algorithm can be built on that operation. It looks like this:

  • KeyGen: the p, q and g integers are already fixed, and potentially shared by everybody. To generate a new private key, produce a random integer x between 1 and q-1. The public key is y = gx mod p.

  • Sign:

    • Given a message m, hash it, then convert the hash value into an integer h modulo q.
    • Generate a new, fresh, discard-after-use random integer k between 1 and q-1.
    • Compute r = gk mod p mod q (the exponentiation is done modulo p, then the result is furthermore reduced modulo q).
    • Compute s = (h + xr) / k mod q. The signature is (r, s).
  • Verify:

    • Hash message m to recompute h.
    • Compute w = 1 / s mod q.
    • Compute u1 = hw mod q.
    • Compute u2 = rw mod q.
    • Compute v = gu1 yu2 mod p mod q.
    • If v = r, the signature is valid; otherwise, it is not.

Now good luck with trying to describe that as some sort of "encryption". If you find that it is unclear what is being encrypted here, it is because nothing is encrypted here. This is not encryption.


However, there is an hand-waving conceptual description of signatures that works with both RSA, DSA, and many other signature algorithms. You can view signatures as a specific kind of authentication.

In authentication, one person (the prover) demonstrates his identity to another (the verifier). The prover does this by performing some action that only that person can do, but in such a way that the verifier can be convinced that he witnessed the genuine thing. For instance, a very basic authentication system is called "show-the-password": the prover and the verifier both know a shared secret (the "password"); the prover demonstrates his identity to the verifier by uttering the password.

For signatures, we want something a bit more complex:

  • The signature is asynchronous. The signer acts once; verification is done afterwards, possibly elsewhere, and without any further active help from the signer.
  • The verifier should not need to know any secret. The signature should be convincing for everybody.
  • By signing, the signer shall not reveal any secret. His private key should not be consumed (yes, I know there are signature schemes that work with consumption; let's not go there).
  • The signature should be specific to a given message m.

One rather generic structure for authentication schemes is based on challenges: the verifier sends to the prover a challenge, that the prover can answer to only thanks to his knowledge of his secret.

If you look at RSA, then you can see that it is a challenge-based authentication mechanism. The challenge is the hashed-and-padded message. The signer demonstrates his mastery of the private key by applying the RSA reverse operation on that challenge, something that only he can do; but everybody can apply the RSA forward operation to see that the challenge was indeed well met.

If you look at DSA, then you can again see a challenge-based authentication mechanism. The signer first commits to a secret value k by publishing r; then the challenge is (again) the message h combined with the commitment r; the signer can answer to that challenge only by using his private key x. In DSA, the signer has a permanent private key x, produces a one-shot private value k, and demonstrates his knowledge of x/k mod q. (This does not leak information on x because k is used only once.)


Summary: signature algorithms are not encryption algorithms, and explanations of signatures based on encryption can only be, at best, utterly confusing. A much better explanation is by showing that a signature algorithm is, in fact, a specific kind of authentication mechanism, by which the signer demonstrates his knowledge of the private key in response to a synthetic challenge that involves the signed message.

This authentication is convincing for bystanders as long as the said challenge is sufficiently well specified that it is provably not cooked in the advantage of the signer. In RSA, it is the result of a deterministic hashing and padding (and the padding takes care to avoid the values where the RSA reverse operation becomes easy). In DSA, the challenge is computed from a prior commitment of the signer.

Indeed, any zero-knowledge authentication system can be turned into a signature mechanism by making it non-interactive: since a ZK system works by commitments, challenges and responses to these challenges, you can make the signer compute all his commitments, hash them all along with the message to sign, and use the hash value as the challenges. This does not mean that a ZK proof lurks within all signature algorithms; however, if you find that DSA kinda looks like that, well, there are good reasons for that.

2

Digital signature includes two steps:

a) Message digest evaluation. The main purpose for evaluating a digest is to ensure that the message is kept unaltered; this is called message integrity.

b) Digest signature. A signature is in fact an encryption using the issuer’s private-key. Included in the signature is also the hashing algorithm name used by the issuer. The issuer’s public-key is also appended to the signature. Doing so lets anyone decrypt and verify the signature using the issuer’s public-key and hashing algorithm. Given the properties of public-key encryption and hashing algorithms, the recipient has proof that:

i) The issuer’s private-key has encrypted the digest;

ii) The message is protected against any alteration.

Along with an entity’s or individual’s public key, digital certificates contain information about the algorithm used to create the signature, the person or entity identified, the digital signature of the CA that verified the subject data and issued the certificate, the purpose of the public key encryption, signature and certificate signing, as well as a date range during which the certificate can be considered valid.

Steps for Decrypting and verifying the signature of a message

 Steps for Decrypting and verifying the signature of a message

enter image description here

however, digital signature necessarily, does not only this type:

Some digital signature algorithms:

  1. RSA-based signature schemes, such as RSA-PSS
  2. DSA and its elliptic curve variant ECDSA
  3. ElGamal signature scheme as the predecessor to DSA, and variants Schnorr signature and Pointcheval–Stern signature algorithm
  4. Rabin signature algorithm
  5. Pairing-based schemes such as BLS - allows a user to verify that a signer is authentic. The scheme uses a bilinear pairing for verification and signatures are group elements in some elliptic curve
  6. Undeniable signatures - It has two distinctive features: The verification process is interactive, so that it is impossible to verify a signature without the signer's participation.A disavowal protocol, which is a cryptographic protocol that allows a verifier to distinguish two cases: (a) the signature is not valid; (b) the signer is giving improper responses.
  7. Aggregate signature - a signature scheme that supports aggregation: Given n signatures on n messages from n users, it is possible to aggregate all these signatures into a single signature whose size is constant in the number of users. This single signature will convince the verifier that the n users did indeed sign the n original messages.
  8. Signatures with efficient protocols - are signature schemes that facilitate efficient cryptographic protocols such as zero-knowledge proofs or secure computation.
  • Full white paper here (pages 6-7): cgi.com/files/white-papers/cgi_whpr_35_pki_e.pdf – StackzOfZtuff May 2 '15 at 10:14
  • From section b), I see one sentence: "The issuer’s public-key is also appended to the signature. Doing so lets anyone decrypt and verify the signature". That means public key can be used for decrypting things encrypted by private key???? – Aaron Shen May 2 '15 at 12:21
  • yes public key is public key(every one must know that),here we talk about digital signature(DS) that is used for providing integrity not confidentiality,if we need confidentiality another layer of encryption/decryption must be applied to the message, we just sign a message that show message has not been tampered by man in the middle and we can verify the sender(Alice). – Ali May 2 '15 at 12:50
  • RSA signatures are not encryption using the issuer’s private-key. See this answer. – user49075 May 2 '15 at 21:04
  • This is wrong. Signatures in general are not encryption with a private key. – cpast May 2 '15 at 22:11
0

For RSA encryption, the public and private keys can both be used for encryption or decryption. The only difference between them is that you keep one key private while you advertise the other.

What your text is referring to is that, when you're encrypting a message to send to someone, you use their public key to encrypt it. You, of course, couldn't use their private key because it's private. This secures the message as only they have their private key.

But both keys work for the cryptography operations. So for digital signature, the author encrypts their hash using their private key and you validate by decrypting with their public key.

This is not true for all asymmetric encryption algorithms.

  • This is only true in RSA. It is absolutely false in general; in many schemes, the private key is an integer k and the public key is a group element g^k (where g is a standardized generator), so the private key a) can't be used for encryption and b) makes it trivial to derive the public key. – cpast May 2 '15 at 22:10
  • Thx @cpast. Updated answer to be more specific. – Neil Smithline May 2 '15 at 22:17
  • I don't think that is true for RSA. You generate a public key after computing the private one. If you announce the private you are screwed. – BrunoMCBraga May 2 '15 at 22:29
  • @returnFromException In principle, RSA private and public exponents are interchangeable. It's only in practice that they aren't (because the public exponent is traditionally always 65537). The private key file contains some additional info for speed reasons, but that's an implementation detail and you can do RSA with just the exponents. – cpast May 2 '15 at 22:30
0

A digital signature is best understood by completely decoupling it from encryption. A signature algorithm generically consists of two operations, SIGN and VERIFY. SIGN takes a message and a private key and produces a blob of data known as a "signature;" VERIFY takes a message, a signature produced by SIGN, and a public key and outputs whether the signature is a valid signature for that message.

Here's an example of a signature mechanism not involving anything resembling encryption; it's known as the Digital Signature Algorithm:

  • The signer first picks some parameters: a large prime number p, a hash function H, a prime number q which is at most as long as the output of H, and a generator g for which g^q = 1 (mod p) and g^k != 1 (mod p) if 0 < k < q (i.e. q is the smallest positive number where g to that power is 1). These parameters can be shared between different users; in fact, for the closely related ECDSA, there's a single choice of parameters that just about everyone uses.
  • The signer's private key consists of an integer x < q. Their public key is y = g^x (mod p).
  • To sign a message, they do the following:
    • Create a random number k between 1 and q-1 inclusive. k must be random, and must be different for every message you sign with the same key. Compute r = (g^k (mod p)) (mod q).
    • Compute s = k^{-1} (H(m)+xr) (mod q). The signature is (r,s).
    • If r or s is zero, pick a different k and start over.
  • To verify, do the following:
    • Compute w = s^{-1} (mod q).
    • Compute u = (w)(H(m)) (mod q) and v = (w)(r) (mod q).
    • Compute t = ((g^u)(y^v) (mod p)) (mod q).
    • The signature is valid if and only if t=r.

As you can see, this doesn't exactly look like an encryption. Extracting t requires already knowing r (which it is supposed to be equal to). It works because the signer, knowing x, can create two numbers r and s with a certain relationship that can be verified by someone knowing g^x. There's nothing that you can get out of the signature except r, which is already in the signature; this algorithm (unlike textbook RSA or RSA with PKCS 1.5 signature padding) doesn't give you the hash of the message from the signature. Verification takes the hash as an input, but it then feeds it into a complex calculation to see if two other things are equal.

And that's all a verification is. Signing produces a bunch of data that is claimed to have some relationship to a particular message. The relationship doesn't need to be as simple as "apply this operation to the signature and you'll get the hash of the message;" it can be a fairly complicated thing like in DSA.

  • Why the downvote? – cpast May 3 '15 at 3:47

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.