Saturday, 4 May 2019

Digital Signatures

You know, I must be getting old because I was about to open this post with the words 'back in the day'. The thing is though that I'm not really all that sure if signatures are used as much as they used to be used. These days when it comes to banking transactions we have Personal Identification Numbers, but when I was younger what we had were this little squiggles that we would put at the bottom of a paper as a way so saying either 'I wrote this' or 'I assent to this'. Actually, having been over seas, I have noticed that for some reason when I pay using a credit card I still have to sign the little piece of paper that is spat out of the machine as a means of confirming that I assent to this transaction.

However the problem is that signatures can be forged. The other problem is that when somebody signs something the signature might not be exactly the same, and depending on the person who is requesting the signature, they might either make you jump through hoops to prove that you are who you say you are, or they might handover $1000.00 to the guy who stole your card because, well, they are simply too lazy to check.

So, how does that apply to computer security you ask? Well, we have signatures in the digital world as well, known as digital signatures, and they work similarly to the encryption techniques we looked at previously. However, there is a slight difference. Were a message is encrypted using a public key, and decrypted using a private key, the digital signature is signed using a private key, and verified using a public key. Basically, like the signature that I carried on about above, a digital signature is a means of verifying that you have assented, or sent, something. In fact, that pin number you have to remember for your bank card could quite well be the private key that is used to generate a digital signature that authenticates the purchase, or withdrawal.

In fact, this diagram from the lecture notes is a good explanation of how it works:

Like real world signatures, only the person to whom the signature relates should be capable of actually generating the signature. Another thing is that the document that is signed is usually placed into the signature in the form of a hash as another means of verification.

There are a few ways of generating a digital signature, but we will only look at two of them: RSA and El-Gamal (though this will be the theoretical math component - I'll run through all of what we have done here in a more practical way in a later post, using the Linux terminal of course). Of course, the process in generating a signature is as follows:

  • Sender sets the parameters and generates the public and private keys
  • Sender uses the private key to sign the message
  • Receiver uses the public key to verify the message

RSA Signatures

So, we have a situation where Captain Ed Mercer wants to send an order to the crew of the Orville. Now, as a part of the protocol Ed must sign all of the orders using his digital signature. So, first of all, Ed picks two prime numbers p=17 and q=11. He then generates n by the following method: n=p*q = 187. Ed then calculates φ(n) = (p-1)*(q-1) = 160. Finally Ed picks a number e that is co-prime with φ(n) and that 1 <e < φ(n). Being co-prime, as we remember, means that GCD(φ(n),e) = 1, so Ed picks e=7.

Now that we have all the numbers, Ed sends the public key n and e to the crew of the Orville. Ed then generates the private key d, where d*e = 1 mod φ(n). In this instance d=23, which he retains.

Ed signs the message m=33 as follows:

s = md mod n = 3323 mod 187 = 11.

Now that Ed has his signature, he signs his order and sends it to the crew of the Orville.

Commander Kelly Greyson, who happens to be Ed's 2IC, receives the signed message, and must now verify the message. She does so as follows:

m' = se mod n = 117 mod 187 = 88.

So, the order has been verified, so Kelly passes the order on to the crew.


Well, it turns out that central command has decided that using RSA for a signature isn't all that secure, and since they are a military outfit, they decided that they will use El-Gamal instead.

So, in this instance, Ed the prime p=11 and the generator g=2, and the private key parameter x=8. Ed then generates the public key y using the following:

y=gx mod p = 28 mod 11 = 3.

Now that Ed has the public key, he sends it through to the Orville.

For the private key, Ed needs to select k where 1 ≼ k  ≼ p-2 where k is co-prime with p-1, or GCD(k,p-1) = 1. Ed decides that k=9 satisfies this criteria. However, it isn't over yet because Ed now needs to generate r as follows:

r=gk mod p = 29 mod 11 = 6

And then sign the message m=5:

s= k-1 (m - x*r) mod (p-1) = 9-1 (-43) mod (10) = 3.

Now that he has the signature s=3, he sends the order to the Orville.

Once again, Kelly receives the order and must verify that it comes from Ed. She does so as follows:

v = gm mod p = 25 mod 11 = 10
w = yr * rs mod p = 38 * 63 mod 11 = 10.

Now, to verify the message, v must equal w, ie: v=w. In this case v=10 and w=10, so the signature has been authenticated.

Now, the reason this provides integrity is because the message m and the signature s are sent together. Now, if the message fails but the signature is okay, then the message has been tampered with, however if the message is okay, but the signature fails, then the signature has been tampered with.

Another thing that signatures provide is non-repudiation. Basically since you are the only one who has the private key, then if you sign a message and send it out you can't then go back on your word. This makes it better than a physical signature, particularly with regards to the concerns over such a signature being forged - in this instance the only way for somebody to forge your signature is to steal your private key.

However, it should be pointed out that we shouldn't be using the same key pair to sign and authenticate a message, and also encrypt the said message. The reason for this is that our hacker could trick us into decrypting a message. For instance, if our hacker sends us a message that they intercepted and requests that it be signed, since we are signing with the private key, we might also be decrypting the message, which means that when we return the message it will actually be plain text.

Digital Certificates

These are certificates that are issues by a trusted third party, such as Verisign. The certificate basically guarantees your authenticity, and in fact are used on a lot of websites. Basically if the certificate is valid, then your browser will allow you to access the site, but if it isn't valid then it was kick up a stick and refuse access (though you can always override it, but not always).

The digital certificate must have the name of the holder, and a public key, but to be helpful it should also be signed by the trusted third party. Beyond that the certificate can pretty much hold anything, though if it has too much information on it, then if any of that information changes a new certificate needs to be issued.

Creative Commons License

This work by Digital Signatures is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Based on a work at This license only applies to the text and any image that is within the public domain. Any images or videos that are the subject of copyright are not covered by this license. Use of these images are for illustrative purposes only are are not intended to assert ownership. If you wish to use this work commercially please feel free to contact me

No comments:

Post a Comment