Abstract
While it is well-known that the RSA public-key cryptosystem can be broken if its modulusN can be factored, it is not known whether there are other ways of breaking RSA. This paper presents a public-key scheme which necessarily requires knowledge of the factorization of its modulus in order to be broken. Rabin introduced the first system whose security is equivalent to the difficulty of factoring the modulus. His scheme is based on squaring (cubing) for encryption and extracting square (cube) roots for decryption. This introduces a 1∶4 (1∶9) ambiguity in the decryption. Various schemes which overcome this problem have been introduced for both the quadratic and cubic case. We generalize the ideas of Williams' cubic system to larger prime exponents. The cases of higher prime order introduce a number of problems not encountered in the quadratic and cubic cases, namely the existence of fundamental units in the underlying cyclotomic field, the evaluation of higher power residue symbols, and the increased difficulty of Euclidean division in the field.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
E. Bach, Explicit bounds for primality testing and related problems,Math. Comp., Vol. 55, No. 191 (1990) pp. 355–380.
J. Buchmann, On the computation of units and class numbers by a generalization of Lagrange's algorithm,J. Number Theory, Vol. 26, No. 1 (1987) pp. 8–30.
J. Buchmann and H. C. Williams, On principal ideal testing in totally complex quartic fields and the determination of certain cyclotomic constants,Math. Comp., Vol. 48, No. 177 (1987) pp. 55–66.
J. Buchmann and H. C. Williams, On principal ideal testing in algebraic number fields.J. Symb. Comp., Vol. 4 (1987) pp. 11–19.
E. E. Kummer,Collected Papers, Vol. 1, Springer, Berlin (1975).
E. Landau,Vorlesungen über Zahlentheorie, Chelsea, New York (1969).
H. W. Lenstra, Jr., Euclid's algorithm in cyclotomic fields,J. Lond. Math. Soc. Vol. 2, No. 10 (1975) pp. 457–465.
H. W. Lenstra, Jr., Euclidean number fields I,Math. Intelligencer, Vol. 2 (1979/80) pp. 6–15.
J. Loxton, D. S. P. Khoo, G. J. Bird, and J. Seberry, A cubic residue code equivalent to factorization,J. of Cryptology, Vol. 5, No. 2 (1992) pp. 139–150.
J. M. Masley and H. L. Montgomery, Cyclotomic fields with unique factorization,J. Reine Angew. Math., Vol. 286/287 (1976) pp. 248–256.
R. G. McKenzie,The Ring of Cyclotomic Integers of Modulus Thirteen Is Norm-Euclidean, Ph.D. Dissertation, Department of Mathematics, Michigan State University (1988).
M. O. Rabin, Digitized Signatures and Public-Key Functions as Intractable as Factorization, M.I.T. Lab for Computer Science, Tech. Rep. LCS/TR-212 (1979).
H. J. S. Smith,Report on the Theory of Numbers, Chelsea, New York (1965).
J. Uspensky, Note sur les nombres entiers dépendant d'une racine cinquième de l'unité,Math. Ann., Vol. 66 (1909) pp. 109–112.
H. C. Williams, A modification of the RSA public-key encryption procedure,IEEE Trans. Inf. Theory, Vol. IT-26, No. 6 (1980) pp. 726–729.
H. C. Williams, An M3 public-key encryption scheme,Advances in Cryptology—CRYPTO '85 Proceedings, Springer, Berlin (1986), pp. 358–368.
K. S. Williams, Explicit forms of Kummer's complementary theorems to his law of quintic reciprocity,J. Reine Angew. Math., Vol. 288 (1976) pp. 207–210.
Author information
Authors and Affiliations
Additional information
Communicated by: R. Mullin
Rights and permissions
About this article
Cite this article
Scheidler, R., Williams, H.C. A public-key cryptosystem utilizing cyclotomic fields. Des Codes Crypt 6, 117–131 (1995). https://doi.org/10.1007/BF01398010
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01398010