Realizacja w układach FPGA mnożenia Montgomery dla akceleracji operacji kryptograficznych

• Autorzy: Janiszewski M. , Russek P. , Wiatr K.

Warianty tytułu

EN

Implementation of Montgomery multiplication for cryptographic algorithm acceleration in FPGA

• Języki publikacji: PL

Abstrakty

PL

W niniejszej pracy podjęto temat realizacji modułu sprzętowego, mogącego skutecznie przyspieszyć programowe realizacje operacji kryptograficznych. Rozpatrywanym algorytmem jest szyfrowanie asymetryczne RSA. Moduł został zaimplementowany w układzie firmy Xilinx - Virtex 4 LX200. Prędkość działania modułu została porównana z najpopularniejszymi rozwiązaniami programowymi. Rezultaty pokazują, że rozwiązania bazujące na układach rekonfigurowanych mogą konkurować z implementacjami opartymi na procesorach ogólnego przeznaczenia (GPP).

EN

Modular exponentiation is a key operation for RSA cryptographic algorithm. There are many algorithms for computing modular exponentiation - equation 1. The most basic are right to left and left to right binary algorithms. For key length k=1024 bits, 1024 modular squarings and 512 modular multiplications on average must be performed. There are many optimization which allows to minimize the number of multiplications, however they are more suited for software implementations. Therefore key factor for faster modular exponentiation is fast multiplier module. This work presents example implementation of modulo multiplier using Montgomery multiplication algorithm [1]. Montgomery multiplication is the most efficient algorithm when large number of multiplications must be performed with respect to the same modulus n. Our results show that timings comparable with modern processors can be achieved - table 2. This works also presents optimizations of proposed module, which allow greater speedup and application of FPGA bas

Słowa kluczowe

PL

mnożenie Montgomery; mnożenie modulo; FPGA; RSA

EN

Montgomery multiplication; modular multiplication; FPGA; RSA

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2008
• Tom: R. 54, nr 8
• Strony: 550--552
• Opis fizyczny: rys., tab., wzory

Twórcy

autor

Janiszewski M.

autor

Russek P.

autor

Wiatr K.

• Akademickie Centrum Komputerowe "Cyfronet", Akademia Górniczo-Hutnicza w Krakowie,

Bibliografia

• [1] P. L. Montgomery. Modular Multiplication without Trivial Division. Mathematics of Computation, 1985 r.
• [2] W. Diffie, M. E. Hellman. New Directions in Cryptography. IEEE Transactions on Infromation Theory, 1976 r.
• [3] R. Rivest, A. Shamir, L. Adelman. A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Communications of the ACM, 1978 r.
• [4] Tolga Acar, Çetin Kaya KoÇ, Burton S. Jr. Kaliski. Analyzing and Comparing Montgomery Multiplication Algorithms. IEEE Micro, 1996 r.
• [5] C. D. Walter. Montgomery exponentiation needs no final substractions. Electronic Letters, 1999 r.
• [6] C. McIvor, M. McLoone, J. V. McCanny. Modified Montgomery modular multiplication and RSA exponentiation techniques. Computers and Digital Techniques, IEE Proceedings, 2004 r.
• [7] Thomas Blum, Christoph Paar. Montgomery modular exponentiation on reconfigurable hardware. 14th IEEE Symposium on Computer Arithmetic (ARITH-14), 1999 r.