Continuing on from my previous walkthrough on public-key cryptography, I also wanted to learn how you can sign documents using the private key, verifying the signature with the public key.
The concept here is verification – was this message sent by someone with access to a specific private key. For example, consider Paul Revere, waiting for a message from Robert Newman. What if somehow a British spy knew that Paul was expecting an email from Robert, and wanted to fool Paul by pretending to be Robert. For Paul to be sure the message is legitimately from Robert, it doesn’t matter whether the message was encrypted with Paul’s public key – after all, anyone could have the public key. To be verified, the message must be signed by Robert’s private key. Remember, this isn’t about encryption – the signature is “in the clear” – anyone can see it.
So we need a new public/private key pair for Robert Newman. Since I’ve already gone through the effort of explaining how to calculate them last time, I’ll just provide you with the numbers themselves this time:
- n is 221
- e is 191
- d is 383
To sign text, you use the private key to create a cryptographic signature. Robert is following up from the previous email, he wants to tell Paul how many boats the British are rowing across the river. So he wants to send the message: “5”.
- m is 5
The signature s is calculated by the formula: m^d % n
Remember, d is part of the data that Paul has kept private. Only he knows what d is.
m^d is 5^383 which is:
5075883674631298446548049111661087093647237699402191163212120642478953395778598947864814858111568572459329182115501791693204142684887253405561412715352359556877432999471390133765317641336487613681905654361561422102765594427495506046899009788830881007015705108642578125 That number modulo n (i.e. 221) is: 177
- s is 177
So when we send this communication to someone, we send both the message itself “5” and the signature: “177”
Verifying a Signature
To verify the signature, we want to see that s^e mod n == the message. Remember, e is part of the public key.
s ^ e is 177 ^ 191 or:
2306183577149085201596305325596159226547118569300925189229389857203796357207862044982857315199283790476827017647730527617852804108867519414430432193245871218986251822073578619863609881193149770246390198636414790783766688663380790017386360674016112360841035988551564172980501137196833264766988401289008585444215905916895724644294397505093631160639335548542153668065643942589783649622290133120663019258868021033347931734637973384273 And that number modulo n (i.e. 221) is:
And that’s how Paul can know that this message was sent by Robert Newman.
Bringing these things together
In the original scenario, Robert Newman wants to tell Paul that the British are coming by sea. So he encrypted the code number: “3” with Paul’s public key, knowing that only Paul can decrypt it. As you saw from the encryption demonstration walkthrough, the actual message that Robert sent was the value “70”.
And realistically, we’d want Robert to sign that message “70” with his private key. This provides the best of both worlds – only Paul can decrypt the message, and it could only have been sent by Robert.
So what is the value of the signature for a message with the value 70? I leave that as an exercise for you.