A digital signature is verified using an algorithm that takes three inputs: the message, the digital signature (message encrypted with private key)* and the public key. If the public key is used to verify the original message to the signature, than logically the algorithm must contain a method to tranform the public key into the private key, so that verification may take place. This would imply a method to get the private key from the public key, which defeats the purpose.

Can someone explain to me how the algorithm is implemented to avoid this problem?

*as explained by Mike below, the signature is actually a digest of the message encrypted with the private key


I think "logically" was a poor choice of words. I meant to say it seemed "intuitive" that the only way to decrypt the signature would be to convert the public key to the private key. Obviously this would compromise the confidentiality of the private key and "defeat the purpose." In light of that I was trying to understand how the public key verifies the signature without conversion to private key. I need help with the math because asymmetry is not intuitive.

Digital signatures aren't the same as key exchange. As far as I can tell, in a broad sense, the former uses the public key to "decrypt/verify" the message, while the latter uses the private key to "decrypt" the exchanged symmetric key (which was "encrypted" using the associated public key).

  • 1
    Can't wait to hear why this one was downvoted – RamBam Jun 29 '16 at 21:12
  • 3
    Not the downvoter but probably because your logical deduction was wrong. There isn't a method that transforms the public key into the private key. I'd suggest reading up on RSA Encryption as it will be a good intro on how asymmetric encryption works. In fact, if you could get the private key from the public key, there would be a serious problem – d0nut Jun 29 '16 at 21:18
  • The keys are mathematically related but there isn't a way to get from one key to another directly. en.wikipedia.org/wiki/Public-key_cryptography This could help – d0nut Jun 29 '16 at 21:24
  • @iismathwizard I was implying that the public key couldn't be turned into the private key because it would "defeat the purpose." I was asking for an explanation for how the algorithm verifies without doing so. I know how rsa works for key exchanges but asymmetric excryption is used completely differently in digital signatures. I'll have to reword my question – RamBam Jun 29 '16 at 21:40
  • 2
    Another reason for the downvotes may be your lack of research. Googling the question title seems to return many fine answers to your question. – Neil Smithline Jun 30 '16 at 0:49

I will try to simplify as much as possible

The difficulty comes from some "hard to compute" operations in maths. For example, some operations are two-ways easy to compute. If I compute 5*6 = 30, it is easy to calculate x*6 = 30 (30/6 = 5).
Some other operations are only one-way easy to compute: 5^6 = 15625. Ok but if I give you x^6 = 15625... how the fuck do you manage to find x? You have to try with 1, 2, 3, 4, 5 (ho this is this one).
So to compute 5^6 you have one operation. To compute 15625^(1/6) you have five operations.
In asymmetric cryptography, we talking about this kind of problematic.

I propose you a very simple view about the problem:

Let's say that x^y means "x power y"
You know that in maths (x^y)^z == x^(y*z)
you know what a modulus is (13 % 7 == 6)
And you know that x^1 == x

In asymmetric cryptography you perform operation with a very huge modulus N. And your private key A and your public key B are two huge numbers designed to be equal to 1 when they are multiplied.
So when you want to encrypt a clear message M, you perform M^B % N = C which is a very huge number.
When you want to sign a message M, you compute M^A % N = S which is a very huge number too.

When you want to decrypt C, you perform C^A % N = (M^B)^A % N = M^(B*A) % N and I have said B and A are designed to be equal to 1 (with the big modulus N) so M^(B*A) = M^1 = M

When you want to check the signature, you perform S^B = (M^A)^B = M^(A*B) = M^1 = M

Beauty is that, even if I know M, B and S, and I know that S == M^x and B*x == 1 ...it is absolutely awful to try to find x, especially when modulus are involved.

Try a little exercise: imagine a kind of world in modulus 13. Each time you reach 13, you go back to 0. So you count as: 1,2,3,4,5,6,7,8,9,10,11,12,0,1,2,3...
5+5 = 10
5+7 = 12
5+9 = 1
5+11 = 3
If I say that 7^x % 13 = 4 (one operation to compute that)...find x.
By trying every possibilities, you will see that you have absolutely no clue about being near to the solution or not
For example, 7^4 % 13 == 9 and 7^8 % 13 == 3 ... do you have any idea if x is between 4 and 8 ? this operation is called discrete logarithm. And this is very painful to compute. With very huge numbers, this become a nightmare.

SO the response is YES with knowing a signature, the original message and the public key, you can know how to compute the private key (you can know what calculation has to be made). In fact, only the public key is enough to know what calculation is needed.
But no, you will not reach the result before you die ... many many times

| improve this answer | |

The piece that seems to be missing is that, for some public key crypto algorithms, the public and private keys are cryptographic inverses of one another. So, encrypt with a public key, decrypt with the private key; encrypt with a private key, decrypt with the public key.

So, if I encrypt a message, or more likely, a message digest, with my private key, anyone can decrypt it with my public key. There's no confidentiality, but the message could only have been encrypted by someone with access to my private key.

You can trust such a digital signature exactly as much as you trust that a) I have not allowed my private key to be compromised and b) you trust that you really have my public key and not Eve's.

| improve this answer | |

Where you are missing is the second input to the algorithm.

To sign a message, you don't encrypt the message itself, but rather, you create a message digest using a cryptographic hash function. This digest is then encrypted with your private key, and then sent along with the message.

To verify, the recipient computes the same digest from the message, decrypts the signature with your public key, and compares the two digests. If they are identical, then that proves the message came from you because it was encrypted with your private key and decrypted with your public key.

The reason signing is considered the opposite of encryption is because when encrypting the message, you the sender use the recipient's public key to encrypt and the recipient uses their own private key to decrypt.

To sum up:

  • Encrypt with the other's public key
  • Sign with your private key
  • Decrypt with your private key
  • Verify with the other's public key
| improve this answer | |
  • I wasn't sure if the signature was applied before or after the hash so I left that out. Thanks for clarifying. Also thanks for verifying my thoughts on signatures vs. key exchange/encryption. Do you know the details of how the public key decrypts the signature? – RamBam Jun 29 '16 at 22:25
  • 2
    You could encrypt the message itself, and it would be just as valid a digital signature. We don't do that because public key crypto is computationally expensive. – Bob Brown Jun 29 '16 at 22:53

It is not feasable to get private key from the public key. Why? Because You should find two prime numbers which are terms of a big number and this is a really time consuming computation

| improve this answer | |
  • When you give a negative score you should comment why. This way people learn from their mistakes. – MSD561 Jun 30 '16 at 21:13

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.