Analysis of the RSA-cryptosystem in abstract number rings

N. V. Kondratyonok

Journal of the Belarusian State University. Mathematics and Informatics, Tome 1 (2020), pp. 13-21.

Résumé

Quantum computers can be a real threat to some modern cryptosystems (such as the RSA-cryptosystem). The analogue of the RSA-cryptosystem in abstract number rings is not affected by this threat, as there are currently no factorization algorithms using quantum computing for ideals. In this paper considered an analogue of RSA-cryptosystem in abstract number rings. Proved the analogues of theorems related to its cryptographic strength. In particular, an analogue of Wiener’s theorem on the small secret exponent is proved. The analogue of the re-encryption method is studied. On its basis the necessary restrictions on the parameters of the cryptosystem are obtained. It is also shown that in numerical Dedekind rings the factorization problem is polynomial equivalent to factorization in integers.

Détail

Keywords: RSA-cryptosystem; abstract number ring; Dedekind ring; factorization; ideal.

Bibliographie

[1] R. L. Rivest, A. Shamir, L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems”, Communications of the ACM, 21(2) (1978), 120–126 | DOI | MR | Zbl

[2] B. Li, “Generalizations of RSA public key cryptosystem”, IACR, Cryptology ePrint Archive, 2005, arXiv: https://arxiv.org/ia.cr/2005/285

[3] H. Elkamchouchi, K. Elshenawy, H. Shaban, “Extended RSA cryptosystem and digital signature schemes in the domain of Gaussian integers”, Proceedings of the 8th International conference on communication system (Singapore), 1 (2002), 91–95 | DOI

[4] A. Koval, B. Verkhovsky, “Analysis of RSA over Gaussian Integers Algorithm”, Proceedings of the Fifth International conference on information technology: new generations (Las Vegas, Nevada), 2008, 101–105, Washington: IEEE Computer Society | DOI

[5] A. N. El-Kassar, R. A. Haraty, Y. A. Awad, N. C. Debnath, “Modified RSA in the domains of Gaussian integers and polynomials over finite fields”, Proceedings of the ISCA 18th International conference on computer applications in industry and engineering (Honolulu, Hawaii). International Society for Computers and their Applications (ISCA), 2005, 298–303

[6] M. Vaskouski, N. Kondratyonok, N. Prochorov, “Primes in quadratic unique factorization domains”, Journal of Number Theory, 168 (2016), 101–116 | DOI | MR | Zbl

[7] K. A. Petukhova, S. N. Tronin, “RSA Cryptosystem for Dedekind rings”, Lobachevskii Journal of Mathematics, 37 (2016), 284–287 | DOI | MR | Zbl

[8] A. Brunyate, P. L. Clark, “Extending the Zolotarev – Frobenius approach to quadratic reciprocity”, The Ramanujan Journal, 37(1) (2015), 25–50 | DOI | MR | Zbl

[9] H. A. Cohen, “Course in computational algebraic number theory”, Berlin: Springer, 1996, 545 | MR

[10] H. Cohen, “Advanced topics in computational number theory”, New York: Springer, 1999, 599 | MR

[11] D. Coppersmith, “Small solutions to polynomial equations, and low exponent RSA vulnerabilities”, Journal of Cryptology, 10 (1997), 233–260 | DOI | MR | Zbl

[12] R. Dedekind, “Uber den zusammenhang zwischen der theorie der ideale und der theorie der hoheren congruenzen”, Abhandlungen der Koniglichen Gesellschaft der Wissenschaften in Gottingen, 23 (1878), 3–38

[13] D. Wikstrom, “On the l-Ary GCD-algorithm in rings of integers; Automata, Languages and Programming”, 32nd International Colloquium, ICALP (Lisbon, Portugal), 2005, 1189–1201, Berlin: Springer | DOI | MR | Zbl

[14] M. J. Wiener, “Cryptanalysis of short RSA secret exponents”, IEEE Transactions on Information Theory, 36(3) (1990), 553–558 | DOI | MR | Zbl

[15] J. S. Coron, A. May, “Deterministic polynomial-time equivalence of computing the RSA secret key and factoring”, Journal of Cryptology, 20(1) (2007), 39–50 | DOI | MR | Zbl

[16] M. Vaskouski, N. Kondratyonok, “Shortest division chains in unique factorization domains”, Journal of Symbolic Computation, 77 (2016), 175–188 | DOI | MR | Zbl

[17] M. M. Vaskovskii, “Polinomialnaya ekvivalentnost vychisleniya funktsii Eilera RSA-modulya i poiska sekretnogo klyucha v kvadratichnykh evklidovykh koltsakh”, Mezhdunarodnyi kongress po informatike: informatsionnye sistemy i tekhnologii, Belarus, Minsk (Materialy Mezhdunarodnogo nauchnogo kongressa), BGU

[18] O. V. Babul, D. V. Vasilev, “O faktorizatsii idealov v koltsakh tselykh algebraicheskikh chisel”, Izvestiya Natsionalnoi akademii nauk Belarusi. Seriya fiziko-matematicheskikh nauk, 1 (2011), 32–36 | MR

[19] M. E. Pohst, “Computational algebraic number theory”, Basel: Birkhauser, 1993, 88 | DOI | MR | Zbl

[20] R. Kannan, A. Bachem, “Polynomial algorithms for computing the smith and hermite normal forms of an integer matrix”, SIAM Journal on Computing, 8(4) (1979), 499–507 | DOI | MR | Zbl

[21] M. M. Vaskovskii, G. V. Matveev, “Verifikatsiya modulyarnogo razdeleniya sekreta”, Zhurnal Belorusskogo gosudarstvennogo universiteta; Matematika; Informatika, 2 (2017), 17–22 | MR

[22] G. V. Matveev, V. V. Matulis, “Sovershennaya verifikatsiya modulyarnoi skhemy”, Zhurnal Belorusskogo gosudarstvennogo universiteta. Matematika. Informatika, 2 (2018), 4–9 | Zbl

[23] G. V. Matveev, “Razdelenie sekreta v koltsakh mnogochlenov ot neskolkikh peremennykh s ispolzovaniem kitaiskoi teoremy ob ostatkakh”, Zhurnal Belorusskogo gosudarstvennogo universiteta. Matematika. Informatika, 3 (2019), 129–133 | DOI | Zbl

[24] E. Gekke, “Lektsii po teorii algebraicheskikh chisel”, Moskva: Gosudarstvennoe izdatelstvo tekhniko-teoreticheskoi literatury, 1940, 261

[25] M. M. Glukhov, I. A. Kruglov, A. B. Pichkur, A. V. Cheremushkin, “Vvedenie v teoretiko-chislovye metody kriptografii”, Sankt-Peterburg: Lan, 2011, 400

[26] N. Koblitz, “Course in number theory and cryptography”, New York: Springer-Verlag, 1994, 235 | MR | Zbl