52 Things: Number 21: How does the CRT method improve performance of RSA?

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year.

The Chinese Remainder Theorem (CRT) states that if we have two equations:

$x = a (mod N)$ and $x = b (mod M)$, then there is a unique solution modulo MN iff $gcd(N, M) = 1$.   

In RSA we must perform a modular exponentiation with respect to a modulus of a thousand or more bits [1]. As a generic remark we could say that public key algorithms are slower compared to symmetric schemes. This characteristic might result to slow web servers-networks and improving efficiency during implementation (software algorithms) plays a crucial role in order to avoid performance problems.

We denote that the main operation in RSA scheme is the modular exponentiation $M = C^d (mod N)$. A modular exponentiation, at an improved state, can be performed using (h - 1) multiplications and (t - 1) squarings (t is the bit length of the exponent and h is the Hamming weight). The number of multiplications and squarings on average is $t + t/2 -1$. 

Further performance improvements can be achieved using binary exponentiation algorithms (e.g. right-to-left exponentiation) or window methods. For the latter we process w bits of the exponent at a time. For this method we still need t squarings but the number of multiplications reduces to t/w on average. Further improvements can be obtained by adopting sliding window methods [t/(w + 1) multiplications on average].  

To make the RSA exponentiation even faster we can perform some additional tricks depending on whether we are performing an encryption operation with the public key or a decryption operation with the private key. The CRT is used in the case of RSA decryption. Thus, we are considering a private key operation which means that we have access to the private key and hence the factorization of the modulus, $N = pq$. If we suppose we want to decrypt a message, then our goal is to calculate $M = C^d (mod N)$.

First we will compute M modulo p and M modulo q as follows:

$M_p = C^d (mod p) = C^{d (mod p - 1)} (mod p)$

$M_q = C^d (mod q) = C^{d (mod q - 1)} (mod q)$

This calculation requires two exponentiations modulo 512-bit moduli and 512-bit exponents because $p$ and $q$ are 512-bit numbers. This is faster than a single exponentiation modulo a 1024-bit number with a 1024-bit exponent.

Using the CRT we recover $M$ from $M_p$ and $M_q$ as follows: 

Compute $T = p^{-1} (mod q)$, store it with the private key.

M (the message) can be recovered from $M_p$ and $M_q$ as follows:

$U = (M_q – M_p) T (mod q)$,

$M = M_p + up$.  

[1] http://www.cs.bris.ac.uk/~nigel/Crypto_Book/book.ps (Chapter 15)

52 Things: Number 20: How are Merkle-Damgaard style hash functions constructed?

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. To finish the basic schemes section, we look at one of the most popular hash function designs...

A Merkle-Damgaard (MD) hash function is a hash function built by extending the domain of a collision-resistant compression function that preserves the collision resistance. This means we can take a small (and fixed) width compression function, prove it is secure and then use it to make a variable length hash function.  Whilst other methods for building hash functions exist, MD is by far the most "popular" (well, most frequently used at least!), with examples including MD5,SHA1 and SHA2. So, time to break those terms down:

Secure Hash Function?

Traditionally, a secure hash function $h$ should be:

• Pre-image resistant: given $h(x)$, it is hard to find $x$.
• Second pre-image resistance: given $x$, it is hard to find $y$ such that $h(x)=h(y)$.
• Collision Resistance: It is hard to find $x,y$ such that $h(x)=h(y)$.

If a hash function is collision then clearly it must be second pre-image resistant, so it is this [collision resistance] that we will focus on.

Compression Function

A compression function $f:\{0,1\}^n\times\{0,1\}^r\to\{0,1\}^n$ is a function that, as the name suggest, compresses $n+b$-bits worth of input into an $n$-bit output. As you might expect, a collision resistant compression function is a compression function that is collision resistant. So, it can be thought of as a fixed input length hash function, but what happens if we want our hash function to be secure for any input length?

The MD hash function construction

