Realizacja koprocesora wspierającego poszukiwanie logarytmu dyskretnego na krzywych eliptycznych z wykorzystaniem częściowej wiedzy

• Autorzy: Kędzierski M. , Misztal M. , Wroński M

Identyfikatory

DOI

10.5604/01.3001.0010.8185

Warianty tytułu

EN

Realization of coprocessor which supports counting of discrete logarithm on elliptic curves with partial knowledge

• Języki publikacji: PL

Abstrakty

PL

W niniejszej pracy podjęto się analizy realizacji w strukturach programowalnych koprocesora wspierającego poszukiwanie logarytmu dyskretnego na krzywych eliptycznych nad ciałem GF(p), gdzie p oznacza dużą liczbę pierwszą. Główna idea realizacji koprocesora polega na zastosowaniu wielu podukładów zdolnych do dodawania punktów, ale o stosunkowo niewielkiej złożoności. Przedstawiono przypadek uproszczony, zakładając, że znamy l najbardziej znaczących bitów parametru klucza k i wykorzystujemy jednowymiarową metodę Gaudry’ego-Schosta. Następnie zaprezentowano uogólnienie i analizę przypadku, gdy nieznane bity znajdują się w wielu rozłącznych przedziałach. W tym celu zaproponowano wykorzystanie wielowymiarowej metody Gaudry’ego-Schosta. Na końcu przedstawiono rozwiązanie, które zapewnia najlepszy stosunek całkowitej przepustowości do ceny urządzenia.

EN

In this paper we analyse realization of a coprocessor which supports counting of discrete logarithm on elliptic curves over the field FG(p), where p is the large prime, in FPGA. Main idea of the realization is based on using modules which are able to add the points and have relatively small resources’ requirements. We showed the simplified case in which we know l most significant bits of key k and we used one-dimensional Gaudry–Schost method. We also generalize that case and analyse the case when unknown bits are given in many disjoint intervals. To do this we propose using a multidimensional Gaudry–Schost method. At the end of this article we show the solution which provides best trade-off between throughput and price of a device.

Słowa kluczowe

PL

krzywe eliptyczne; logarytm dyskretny na krzywych eliptycznych (ECDLP); atak z częściową informacją; wielowymiarowy algorytm Gaudry’ego-Schosta

EN

cryptology; elliptic curves; discrete logarithm on elliptic curves (ECDLP); attacks with partial knowledge; multi-dimensional Gaudry–Schost algorithm

• Wydawca: Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
• Czasopismo: Biuletyn Wojskowej Akademii Technicznej
• Rocznik: 2017
• Tom: Vol. 66, nr 4
• Strony: 57--73
• Opis fizyczny: Bibliogr. 11 poz., rys., tab., wykr.

Twórcy

autor

Kędzierski M.

• Wojskowa Akademia Techniczna, Wydział Cybernetyki, Instytut Matematyki i Kryptologii, ul. Gen. W. Urbanowicza 2, 00-908 Warszawa

autor

Misztal M.

• Wojskowa Akademia Techniczna, Wydział Cybernetyki, Instytut Matematyki i Kryptologii, ul. Gen. W. Urbanowicza 2, 00-908 Warszawa

autor

Wroński M

• Wojskowa Akademia Techniczna, Wydział Cybernetyki, Instytut Matematyki i Kryptologii, ul. Gen. W. Urbanowicza 2, 00-908 Warszawa

Bibliografia

• [1] Blake I., Seroussi G., Smart N., Krzywe eliptyczne w kryptografii, WNT, 1999.
• [2] Chmielowiec A., Wydajne metody generowania bezpiecznych parametrów algorytmów klucza publicznego, Warszawa, 2012.
• [3] Sliverman J.H., The Arithmetic of Elliptic Curves, USA, 2009.
• [4] Zhou Y.B., Feng D.G., Side-Channel Attacks: Ten Years After Its Publication and the Impacts on Cryptographic Module Security Testing, https://eprint.iacr.org, 2005.
• [5] Rosen K.H., Elliptic Curves Number Theory and Cryptography. Second Edition, LLC, 2008.
• [6] Vredendaal Ch., Rank Estimation Methods in Side Channel Attacks, Stanford Security Seminar, 2014.
• [7] Menezes A.J., van Oorschot P.C., Vanstone S.A., Handbook of Applied Cryptography, 1CRC Press, 1, 1996.
• [8] Ruprai R.S., Improvements to the Gaudry-Schost Algorithm for Multidimensional discrete logarithm problem and Applications, Department of Mathematics, Royal Holloway University of London, 2010.
• [9] Gopalakrishnan K., Theriault N., Yao Ch.Z., Solving Discrete logarithms with Partial Know-ledge of the Key, Springer, 2007.
• [10] Montgomery P.L., Modular Multiplication without trial division, JSTOR, 1985.
• [11] Mathematical routines for the NIST prime elliptic curves, https://www.nsa.gov.