Wydajne metody generowania bezpiecznych parametrów algorytmów klucza publicznego

Abstract

Przedmiotem niniejszej pracy jest opracowanie i analiza nowego, efektywnego algorytmu mnożenia wielomianów i szeregów potęgowych o współczynnikach całkowitych oraz jego zastosowanie w procesie generowania krzywych eliptycznych na potrzeby kryptografii. Operacje tego typu odgrywają fundamentalną rolę podczas generowania parametrów dla systemów klucza publicznego, a ich efektywna implementacja ma bezpośrednie przełożenie na szybkość działania tych algorytmów w praktycznych zastosowaniach. Algorytm został specjalnie opracowany w celu przyspieszenia procesu generowania wielomianów modularnych, ale jego właściwości numeryczne okazały się na tyle dobre, że z całą pewnością znajdzie on zastosowanie również w przypadku innych problemów obliczeniowych. Istotą konstrukcji nowej metody było przede wszystkim dostosowanie jej do równoległego wykonywania obliczeń. W dzisiejszych czasach jest to bardzo ważna cecha, gdyż pozwala na pełne wykorzystanie mocy obliczeniowej oferowanej przez współczesne procesory.

Połączenie twierdzenia chińskiego o resztach i szybkiej transformaty Fouriera umożliwiło opracowanie bardzo efektywnej metody mnożenia. Pod pewnymi warunkami jest ona asymptotycznie szybsza niż algorytm wykorzystujący szybką transformatę Fouriera zarówno do mnożenia liczb, jak i wielomianów. Wynik ten jest niewątpliwie najważniejszym wnioskiem teoretycznym płynącym z tej pracy.

Praca zawiera dokładny opis konstrukcji algorytmu wraz z lematami i twierdzeniami uzasadniającymi poprawność jego działania. Przedstawione zostały wyniki testów numerycznych oraz implementacja wzorcowa proponowanego al- gorytmu. Otrzymane wyniki praktyczne pokazują, że nową metodę można skutecznie stosować już w przypadku wielomianów mających kilkaset współczynników.

This paper aims to develop and analyze a new, effective algorithm for multiplying polynomials and power series with integer coefficients, and to use this algorithm in the process of generating elliptic curves for cryptographic applications. Such operations are of fundamental importance when generating parameters for public key cryptosystems, whereas their effective implementation translates directly into the speed of such algorithms in practical applications. The algorithm has been designed specifically to accelerate the process of generating modular polynomials, but due to its good numerical properties it may surely be used to solve other computational problems as well. The basic idea behind this new method was to adapt it to parallel computing. Nowadays, it is a very important property, as it allows to fully exploit the computing power offered by modern processors.

The combination of the Chinese Remainder Theorem and the Fast Fourier Transform made it possible to develop a highly effective multiplication method. Under certain conditions, it is asymptotically faster than the algorithm based on Fast Fourier Transform when applied to multiply both: numbers and polynomials. Undoubtedly, this result is the major theoretical conclusion of this paper. This paper describes in detail the construction of the algorithm as well as theorems and lemmas justifying its correct operation. Moreover, it presents the results of numerical tests and a model implementation of the proposed algorithm. The achieved practical results show that the new method may be successfully applied to polynomials even with several hundred coefficients.