Design And Implementation Of Efficient Finite Field Modular Multiplication For SIDH

Recent progress in the design and development of quantum computers shows that real quantum computers may be available in the not too distant future.The computing capability of quantum computers is significantly higher than classical computers.As a result,commonly used public-key cryptographic algorithms,such as RSA and elliptic curve cryptography(ECC),which rely on integer factorization and the discrete log problem that are used in all of today's communications and internet security will be vulnerable to attack.Post-quantum cryptographic(PQC),or quantum-safe,schemes,which refer to conventional non-quantum cryptographic algorithms that are secure today but should remain secure even after practical quantum computing is a reality.Although the SIDH key exchange protocol based on the isogeny between two supersingular elliptic curves is a young contender in the post-quantum cryptography arena,the current picture of its security properties and applications looks promising.As modular arithmetic in a finite field is one of the main computational bottlenecks in the SIDH key exchange protocol,it is very important to design and implement efficient modular multiplication algorithms for this key exchange protocol.Several modular multiplication algorithms that can be applied to the SIDH key exchange protocol is firstly reviewed,which include the Montgomery modular multiplication algorithm,the Barrett reduction algorithm and the efficient finite field multiplication(EFFM)algorithm.These modular multiplication algorithms are also compared and analyzed to find the advantages and disadvantages of each algorithm.Two finite field multiplication algorithms are proposed in this thesis.Firstly,based on the EFFM,an improved EFFM(IEFFM)is proposed,which can reduce the number of arithmetic operations.The IEFFM is designed and implemented in both software and hardware platforms.The software implementation is written in C language based on GMP library and the hardware implementation is based on the Kintex-7 FPGA.Compared with previous works,the IEFFM is much faster.For software implementation,a speed-up of 24% is achieved and for hardware implementation the speed performance can be improved over 6 times compared with original EFFM.Secondly,a new finite field multiplication(NFFM)algorithm is inspired by the EFFM efficient division algorithm,which can calculate the modular multiplication by transfering part of the division operation into shifting operations.For software implementation,the speed performance is better than the EFFM but worse than the IEFFM.Compared with the EFFM and the IEFFM,the NFFM can be applied with a wider range of primes for the SIDH key exchange protocol.