When Pow Is Good

When Pow Is Good

In cryptography we deal with large numbers … in fact very large numbers. While are processors have registers that hold 64 bits, and our integer values in programs are stored as 64-bit values, in crypto land these values are normally constrained only by the length of a large prime number. And, for example, if we operate on two 64-bit values, the result will be 128 bits in length, and we do not allow it to overflow (as we would in our normal operations).

A 2,048 bit value (and which is often used in RSA) is something of the form (2²⁰⁴⁸):

32,317,006,071,311,007,300,714,876,688,669,951,960,444,102,669,715,484,032,130,345,427,524,655,138,867,890,893,197,201,411,522,9 13,463,688,717,960,921,898,019,494,119,559,150,490,921,095,088,152,386,448,283,120,630,877,367,300,996,091,750,197,750,389,652,1 06,796,057,638,384,067,568,276,792,218,642,619,756,161,838,094,338,476,170,470,581,645,852,036,305,042,887,575,891,541,065,808,6 07,552,399,123,930,385,521,914,333,389,668,342,420,684,974,786,564,569,494,856,176,035,326,322,058,077,805,659,331,026,192,708,4 60,314,150,258,592,864,177,116,725,943,603,718,461,857,357,598,351,152,301,645,904,403,697,613,233,287,231,227,125,684,710,820,2 09,725,157,101,726,931,323,469,678,542,580,656,697,935,045,997,268,352,998,638,215,525,166,389,437,335,543,602,135,433,229,604,6 45,318,478,604,952,148,193,555,853,611,059,596,230,656

This has 617 digits.

Finite fields and the mod p operation

In cryptography are calculations can get very large, so we constrain them with a finite field (or a GF(p) — Galois field of p, or with 𝔽p), and where our outputs from calculation will range from 0 to p-1 The modulo is remainder of an integer division and p is a prime number.

The reason we use the prime number is that we can still perform our maths operations with we take the modulus of our calculations. For example:

a×b(mod p)

is the same as:

a(mod p)×b(mod p) (mod p)

and it works with other operators too, such as with an adding operation:

a+b (mod p)

is the same as:

a(mod p)+b(mod p) (mod p)

and with subtraction:

a−b (mod p)

is the same as:

a(mod p)−b(mod p) (mod p)

For the value raised to the power we have:

(aˣ)ʸ (mod p)

is equivalent to:

(aˣ (mod p))ʸ (mod p)

A sample run illustrates this:

a =  10
b =  20
p =  23
a * b (mod p)=                      16
(a (mod p) x b (mod p)) (mod p)=    16
a + b (mod p)=                      7
(a (mod p) + b (mod p)) (mod p)=    7
a - b (mod p)=                      13
(a (mod p) - b (mod p)) (mod p)=    13

Very, very difficult … pow() to the rescue

But a standard operation that we do in cryptography relates to discrete logarithms with the operation of:

Y = Gˣ mod p

In Python this could be coded as:

a**b % p

and which is a to the power of b modulus p.

Even with small numbers, Gˣ gets very large and will often take a relatively long time to compute, as the process must try to operate of values that are even larger than the size of p.

So let’s look at an example and we will see that there is a smarter way of doing with operation. We can pick a prime number that has a given number of bits by taking a power of 2, and then subtracting one from it. So let’s take a small prime of 2²⁵⁶ -1 (p), and run two tests for a value of a=150,000 and b=200,000 (where we will calculate aᵇ mod p). One with the core operators and the other using the pow() function:

>>> import time
>>> a=150000
>>> b=200000
>>> p=2**256–1
>>> start = time.time()
>>> y1=(a**b) % p
>>> end = time.time()
>>> t1=end — start
>>> start = time.time()
>>> y2=pow(a,b,p)
>>> end = time.time()
>>> t2=end — start
>>> print y1,y2
104576585425667029820280240312765541820497639808288669289015960778922582820255 104576585425667029820280240312765541820497639808288669289015960778922582820255
>>> print “T1=”,t1
T1= 0.422417879105
>>> print “T2=”,t2
T2= 0.00106906890869
>>> res=t1/t2
>>> print “Speed up”,res
Speed up 395.126895629

We can see that pow() is nearly 400 times faster than using the core operators. This is because it is performing the operations with respect to the modulus operator.

At the core of the speed-up is the Montgomery reduction algorithm. With the RSA and the Diffie-Hellman methods we perform large exponential calculations, such as:

Y = Gˣ mod p

and where we will continually multiply large integers by an exponent to get a result. In a traditional multiplication of two value (x and y) for a modulus of N, we multiply x times y and then divide by N to find the remainder. The number of bits in the multiplication with this be the number of bits in x added to the number of bits in y. In Montgomery reduction we add multiples of N in order to simply the multiplication.

An example of this is here, and a sample run for x=10, y=5 and N=29 is:

x=	10
y=	5
N=	29
x*y (mod N)
Result (Montgomery)=	21
Result (x*y % mod)=	21
x^y (mod N)
Result (Montgomery)=	8
Result (x^y % mod)=	8

In this case we get 50 (mod 29) which is 21, and 10⁵ mod 29 which is 8 [try here].

Conclusions

And there you go. In crypto space, the pow() method is your friend.

Learn more about the magic of finite fields here: