3
$\begingroup$

I know that calculating the cardinality of $U_{pq}$ is infeasible and therefore it is extremely hard to break a code using Lagrange's theorem. But later on my studies i realized main principle of RSA can be generalized to any abelian finite group. Is there another group structure $G$ that is suitable for RSA (i.e. it is infeasible to compute $|G|$)?

Of course in such cases, we wouldn't be able to do padding, hence our algorithm would be deterministic and unsafe. But i am just asking out of curiosity.

For expressing my thoughts more formally:

Given a finite abelian group $(G, \cdot)$, every function $f:G \to G$,

$$f(x) = x^n$$ is an automorphism (structure-preserving permutation) of $G$ for $(|G|, n) = 1$. Since it is an isomorphism, it does have an inverse isomorphism $f^{-1} = x^m$ for $m$ being modular inverse of $n$ in modulo $|G|$.

So, summing up:

$$f: x \mapsto x^n$$ $$f^{-1}: x \mapsto x^m$$

We can treat each element of $G$ as a message. We can encrypt this message with $f$, we can decrypt resulting code with $f^{-1}$, as we did in RSA. All difficulty to break this algorithm is the difficulty of calculating $|G|$.

This is a generalization of the main principle of RSA. Is it suitable for a group structure other than $U_{pq}$?

$\endgroup$
1
$\begingroup$

The key point in RSA is the fact that inversion in modulo $|G|$ is hard, of course other groups are a priori okay to build a secure encryption scheme.

For example $U_{pqr}$, with $p, q, r$ large primes seems to be okay. But it will be probably less efficient (keys and ciphertexts will be probably larger for the same level of security).

Of course, it is not because the problem seems to be hard, that we can conclude with the same level of confidency that the RSA-problem-hardness. The RSA-problem has been particularly well-studied. And if you choose to change the group used, the risk to discover that "inversion in modulo $|G|$ is not so hard" is more important.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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