# Chinese Remainder Theorem and Elgamal

I am studying an encryption scheme which is Elgamal-like where I think CRT can help optimise the encryption and decryption but I am not sure if I am applying CRT the correct way.

I have a cyclic group $$G$$ of order $$n=p_1p_2q$$, generator $$g$$ of $$G$$, an element $$h=g^x$$ of $$G$$ where $$x$$ is a random integer and the secret key, and a message $$m\in\mathbb{Z}_{p_1p_2}^*$$. This group $$G$$ has a cyclic subgroup $$F$$ of order $$p_1p_2$$ generated by $$f$$. Computing discrete logs in $$F$$ is easy which we use to recover our message $$m$$ as follows:

Encryption -- Compute ciphertext $$(c_1,c_2) = (g^r,\ f^mh^r)$$ where $$r$$ is a random integer

Decryption -- Compute $$c_2/c_1^x = f^m = l$$. Recover $$m$$ by computing $$m = l^{-1}\pmod{p_1p_2}$$.

I am applying CRT in the final step by computing $$l^{-1}\pmod{p_1}$$ and $$l^{-1}\pmod{p_2}$$ and then combining them both using CRT to recover $$m$$. I have a feeling this is stupid because I am not really optimising anything, infact making it more computation heavy as single inversion modulo is faster than two inversions modulo + CRT. This is also visible when I time these two methods -- single inversion modulo $$p_1p_2$$ is faster.

So how should I properly apply CRT in these type of schemes?

• Decryption -- Compute $c_2/c_1^x = f^m = l$. Recover $m$ by computing $$m = l^{-1}\pmod{p_1p_2}$$ Is it correct? $l^{-1} = f^{-m}$ and I don't see how $l^{-1}\pmod{p_1p_2}$ gives you $m$. – Changyu Dong Oct 6 '18 at 9:33
• Oh, I see it is an abuse of notation on my part. $f$ and $f^m$ are not integers, they are ideals and $l$ is an ideal which has $m^{-1}$ which can be easily read off. Proposition 1 from eprint.iacr.org/2015/047.pdf – Papa Delta Oct 6 '18 at 19:34
• That's too much an abuse, better to use more conventional notations in the question. – Changyu Dong Oct 6 '18 at 20:02