0
$\begingroup$

I am on the verge to understanding RSA, but suddenly a question popped into mind. When we are calculating $U(N)$ i.e $U(PQ)$, we are taking invertible elements that are co-prime to $N$. For example, $U(5\times2)$ becomes $\{1,3,7,9\}$. We are ultimately never using the inverses in $U(N)$ in either key generation or encryption. But just the order of $U(N)$ is what we need. We are using invertible elements in the order of $U(N)$ as a part of key generation, And that part I understand why, but the never using the invertible elements within $U(N)$ itself. So thereby the question, Why we don't use additive groups? Is it a security thing? PS, I don't know much about additive groups, just the multiplicative group as it's a part of RSA and I am studying RSA. Thanks :)

$\endgroup$
  • 3
    $\begingroup$ With additive group, reversing the multiplication (using division) would be easy as the order of the group is $N$ obviously. With multiplication, calculating the discrete root would be difficult. $\endgroup$ – DannyNiu Mar 19 at 6:29
2
$\begingroup$

Why we don't use additive groups? Is it a security thing?

Yes, it's a security consideration. If we used the additive group $(\Bbb Z_N,+)$ rather than $(\Bbb Z_N^*,*)$ for RSA, public encryption would go $M\mapsto C=e\,M\bmod N$ rather than $M\mapsto C=M^e\bmod N$. Problem is, decryption would be trivial since anyone with the public key $(N,e)$ could compute $d=e^{-1}\bmod N$ (e.g. using the extended Euclidean algorithm) and then decrypt as $S\mapsto M=d\,S\bmod N$, without knowing the factorization of $N$.

This is related to the order of $(\Bbb Z_N,+)$ being $N$ part of the public key $(N,e)$, when the order of $(\Bbb Z_N^*,*)$ is $\Phi(N)$, which is not easily obtained from the public key.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank You. I almost figured that out myself. But being not a mathematician, I was not sure about if what I thought was true. So thanks for the clarification. :) $\endgroup$ – C0DEV3IL Mar 19 at 20:06
1
$\begingroup$

Your question is not clear. Which additive group would you like to use? RSA is hard because the group ${\mathbb Z}_N^*$ has unknown order (assuming the factorization of $N$ is unknown). Which additive group has that property?

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank You. I almost figured that out myself. But being not a mathematician, I was not sure about if what I thought was true. So thanks for the clarification. :) $\endgroup$ – C0DEV3IL Mar 19 at 20:06

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.