I'm doing a project where I have to implement the NTRUEncrypt public key cryptosystem. This is th开发者_如何学编程e first step according to their guide in encrypting - "Alice, who wants to send a secret message to Bob, puts her message in the form of a polynomial m with coefficients {-1,0,1}" . I want to know how I can make my message into a polynomial. Thank you.
You can do it however you like. Perhaps the most straightforward way is to convert your message to a ternary representation
"Hello" -> 72, 101, 108, 108, 111 -> 02200, 10202, 11000, 11000, 11010
So I'm converting the characters to their ASCII representation and then converting those representations to their ternary representation (assuming that I'm limited to the 7-bit ASCII space I only need five ternary digits).
Then convert the ternary representation to a polynomial on {-1, 0, 1}
by mapping the ternary digit 0
to 0
, the ternary digit 1
to 1
and the ternary digit 2
to -1
and assuming that the digit corresponding to 3^k is the coefficient of x^k1:
02200 -> p1(x) = 0 + 0 * x + (-1) * x^2 + (-1) * x^3 + 0 * x^4
10202 -> p2(x) = (-1) + 0 * x + (-1) * x^2 + 0 * x^3 + 1 * x^4
11000 -> p3(x) = 0 + 0 * x + 0 * x^2 + 1 * x^3 + 1 * x^4
11000 -> p4(x) = 0 + 0 * x + 0 * x^2 + 1 * x^3 + 1 * x^4
11010 -> p5(x) = 0 + 1 * x + 0 * x^2 + 1 * x^3 + 1 * x^4
and then my message is
p1(x) + x^5 * p2(x) + (x^5)^2 * p3(x) + (x^5)^3 * p4(x) + (x^5)^4 * p5(x)
so that my polynomial's coefficients are
(0, 0, -1, -1, 0, -1, 0, -1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1).
Regardless how you do it, the point is that you can represent your message as a polynomial however you like. It's just preferred that you find a bijection from your message space to the space of polynomials on {-1, 0, 1}
that is easily computed and has an easily computed inverse.
1 This is the crux of the transformation. A five-digit ternary number a
4
a
3
a
2
a
1
a
0
corresponds exactly to evaluating the polynomial a
4
* x^4 + a
3
* x^3 + a
2
* x^2 +a
1
* x + a
0
* x^0
at x = 3
. So there is an obvious one-to-one correspondence between polynomials on {-1, 0, 1}
and ternary numbers.
I work for NTRU, so I'm glad to see this interest.
The IEEE standard 1363.1-2008 specifies how to implement NTRUEncrypt with the most current parameter sets. The method it specifies for binary->trinary conversion is:
Convert each three-bit quantity to two ternary coefficients as follows, and concatenate the resulting ternary quantities to obtain [the output].
{0, 0, 0} -> {0, 0}
{0, 0, 1} -> {0, 1}
{0, 1, 0} -> {0, -1}
{0, 1, 1} -> {1, 0}
{1, 0, 0} -> {1, 1}
{1, 0, 1} -> {1, -1}
{1, 1, 0} -> {-1, 0}
{1, 1, 1} -> {-1, 1}
To convert back:
Convert each set of two ternary coefficients to three bits as follows, and concatenate the resulting bit quantities to obtain [the output]:
{0, 0} -> {0, 0, 0}
{0, 1} -> {0, 0, 1}
{0, -1} -> {0, 1, 0}
{1, 0} -> {0, 1, 1}
{1, 1} -> {1, 0, 0}
{1, -1} -> {1, 0, 1}
{-1, 0} -> {1, 1, 0}
{-1, 1} -> {1, 1, 1}
{-1, -1} -> set "fail" to 1 and set bit string to {1, 1, 1}
Note that to encrypt a message securely you can't simply convert the message to trinary and apply raw NTRU encryption. The message needs to be pre-processed before encryption and post-processed after encryption to protect against active attackers who might modify the message in transit. The necessary processing is specified in IEEE Std 1363.1-2008, and discussed in our 2003 paper "NAEP: Provable Security in the Presence of Decryption Failures" (Available from http://www.ntru.com/cryptolab/articles.htm#2003_3, though be aware that this description is targeted at binary polynomials rather than trinary).
Hope this helps.
@Bert: at various times we've recommended binary or trinary polynomials. Trinary polynomials allow the same security with shorter keys. However, in the past we thought that binary polynomials allowed q (the big modulus) to be 256. This was attractive for 8-bit processors. We've since established that taking q = 256 reduces security unacceptably (specifically, it makes decryption failures too likely). Since we no longer have small q as a goal, we can take advantage of trinary polynomials to give smaller keys overall.
精彩评论