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?

  • $\begingroup$ The exponentiation part is easy if you're willing to sacrifice performance. The modular reduction is harder, considering that even the modulus is secret. $\endgroup$ Commented Apr 28, 2014 at 7:52
  • 3
    $\begingroup$ 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. $\endgroup$
    – rath
    Commented Apr 29, 2014 at 23:38
  • 2
    $\begingroup$ @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. $\endgroup$
    – fgrieu
    Commented Apr 30, 2014 at 2:29
  • 2
    $\begingroup$ 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. ;) $\endgroup$
    – e-sushi
    Commented Apr 30, 2014 at 16:27

4 Answers 4


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.

  • 2
    $\begingroup$ Considering the beginner mistakes in GnuPG's RSA I'm beginning to have doubts about that. $\endgroup$ Commented Apr 28, 2014 at 7:49
  • 2
    $\begingroup$ @fgrieu GnuPG used the naive if e[i] then c *= M until 2013. This enables cross VM attacks: eprint.iacr.org/2013/448 $\endgroup$ Commented Apr 29, 2014 at 8:04
  • 6
    $\begingroup$ 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. $\endgroup$
    – rath
    Commented Apr 29, 2014 at 9:11
  • 2
    $\begingroup$ What Rath said - this would be better as a comment on the O.P. $\endgroup$ Commented Apr 29, 2014 at 10:19
  • 2
    $\begingroup$ @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$. $\endgroup$
    – fgrieu
    Commented Apr 29, 2014 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))


  • 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


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


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

  • 2
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Apr 29, 2014 at 23:53
  • $\begingroup$ @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. ;) $\endgroup$
    – e-sushi
    Commented Apr 30, 2014 at 15:43

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.

  • 3
    $\begingroup$ But you cannot use an if for this. You need a constant time conditional swap for that. $\endgroup$ Commented Apr 28, 2014 at 7:50
  • 2
    $\begingroup$ 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] $\endgroup$
    – fgrieu
    Commented Apr 29, 2014 at 12:54

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

  • 5
    $\begingroup$ your square and multiply fails to provide the constant time feature. $\endgroup$
    – DrLecter
    Commented Apr 28, 2014 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.