MODIFICATION OF POLLARD RHO ALGORITHM USING NEGATION MAPPING

  • Sa'aadah Sajjana Carita Cryptographic Engineering Study Program, Cyber and State Crypto Polytechnic
  • Herman Kabetta Cryptographic Engineering Study Program, Cyber and State Crypto Polytechnic
DOI: https://doi.org/10.30598/barekengvol16iss4pp1159-1166
Keywords: el gamal encryption, elliptic curve cryptography, pollard rho algorithm, negation map

Abstract

El Gamal encryption was introduced in 1985 and is still commonly used today. Its hardness is based on a discrete logarithm problem defined over the finite abelian cyclic group group chosen in the original paper was but later it was proven that using the group of Elliptic Curve points could significantly reduce the key size required. The modified El Gamal encryption is dubbed its analog version. This analog encryption bases its hardness on Elliptic Curve Discrete Logarithm Problem (ECDLP). One of the fastest attacks in cracking ECDLP is the Pollard Rho algorithm, with the expected number of iterations where is the number of points in the curve. This paper proposes a modification of the Pollard Rho algorithm using a negation map. The experiment was done in El Gamal analog encryption of elliptic curve defined over the field  with different values of small digit . The modification was expected to speed up the algorithm by  times. The average of speed up in the experiment was 1.9 times.

Downloads

Download data is not yet available.

References

D. R. Kohel, “Cryptography,” 2015. http://iml.univ-mrs.fr/~kohel/tch/M2-CryptoSymetrique/crypto.pdf (accessed May 23, 2022).

B. Schneier, Applied cryptography: Protocols, algorithm, and source code in C. The University of Michigan: Wiley, 1996.

A. J. Menezes, P. C. Van Oorschot, and S. A. Vanstone, Applied Cryptography. Boca Raton: Taylor & Francis, 1997.

ECRYPT (European Network of Excellence in Cryptology), “Hardness of the Main Computational Problems Used in Cryptography,” Leuven, 2007.

T. Elgamal, “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,” IEEE Trans. Inf. Theory, vol. 31, no. 4, pp. 469–472, 1985.

W. Diffie and M. E. Hellman, “New Directions in Cryptography,” IEEE Trans. Inf. Theory, vol. 22, no. 6, pp. 644–654, 1976.

H. R. Hashim, “The Discrete Logarithm Problem in the ElGamal Cryptosystem over the Abelian Group U(n) Where n= p^m ,or 2p^m,” Int. J. Math. Trends Technol., vol. 7, no. 3, pp. 184–189, 2014.

N. Koblitz, “Elliptic curve cryptosystems,” Math. Comput., vol. 48, no. 177, pp. 203–209, 1987.

K. Lauter, “The advantages of elliptic curve cryptography for wireless security,” IEEE Wirel. Commun., vol. 11, no. 1, pp. 62–67, 2004.

A. Blumenfeld, “Discrete Logarithms on Elliptic Curves,” J. Rose-Hulman Undergrad. Math. J., vol. 12, no. 1, pp. 30–57, 2011.

A. A. Neamah, “New Collisions to Improve Pollard’s Rho Method of Solving the Discrete Logarithm Problem on Elliptic Curves,” J. Comput. Sci., vol. 11, no. 9, pp. 971–975, 2015.

J. H. Silverman, The Arithmetic of Elliptic Curves. New York: Springer, 2009.

ISARA, “Isogeny-Based Cryptography Tutorial,” 2019. [Online]. Available: https://www.isara.com/resource-center/isogeny-based-cryptography-tutorial.html.

M. Z. Seet, J. Franklin, and P. Brown, “Elliptic Curve Cryptography Improving the Pollard-Rho Algorithm,” University of New South Wales, Australia, 2007.

J. M. Pollard, “Monte Carlo Methods for Index Computation (mod p),” vol. 32, no. 143, pp. 918–924, 1978.

I. Duursma, P. Gaudry, and F. Morain, “Speeding up the Discrete Log Computation on Curves with Automorphisms,” in Advances in Cryptology - ASIACRYPT’99, 1999, pp. 103–121.

A. Menezes, E. Teske, and A. Weng, “Weak Fields for ECC,” in Topics in Cryptology – Cryptographers’ Track at the RSA Conference, 2004, pp. 366–386.

D. Hankerson, A. Menezes, and S. Vanstone, Guide to Elliptic Curve Cryptography. New York: Springer, 2004.

A. J. Menezes, T. Okamoto, and S. A. Vanstone, “Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field,” IEEE Trans. Inf. Theory, vol. 39, no. 5, pp. 1639–1646, 2003.

E. Teske, “Speeding Up Pollard’s Rho Method for Computing Discrete Logarithms,” in International Algorithmic Number Theory Symposium, 1998, pp. 541–554.

I. Muchtadi-Alamsyah, T. Ardiansyah, and S. S. Carita, “Pollard Rho Algorithm for Elliptic Curves over GF(2^n) with Negation Map, Frobenius Map, and Normal Basis,” Far East J. Math. Sci., no. IV, pp. 385–402, 2013.

Published
2022-12-15
How to Cite
[1]
S. Carita and H. Kabetta, “MODIFICATION OF POLLARD RHO ALGORITHM USING NEGATION MAPPING”, BAREKENG: J. Math. & App., vol. 16, no. 4, pp. 1159-1166, Dec. 2022.
Issue
Vol 16 No 4 (2022): BAREKENG: Jurnal Ilmu Matematika dan Terapan
Section
Articles

Copyright (c) 2022 Sa'aadah Sajjana Carita, Herman Kabetta

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Authors who publish with this Journal agree to the following terms:

  1. Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
  2. Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
  3. Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.