Editing Montgomery modular multiplication (section)

== Side-channel attacks ==

Because Montgomery reduction avoids the correction steps required in conventional division when quotient digit estimates are inaccurate, it is mostly free of the conditional branches which are the primary targets of timing and power [[side-channel attack]]s; the sequence of instructions executed is independent of the input operand values.  The only exception is the final conditional subtraction of the modulus, but it is easily modified (to always subtract something, either the modulus or zero) to make it resistant.<ref name="kizhvatov">{{cite conference
 |first1=Zhe |last1=Liu  |first2=Johann |last2=Großschädl  |first3=Ilya |last3=Kizhvatov
 |url=https://www.nics.uma.es/seciot10/files/pdf/liu_seciot10_paper.pdf
 |title=Efficient and Side-Channel Resistant RSA Implementation for 8-bit AVR Microcontrollers
 |conference=1st International Workshop on the Security of the Internet of Things
 |date=29 November 2010 |location=Tokyo
 |conference-url=https://www.nics.uma.es/pub/seciot10/
}}  ([https://www.nics.uma.es/pub/seciot10/files/ppt/liu_seciot10.pdf Presentation slides].)</ref>  It is of course necessary to ensure that the exponentiation algorithm built around the multiplication primitive is also resistant.{{r|kizhvatov}}<ref>Marc Joye and Sung-Ming Yen. [http://cr.yp.to/bib/2003/joye-ladder.pdf "The Montgomery Powering Ladder"]. 2002.</ref>