Analiza algorytmów mnożenia w ciele GF(2m)

• Autorzy: Pamuła D. , Hrynkiewicz E. , Tisserand A.

Warianty tytułu

EN

Direct multiplication over GF(2m) - analysis

• Języki publikacji: PL

Abstrakty

PL

Artykuł przedstawia analizę algorytmów mnożenia w ciele GF(2m). Algorytmy analizowane są pod kątem ich możliwości implementacji w sprzęcie. Badane są ich wady i zalety w celu ułatwienia projektantom kryptosystemów opartych na krzywych eliptycznych podjęcia decyzji co do tego jakiego algorytmu mnożenia w ciele skończonym użyć aby stworzone urządzenie było wydajne i nie zajmowało nadmiernej ilości zasobów.

EN

Cryptographic systems are based on mathematical theories, thus they strongly depend on the performance of arithmetic units comprising them. If an arithmetic operator does not take a considerable amount of resources or is time non efficient, it negatively impacts the performance of the whole cryptosystem. The purpose of this paper is to analyse the hardware possibilities of the algorithms performing multiplication in GF(2m) which are used for elliptic curve cryptography(ECC) applications. There are only two operations defined in this field: addition considered as a trivial one, it is a simple bitwise xor ,and multiplication - a very complex operation. To conform to the requirements of ECC systems, the multipliers should be fast, area efficient and, what is the most important, perform multiplication of big numbers (100 - 600 bit). The paper presents analysis of GF(2m) two-step modular multiplication algorithms. It considers classical (school) multiplication, matrix-vector approach and Karatsuba - Ofman algorithm, exploring thoroughly their advantages and disadvantages.

Słowa kluczowe

PL

kryptografia krzywych eliptycznych; GF(2m); mnożenie

EN

ECC; finite fields; GF(2m); multiplication; Karatsuba-Ofman

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2011
• Tom: R. 57, nr 1
• Strony: 58--60
• Opis fizyczny: Bibliogr. 7 poz., tab., wzory

Twórcy

autor

Pamuła D.

autor

Hrynkiewicz E.

autor

Tisserand A.

• Politechnika Śląska, Instytut Elektroniki, ul. Akademicka 16, 44-100 Gliwice,

Bibliografia

• [1] Lidl, R., Niederreiter, H.: Introduction to finite fields and their applications, Cambridge University Press. 1994.
• [2] Hankerson, D., Menzes, A., Vanstone, S. A.: Guide to Elliptic Curve Cryptography. Springer-Verlag, NY, 2004.
• [3] Erdem, S. S., Yanik, T., Koc, C. K.: Polynomial Basis Multiplication over GF(2m). Acta Applicandae Mathematicae. Vol. 93, 2006.
• [4] Karatsuba, A., Ofman, Y.: Multiplication of Multidigit Numbers on Automata. Soviet Phys. Doklady, vol. 7, strony 595-596, 1963.
• [5] Deschamps, J-P., Imana, J.L., Sutter G.D.: Hardware Imple-mentation of Finite-Field Arithmetic. McGraw-Hill, 2009.
• [6] Bernstein, D. J.: Multidigit Multiplication for Mathematicians, 2001.
• [7] NIST. Digital Signature Standard. Draft – FIPS publication 186-3. National Institute of Standards and Technology, United States, 2008.