We describe several algorithms for computing e-th roots of elements in a number field K, where e is an odd prime-power integer. In particular, we generalize Couveignes’ and Thomé’s algorithms originally designed to compute square-roots in the context of the General Number Field Sieve algorithm for integer factorization. Our algorithms cover most cases of e and K and their complexity is better than general root finding algorithms. Our (publicly available) Python implementation compares extremely well in performance to the implementation of these generic algorithms in well-known computer algebra softwares, allowing us to obtain reasonable timings even for large degree number fields and huge exponents e, which correspond to previously intractable cases using these softwares.

In [1] the authors introduced the leak resistant arithmetic in RNS to randomize RSA modular exponentiation. This randomization is meant to protect implementations on embedded device from side channel analysis. We propose in this paper a lazy version of the approach of [1] in the case of right-to-left square-and-multiply exponentiation. We show that this saves roughly 30% of the computation when the randomization is done at each loop iteration. We also show that the level of randomization of the proposed approach is better than the one of [1] after a few number of loop iterations.

Copyright 2016 by SCITEPRESS - Science and Technology Publications, Lda. All rights reserved.Cryptographic operations performed on an embedded device are vulnerable to side channel analysis and particularly to differential and correlation power analysis. The basic protection against such attacks is to randomize the data all along the cryptographic computations. In this paper we present a modular multiplication algorithm which can be used for randomization. We show that we can use it to randomize the modular exponentiation of the RSA cryptosystem. The proposed randomization is free of computation and induces a level of randomization from 210 to 215 for practical RSA modulus size.