RSA Paper Example

Question

I am reading the 1978 paper on RSA Algorithm. There is an example included in the paper and there is a section I can't get my head around.

It says:

Since $e = 10001$ in binary, the first block ($M = 920$) is enciphered: $M^{17} = (((((1)^2· M)^2)^2)^2)^2· M = 948 (mod 2773)$

What I don't understand is how e in binary has relevance to finding $M^{17}$ or why $M^{17}$ is written in that format. The paper can be found here https://people.csail.mit.edu/rivest/Rsapaper.pdf

Answer 1

$M^{17}$ is encoded as $(((M^2)^2)^2)^2\times M$ because it's faster that way. (I don't know why the $(1)^2$ is in there.)

The naive way of obtaining $M^{17}$ requires $16$ successive multiplications of $M$. By comparison, if you apply the square function to $M$ (and then its results) four times, you reduce the count to five times. If $M$ is large (encryption blocks are typically thousands of bits, and hence equivalent numbers in the high hundreds or low thousands of digits), this can save a significant amount of time over many encryptions.

This works primarily because $17$ is just one more than a power of $2$. If you picked $23$, say, which has the binary representation $10111$, you'd have to square four times, and then multiply three more times, for a total of seven multiplications. Not a lot more, but two more than you had to do.

Answer 2

The example follows the algorithm for computing $M^e$ (mod $n$) described at the bottom of page 8 of the paper. Here's an implementation in Python:

def binary(e):
    bits = []
    while e > 0:
        b = e % 2
        bits.append(b)
        e = e >> 1
    bits.reverse()
    return bits

def pow(M, e, n):
    bits = binary(e)
    print "Step 1: Binary representation of %d is %r" % (e, bits)
    C = 1
    strC = "1"
    print "Step 2: C = %s" % (strC)
    for e_i in bits:
        C = (C * C) % n
        strC = "(%s)^2" % strC
        print "Step 3a: C = %d = %s mod %d" % (C, strC, n)
        print "Step 3b: e_i = %d" % e_i,
        if e_i == 1:
            C = (C * M) % n
            strC = "%s x %s" % (strC, M)
            print "so C = %d = %s mod %d" % (C, strC, n)
        else:
            print "so don't change C"

pow(920, 17, 2773)

with output:

Step 1: Binary representation of 17 is [1, 0, 0, 0, 1]
Step 2: C = 1
Step 3a: C = 1 = (1)^2 mod 2773
Step 3b: e_i = 1 so C = 920 = (1)^2 x 920 mod 2773
Step 3a: C = 635 = ((1)^2 x 920)^2 mod 2773
Step 3b: e_i = 0 so don't change C
Step 3a: C = 1140 = (((1)^2 x 920)^2)^2 mod 2773
Step 3b: e_i = 0 so don't change C
Step 3a: C = 1836 = ((((1)^2 x 920)^2)^2)^2 mod 2773
Step 3b: e_i = 0 so don't change C
Step 3a: C = 1701 = (((((1)^2 x 920)^2)^2)^2)^2 mod 2773
Step 3b: e_i = 1 so C = 948 = (((((1)^2 x 920)^2)^2)^2)^2 x 920 mod 2773