Tags: paillier svp lattice lll crypto shamir
Rating:
* Shamir's Secret Sharing Scheme and Paillier cryptosystem combined
* The quadratic polynomial $f(x)$ on $F_p$ is randomly generated and the result of $y = f(x)$ is calculated for each $x=1\sim5$. All shares are given so we should decrypt SSSS immediately but funky noises are added to $y$ and it's encrypted with Paillier cryptosystem, so we cannot decrypt it.
* The following values are random-generated among encryption:
* The coefficients $a,b,c$ in the polynomial of SSSS and modulus $p$ (all with 1024bits, c is the flag)
$f(x)=ax^2+bx+c\bmod p$
* The noises added to secret shares, $e_i$ (256bit)
$y_i=f(x_i)+e_i\:(x_i=1,2,3,4,5)$
* The prime factors $p_i,q_i$ (1024bit, 512bit) of the modulus $N_i$ in the Paillier cryptosystem
$N_i=p_iq_i\:(p_i\approx p+e_i)$
* The coefficients $k_i$ (256bit) of Paillier cryptosystem
$g_i=1+k_iN_i\bmod N_i^2$
* The random value $r_i$ (256bit) introduced in Paillier cryptosystem
$c_i=g_i^{y_i}r_i^{N_i}\bmod N_i^2$
* $N_i,g_i,c_i$ are given
### Solution
On closer inspection, $e_i$: 256bit is a bit small compared to $p$: 1024bit which satisfies $p_i\approx p+e_i$. Thus about 75% of the highest bits of the five $N_i$ are shared. It smells like lattice-y :sunglasses:
I dunno the appliable method for this situation, but I googled some and found [this paper](https://hal.archives-ouvertes.fr/hal-01288914/document) that can hint me (this is paper in 2010. cool)
According to the paper, when the size of $q$ is $\alpha$ bits and the $t$ bits of LSB of $p$ is shared for $k$ RSA public keys, it should satisfy
$$t\geqq\frac{k}{k-1}\alpha$$
to be broken with lattices. In this challenge the coefficients are $t=768,\alpha=512,k=5$ so the constraint is satisfied.
We consider the following lattice (with row vectors) reffering to the paper:
$$
\mathcal{L}=\left[\begin{array}{ccccccccccccccc}
K & 0 & 0 & 0 & 0 & N_{2} & N_{3} & N_{4} & N_{5} & 0 & 0 & 0 & 0 & 0 & 0\\
0 & K & 0 & 0 & 0 & -N_{1} & 0 & 0 & 0 & N_{3} & N_{4} & N_{5} & 0 & 0 & 0\\
0 & 0 & K & 0 & 0 & 0 & -N_{1} & 0 & 0 & -N_{2} & 0 & 0 & N_{4} & N_{5} & 0\\
0 & 0 & 0 & K & 0 & 0 & 0 & -N_{1} & 0 & 0 & -N_{2} & 0 & -N_{3} & 0 & N_{5}\\
0 & 0 & 0 & 0 & K & 0 & 0 & 0 & -N_{1} & 0 & 0 & -N_{2} & 0 & -N_{3} & -N_{4}
\end{array}\right]
$$
where $K$ is $K=2^{n-t}$ with $n$ as the size of $N$. Then the coefficients of base vectors of the shortest vector will become $q_1,\cdots,q_5$, and $N_i$ can be factorized. This can be achieved by applying LLL and solve SVP, and inspect the leading 5 elements of the shortest vector.
Now we have prime factors of $N_i$. Then Paillier cryptosystem can be decrypted ($k_i$ can be retrieved from the basis of $g_i=1+k_iN_i$) so we also have $y_i$.
By denoting $p_i$ as $p_i=p+e_i+\delta_i\:(\delta_i<\text{approx 1000})$ and organizing the equations around $f(x)$, we get:
$$
\begin{aligned}
f\left(1\right)-\delta_{1} &=y_{1}-p_{1}\bmod p\\
f\left(2\right)-\delta_{2} &=y_{2}-p_{2}\bmod p\\
f\left(3\right)-\delta_{3} &=y_{3}-p_{3}\bmod p\\
f\left(4\right)-\delta_{4} &=y_{4}-p_{4}\bmod p\\
f\left(5\right)-\delta_{5} &=y_{5}-p_{5}\bmod p\\
\end{aligned}
$$
By the way the following is satisfied:
$$
\begin{aligned}
f\left(1\right)-3f\left(2\right)+3f\left(3\right)-f\left(4\right)=&\left(a+b+c\right)-3\left(4a+2b+c\right)\\
&+3\left(9a+3b+c\right)-\left(16a+4b+c\right)\\
=&0
\end{aligned}
$$
so if we define $d_i$ as $d_i:=y_i-p_i$:
$$
d_1-3d_2+3d_3-d_4=kp-\delta_1+3\delta_2-3\delta_3+\delta_4\:(k\in\mathbb{Z})
$$
so we can get the good approximate value of the small multiple of $p$. Actually, $k$ was $1$ in this chal.
And also:
$$
\begin{aligned}
3f\left(1\right)-3f\left(2\right)+f\left(3\right)=&3\left(a+b+c\right)-3\left(4a+2b+c\right)\\
&+\left(9a+3b+c\right)\\
=&c
\end{aligned}
$$
then if we calculate the following:
$$
3d_1-3d_2+d_3\bmod p=c-3\delta_1+3\delta_2-\delta_3
$$
with the approximate value of $p$ above, we can get
```
c = 20713161535193761558784128809506534938870667474516138291919014014508231236559472271196444472147718083977745751388526121905625505
```
as the approximate solution of $c$. Convert it to string and we get:
```
"zer0pts{excellent_w0rk!y0u_are_a_master_0f_crypt0!!\x19\xA1"
```
Guess its some least bits and the flag is:
`zer0pts{excellent_w0rk!y0u_are_a_master_0f_crypt0!!!}`
{%gist hakatashi/0fce3ea3e73c4ef1615108594ed46b2e %}
