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…