# Question about Damgård–Jurik crypto system

In the proof, I found this equation

$c^d = (g^mr^{n^s})^d = (\boxed{(1+n)^{j m}x^m}r^{n^s})^d = \boxed{(1+n)^{j md\pmod{n^s}}}(\boxed{x^m}r^{n^s})^{d\pmod{\lambda}}$,

where $g=(1+n)^{j x}\pmod{n^{s+1}}$, $n=pq$ is an RSA module number, $\lambda$ is the least common multiple of $(p − 1)$ and $(q − 1)$, and $\lambda|d$.

I don't know why $((1+n)^{j m}x^mr^{n^s})^d = {(1+n)^{j md\pmod{n^s}}}({x^m}r^{n^s})^{d\pmod{\lambda}}$ holds, can anyone tell me? Thank you!

• I'm not sure about the second part, but $(1+n)^{n^s}=1$ mod $n^{s+1}$ – Florian Bourse Jul 5 '18 at 12:57

The simple answer is that the element $(n+1)$ is of order $n^s$, i.e. $(n+1)^{n^s} \equiv 1 \bmod n^{s+1}$. Thus the first part can be written as $(1+n)^{jmd \bmod n^s}$.
For the other part it is $(x^mr^{n^s})^d$, it is written in that way so that it is easier to see the setting that $d \equiv 0 \bmod \lambda$ ensures this part $(x^mr^{n^s})^d \equiv 1 \bmod n^{s+1}$. To see why, note that $x^\lambda \equiv 1 \bmod n^{s+1}$ and also $(r^{n^s})^\lambda \equiv 1 \bmod n^{s+1}$. The explaination is as the following:
• We know that $x\in H$ where $H=\{g^{n^s} \bmod n^{s+1}|g\in Z_{n^{s+1}}^*\}$ is a subgroup of $Z_{n^{s+1}}^*$, we know $r \in Z_{n}^*$ and $Z_{n}^*$ is a subgroup of $Z_{n^{s+1}}^*$ (thus $r$ is also in $Z_{n^{s+1}}^*$).
• We know the exponent (the least common multiple of the orders of all elements of the group) of $Z_{n^{s+1}}^*$ is $n^s\lambda$ (see here, $\lambda$ in the paper is a shorthand for $\lambda(n)$). In other words, $a^{n^s\lambda}\equiv 1 \bmod n^{s+1}$ holds for any element $a$ in $Z_{n^{s+1}}^*$
• Therefore, $x^\lambda=g^{n^s\lambda}\equiv 1 \bmod n^{s+1}$, and $r^{n^s\lambda}\equiv 1 \bmod n^{s+1}$
It thus follows that if $d\equiv 0 \bmod \lambda$ (i.e. $d = k\lambda$ for some k), then $(x^mr^{n^s})^d \equiv 1 \bmod n^{s+1}$.
• Sir, can you please tell me why $(x^mr^{n^s})^d\mod{n^{s+1}} =({x^m}r^{n^s})^{d\pmod{\lambda}}$ in detail? Thank you – Felix LL Jul 9 '18 at 12:39