91Ó°ÊÓ

Alice's public key for a knapsack cryptosystem is $$ \mathbf{M}=(5186,2779,5955,2307,6599,6771,6296,7306,4115,7039) . $$ Eve intercepts the encrypted message \(S=26560\). She also breaks into Alice's computer and steals Alice's secret multiplier \(A=4392\) and secret modulus \(B=8387\). Use this information to find Alice's superincreasing private sequence \(\mathbf{r}\) and then decrypt the message.

The guidelines for choosing NTRU public parameters \((N, p, q, d)\) require that \(\operatorname{gcd}(p, q)=1\). Prove that if \(p \mid q\), then it is very easy for Eve to decrypt the message without knowing the private key. (Hint. First do the case that \(p=q .\) )