# Pseudocode for constant time modular exponentiation

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?

-
The exponentiation part is easy if you're willing to sacrifice performance. The modular reduction is harder, considering that even the modulus is secret. –  CodesInChaos Apr 28 at 7:52
This question appears to be off-topic because it is a ref. request on an algorithm, not about crypto. It would be better at the Computer Science or Mathematics sites instead. –  rath Apr 29 at 23:38
@rath: The question would only be off-topic because its ask for "descriptions" in pseudocode, rather than "methods preferably with a description" in pseudocode, but that's semantic. I think that it got no satisfactory direct answer yet primarily because what's asked is hard to do in general without too much a sacrifice in performance; and secondarily because usual practice about the issue (do it in hardware to get constant time, or change goal to: find ways of dealing with potentially dangerous non-constant time in a safe way) do not match the statement. –  fgrieu Apr 30 at 2:29
I agree with @fgrieu, the question may have been formulated a bit too general (fixed that), but it’s clearly a crypto-related reference request. Besides, I don’t think the question belongs to CS.SE or Math.SE as those sites don’t handle crypto-related algorithms or math-based security solutions in a way Crypto.SE does. Remember: when it comes to crypto, we “trust in the math”. Yet, that doesn’t automatically mean everything math-related belongs on Math.SE (or alike sites). If that were the case, we might as well shut down Crypto.SE as there wouldn’t be much left to talk about. ;) –  e-sushi Apr 30 at 16:27

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.

-
Considering the beginner mistakes in GnuPG's RSA I'm beginning to have doubts about that. –  CodesInChaos Apr 28 at 7:49
@fgrieu GnuPG used the naive if e[i] then c *= M until 2013. This enables cross VM attacks: eprint.iacr.org/2013/448 –  CodesInChaos Apr 29 at 8:04
I visit this answer in the review queue and unfortunately I agree. The caveat is always useful but it doesn't answer the question; maybe the OP is implementing it as an exercise. –  rath Apr 29 at 9:11
What Rath said - this would be better as a comment on the O.P. –  figlesquidge Apr 29 at 10:19
@CodesInChaos: what you describe in GnuPG is a timing dependency, and might be a side-channel vulnerability (e.g. by acoustic noise, cross-VM cache flushing..) absent countermeasures, but is NOT a significant timing vulnerability in an RSA context. The adversary gets nothing exploitable with the hamming weight of $d$. –  fgrieu Apr 29 at 17:23

## 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.

-
You might have missed the "constant time" in the title (and also mentioned once more in the question). I don't blame you, because that wasn't emphasized in the question as it might have been, and the question didn't mention what prior research he'd done (a shortcoming of the question). But I don't think Alex Gaynor was looking for a generic description of the RSA algorithm; I think he was looking for a description of how to make a constant-time implementation of RSA. That said, I agree that the question could have been clearer. –  D.W. Apr 29 at 23:53
@D.W. Oops, you’re right. I guess those closing words saying “…someone without much a math background” erased my brain and caused a reboot into a how-much-does-he-understand-at-all sequence. Hmmm, not sure if it makes sense now that the question is closed, but I added some words about constant time and co. Anyway… [+1] for your answer. Looking back, I guess your answer was probably the shortest but also the most on-point. ;) –  e-sushi Apr 30 at 15:43

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.

-
But you cannot use an if for this. You need a constant time conditional swap for that. –  CodesInChaos Apr 28 at 7:50
While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. –  rath Apr 29 at 9:11
From the standpoint of timing dependency in RSA, using Montgomery ladder aims at solving the wrong timing dependency. It is no big deal to disclose, by timing, the hamming weight of the secret exponent $d$: that's too small an information leak to be a danger; also, there are several working $d$ since they are defined $\pmod{\operatorname{LCM}(p-1,q-1)}$. The real danger is timing dependency on what's exponentiated. Montgomery multiplication helps towards that (but is no silver bullet). Montgomery ladder may help for other forms of signal leakage, but the devil is in the details. [fixed] –  fgrieu Apr 29 at 12:54

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

-
your square and multiply fails to provide the constant time feature. –  DrLecter Apr 28 at 6:35