Resistance of the Montgomery kP Algorithm against Simple SCA: Theory and Practice

The Montgomery kP algorithm is reported in literature as resistant against simple SCA due to the fact that the processing of each key bit value of the scalar k is done using the same sequence of operations. We implemented the Montgomery kP algorithm using Lopez-Dahab projective coordinates for the NIST elliptic curve B-233. We instantiated the same VHDL code for wide range of clock frequencies for the same target FPGA and using the same compiler options. We measured electromagnetic traces of the kP executions using the same input data, i.e. scalar k and elliptic curve point P, and measurement setup. Our experiments clearly show that the success of simple electromagnetic analysis depends on the target frequency for which the design was implemented and at which it is executed significantly. In our experiments the used scalar k was successfully revealed via simple visual inspection of the trace for frequencies from 40 MHz to 100 MHz for standard compile options as well as from 50 MHz up to 240 MHz for performance optimizing compile options.