I Love Crypto … Because It Can Perform Magic!

I Love Crypto … Because It Can Perform Magic!

How A Simple Theorem Secured The Internet: Fermat’s Little Theorem with Binary Field Arithmetic

I love cryptography as I can do magic. One little piece of magic is a little theory that is so powerful that it has secured the Internet … Femat’s Little Theorem. It was first stated by Pierre de Fermat on 18 October 1640 and defines that:

and where p is a prime number. For example, if we have a of 531 and p of 997, in Python we can compute:

>>> pow(531,997,997)
531

Also, there is a special case of this theorem, and where a and p do not share a factor (they are co-prime). With this, we get:

For example, with a=531 and p=997, a and p do not share a factor (gcd(a,p)=1), thus:

>>> pow(531,997-1,997)
1

In fact, this is the basis of the RSA method, and allows us to create a public key pair. So, this simple theorem has basically allowed us to encrypt data, and create a trustworthy Internet for over four decades.

Let The Magic Begin: Finite field binary multiplication

In cryptography, we can have large numbers which are operated on within a finite field. This finite field will constrain the size of the results of operations. In this case, we will use a finite field of 2²⁵⁶ and multiply two 256-bit values (little endian format) within a finite field of 2²⁵⁶ — this is known as GF(2²⁵⁶). As it can be difficult to check the result, we will prove Fermat’s little theorem, and which defines that a^p (mod p)=a. For this, we will multiply a by itself p times, and where we should end with a.

With the multiplication A times B with binary field arithmetic, we defined that we have a W-bit architecture, and where W is a multiple of 8. With this, the bit on the right hand side is defined as the least significant bit (little Endian). We then use simple operations of bitwise EX-OR and AND, shift right and shift left. In this case, we will use W=256, and where we have 32-byte values to multiply. This is defined as operating with GF(2²⁵⁶).

Little-endian

A Little-endian format of 0x2301 will be stored in memory with “01” and then “23” as byte values. Thus in our hexadecimal format, a value of 3 in decimal would be represented as “0x0300000000000000000000000000000000000000000000000000000000000000”. So let’s try 3 times 5:

func main() {
d1, _ := hex.DecodeString("0300000000000000000000000000000000000000000000000000000000000000")
 d2, _ := hex.DecodeString("0500000000000000000000000000000000000000000000000000000000000000")
 d3 := binaryFieldMul(d1, d2)
 fmt.Printf("\n\n3= %x\n", d1)
 fmt.Printf("5= %x\n", d2)
 fmt.Printf("3 times 5= %x\n", d3)
}

For this we get:

3= 0300000000000000000000000000000000000000000000000000000000000000
5= 0500000000000000000000000000000000000000000000000000000000000000
3 times 5= 0f00000000000000000000000000000000000000000000000000000000000000

And which is correct as 0xf as the least significant byte gives us a value of 15. If we now try 4 times 5, we get:

4= 0400000000000000000000000000000000000000000000000000000000000000
5= 0500000000000000000000000000000000000000000000000000000000000000
3 times 5= 1400000000000000000000000000000000000000000000000000000000000000

And where 0x14 is 20 in decimal. If we try, 0x17 (23) times 0x35 (53) we get 0xdb03:

A= 1700000000000000000000000000000000000000000000000000000000000000
B= 3500000000000000000000000000000000000000000000000000000000000000
A times B= db03000000000000000000000000000000000000000000000000000000000000

Overall, to constrain the range of our values, we perform the multiplication over a finite field by performing a modulo of an irreducible polynomial of f(X)=X²⁵⁶+X¹⁰+X⁵+X²+1. This is the equivalent to performing a (mod p) operation within integer operations. For multiplication of two 2,048 bit values (256 bytes), we will use the code at [1][here]:

package main
// https://github.com/coinbase/kryptology/blob/master/pkg/ot/extension/kos/kos_test.go
import (
	"crypto/rand"
	"fmt"
)
func binaryFieldMul(A []byte, B []byte) []byte {
 // multiplies `A` and `B` in the finite field of order 2^256.
 // The reference is Hankerson, Vanstone and Menezes, Guide to Elliptic Curve Cryptography. https://link.springer.com/book/10.1007/b97644
 // `A` and `B` are both assumed to be 32-bytes slices. here we view them as little-endian coordinate representations of degree-255 polynomials.
 // the multiplication takes place modulo the irreducible (over F_2) polynomial f(X) = X^256 + X^10 + X^5 + X^2 + 1. see Table A.1.
 // the techniques we use are given in section 2.3, Binary field arithmetic.
 // for the multiplication part, we use Algorithm 2.34, "Right-to-left comb method for polynomial multiplication".
 // for the reduction part, we use a variant of the idea of Figure 2.9, customized to our setting.
 const W = 64             // the machine word width, in bits.
 const t = 4              // the number of words needed to represent a polynomial.
 c := make([]uint64, 2*t) // result
 a := make([]uint64, t)
 b := make([]uint64, t+1)  // will hold a copy of b, shifted by some amount
 for i := 0; i < 32; i++ { // "condense" `A` and `B` into word-vectors, instead of byte-vectors
  a[i>>3] |= uint64(A[i]) << (i & 0x07 << 3)
  b[i>>3] |= uint64(B[i]) << (i & 0x07 << 3)
 }
 for k := 0; k < W; k++ {
  for j := 0; j < t; j++ {
   // conditionally add a copy of (the appropriately shifted) B to C, depending on the appropriate bit of A
   // do this in constant-time; i.e., independent of A.
   // technically, in each time we call this, the right-hand argument is a public datum,
   // so we could arrange things so that it's _not_ constant-time, but the variable-time stuff always depends on something public.
   // better to just be safe here though and make it constant-time anyway.
   mask := -(a[j] >> k & 0x01) // if A[j] >> k & 0x01 == 1 then 0xFFFFFFFFFFFFFFFF else 0x0000000000000000
   for i := 0; i < t+1; i++ {
    c[j+i] ^= b[i] & mask // conditionally add B to C{j}
   }
  }
  for i := t; i > 0; i-- {
   b[i] = b[i]<<1 | b[i-1]>>63
  }
  b[0] <<= 1
 }
 // multiplication complete; begin reduction.
 // things become actually somewhat simpler in our case, because the degree of the polynomial is a multiple of the word size
 // the technique to come up with the numbers below comes essentially from going through the exact same process as on page 54,
 // but with the polynomial f(X) = X^256 + X^10 + X^5 + X^2 + 1 above instead, and with parameters m = 256, W = 64, t = 4.
 // the idea is exactly as described informally on that page, even though this particular polynomial isn't explicitly treated.
 for i := 2*t - 1; i >= t; i-- {
  c[i-4] ^= c[i] << 10
  c[i-3] ^= c[i] >> 54
  c[i-4] ^= c[i] << 5
  c[i-3] ^= c[i] >> 59
  c[i-4] ^= c[i] << 2
  c[i-3] ^= c[i] >> 62
  c[i-4] ^= c[i]
 }
 C := make([]byte, 32)
 for i := 0; i < 32; i++ {
  C[i] = byte(c[i>>3] >> (i & 0x07 << 3)) // truncate word to byte
 }
 return C
}
func main() {
 temp := make([]byte, 32)
 _, _ = rand.Read(temp)
 expected := make([]byte, 32)
 copy(expected, temp)
 count := 0
 for j := 0; j < 256; j++ {
  temp = binaryFieldMul(temp, temp)
  fmt.Printf("[%x...] ", temp[:3])
  count = count + 1
 }
 fmt.Printf("Multiplications: %d\n", count)
 fmt.Printf("\n\nFinal: %x\n", temp)
 fmt.Printf("Expected: %x\n", expected)
}

We are thus multiplying a value by itself 256 times. This should give us the same value that we started with, as Little Fermat’s theory says:

a^p (mod p)=a

To debug, the first three bytes of each multiplication is give, but at the end we should be able to reveal that the final multiplication is the same as the original value [here]:

[456521...] [73ed7d...] [81dad4...] [23f4b4...] [b44096...] [35956c...] 
[463302...] [e82821...] [a643c8...] [3ca172...] [ecf026...] [b1c667...] 
[24744b...] [754908...] [1be528...] [d6e1dd...] [6606cb...] [e509b4...] 
[743c1d...] [ab40b9...] [7d6e18...] [bd13a3...] [74c5da...] [a1c503...] 
[b05024...] [7f0241...] [f30ba8...] [ae0b45...] [431eeb...] [8c6ea4...] 
[848d69...] [0d8ffe...] [a74c53...] [1854be...] [68306e...] [35424b...] 
[f0d7cb...] [3fdf32...] [37cd76...] [ee49b2...] [af8c36...] [b4b36a...] 
[b10a8b...] [46785f...] [f523c9...] [6987c5...] [bde8e7...] [ad0872...] 
[51a563...] [297058...] [880656...] [729a40...] [43784d...] [8ceade...] 
[a6ed54...] [6bc796...] [f97507...] [d204ac...] [49e995...] [11f39a...] 
[3ecb0e...] [4ecb9a...] [e5d0d8...] [64b37a...] [1a3094...] [800377...] 
[75c217...] [3924fe...] [b0f9c3...] [474d45...] [2dcba5...] [edb12b...] [d2ca83...] [e8323a...] [eb8efe...] [7d1bd5...] [d83b06...] [1d268a...] [85cc88...] [e7396c...] [befb39...] [0432ce...] [d9c675...] [82f35c...] [1e4a1c...] [09539f...] [cf4ada...] [12a9bc...] [9011b0...] [8eba2b...] [2ce733...] [17bdb4...] [becb41...] [3b8d47...] [05d819...] [92abb8...] [c71235...] [f4333e...] [993b0f...] [5cfb28...] [75e43d...] [9fdbb1...] [0f2700...] [9bf2df...] [d6a1d8...] [3170a4...] [2951d2...] [c81f89...] [a67223...] [14b52c...] [947f21...] [c46d3e...] [d3430d...] [202097...] [1d7aab...] [cff1e2...] [b30721...] [e3d677...] [b3c50a...] [8cef49...] [65db99...] [41638e...] [829e48...] [807ea9...] [356a3d...] [39f00d...] [a0430b...] [2f51fe...] [b47715...] [c45c14...] [10103c...] [4d8c3b...] [aa694d...] [76ebe2...] [dda622...] [8fe87e...] [18a8d7...] [1d13b7...] [eda4a4...] [d55fe2...] [51a92c...] [3e6a7b...] [616fb0...] [c5735a...] [74388d...] [8ee5c3...] [7c04bd...] [a60954...] [61a3da...] [51c2f4...] [d80834...] [1a12c5...] [66145a...] [ff531a...] [cc205c...] [d9ea03...] [d54171...] [4cd762...] [07d7ba...] [670709...] [2aab6d...] [660140...] [f236d6...] [598325...] [88261c...] [780ff0...] [8e1656...] [90c6bc...] [b6b583...] [499391...] [c8aab7...] [c3de19...] [3dae15...] [336c4d...] [4f5d42...] [f4fe80...] [28ab70...] [4df579...] [a0fc78...] [93d1ef...] [152f04...] [7939ae...] [a7d690...] [48c2d6...] [284d87...] [4031ca...] [9e111b...] [0e126e...] [b5a719...] [0b7ad7...] [a3172d...] [f3dcbb...] [fe092c...] [ddaf2e...] [c2c42e...] [e50665...] [4ca731...] [7f8104...] [d65f7b...] [265f18...] [6186a6...] [f7b9d0...] [f42615...] [89556e...] [857729...] [0b0aa4...] [552ee9...] [b06b11...] [f6a81c...] [8d91ec...] [a04d4b...] [a12edb...] [639c09...] [e36634...] [450d47...] [51dd37...] [0c1170...] [fbca64...] [f9f0f5...] [989869...] [8453cd...] [0d5b37...] [7431eb...] [47f78f...] [3d8024...] [29b219...] [d260d3...] [314ee2...] [5c8312...] [898c7e...] [d8f16e...] [acd398...] [a1ddcb...] [826bb2...] [ca6667...] [049db6...] [40775e...] [b6b471...] [6cd789...] [ab58c3...] [1882ae...] [890337...] [ba4cbf...] [97fc3e...] [552d1c...] [cff8ad...] [beb660...] [bf020e...] [2d5337...] [2e767e...] [0e07bd...] [5e5133...] [4e0b26...] [f27b6b...] [afea03...] [8b9882...] 
Multiplications: 256

Final: 8b988254aff67f9d9f73d9053395266a1479b86da6b158f7737da337a6050927
Expected: 8b988254aff67f9d9f73d9053395266a1479b86da6b158f7737da337a6050927

And we can see that this is correct, and so our binary arithmetic multiplication passes this test. With this we have proven that we can multiple a value by itself (with a field of ²²⁵⁶) and end up with the same value — crypto magic!

Conclusions

And, so, Fermat’s Little Theorem has secured the Internet, and RSA is still the most popular method of public key encryption, and for digital signatures on the Internet. If you want to try the binary multiplication, try here:

https://asecuritysite.com/golang/fer

References

[1] Kryptology, https://github.com/coinbase/kryptology/blob/master/pkg/ot/extension/kos/kos_test.go.