15 Matrix methods

 

This chapter covers

  • Ciphers using multiplication by a matrix of integers, or a matrix of ring elements
  • Ciphers using multiplication by large and small integers
  • Solving linear congruences
  • Constructing rings and invertible matrices

Matrices are a tool well-suited for cryptography because they can encipher arbitrarily large blocks of text in one operation. Typically, each block in the message is treated as a vector of bytes, meaning integers modulo 256.

15-unnumb-1

When Sandra uses a matrix to encipher a message, Riva must use the inverse of that matrix to decipher the message. Let’s begin the discussion of matrix methods with a technique for inverting a matrix.

15.1 Inverting a matrix

There are several ways of solving a matrix equation such as C = AP when there is known plaintext. Since Emily knows P and C, but does not know A, she can solve the equation for A by right-multiplying it by P' to get CP' = APP' = A. So Emily needs to invert P. Riva does the opposite. She knows A, but does not know P, so she needs to invert A. Left-multiplying the equation by A', she gets A'C = A'AP = P.

15.2 Transposition matrix

15.3 The Hill cipher

15.4 Hill cipher, computer versions

15.5 Large integer multiplication

15.5.1 Multiplying and dividing congruences

*15.6 Solving a linear congruence

15.6.1 Reducing a congruence

15.6.2 Half-and-Half Rule

15.6.3 Laddering

15.6.4 Continued fractions

15.7 Large integer ciphers

15.8 Small integer multiplication

sitemap