Pseudocode for constant time modular exponentiation

Question

I'm looking to implement modular exponentiation (for RSA) in constant time, but most of the examples I've found are more mathematical descriptions of the operations. Are there any references with descriptions in psuedo-code, which are understandable (and implementable!) by someone without much of a math background?

Answer 1

No. If you don't have a strong math background, implementing RSA yourself is a bad idea (and perhaps even if you do). There are many ways to go wrong, which can open up subtle security weaknesses.

Instead, you should use a well-vetted RSA implementation from a standard crypto library, and a well-vetted protocol -- or hire a cryptographer who does understand the mathematics, if you don't think you can trust any existing implementation or need help selecting one that is suitable.

Answer 2

A glimpse at how RSA works

Key Generation Algorithm

1. Choose two very large random prime integers: p and q
2. Compute n and φ(n): n = pq and φ(n) = (p-1)(q-1)
3. Choose an integer e, 1 < e < φ(n) such that: gcd(e, φ(n)) = 1
   (where gcd means greatest common denominator)
4. Compute d, 1 < d < φ(n) such that: ed ≡ 1 (mod φ(n))

Where…

• the public key is (n, e) and the private key is (n, d)
• the values of p, q and φ(n) are private
• e is the public or encryption exponent
• d is the private or decryption exponent

Encryption

The cyphertext C is found by the equation 'C = Me mod n' where M is the original message.

Decryption

The message M can be found form the cyphertext C by the equation 'M = Cd mod n'.

---

An example

This is an extremely simple example and would not be secure using primes so small, normally the primes p and q would be much larger.

Select the prime integers q=11, q=3.  
n=pq=33; φ(n)=(p-1)(q-1)=20  
Choose e=3  
    Check gcd(3,20)=1  
Compute d=7  
    (3)d ≡ 1 (mod 20)

Therefore the public key is (n, e) = (33, 3) and the private key is (n, d) = (33, 7).

Now say we wanted to encrypt the message M=7

$C = M^e \mod n$
$C = 7^3 \mod 33$
$C = 343 \mod 33$
$C = 13$

So now the cyphertext C has been found. The decryption of C is performed as follows.

$M' = C^d \mod n$
$M' = 13^7 \mod 33$
$M' = 62,748,517 \mod 33$
$M' = 7$

As you can see after the message has been encrypted and decrypted the final message M' is the same as the original message M. A more practical way to use the algorithm is to convert the message to hexadecimal and perform the encryption and decryption steps on each octet individually.

---

Security Notice

Now, please note that the example provided is nowhere near secure. A lot of important nit-bits are missing in this rather rough, introductory explanation. Also (for a good reason) RSA uses huge primes compared to the ones used in the example.

In the end it’s hard to provide “pseudo-code” while skipping the math (as you requested), because the algorithm depends on the math! But it shouldn’t be all too hard to follow the above description to get a first hint at how things work… and build/expand your knowledge upon that.

One thing’s for sure: if you don’t grasp the math behind it, you’ll have a hard time making sure you don’t mess up your home-grown implementation. In case of doubt, please use one of the well-vetted implementations/libraries like other users already suggested. Those were build by people who do understand the maths involved and who know what they are doing (at least, most of the time).

“Constant time” and company…

Depending on how you implement it, RSA may provide room for several security problems. One of them being the missing defence against side-channel attacks. Yet, to build an appropriate defence requires a good understanding of the maths behind it. You could check out the “Exponentiation by squaring” article at Wikipedia. Among other things, it mentions Montgomery's ladder technique…

x1=x; x2=x2
for i=k-2 to 0 do
  If ni=0 then
    x2=x1*x2; x1=x12
  else
    x1=x1*x2; x2=x22
return x1

But that won’t cut it! (The “if“ is a problem… so you would need to adapt this pseudo-code.)

From my point of view, neither pseudo-code, nor such Wikipedia articles will be able to cover all potential security issues that might arise when practically implementing RSA. In fact, covering every potential problem would be too broad for an answer, and not knowing your current level of knowledge (and what research you’ve done, and what you’re learned from that research), it’s near to impossible to judge what might help you and what might not. Yet, what I know is that pseudo-code surely won’t satisfy your needs.

Please don’t get me wrong, but since you indicated that you have a hard time grasping the math behind it all, I would like to repeat: in case of doubt, you should think about using one of the well-vetted (tested) implementations. You surely don’t want to risk messing up something important due to the lack of some knowledge and/or experience. After all, making a mistake is not an option when it comes to crypto… if anything, mistakes will break the crypto and – in the end – your neck.

Answer 3

Frighteningly, answering my own question. The answer appears to be “Montgomery's ladder technique”.

Quoting the Wikipedia article:

Many algorithms for exponentiation do not provide defence against side-channel attacks. Namely, an attacker observing the sequence of squarings and multiplications can (partially) recover the exponent involved in the computation. This is a problem if the exponent should remain secret, as with many public-key cryptosystems. A technique called Montgomery's Ladder (Montgomery, P. L. "Speeding the Pollard and Elliptic Curve Methods of Factorization." Math. Comput. 48, 243-264, 1987). addresses this concern.
…

Answer 4

The follows may be helpful:

compute:$ M^e $ (mod n)

$ e=e_{k}e_{k-1}...e_{1}e_{0};$
$ c=1 $

for $ i=k $ downto 0
    $c=c^{2} \pmod n$
    if $ e_i = 1 $ then $ c=c*M \pmod n$

return c