The MD construction provides a method for extending the domain of a fixed length compression function into a variable input length hash function. Using a compression function $f$ as above, we are going to use the $n$-bit value as our internal state, and feed in $r$-bits each iteration (it's quite common to set $r=n$). To do this, we begin with an initial value (IV) and split the message $M$ up into blocks of $r$ bits $M=M_0M_1\cdots M_m$, and then simply iterate the construction by setting:
$$S_0:=IV; \qquad i=0,\dots,m-1: S_{i+1}=f(S_i,M_i); \qquad h(M):=S_m$$
Confused? Perhaps the the following diagram will help:

Diagram of the MD construction (from Wikipedia)

The most important thing about the MD-construction is that if the compression function is collision resistant, then so is the overall construction (as proven by Merkle). This gives us a secure method for building hash functions out of a smaller, easier studied primitives.

Length Extension

You might notice that the diagram has an extra stage that my description didn't: the "finalisation" stage. This is to prevent length extension attacks. For an example, if $N$ is a single block (ie $N\in\{0,1\}^r$) if the attacker knows $h(M)=x$, then he can very easily calculate $h(M||N)$, because $h(M||N)=f(M,N)$. So, some form of finalisation function has to be used to break this relationship.

52 Things: Number 19: The Shamir secret sharing scheme.

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year.

The Shamir secret sharing scheme [3], is an algorithm invented by Adi Shamir to allow multiple parties to divide up a secret, such as a key, and when enough of those parts are combined the whole secret can be calculated.

To put it slightly more formally, if we have a secret $S$ and $n$ parties, we can divide $S$ into $n$ parts and distribute those to the various parties. The secret can be divided in such a way that a threshold $k$ can be set so that when $k$ parts of the secret $S$ are known then the whole secret can be calculated. If $k-1$ or less parts of $S$ are known then $S$ can't be calculated. This scheme is called a $(k,n)$ threshold scheme.

The best way to explain how this scheme is constructed is by means of an example. Assume we want to divide the secret $S=1425$ between $5$ parties ($n=5$) and need $3$ parts to be known to allow the secret to be computed. First we construct a polynomial[1] $f(x)$ of order $k-1 = 2$ with random coefficients (say $a_1= 64, a_2 = 112)$ and constant $S$.

$$f(x)= S + a_1 x + a_2 x^2 = 1425 + 64 x + 112 x^2$$

From this polynomial we can construct $n=5$ points, these points can then be distributed between our parties, one point per party.

$P_0=(1,1601),P_1=(2,2001),P_2=(3,2625),P_3=(4,3473),P_4=(5,4545)$

If we assume that we know $3$ of the $5$ points, we can compute $3$ Lagrange Polynomials[2], the sum of which, when multiplied by the associated $y_j$ values, gives $f(x)$ and therefore gives us the secret $S$. For example if we know

$$(x_0,y_0)=(2,2001), (x_1,y_1)=(3,2625), (x_2,x_3)=(5,4545)$$

Computing 3 Lagrange Polynomials gives

$$l_0 = \frac{x-x_1}{x_0-x_1}\frac{x-x_2}{x_0-x_2} = \frac{1}{3}x^2 - \frac{8}{3}x + 5 \\ l_1 = \frac{x-x_0}{x_1-x_0}\frac{x-x_2}{x_1-x_2} = -\frac{1}{2}x^2 + \frac{7}{2}x - 5 \\ l_2 = \frac{x-x_0}{x_2-x_0}\frac{x-x_1}{x_2-x_1} = \frac{1}{6}x^2 - \frac{5}{6}x + 1 \\ \sum_{j=0}^2 y_j l_j(x) = 112 x^2 + 64 x + 1425.$$

As demonstrated, this method works fine. However, the eavesdropper is able to glean quite a lot of information about the secret $S$; since in the above we have worked with rational arithmetic.However, if we instead work in a finite field (so the secret and the polynomial are defined over a field of size q) then if any two or less parties come together they can learn nothing about the secret. 

This is because for two such parties, say party one and party two, and any secret value S' from the field, there is always a degree two polynomial defined over the finite field which interpolates the three values (0,S'), (2,2001 mod q) and (3,2625 mod q).

[1] - http://en.wikipedia.org/wiki/Polynomial

[2] - http://en.wikipedia.org/wiki/Lagrange_polynomial

[3] - http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing

52 Things - Number 18: Draw a diagram (or describe) the ECB, CBC and CTR modes of operation

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year.

Week 18's task is to draw a diagram (or describe) the ECB, CBC and CTR modes of operation. Someone on Wikipedia has already gone a good job of drawing some nice diagrams, so for the purposes of this blog post I'll stick to explaining the rationale behind them, providing links where appropriate.

Modes of operation: the security provided by a block cipher applies to the encryption or decryption of a single fixed-length plaintext "block". When the encryption or decryption of messages longer than a block is required (as is typical), we use a mode of operation to link together the encryption of multiple blocks of plaintext. As we will see, the approach used to chain multiple blocks together is important.

Electronic Codebook (ECB) mode. (Encryption) (Decryption). ECB mode is the most straightforward approach---the plaintext is divided into m blocks, where each block is encrypted separately using the same key. The inherent problem with ECB mode is that repeated plaintext blocks produce the same ciphertext blocks. The best illustration of this problem is with the encryption of images, where repeated patterns in the original image reappear in the encrypted image. See, for example, the source image and the corresponding ECB encrypted image.

Cipher-block chaining (CBC) mode. (Encryption) (Decryption). CBC mode takes away the limitations of ECB mode. Each plaintext is XORed with the previous ciphertext before being encrypted, where the first plaintext block is XORed with a random initialisation vector (IV). The repeated patterns in the ciphertext blocks produced by ECB mode encryption are removed by the randomness and error propagation supplied through the XOR operation and initial IV. CBC is most commonly used mode in practice.

Counter (CTR) mode. (Encryption) (Decryption). Counter mode differs from ECB and CBC in that it in some sense it acts like a stream cipher. CTR mode generates a keystream by repeatedly encrypting a successive values of a "counter", which is initially set using an initialisation vector. Incrementing the counter for successive encryptions can be a simple as incrementing the initial counter by 1. Each encryption of the counter is, like a stream cipher, XORed with the next plaintext block to produce the next ciphertext block.

Further reading: some modes of operation guarantee the authenticity of a plaintext in addition to its confidentiality. See AEAD modes for more.