I need help understand the attack on NTRU cryptosystem https://en.wikipedia.org/wiki/NTRUEncrypt
For example:
Given Alice’s public key: q = 131 and h = 100. Suppose that Bob sends the encrypted message e =78. I do the attacker find his message m before encryption?
Attempt:
The relevant lattice L is the one with the basis (1,100), (0,131). I can use Gauss’ lattice basis reduction algorithm to find a reduced basis of L: (4, 7), (-13, 10)
So I can guess f=4, g=7, then calculate
$a=fe \mod q = 50$
$m=f^{-1} a \mod g =2$?
I cannot validate this with $1 \leq r \leq 8$:
r=5: $e=r*h+m \mod q=72\ne78$
r=6: $e=86$ ...
An Introduction to Mathematical Cryptography has a section 7.13.1 Gaussian Lattice Reduction on page 436