In NTRU crypto system I have used these polynomials and parameters:
$N = 17, p = 7, q = 64$ and $f$ as private key is:
$$f = -1 + x + x^2 - x^4 + x^6 + x^9 - x^{10}$$
So the inverse of $f$ in ring $\mathbb{Z}[X]/(X^N-1)$ is:
$$f_p = 3x^{16} + 3x^{15} + x^{14} + 6x^{13} + 5x^{12} + 6x^{11} + x^{10} + 2x^9 + 2x^8 + 3x^7 + 4x^4 + 3x^3 + 3x^2 + 4x + 4$$
and
$$f_q = 63x^{16} + 54x^{15} + 7x^{14} + 44x^{13} + 51x^{12} + 16x^{11} + 35x^{10} + 12x^9 + 50x^8 + 29x^7 + 11x^6 + 4x^5 + 43x^4 + 19x^3 + 44x^2 + 50x + 45$$
and choose $g$ to construct public key such that:
$$g = -1 + x^2 + x^3 + x^5 - x^8 - x^{10} $$
then compute $h$ as public key as follow:
$$h = pf_q \cdot g \pmod q$$
then:
$$h = 49x^{16} + 45x^{15} + 62x^{14} + 46x^{13} + 14x^{12} + 44x^{11} + 33x^{10} + 26x^9 + 27x^8 + 8x^7 + 21x^6 + 2x^5 + 58x^4 + 52x^3 + 45x^2 + 54x + 54$$
Choose message $m = -x^{13} + x^{12} + x^{11} - x^{10} + x^9 + x^7 + x^6 + x^5 - x^3 - 1$, and random polynomial $r = x^{10} + x^8 - x^7 + x^5 - x^3 - x^2 + x - 1$ to encode the message.
As we know, $e = r \cdot h + m$, so
$$e = 18x^{16} + 37x^{15} + 23x^{14} + 14x^{13} + 17x^{12} + 6x^{11} + 6x^{10} + 25x^9 + 55x^8 + 56x^7 + 32x^6 + 45x^5 + 36x^4 + 58x^3 + 24x^2 + 32x + 30$$
But when I want to decrypt the $e$ in NTRU algorithm, first compute $a$:
$$a = f \cdot e \pmod q = -9x^{16} + 6x^{15} + 2x^{14} + 18x^{13} + 6x^{12} + 6x^{11} + 16x^{10} - 17x^9 + 2x^8 + 9x^7 + 32x^5 + 3x^3 - 4x^2 - 20x + 16$$
and finally compute the original message with $m = b \cdot f_p \pmod p$ such that $b = a \pmod p$. So
$$b = -2x^{16} - x^{15} + 2x^{14} - 3x^{13} - x^{12} - x^{11} + 2x^{10} - 3x^9 + 2x^8 + 2x^7 - 3x^5 + 3x^3 + 3x^2 + x + 2$$
and then:
$$m = -x^{16} + x^{15} + 2x^{14} + x^{13} - 3x^{12} + x^{11} - x^{10} - 2x^9 + 3x^8 - 3x^7 - 2x^6 - 2x^5 + 3x^4 + 2x^3 + x^2 - x - 3$$
But as you see this is not equal with the previous message $m$.
This is my problem, where I have mistake?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Could it be a case of the known NTRU decryption failure? If yes: on a fine-tuned, real-life-sized NTRU system, this is supposed to be so rare as never being seen in practice. $\endgroup$– fgrieu ♦Apr 23, 2015 at 7:32
-
$\begingroup$ Assuming the computations are right, I guess the problem is with the parameters (maybe too small?). You should try standard parameters. This paper could be of use. $\endgroup$– cygnusvApr 23, 2015 at 8:11
-
$\begingroup$ BTW, why don't you try with the more usual choice $p = 3$? $\endgroup$– cygnusvApr 23, 2015 at 8:12
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I've searched about this problem these two days, considering the paper cygnusv mentioned, and finally after reading the problem related to the pqc implementation, I guess that's the condition which is not formally mentioned in NTRU papers. And this condition $$q > p(6d + 1)$$ must be true in order for the probability of unrecoverable messages to be less than $2^{-80}$.