Algorithm Optimization And Hardware Implementation Of Finite Field Modular Multiplication For SIKE

With the development of quantum computation and quantum computer,the challenges of existing public key cryptography are growing,which promotes the research work of post quantum cryptography system and is of great significance for the future security based on public key cryptography.The Supersingular Isogeny Key Encapsulation(SIKE)protocol based on the problem of the isogeny mapping of supersingular elliptic curves has been listed by National Institute of Standard and Technology(NIST)as one of the important post quantum encryption candidates.Thus,it has great research prospects and potential.The modular multiplication on a finite field is one of computational bottlenecks in the SIKE protocol.Therefore,algorithm optimization for modular multiplication on a finite field based on SIKE and the hardware implementation are essential for the research and application of SIKE protocol.At first,this thesis studies the existing two modular multiplication algorithms on a finite field based on SIKE and their corresponding hardware structures,including the Montgomery algorithm with systolic array and the efficient finite field multiplication on a finite field of special form.It analyzes the two algorithms in detail.The implementation of EFFM algorithm is limited by the special form of a finite field while the Montgomery algorithm isn't.Next,based on the EFFM algorithm,two improved algorithms are proposed in this thesis.The first one is Finite Field Multiplication 1(FFM1),which reduces the computational complexity by reducing the number of operands,and thus it improves the algorithm performance.The second one called Finite Field Multiplication 2(FFM2)converts a large number division to a shift operation and a division with a small divisor by mathematical transform,which is inspired by Barrett Division algorithm.This thesis also designs hardware architectures targeting at the two optimization algorithms and explores the impact from the multipliers with different input size.At last,a detailed comparison about above four algorithms and corresponding hardware architectures is presented,including complexity,applicable range,running time,consumed resources and operating frequency.The software implementation result shows that FFM1 algorithm can be 24 faster than the original EFFM algorithm.The hardware results are much better,which is over 6 times faster than the previous one.The hardware implementation of the FFM2 algorithm is the fastest among the four algorithms.Furthermore,the FFM2 algorithm can be applied for a wider range of modulo,which is limited in the EFFM and the FFM1 algorithms.In the end,this thesis applies the FFM2 algorithm and structure into the SIDH protocol,which is 30.98 faster than the original software implementation of SIDH protocol.