Introduction

Similarly as digital signatures, Message Authentication Codes provide message integrity and message authentication. When Alice generates a MAC and sends the message and MAC to Bob, Bob verifies that the message has integrity by calculating the MAC himself. He also authenticates the message, because only Alice could have generated the MAC.

Unlike digital signatures they do however not provide nonrepudiation, since all involved parties share the secret key \(k\). MAC's can be implemented using cryptographically secure hash functions (HMAC) or symmetric block ciphers like AES.

A MAC consists of a set of messages \(X\), a finite set of hash values \(Y\) and a key space \(K\). Each key \(k\) specifies a hash function \(h_k: X \rightarrow Y\). Let \(n=|X|\) and \(m=|Y|\) and \(l=|K|\).

Each MAC must have a property known as computation resistance: Even if an attacker knows \(n\) text-hash pairs \((x_n, h_k(x_n))\), it remains computationally unfeasible to find a valid MAC for a message without knowledge of the used key \(k\).

The goal of an attacker is to compute a valid MAC for a message \(x \in X\) without knowing the secret key \(k\). There are a series of different …

Continue reading

Introduction

This blog post will introduce cryptographic hash functions. We are going to discuss the Merkle-Damgård construction which underlies many hash functions that were and are used nowadays. The MD4, MD5, SHA-1 and SHA-2 hash families are all functions that built on top of the Merkle-Damgård construction. Then we will introduce an alternative construction that was popularized during the publication of Keccak (SHA-3): The Sponge construction.

But what are cryptographic hash functions good for?

The general idea is to apply a unique and stable fingerprint to each input data \(x\). This fingerprint is computed with a hash function \(h\) and the resulting value \(y = h(x)\) is called a message digest. The size of \(h(x)\) is fixed, even though the input data \(x\) may have arbitrary length. The intended task for \(h\) is to assign a unique identification code \(h(x)\) for each input \(x \in X\) where \(X\) is the set of all possible inputs. The avid reader might realize that this task is impossible, since there is no bijective function that connects an infinite large input set \(X\) with fixed sized output set \(h(x)\). Thus there must be collisions: For some inputs \(x_1 \neq x …

Continue reading

Introduction

All sources for this blog post can be found in the Github repository about large primes. The most recent version of the sources may only be found in the Github repository.

It has been a long time since I found the energy to write a new blog post. In this article, I am going to dig into a interesting area of cryptography: The task to find large prime numbers. We hopefully are all familiar with the concept of prime numbers. Prime numbers are integers \(p\) which are dividable only by \(p\) itself and \(1\). But why is it necessary to find large prime numbers in the area of cryptography?

One of the first asymmetric cryptosystems invented was RSA (1977). As all public key algorithms, the security of RSA depends on the existence of a one-way function.

In the case of RSA, the one-way function is built on top of the integer factorization problem: Given two prime numbers \(p,q\in \mathbb{N}\), it is straightforward to calculate \(n=p \cdot q\), but it is computationally infeasible to reverse this multiplication by finding the factors \(p\) and \(q\) given the product \(n\). Even when the primes \(p\) and \(q\) are …

Continue reading