System typu SoC do kryptoanalizy szyfrów opartych na krzywych eliptycznych

• Autorzy: Orkiszewski M. , Wojciechowski T. , Rawski M.

Warianty tytułu

EN

System-on-Chip solution for cryptanalysis of elliptic curve based ciphers

• Języki publikacji: PL

Abstrakty

PL

W pracy zaprezentowano system typu SoC (System-on-Chip) zrealizowany w układach FPGA wspomagający obliczenia pozwalające na złamanie szyfru opartego na krzywych eliptycznych. Do ataku kryptoanalitycznego wykorzystano algorytm rho Pollarda. System zbudowany jest ze sprzętowych jednostek obliczeniowych HardRho pracujących pod kontrolą procesora NiosII i wykorzystuje interfejs Ethernet do komunikacji zewnętrznej. Omówiona została koncepcja budowy rozproszonego systemu obliczeniowego składającego się z jednostek obliczeniowych będących systemami typu SoC.

EN

Public-key cryptosystems allow secure connections and data exchange through unsafe communication channel without the need of a previous secure key exchange. One of popular cryptosystems used nowadays is Elliptic Curve Cryptosystems (ECC). Cryptanalytic attack on ECC system involves solving the Elliptic Curve Discrete Logarithm Prob-lem (ECDLP). The best known algorithm used to solve ECDLP is Pollard's rho method. So far successful attacks on ECC systems have mostly been based on distributed computer networks. In this paper a hardware cryptanalytic system is presented. The system is implemented in FPGA devices and performs computations of rho Pollard's algorithm. System is based on SoC solution (System-on-Chip) and works under control of a central server in order to form a greater distributed computing system. In the first paragraph of this paper there are presented the aim of work as well as the reasons for choosing FPGA devices and SoC solution. The second paragraph gives the theoretical background [3, 4, 5], explains the basic terms and presents the rho Pollard's algorithm [6, 7]. The third paragraph describes HardRho computation unit HardRho hardware (Fig. 1) and shows differences between the current and recent unit version of unit described in [8, 9]). The fourth paragraph of the paper deals with the SoC solution composed of several HardRho units, NiosII processor and Ethernet communication interface. The system structure (Fig. 2) and internal components [11, 12] are presented. The fifth paragraph is nfocused on the results of implementation and the estimated time of cryptanalysis of an elliptic curve ECC2-89 [1] (Tab. 1). The HardRho unit and [13] are compared (Tab. 2). The obtained results suggest high efficiency of the presented SoC solution. The future investigations and possible optimisation of the system are discussed.

Słowa kluczowe

PL

kryptoanaliza; obliczenia rozproszone; system-on-chip; SoC; krzywe eliptyczne; rho Pollard; ECC; ECDLP

EN

cryptanalysis; distributed computing; system on chip SoC; elliptic curves; rho Pollard; ECC; ECDLP

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2010
• Tom: R. 56, nr 7
• Strony: 745--748
• Opis fizyczny: Bibliogr. 15 poz., rys., tab., wzory

Twórcy

autor

Orkiszewski M.

autor

Wojciechowski T.

autor

Rawski M.

• Politechnika Warszawska, Wydział Elektroniki i Technik Informacyjnych, Instytut Telekomunikacji, ul. Nowowiejska 15/19, 00-665 Warszawa,

Bibliografia

• [1] Certicom Research, Certicom ECC Challenge 10-11-2010. http:// www.certicom.com/index.php/the-certicom-ecc-challenge
• [2] RSA Laboratories, Cryptographic Challenges. http://www.rsa.com/ rsalabs/node.asp?id=2091
• [3] Blake I., Seroussi G., Smart N.: Krzywe eliptyczne w kryptografii. WNT 2004.
• [4] Gao S., Lenstra H. W.: Optimal Normal Bases.1992.
• [5] IEEE P1363. Standard Specifications for Public Key Cryptography. Draft 13. 1999.
• [6] Pollard J.M.: Monte Carlo methods for index computation mod p, Mathematics of Computation, Volume 32, 1978.
• [7] Menezes A., Hankerson D., Vanstone S.: Guide to elliptic curve cryptography. Springer 2004.
• [8] Majkowski P., Wojciechowski T., Wojtyński M., Kotulski Z., Rawski M.: Analiza możliwości sprzętowej kryptoanalizy szyfrów opartych na krzywych eliptycznych, Miesięcznik Naukowo-Techniczny Pomiary Automatyka Kontrola, s. 536-539, nr 08, 2008.
• [9] Majkowski P., Wojciechowski T., Wojtyński M., Rawski M.: Realizacja jednostki wspomagającej kryptoanalizę szyfrów opartych na krzywych eliptycznych w strukturach reprogramowalnych, Miesięcznik Naukowo-Techniczny Pomiary Automatyka Kontrola, s. 24-26, nr 7, 2007.[10] Itoh T., Tsujii S.: A Fast Algorithm for Computing Multiplicative Inverses in GF(2m) Using Normal Bases, Information and Comp., vol. 78, pp. 171-177, 1988.
• [10] Itoh T., Tsujii S.: A Fast Algorithm for Computing Multiplicative Inverses in GF(2m) Using Normal Bases, Information and Comp., vol. 78, pp. 171-177, 1988.
• [11] LwIP - A Lightweight TCP/IP stack http://savannah.nongnu.org/ projects/lwip/
• [12] Altera Corporation, Avalon Memory-Mapped Interface Specification http://www.altera.com/literature/manual/mnl_avalon_spec.pdf
• [13] Bulens, P., de Dormale G. M., Quisquater J. -J.: Hardware for Collision Search on Elliptic Curve over GF(2m). SHARCS 2006, Ecrypt Workshop.
• [14] National Institute of Standard and Technology, Recommended elliptic curves for federal government use, July 1999. http://csrc.nist.gov/ groups/ST/toolkit/documents/dss/NISTReCur.pdf
• [15] Projekt badawczy: http://www.ecc-challenge.info/