Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 20

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  elliptic curves
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
EN
Computing isogenies between elliptic curves is a significant part of post-quantum cryptography with many practical applications (for example, in SIDH, SIKE, B-SIDH, or CSIDH algorithms). Comparing to other post-quantum algorithms, the main advantages of these protocols are smaller keys, the similar idea as in the ECDH, and a large basis of expertise about elliptic curves. The main disadvantage of the isogeny-based cryptosystems is their computational efficiency - they are slower than other post-quantum algorithms (e.g., lattice-based). That is why so much effort has been put into improving the hitherto known methods of computing isogenies between elliptic curves. In this paper, we present new formulas for computing isogenies between elliptic curves in the extended Jacobi quartic form with two methods: by transforming such curves into the short Weierstrass model, computing an isogeny in this form and then transforming back into an initial model or by computing an isogeny directly between two extended Jacobi quartics.
2
EN
The purpose of this paper is to generate cryptographically strong elliptic curves over prime fields Fp, where p is a Mersenne prime, one of the special primes or a random prime. We search for elliptic curves which orders are also prime numbers. The cryptographically strong elliptic curves are those for which the discrete logarithm problem is computationally hard. The required mathematical conditions are formulated in terms of parameters characterizing the elliptic curves. We present an algorithm to generate such curves. Examples of elliptic curves of prime order are generated with Magma.
3
Content available remote Integral points on elliptic curves y2 = x(x - 2m)(x + p)
EN
We provide a description of the integral points on elliptic curves y2 = x(x-2m) x (x + p), where p and p + 2m are primes. In particular, we show that for m = 2 such a curve has no nontorsion integral point, and for m = 1 it has at most one such point (with y > 0). Our proofs rely upon numerical computations and a variety of results on quartic and other diophantine equations, combined with an elementary analysis.
PL
Przez tysiąclecia tworzono, udoskonalano i łamano dziesiątki rozwiązań, których jedynym celem było uniemożliwienie odczytania informacji przez postronnych. Doprowadziło to do powstania dwóch przeciwstawnych w swoich działaniach dziedzin - kryptografii i kryptoanalizy. W dobie komputerów zrezygnowano ze wszystkich dotychczasowych rozwiązań i wprowadzono zupełnie nowe, z których za najbezpieczniejsza można uznać RSA i szyfry oparte o krzywe eliptyczne. Oba są uznawane za niemożliwe do złamania. Wynika to bezpośrednio z zależności matematycznych użytych w ich definicji. W dotychczasowych badaniach wykazano już kilka ich słabości, lecz nadal nie ma rozwiązania, które działałoby w każdym jednym przypadku. Z uwagi na to postanowiono przyjrzeć się głębiej słabym punktom szyfrów eliptycznych z uwzględnieniem wszystkich dotychczas dostępnych informacji.
EN
For millennia, dozens of solutions, which sole purpose was to prevent outsiders from reading information, have been developed, refined and broken. This led to the emergence of two opposing fields - cryptography and cryptanalysis. In the age of computers, all existing solutions have been abandoned and new ones have been introduced, with the most secure ones RSA and ciphers based on elliptic curves. Both considered impossible to break. This result directly from the math used in their definitions. Some previous researches have already shown some of their weaknesses, but there is still no solution that would work in every single case. Because of this, it was decided to take a closer look at the weak points of elliptic ciphers, taking into account all the information available to date.
5
Content available remote Constructing Elliptic Curves for the GLV Method with Low-cost Decomposition
EN
The GLV method allows to improve scalar multiplication on an elliptic curve E/Fqwith an efficiently computable endomorphism Φ : E → E over Fq. For points in a subgroup of large prime order r this requires decomposition of scalar k = k0 + k1λ mod r, where Φ acts on the subgroup of order r as multiplication by λ ∊ Fr and k0, k1 are integers O(√r) . In this note we consider the case when λ is of the form λ = 2s + a, where a is a small integer and λ=O(√r), which allows very easy and fast decomposition of k especially in hardware implementations. We give a method to construct such elliptic curves based on the complex multiplication method, and give examples of elliptic curves for λ ∊ {2s, 2s - 1} and various security levels.
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.
7
Content available Properties of reducible polynomials
EN
We consider polynomials p(x) over the 2-element field F2. If p(x) of degree n is irreducible, then a set of polynomials of degree less than n together with operations (of addition and multiplication) modulo p(x) forms the finite field GF(2n). If p(x) of degree n is reducible, then the set of all polynomials of degree less than n contains several groups with respect to multiplication modulo p(x). Properties of these groups are described in Section 3. In Section 4 is presented a polynomial factorization algorithm. Irreducible polynomials are widely used (for instance in cryptography) due to the possibility of an efficient representation of all the elements from GF(2n) on a fixed number of bits.
PL
Analizowano wielomiany z jedną zmienną nad ciałem skończonym F2. Jeśli wielomian p(x) stopnia n jest nierozkładalny, to zbiór wielomianów stopnia mniejszego od n wraz z operacjami (dodawania i mnożenia) modulo p(x) tworzy ciało skończone GF(2n). Jeżeli p(x) stopnia n jest rozkładalny, w zbiorze wielomianów stopnia mniejszego od n można wyróżnić kilka podzbiorów, które wraz z działaniem *p (mnożenie modulo p(x)) tworzą grupy. Własności tych grup (oparte na wykonanych testach) opisano w sekcji 3. W sekcji 4 zaproponowano algorytm faktoryzacji wielomianów. Wydajność zapisywania elementów GF(2n) na ustalonej liczbie bitów zachęca do wykorzystywania wielomianów nierozkładalnych na przykład w kryptografii.
PL
Celem artykułu jest zaprezentowanie metod doboru bezpiecznych krzywych eliptycznych stosowanych do konstruowania protokołów kryptograficznych oraz sprzętową implementacje koprocesora realizującego operacje arytmetyczne na tej rodzinie krzywych algebraicznych.
EN
The main purpose of this paper is to present some methods of choosing secure ECs for construction of cryptographical protocols and hardware implementation of coprocesor that performs aritmetical operations over this set of algebraic curves.
9
Content available remote Uogólnione struktury uprawnień z hierarchią
PL
Struktury dostępu są używane przy zagadnieniach bezpieczeństwa związanych z sytuacjami gdzie jeden lub więcej podmiotów próbuje uzyskać pewien zasób. Przedstawimy uogólnienie struktur dostępu na przypadek wielu zasobów, co pozwala na zgrabne ujęcie schematów progowych i hierarchicznych. Zaprezentujemy też użycie tzw. iloczynu dwuliniowego, definiowanego w grupie punktów n-torsyjnych krzywej eliptycznej nad ciałem skończonym na dwóch przykładowych hierarchicznych schematach przydzielania kluczy.
EN
Access structures are used in cases associated with situations when one or more entities are trying to get a resource. We will present a generalization to the case of access structures many resources, which allows for a nice description of thresholds and hierarchical schemes. We will also present the use of the so-called bilinear product, defined in the group of n-torsion points of an elliptic curve over a finite field on two exemplary hierarchical allocation key schemes.
10
Content available remote Nowe wyzwania dla polskiej kryptologii drugiej dekady XXI wieku
PL
W artykule analizujemy wyzwania dla polskiej kryptologii XXI wieku ze szczególnym uwzględnieniem potrzeb narodowej kryptologii i roli, jaką spełniają w niej wybrane dziedziny matematyki, takie jak teoria liczb i geometria algebraiczna. W szczególności pokreślono rolę i bezpieczeństwo kryptosystemów bazujących na iloczynach dwuliniowych, a także problemy złożoności obliczeniowej ważnych dla kryptologii algorytmów deterministycznych. Wskazano na znaczenie funkcji typu L we współczesnej kryptografii i kryptoanalizie.
EN
In this paper we analyze the challenges for the twenty-first century Polish cryptology with special emphasis on the needs of the national cryptology and the role they perform in the selected areas of mathematics such as number theory and algebraic geometry. In particular, westress the role and security of bilinear based cryptosystems, as well as the problems of computational complexity of deterministic algorithms important for cryptology. We pointed out the importance of L-functions in modern cryptography and cryptoanalysis.
11
Content available remote Kodowanie deterministyczne na krzywych eliptycznych
PL
W pracy przedstawiono problematykę znajdowania punktów na krzywych eliptycznych określonych nad ciałami skończonymi, ze szczególnym uwzględnieniem algorytmów deterministycznych. Algorytmy takie nie były znane do 2005 roku. Wcześniejsze metody, chociaż dość praktyczne, miały charakter probabilistyczny, a ich efektywność była uwarunkowana hipotezami Riemanna.
EN
The methods of finding points on elliptic curves over finite fields are presented with special emphasis on deterministic algorithms. Such algorithms were unknown until 2005. Earlier methods were probabilistic in nature and their efficiency was strongly conditioned on unproved Riemann conjectures.
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.
PL
Opisano jednostkę sprzętową służącą do efektywnego rozwiązywania zagadnienia logarytmu dyskretnego na krzywych eliptycznych zdefiniowanych nad ciałem GF(2n) za pomocą równoległej wersji algorytmu rho Pollarda. Rozwiązanie tego zagadnienia umożliwia ataki kryptoanalityczne na szyfry oparte na krzywych eliptycznych. Zaprezentowano wyniki implementacji oraz zbadano efektywność obliczeń.
EN
This paper describes hardware unit designed for effective solving Elliptic Curve Discrete Logarithm Problem using parallel version of rho Pollard's algorithm. Solving this problem allows cryptanalytic attacks on Elliptic Curve Cryptosystems. In the paper results of system implementation are presented, also effectiveness of calculations are analyzed.
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.
PL
Artykuł opisuje jednostkę sprzętową służącą do efektywnego dodawania punktów na krzywej eliptycznej zdefiniowanej nad ciałem GF(2n). Układ zawiera moduł wykonujący operacje arytmetyczne w ciele bazowym, korzystający z właściwości optymalnych baz normalnych. Wyniki efek-tywności działania układu pozwoliły następnie na oszacowanie czasu potrzebnego na kryptoanalizę krzywej ECC2-89 (jednej z listy wyzwań firmy Certicom) za pomocą równoległej wersji algorytmu Rho Pollarda.
EN
This paper presets the FPGA implementation of algorithm for addition of points on an elliptic curve defined over discrete field GF(2n). In proposed implementation a module was used that performs arithmetic operations in the base field, using characteristic features of optimal normal bases. The resulting FPGA core was used to estimate time necessary to cryptanalyze curve ECC2-89 (the one from the Certicom Challenge List) using parallel version of Pollard Rho algorithm.
16
Content available remote On equations y^2 = x^n + k in a finite field
EN
Solutions of the equations y^2 = x^n + k (n = 3,4) in a finite field are given almost explicitly in terms of k.
17
EN
The paper describes an implementation of the crypto engine, which realizes doubling and addition of points on an elliptic curve. The implementation utilizes Galois Fields of characteristic 2 with a polynomial base representation.
PL
Artykuł zawiera opis budowy koprocesora wyznaczającego wynik podwajania i dodawania dwóch punktów na krzywej eliptycznej wykorzystujących operacje na elementach z ciała GF(2¹⁵⁵), przedstawionych z wykorzystaniem baz wielomianowych.
PL
Artykuł zawiera opis algorytmu mnożenia z wykorzystaniem przedstawienia elementów działania za pomocą baz normalnych oraz zastosowanie przykładowego rozwiązania układu realizującego to działanie w jednostce arytmetycznej wyznaczającej wynik podwojenia punktu i dodawania dwóch punktów na krzywej eliptycznej. Dzięki zastosowaniu przedstawionych w artykule rozwiązań uzyskano przyśpieszenie realizacji działań w szczególności dla przypadku podwojenia punktu.
EN
The multiplication algorithm based on the elements entered in the normal bases and their implementation in the arithmetical unit is described in this article. This unit realizes doubling and addition of two elements on the alliptic curve. As a result of this solution we obtained faster realization of this operation especially in the case of the point doubling.
19
EN
The aim of this note is the numerical investigation of the propertion of cyclic groups among all groups E(Fp) for the elliptic curves over fixed prime fields Fp. We have calculated the orders of the all investigated elliptic curves.
PL
Celem pracy było numeryczne przebadanie stosunku ilości grup cyklicznych do wszystkich grup E(Fp) dla krzywych eliptycznych nad wybranym ciałem Fp (gdzie p jest liczbą pierwszą). Policzono także rzędy tych grup.
20
Content available remote Algorytm znajdowania logarytmu dyskretnego na krzywych hipereliptycznych
PL
W pracy tej przedstawione są pojęcia związane z krzywymi hipereliptycznymi i kryptosystemami na nich opartymi. Pokazany jest algorytm wyznaczania logarytmu dyskretnego w jakobianie krzywej hipereliptycznej. Dla tego algorytmu przedstawiona jest analiza złożoności obliczeniowej i przykłady wykorzystania do złamania kryptosystemów opartych na krzywych hipereliptycznych.
EN
This paper contains basic definitions and theorems connected to the hyperelliptic curves and the cryptosystems based on those curves. There is presented the liptic curves defined over finite fields. For this algorithm the analysis of complexity is presented and the examples of using it to break cryptosystems based on hyperelliptic curves are given.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.