5
$\begingroup$

If we assume the strength of RSA is based on the difficulty of factoring (which I know we can't guarantee) and we compose the modulus of some other quadratic ring that is a unique factorization domain like the Gaussian integers, what is the resistance to attacks based on factoring with classical computing techniques?

As far as I know they are still vulnerable to quantum computing attacks as factoring in most (all?) of these rings is reducible to the hidden subgroup problem for finite Abelian groups, but for classical attacks involving number field sieving, are these rings as difficult to factor as the integers?

For instance, if I composed a key in classical RSA of 2048 bits, is 1024bits of the real part and 1024 bits of the quadratic coefficient equivalent? (1024bits a + 1024bits bi for example for Gaussian integers?)

Are there any tricks to make it easier to factor or do discrete log in these fields, like there are in polynomials?

$\endgroup$
3
  • $\begingroup$ Note: Scheidler-Williams (DCC 1995) and Takagi-Naito (IEICE Trans. J81-A1, 19980in Japanese) may be relaed to this question and discuss security. $\endgroup$
    – xagawa
    Apr 17, 2014 at 0:36
  • $\begingroup$ Can you explain what you mean by "compose the modulus of some other quadratic ring"? Do you mean that instead of multiplying two integers to get the modulus, we multiply two elements of some quadratic ring? Have you worked out what the corresponding version of Euler's lemma is? What is the order of the multiplicative group of such rings? What's the motivation for your question? Are you hoping to get a cryptosystem that will be faster than RSA, for a given security level? $\endgroup$
    – D.W.
    Apr 17, 2014 at 7:35
  • $\begingroup$ Instead of multiplying two integers, we multiply two elements of a quadratic ring, yes; For example the gaussian integers are a quadratic ring of the integral values of the complex numbers. Euler's totient function and lemma work fine for such quadratic rings, as principle ideal domains concepts of modular arithmetic can be represented without much difficulty. The motivation is mathematical interest with increased security a happy accident; It's possible that other unique factorization domains are harder to attack than the integers. $\endgroup$
    – dezakin
    Apr 19, 2014 at 4:07

1 Answer 1

7
$\begingroup$

There are three distinct computational problems related to RSA. They are:

  • FACTORIZATION: given an RSA modulus $n$, find its prime factors $p$ and $q$;
  • ORDER: given an RSA modulus $n$, find the order $\lambda$ of the multiplicative group modulo $n$;
  • RSA Problem: given a ring element $a \in \mathbb{Z}_n$, a public exponent $e$ and an RSA modulus, find an element $b \in \mathbb{Z}_n$ such that $b^e = a \mod n$.

For the integers, the following reductions are known:

  • Given the factorization of a number $n$, it is easy to find the order: $\lambda = \varphi(n) = \varphi(p) \varphi(q) = (p-1)(q-1)$.

  • Given the order of the multiplicative group modulo $n$, it is easy to find the inverse exponent (if it exists): $d = e^{-1} \mod \lambda$. Given the inverse exponent, it is easy to solve the RSA problem: $b = a^{d} = b^{ed} = b^1 \mod n$.

  • Given the order $\lambda$ of the multiplicative group modulo $n$, there exists an efficient way to calculate the prime factors of $n$.

  • However, no algorithm is known that can turn an RSA problem solver into an algorithm that either finds the order $\lambda$ or factorizes $n$.

We can write these relations concisely as FACTORIZATION $\equiv_p$ ORDER $\geq_p$ RSA Problem.

Note: RSA is secure based on the assumption that the RSA problem is hard. This assumption implies, in turn, that factorization is hard. This assumption is weaker than the assumption that factorization is hard.

You correctly note that it is possible to define an analogue of RSA on other unique factorization domains (UFDs). However, on all the UFDs, factorization is either easy, or equivalent to factorization over the integers.* For example: there is a polynomial-time algorithm for factoring polynomials in one variable (see this survey). Factorization over the Gaussian integers reduces to factorization over the real integers (see this stackexchange answer).

*: I should qualify this statement by saying that not all UFDs are known. Perhaps there does exist a UFD where factorization is harder than it is for the integers. But finding this would be a scientific breakthrough because its applications to cryptography would be great.

Lastly, I should not that quantum computers might not be able to factorize efficiently in just any UFD. Shor's algorithm for factorization first finds the order $\lambda$ of the muliplicative group modulo $n$, and then uses this value to find the prime factors of $n$. The quantum algorithm to find the order will translate to any group. However, the reduction from FACTORIZATION to ORDER might not hold for all UFDs.

$\endgroup$
1
  • $\begingroup$ Your answer doesn't show that factorization in all UFDs where there isn't a polynomial time algorithm (like monoid rings and ore extensions of polynomials because of the existence of the derivative) is equivalent to factoring in $\mathbb Z$. In particular, I'm not entirely sure its obvious that the number field sieve is automatically applicable to all commutative quadratic rings, let alone non-commutative or non-associative algebra's with unique factorization like the Hurwitz quaternions or the Cayley integers in the octonions. $\endgroup$
    – dezakin
    Apr 19, 2014 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.