No changes allowed! No forgeries accepted!
When you send a message, how can you be sure your message arrives unaltered? And how can you prove to the recipient that it was you that sent the message?
In cryptography, we often hear about the mnemonic “CIA” which stands for Confidentiality, Integrity, Authenticity. However, we are usually more concerned with the “IA” . We want the recipient to be confident that the message arrived unaltered ( Integrity ) and that it came from us ( Authenticity ).
Integrity
The best way to ensure integrity is to hash the message. A hash is a one-way function that will produce a fixed length output. For example a SHA256 hash produces a fixed 256 bit ( 32 byte ) output, no matter if the message is 100 bytes or 100 GBytes.
The beauty of the hash is that even if 1 bit in the message is changed, the calculated hash will be completely different. If we send the hash of the message along with the message, the receiver can also hash the message and compare their result with the hash that was sent. If the hashes match, the receiver can be confident in the Integrity of the message.
Authenticity
We need to prove to the recipient that the message came from us in a way that can’t possibly be duplicated by anyone pretending to be us. To do this we use a Digital Signing Algorithm. We usually sign the hash of the message rather than the message itself. The signature is made using our private key. The recipient uses the public key corresponding to this private key to validate that the hash was signed with our private key. Note the recipient gains no knowledge about our private key. They can just verify if the signature used our private key or not. If the recipient finds that the hash was signed with our private key, then they know it could only have come from us, as we are the only person that has the private key.
Digital Signature
The best solution to sign our message hash is to use Elliptic Curve Digital Signing Algorithm ( ECDSA ) as it is more efficient than older Digital Signing Algorithms.
Elliptic curves have the property that if you multiply a point on the curve by a number you end up with another point on the curve ( using modulo arithmetic ).
We choose any random number r as our private key. Depending on the elliptic curve chosen, we multiply a fixed ‘generator’ point K(xg,yg) by our random number r which gives us a point P(xp,yp). The point P(xp,yp) is then our Public Key. Note that r=P/K and this is unsolvable using present technology due to the intractability of the Elliptic Curve Discrete Logarithm Problem ( ECDLP). This means nobody can derive our Private Key. Make sure you use one of the published ECC curves ( e.g. secp256k1 ), as other unproven ECC curves may lend themselves to shortcuts in deriving the private key.
Elliptic Curve Digital Signature Algorithm (ECDSA)
To sign the hash of our message with ECDSA we need:
- EC Private Key, P
- A random number, k
- Our message hash, H
The reason we need a random number, k, for each signature is to prevent anyone from deriving our private key when they have a large number of signed hashes to work with. With the introduction of the random number, k, each signature is different, even if we are signing the same hash.
Note that Sony’s Playstation was famously hacked back in 2010 because they used the same value for k each time in their ECDSA signature, allowing derivation of their private key.
Elliptic Curve Digital Signature Verification
The receiver of the message has our public key. They have also received the hash of our message and can calculate the hash of the received message. They do not need to know the random number k used in the Digital Signing Process. They just need to determine whether the signature used our Private Key. It’s either Yes or No ; True or False. If they determine that the signature was signed with our Private Key, then they can be confident in the Authenticity of the message.
Typical Embedded Application Example
The Digital Signature verification and hashing of the received message may be difficult for many small microcontrollers that are used, for example, as IOT nodes. A good solution is to use the Microchip ATECC608B or similar. This is a tiny 50 cent part that the microcontroller can use to speed up hash calculation and ECDSA signature verification. Also the ATECC608B can securely store our Public Key – we don’t care if anybody knows our Public Key but it needs to be securely stored so that nobody can change it.
Then we can send any message or upload any code to our IOT device, knowing that it will reject anything if it cannot verify both the Integrity and Authenticity of the received message.
Python Script:
A relevant Python script ( digital_johnhancock.py ) of what we’ve covered in this blog can be found here. The script has examples of ECC key generation, hashing of message and ECDSA signature and verification.
For convenience, the script output is shown below:
John Hancock’s Message
There, I guess King George will be able to read that without his spectacles!
John Hancock’s Message ( Altered )
There, I guess King George will be able to read that with his spectacles!
Random Private key: d496a54bd8fdd68198f92761cf1e478a5586c5b1d151dbf8f82fd8b9f46f6d17
Public key: 26d1b283be1f877f69b94ab3da126e4be6fe605920b3de9afc3b70e018ec6428,739b2913f864cdef9a53cccc9786d854aa1893db6da4b9f29e1ac020fe23412c
message hash = 9db0bf88e1aa3853997579819118c31b6ae219b42f097a17a372d4ba82668779
altered message hash = d3d1a1100d39a6e5ff85eb90b36cc930aea75e265a0707e3633d58f65b5f3900
Message as sent
signed hash is verified => message Integrity and Authenticity confirmed
***************************************************************************
Message altered
signed hash failed to verify when message was altered
Signed with different Private Key
New Random Private key: 1f1f05afc046623aeee7d4ce607ed7f4d87c7f082ccd4c2b93aa0f7d3bcd084f
signed hash failed to verify with ‘forged’ signature using different private key
***************************************************************************