How to make a post into a polynomial?
I am doing a project where I need to implement the NTRUEncrypt public key cryptosystem. This is the first step according to their encryption manual - "Alice who wants to send a secret message to Bob puts her message as a polynomial m with coefficients {-1,0,1}". I want to know how can I turn my post into a polynomial. Thank.
You can do it however you like. Perhaps the easiest way is to convert your message to 3D
"Hello" -> 72, 101, 108, 108, 111 -> 02200, 10202, 11000, 11000, 11010
So, I convert the characters to their ASCII representation, and then convert those representations to their 3D representation (assuming I'm limited to 7-bit ASCII space, I only need five triple digits).
Then we transform the 3D representation into a polynomial on {-1, 0, 1}
by matching the triple digit 0
before 0
, triple digit 1
before, 1
and triple digit 2
before -1
and assuming that the digit corresponding to 3 ^ k is the coefficient of x ^ k 1 :
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
p1(x) + x^5 * p2(x) + (x^5)^2 * p3(x) + (x^5)^3 * p4(x) + (x^5)^4 * p5(x)
so my polynomial 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 of how you do it, the point is that you can represent your message as polynomial as you like. Just prefer that you find a bijection from your message space into a polynomial space on {-1, 0, 1}
that is easy to compute and has an easy to compute inverse.
1 This is the essence of transformation. Five-digit triple numbera
4
a
3
a
2
a
1
a
0
exactly matches the polynomial estimate a
4
* x^4 + a
3
* x^3 + a
2
* x^2 +a
1
* x + a
0
* x^0
at x = 3
. Thus, there is an obvious one-to-one correspondence between polynomials on {-1, 0, 1}
and triple numbers.
source to share
I work for NTRU, so I'm glad to see this interest.
The IEEE 1363.1-2008 standard defines how to implement NTRUEncrypt with the most recent parameter sets. The method it sets for binary-> trinary conversion:
Convert each three-bit quantity to two triple coefficients as follows and concatenate the resulting three-bit quantity to obtain [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 go back:
Convert each set of two ternary coefficients to three bits as follows, and concatenate the resulting bit count to get [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 for securely encrypting a message, you cannot simply convert the message to trinary and apply raw NTRU encryption. The message must be pre-processed before encryption and after processing after encryption to protect against active intruders who might modify the message in transit. The necessary processing is specified in IEEE Std 1363.1-2008 and discussed in our 2003 article "NAEP: Ensuring Security in the Presence of Decryption Errors" (Available from http://www.ntru.com/cryptolab/articles.htm#2003_3 , although keep in mind that this description is for binary polynomials, not trinary).
Hope it helps.
@Bert: At various times we have recommended binary or trinial polynomials. Trinomial polynomials admit the same security with shorter keys. However, in the past we thought that binary polynomials allowed q (large modulus) to be 256. This was attractive for 8-bit processors. We have since found that adopting q = 256 compromises security unacceptably (in particular, it leads to decryption errors). Since we no longer have a target q, we can use trinial polynomials to give smaller keys overall.
source to share