Prime Numbers and Cryptosystems Based on Discrete Logarithms

• Autorzy: Grześkowiak, M.

Warianty tytułu

PL

Liczby pierwsze i kryptosystemy oparte na logarytmach dyskretnych

• Języki publikacji: EN

Abstrakty

EN

In this paper, we give a short overview of algorithms of generating primes to a DL systems. The algorithms are probabilistic and works in a polynomial time.

PL

W pracy przedstawiamy algorytmy, które generują liczby pierwsze do kryptosystemów opartych na logarytmach dyskretnych. Zaprezentowane algorytmy są probabilistyczne i działają w wielomianowym czasie.

Słowa kluczowe

PL

kryptosystemy oparte na torusie; kryptosystemy eliptyczne; kryptosystemy hipereliptyczne

EN

torus-based cryptography; elliptic curve cryptography; hyperelliptic curve cryptography

• Czasopismo: Studia Bezpieczeństwa Narodowego
• Rocznik: 2014
• Tom: R. 4, Nr 6
• Strony: 163--176
• Opis fizyczny: Bibliogr. 27 poz.

Twórcy

autor

Grześkowiak, M.

• Adam Mickiewicz University Faculty of Mathematics and Computer Science, Umultowska 87, 61-614 Poznań, Poland,

Bibliografia

• [1] L. Adleman, A subexponential algorithm for the discrete logarithm problem with applications to cryptography, The 20th Annual Symposium on Foundations of Computer Science (Washington, DC, USA), SFCS ’79, IEEE Computer Society, 1979, pp. 55–60.
• [2] L. Adleman, J. DeMarrais, and M. Huang, A subexponential algorithm for discrete logarithms over the rational subgroup of the jacobians of large genus hyperelliptic curves over fnite felds, Algorithmic Number Theory, LNCS 877, 1994, pp. 28–40.
• [3] M. Agrawal, N. Kayal, and N. Saxena, Primes is in p, Ann. of Math. 160 (2004), no. 2, 781–793.
• [4] A. Atkin and F. Morain, Elliptic curves and primality proving, Tech. report, Projet ICSLA RR-1256, INRIA, 1990.
• [5] Z. Borevich and I. Shafarevich, Number theory, Academic Press, 1966.
• [6] H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen, and F. Vercauteren, Handbook of elliptic and hyperelliptic curve cryptography, second edition, 2nd ed., Chapman & Hall/CRC, 2012.
• [7] R. Dupont, A. Enge, and F. Morain, Building curves with arbitrary small mov degree over finite prime felds, J. Cryptology 18 (2005), no. 2, 79–89.
• [8] P. Gaudry, An algorithm for solving the discrete log problem on hyperelliptic curves, Advances in Cryptology - EUROCRYPT 2000, LNCS 1807, 2000, pp. 19–34.
• [9] P. Gaudry, E. Thomé, N. Thériault, and C. Diem, A double large prime variation for small genus hyperelliptic index calculus, IACR Cryptology ePrint Archive (2004), 153.
• [10] D. Gordon, Discrete logarithms in gf(p) using the number feld sieve, SIAM J. Discret. Math. 6 (1993), no. 1, 124–138.
• [11] M. Grześkowiak, An algorithmic construction of fnite elliptic curves of order divisible by a large prime, Fund. Inform., to appear.
• [12] M. Grześkowiak, Algorithms for relatively cyclotomic primes, Fund. Inform. 125 (2013), no. 2, 161–181.
• [13] G. H. Hardy and J. E. Littlewood, Some problems of partition numerorum iii: On the expression of a number as a sum of primes, Acta Math. 44 (1922), 1–70.
• [14] A. Joux, A new index calculus algorithm with complexity l(1/4+o(1)) in very small characteristic, 2013.
• [15] A. Joux and R. Lercier, The function feld sieve in the medium prime case, Advances in Cryptology - EUROCRYPT 2006, LNCS 4004 (Serge Vaudenay, ed.), Springer Berlin Heidelberg, 2006, pp. 254–270 (English).
• [16] A. Joux, R. Lercier, N. Smart, and F. Vercauteren, The number feld sieve in the medium prime case, Advances in Cryptology - CRYPTO 2006, LNCS 4117, Springer Berlin Heidelberg, 2006, pp. 326–344.
• [17] N. Koblitz, Hyperelliptic cryptosystems, Journal of Cryptology 1 (1989), no. 3, 139–150 (English).
• [18] A. Lenstra, Using cyclotomic polynomials to construct efcient discrete logarithm cryptosystems over fnite felds.
• [19] A. Lenstra and E. Verheul, The xtr public key system, Advances in Cryptology CRYPTO 2000, LNCS 1880, 2000, pp. 1–19.
• [20] S. Pohlig and M. Hellman, An improved algorithm for computing logarithms over and its cryptographic signifcance (corresp.), IEEE Trans. Inf. Theor. 24 (2006), no. 1, 106–110.
• [21] J. Pollard, Monte Carlo methods for index computation (modp), Mathematics of Computation 32 (1978), 918–924.
• [22] K. Rubin and A. Silverberg, Torus-based cryptography, Advances in Cryptology - CRYPTO 2003, LNCS 2729, 2003, pp. 349–365.
• [23] K. Rubin and A. Silverberg, Using primitive subgroups to do more with fewer bits, Algorithmic Number Theory 6th International Symposium, ANTS-VI, LNCS 3076, 2004, pp. 18–41.
• [24] E. Savaş T.A. Schmidt, and C. K. Koç, Generating elliptic curves of prime order, Cryptographic Hardware and Embedded Systems CHES 2001, LNCS 2162, 2001, pp. 145–161.
• [25] P. Smith and C. Skinner, A public-key cryptosystem and a digital signature system based on the lucas function analogue to discrete logarithms, In Advances in Cryptology ASIACRYPT 1995, LNCS 917, 1995, pp. 357–364.
• [26] N. Thériault, Index calculus attack for hyperelliptic curves of small genus,Advances in Cryptology - ASIACRYPT 2003, LNCS 2894, 2003, pp. 75–92.
• [27] A. Weng, Constructing hyperelliptic curves of genus 2 suitable for cryptography, Math. Comput. 72 (2003), no. 241, 435–458.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).