Efficient modular multiplication techniques for large integers on FPGAs

Abstract

Diffie ve Hellman [1] tarafından ortaya konulan Açık Anahtarlı Şifreleme günümüz haberleşme sistemlerinde yaygınca kulanılmaktadır. RSA ve eliptik eğri tabanlı kriptosistemleri modüler çarpma işlemine dayanmaktadır. Geniş sayılarla modüler çarpma işlemi bu sistemlerdeki ana hesap kısmını oluşturmaktadır. Geleneksel modüler çarpma, bölme işlemi içerdiği için pahalı bir operasyondur. Bölme işleminden kurtulmak için, literatürde Montgomery ve Barrett algoritmaları [5], [27] öne sürülmüştür. Bu algoritmalar bölme işlemi yerine, çarpma ve kaydırma işlemini kullanmaktadır. Bu tezde, ilk olarak, hane tabanlı ve FPGA'nın DSP kaynaklarını kullanan bir Montgomery çarpıcısı tasarlanmıştır. Tasarlanan donanım, Verilog diliyle yazılmıştır ve bir 528 bit Mongomery carpma işlemini Virtex-7 xc7vx330tffg1157-3 çipinde 0.43us'de bir 1056 bit Montgomery çarpma işlemini 1.09 us'de hesaplamaktadır. Sonra, DSP kaynaklarını kullanan bir tam kelime Barrett çarpıcısı öne sürülmüştür. Öne sürülen donanım, bir 528 bit Barrett çarpma işlemini Virtex-7 xc7vx330tffg1157-3 çipinde 0.49 us'de bir 1056 bit Barrett çarpma işlemini 1.88 us'de hesaplamaktadır. Daha sonra, öne sürülen Montgomery çarpıcısına dayanan eliptik eğri nokta çarpıcısı (ECPM) tasarlanmıştır. Tasarlanan ECPM donanımı Virtex-7 xc7vx330tffg1157-3 çipinde, bir adet 528 bit ECPM işlemini herhangi bir asal eğri için 4.06 ms'de, NIST p-521 eğrisi için 2.79 ms'de hesaplamaktadır. Son olarak, Montgomery ve Barrett algoritmaları Vivado HLS aracıyla gerçeklenmiştir. Montgomery ve Barrett algoritmalarının HLS gerçeklemeleri bir 528 bit modüler çarpma işlemini, Virtex-7 xc7vx330tffg1157-3 çipinde, sırasıyla 1.34 us ve 2.57 us'de hesaplamaktadır.Public-key cryptography (PKC) introduced by Diffie and Hellman [1], is widely used in today's communication systems. RSA and elliptic curve based public-key cryptosystems heavily depend on modular multiplication. Modular multiplication operation with large integers is the main computation part in these systems. Conventional modular multiplication is an expensive operation because it requires division. In order to overcome this difficulty, effective modular multiplication algorithms are proposed in the literature. Most common ones are Montgomery and Barrett algorithms [5], [27] which replace division with multiplication and shift operations. Therefore, in this thesis, we first designed a fast digit based Montgomery multiplier using DSP resources of FPGAs. The proposed hardware is implemented Verilog HDL and it takes 0.43 us to compute one 528 bit Montgomery modular multiplication and 1.09 us to compute one 1056 bit Montgomery modular multiplication in Virtex-7 xc7vx330tffg1157-3. We then, proposed full-word Barrett multiplier using DSP resources. It takes 0.49 us to compute one 528 bit Barrett modular multiplication and 1.88 us to compute one 1056 bit Barrett modular multiplication in Virtex-7 device xc7vx330tffg1157-3. We, then designed ECPM hardware based on the proposed Montgomery multiplier. It takes 4.06 ms to compute one 528 bit ECPM in any prime field and 2.79 ms to compute NIST p-521 ECPM in Virtex-7 xc7vx330tffg1157-3. Finally, we implemented Montgomery and Barrett algorithms using Vivado HLS tool. HLS implementation of Montgomery and Barrett algorithm takes 1.34 us and 2.57 us to compute one 528 bit modular multiplication in Virtex-7 device xc7vx330tffg1157-3 respectively.