Fast, compact and secure implementation of RSA on dedicated hardware

Abstract

RSA, günümüzde en sık kullanılan Açık Anahtarlı Şifreleme (AAŞ) türüdür. Daha önce hiç karşılaşmamış iki tarafın birbirleri arasında güvenli bir iletişim kanalı oluşturabilmesi için AAŞ sistemleri kullanılır. RSA'de en temel işlem modüler çarpım işlemidir ve özellikle kullanılan anahtar 1024 bitten uzunsa, bu işlem çok yoğun bir hesaplama gücü gerektirir. Günümüzün kişisel bilgisayarları birkaç RSA işlemini bir saniyeden kısa bir zamanda bitirebilirken, avuçiçi bilgisayarları, cep telefonları ve smart kart gibi az işlem gücüne sahip ortamlarda, bu yüksek hesap gücü gerektiren işlem için kullanılacak ilave donanıma ihtiyaç vardır. Buna ek olarak binlerce kişinin aynı anda erişim isteyebileceği web servis sağlayıcılarında, bu işlem, bir performans darboğazı olarak görünebilir. Donanım için geliştirilen bazı özel algoritmalar sayesinde çok büyük ölçekte paralel hesaplamalar yapılabilir ve böylece donanımın kullanım oranı artırılarak hem enerji harcaması düşürülür, hem de toplam işlem zamanı kısaltılır. Bu amaçla, en verimli modüler çarpım işlemlerinden biri olarak bilinen ve birçok AAŞ alanında kullanılan ?Montgomery Modüler Çarpım? algoritmasını kullanacağız.İlk olarak ?2048-bitlik ve 4 tabanında çalışan Modüler Çarpım? dizaynını anlatacağız ve bunu daha önceki çalışmalarda sıkça kullanılan 2 tabanındaki modüler çarpım devreleriyle karşılaştıracağız. Bizim devrenin, diğer devreleri simule etmek için yaptığımız referans devreye göre çalışma hızının % 82 arttığını ve bunu sadece %33'lük bir alan artışıyla gerçekleştirdiğini gördük. Ayrıca, Xilinx xc2v6000 FPGA'inde 132 MHz'de çalışan bu devre, referans dizayna göre %37'lere varan oranlarda, zaman alan çarpımını azalttı. Benzer kazanımları, UMC 0,18 ?m teknolojisi için sentezlenen devre ile de elde ettik.İkinci bölümde ise nispeten ucuz FPGA'lere uygun, hızlı, parametrik ve yan kanal ataklarına karşı dayanıklı bir modüler çarpım devresini ve bir üs alma devresini sunuyoruz. Bu dizayn, FPGA üzerinde bulunan çarpım birimlerini ve blok RAM'i kullanacak şekilde geliştirildi. Dizaynımızda çarpım işlemi için kullanılan bileşenlerin tabanı (radixi), çarpım ünitelerinin sayısı ve toplam word sayısı parametrik olarak istenen özelliklere göre ayarlanabilir. Mimari yapıda pipelining tekniğini kullandık ve bu bize yüksek frekanslarda, aynı anda birçok çarpım işlemini yapma özelliği kazandırdı. Dizaynımız 1020-bitlik ve 2040-bitlik modüler çarpım işlemlerini Xilinx Spartan-3E 500 FPGA'i üzerinde sırasıyla 7,62 µs ve 27,0 µs'de bitirmektedir ve bu ölçümler FPGA'de bulunan çarpım birimlerinin sadece yarısı kullanılarak elde edilmiştir. Dizanımız daha önceki devrelerle karşılaştırıldığında en düşük alan zaman çarpımını elde etti. Ayrıca 2040-bitlik üs alma devresinin Xilinx Spartan-3E 500 çipine kolaylıkla sığabileceğini gördük. Kullandığımız üs alma devresi, bilinen tüm yan kanal ataklarına karşı korumalı bir şekilde dizayn edildi ve bu koruma çok ufak bir ek donanım getirilerek başarıldı. Üs alma devresi, işlemde kullanılan sayılar blok RAM'e sığdığı sürece her büyüklükteki sayı için kullanılabilir. Bu dizanımız ayrıca ilk dizaynla da avantaj ve dezavantajları açısından karşılaştırıldı.

RSA is the most popular Public Key Cryptosystem (PKC) and is heavily used today. PKC comes into play, when two parties, who have previously never met, want to create a secure channel between them. The core operation in RSA is modular multiplication, which requires lots of computational power especially when the operands are longer than 1024-bits. Although today?s powerful PC?s can easily handle one RSA operation in a fraction of a second, small devices such as PDA?s, cell phones, smart cards, etc. have limited computational power, thus there is a need for dedicated hardware which is specially designed to meet the demand of this heavy calculation. Additionally, web servers, which thousands of users can access at the same time, need to perform many PKC operations in a very short time and this can create a performance bottleneck. Special algorithms implemented on dedicated hardware can take advantage of true massive parallelism and high utilization of the data path resulting in high efficiency in terms of both power and execution time while keeping the chip cost low. We will use the ?Montgomery Modular Multiplication? algorithm in our implementation, which is considered one of the most efficient multiplication schemes, and has many applications in PKC.In the first part of the thesis, our ?2048-bit Radix-4 based Modular Multiplier? design is introduced and compared with the conventional radix-2 modular multipliers of previous works. Our implementation for 2048-bit modular multiplication features up to 82% shorter execution time with 33% increase in the area over the conventional radix-2 designs and can achieve 132 MHz on a Xilinx xc2v6000 FPGA. The proposed multiplier has one of the fastest execution times in terms of latency and performs better than (37% better) our reference radix-2 design in terms of time-area product. The results are similar in the ASIC case where we implement our design for UMC 0.18 ?m technology.In the second part, a fast, efficient, and parameterized modular multiplier and a secure exponentiation circuit intended for inexpensive FPGAs are presented. The design utilizes hardwired block multipliers as the main functional unit and Block-RAM as storage unit for the operands. The adopted design methodology allows adjusting the number of multipliers, the radix used in the multipliers, and number of words to meet the system requirements such as available resources, precision and timing constraints. The deployed method is based on the Montgomery modular multiplication algorithm and the architecture utilizes a pipelining technique that allows concurrent operation of hardwired multipliers. Our design completes 1020-bit and 2040-bit modular multiplications in 7.62 µs and 27.0 µs respectively with approximately the same device usage on Xilinx Spartan-3E 500. The multiplier uses a moderate amount of system resources while achieving the best area-time product in literature. 2040-bit modular exponentiation engine easily fits into Xilinx Spartan-3E 500; moreover the exponentiation circuit withstands known side channel attacks with an insignificant overhead in area and execution time. The upper limit on the operand precision is dictated only by the available Block-RAM to accommodate the operands within the FPGA. This design is also compared to the first one, considering the relative advantages and disadvantages of each circuit.