Cryptographic Primitive


When creating cryptographic systems, designers use Cryptographic Primitives (typically algorithms) as their most basic building blocks.

Because of this, Cryptographic Primitive are designed to do one very specific task in a highly reliable fashion.

Commonly used Cryptographic Primitives#

Cryptographic pseudo-random number generator#

Most of our focus is on Secure Digital communication which implies a Secure connection. At the heart of Secure Digital communication is random numbers. Random numbers are used for Key Generation and to provide unpredictability for otherwise deterministic processes. If the keys we use are predictable, then we would be susceptible to attack right from the very start. Random numbers are difficult to generate on a computer which is meant to behave in a consistent manner. Computers can gather random data from things like mouse movement or keyboard timings. But gathering that randomness (called entropy) takes significant time and involve additional processing to ensure uniform distributions. The process can even involve the use of dedicated hardware (such as a wall of lava lamps). Generally, once we have a truly random value, we use that as a seed to put into a Cryptographic pseudo-random number generator.

Beginning with the same seed will always lead to the same stream of numbers, but what's important is that the stream of numbers descended from the seed do not exhibit any pattern. In the Linux kernel, /dev/random and /dev/urandom, operate in this fashion: they gather entropy from multiple sources, process it to remove biases, create a seed, and can then provide the random numbers used to generate an RSA key for example.

Cryptographic Hash Function#

A Cryptographic Hash Function is meant to take an input (Message) of arbitrary size and produce a usually a fixed size output (Message-Digest). If we can find any two messages that create the same Message-Digest, that's a Cryptographic Collision and makes the Hash Function unsuitable for cryptography. Note the emphasis on "find"; if we have an infinite world of messages and a fixed size output, there are bound to be collisions, but if we can find any two messages that collide without a monumental investment of computational resources, that's a deal-breaker. Worse still would be if we could take a specific message and could then find another message that results in a collision.

As well, the Cryptographic Hash Function should be One-Way Hash Function: given a Message-Digest, it should be computationally infeasible to determine what the message is. Respectively, these requirements are called Collision Resistance Second Preimage Resistance, and Preimage Resistance. If we meet these requirements, our Message-Digest acts as a kind of fingerprint for a message. No two people (in theory) have the same fingerprints, and you can't take a fingerprint and turn it back into a person.

Message Authentication Codes#

Hashes sound great, but what good is sending a Message-Digest with a message if someone can tamper with your message and then tamper with the Message-Digest too? (Integrity)

We need to mix hashing in with the ciphers we have. For Symmetric Key ciphers, we have Message Authentication Codes (MACs). Message Authentication Codes come in different forms, but an HMAC is based on hashing. An HMAC takes the key K and the message M and blends them together using a Cryptographic Hash Function H with the formula H(K + H(K + M)) where "+" is concatenation.

Why this formula specifically? That's beyond this article, but it has to do with protecting the integrity of the HMAC itself. The Message Authentication Code is sent along with an encrypted message. Eve could blindly manipulate the message, but as soon as Bob independently calculates the Message Authentication Code and compares it to the Message Authentication Code he received, he'll realize the message has been tampered with.

More Information#

There might be more information for this subject on one of the following: