Crypto Sometimes Likes Zero: Meet Non-adjacent Form

Here is a bit of trivia for you … why do we use 65,537 as the encryption exponent value for RSA?

Well, 65,537 is a prime number as the encryption exponent cannot share a factor with (p-1)(q-1). Also, in its binary representation of “10000000000000001”, we can see that it has many zeros and only two 1’s. Why is this good? Well, when we perform an operation of:

M^e (mod p)

it is more efficient to process with a zero in the exponent (e) value, than with a 1.

CSD

With the Canonic Signed Digit (CSD) Representation of Integers, we can represent we can represent an integer (n) in the form:

and where we get:

and where L_n can be positive and negative integers. In normal binary, a value of 11 would be:

This could be represented in a CSD form as:

and which is [1 0 -1 0 -1].

Let’s say we have a value of 48,153, and want four values. These could be {(3,-3}), (-7,7),(-1, 1)}, and could represent as:

and repsented as:

[3 0 0 0 -1 0 0 0 0 1 0 0 0 0 -7]

NAF has the advantage that the Hamming weight between values is minimal, and where in a normal binary format, we will have around half of the bits set to 1 and half the bits set to 0. With NAF, this the number of 1s can drop to around one-third. Having so many zeros, allows efficent adding and subtraction. In cryptography, it reduces the number of multiplications requires for exponentation, as zero values are quicker than one values.

Coding

Some sample code is [here]:

package main
import (
 "fmt"
 "math/big"
 "github.com/cloudflare/circl/math"
 "crypto/rand"
    "strconv"
 "os"
)
func reverseInts(input []int32) []int32 {
    if len(input) == 0 {
        return input
    }
    return append(reverseInts(input[1:]), input[0]) 
}
func main() {
 w:=2
 bits:=128

 argCount := len(os.Args[1:])
 if argCount > 0 {
  w,_ = strconv.Atoi(os.Args[1])
 }
 if argCount > 1 {
  bits,_ = strconv.Atoi(os.Args[2])
 }
 var max big.Int
 max.SetInt64(1)
 max.Lsh(&max, uint(bits))

   x, _ := rand.Int(rand.Reader, &max)
   L := math.OmegaNAF(x, uint(w))
   var y big.Int
   for i := len(L) - 1; i >= 0; i-- {
    y.Add(&y, &y).Add(&y, big.NewInt(int64(L[i])))
   }
   L=reverseInts(L)
   got := &y
   fmt.Printf("\nNumber of bits=%d\nw=%d\nx=%s\n%v\nChecking: %v\n",bits,w,x, L,got)
   
  
 
}

For w=2, we have {0, (1, -1)} for values. For a value of 11458119973769479092371685680579383142, we get [here]:

Number of bits=128
w=2
x=11458119973769479092371685680579383142
[1 0 0 0 1 0 1 0 0 0 0 -1 0 -1 0 0 0 0 0 1 0 0 0 -1 0 0 -1 0 0 1 0 1 0 0 0 0 1 0 0 -1 0 0 0 1 0 -1 0 0 -1 0 0 0 0 0 1 0 -1 0 0 0 -1 0 1 0 -1 0 0 0 1 0 0 0 -1 0 1 0 1 0 1 0 -1 0 0 -1 0 -1 0 0 -1 0 1 0 0 0 1 0 0 0 -1 0 -1 0 -1 0 -1 0 0 0 1 0 0 1 0 0 0 0 -1 0 -1 0 1 0 -1 0]
Checking: 11458119973769479092371685680579383142

For w=3, we get three values. In this case we have {0, (1, -1), (3, 3)} and for a value of 3640439295394695171, we get [here]:

Number of bits=64
w=3
x=3640439295394695171
[1 0 0 0 -3 0 0 -3 0 0 0 0 1 0 0 3 0 0 -1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 3 0 0 -3 0 0 0 0 3 0 0 0 0 0 0 -1 0 0 1 0 0 0 0 0 0 0 0 0 0 3]
Checking: 3640439295394695171

For w=5, we get three values. In this case we have {0, (1, -1), (-9, 9), (-13, 13), (-15, 15)} and for a value of 169187459747143294798673799909229736090, we get [here]:

Number of bits=128
w=5
x=169187459747143294798673799909229736090
[1 0 0 0 0 0 0 -1 0 0 0 0 9 0 0 0 0 1 0 0 0 0 9 0 0 0 0 0 -7 0 0 0 0 9 0 0 0 0 15 0 0 0 0 15 0 0 0 0 -7 0 0 0 0 13 0 0 0 0 0 0 0 3 0 0 0 0 9 0 0 0 0 -11 0 0 0 0 5 0 0 0 0 15 0 0 0 0 -13 0 0 0 0 1 0 0 0 0 -15 0 0 0 0 11 0 0 0 0 0 0 0 -13 0 0 0 0 0 3 0 0 0 0 1 0 0 0 0 0 13 0]
Checking: 169187459747143294798673799909229736090