Analiza możliwości sprzętowej kryptoanalizy szyfrów opartych na krzywych eliptycznych

• Autorzy: Majkowski P. , Wojciechowski T. , Wojtyński M. , Kotulski Z. , Rawski M.

Warianty tytułu

EN

Cryptanalysis of elliptic curve based ciphers in reprogrammable structures

• Języki publikacji: PL

Abstrakty

PL

Artykuł opisuje jednostkę sprzętową służącą do efektywnego rozwiązywania zagadnienia logarytmu dyskretnego na krzywej eliptycznych zdefiniowanej nad ciałem GF(2n) za pomocą równoległej wersji algorytmu rho Pollard'a. Układ zawiera moduł sumatora punktów na krzywej eliptycznej wykorzystujący do przeprowadzania operacji w ciele bazowym podmoduł korzystający z właściwości baz normalnych. Artykuł opisuje także genera-tor kodu VHDL pozwalający na uogólnienie rozwiązania na dowolne ciała charakterystyki dwa dla których występuje gaussowska baza normalna. Analizy efektywności działania układu pozwoliły na oszacowanie czasu potrzebnego na kryptoanalizę krzywych z listy wyzwań firmy Certicom.

EN

This paper presents the FPGA implementation of parallel version of the rho Pollard algorithm used for solving a discrete logarithm problem in the elliptic curve addition of points on an elliptic curve defined over discrete field GF(2n). In proposed implementation a hardware module has been developed that performs arithmetic operations in the base field, using characteristic features of optimal normal bases. A special generator of the VHDL source code that generalizes ze the solution is also presented in this paper. The resulting FPGA cores has been used to estimate time necessary for cryptanalysis of curves from the Certicom Challenge List.

Słowa kluczowe

PL

kryptografia asymetryczna; kryptoanaliza; krzywe eliptyczne; bazy normalne; obliczenia rozproszone; rho Pollard; ECDLP; ECC

EN

public key cryptography; cryptanalysis; elliptic curves; optimal normal bases; distributed calculations; rho Pollard algorithm; ECDLP; ECC

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2008
• Tom: R. 54, nr 8
• Strony: 536--539
• Opis fizyczny: Bibliogr. 11 poz., rys., tab., wzory

Twórcy

autor

Majkowski P.

autor

Wojciechowski T.

autor

Wojtyński M.

autor

Kotulski Z.

autor

Rawski M.

• Instytut Telekomunikacji, Politechnika Warszawska,

Bibliografia

• [1] Blake Ian, Seroussi Gadiel, Smart Nigel. Krzywe eliptyczne w kryp-tografii. WNT 2004.
• [2] Gao Shuhong, Lenstra W. Hendrik. Optimal Normal Bases.1992.
• [3] Gawinecki Jerzy, Szmidt Janusz. Zastosowanie ciał skończonych i krzywych eliptycznych w kryptografii. Wojskowa Akademia Tech-niczna 1999.
• [4] IEEE P1363. Standard Specyfications for Public Key Cryptography. Draft 13. 1999.
• [5] Majkowski Piotr. Automatyzacja procesu tworzenia sprzętowego narzędzia służącego do rozwiązywania zagadnienia logarytmu dys-kretnego na krzywych eliptycznych. praca magisterska napisana pod opieką prof. Zbigniewa Kotulskiego. Politechnika Warszawska 2008.
• [6] Majkowski Piotr, Wojciechowski Tomasz, Wojtyński Maciej, Rawski Mariusz. Realizacja jednostki wspomagającej kryptoanalizę szyfrów opartych na krzywych eliptycznych w strukturach reprogramowal-nych. RUC 2007.
• [7] Majkowski Piotr, Wojciechowski Tomasz, Wojtyński Maciej, Rawski Mariusz. System sprzętowo-programowy służacy do rozproszonej kryptoanalizy szyfrów opartych na krzywych eliptycznych. ENIGMA 2007.
• [8] Menezes Alfred , Hankerson Darrel, Vanstone Scott. Guide to elliptic curve cryptography. Springer 2004.
• [9] Certicom. ECC Challenge. www.certicom.com/download/aid-111/cert_ecc_challenge.pdf
• [10] Pollard J. M. Monte Carlo methods for index computation (mod p). Math. Comp. 32, 918-924. 1978.
• [11] van Oorschot P. C., Wiener M. J. Parrallel collision search with cryptoanalytic applications. Journal of Cryptography, volume 12, number 1, 1-12, 1999.