Comment faire un message dans un polynôme?

Question

Je fais un projet dans lequel je dois implémenter le système cryptographique à clé publique NTRUEncrypt. C'est la première étape selon leur guide dans le cryptage - "Alice, qui veut envoyer un message secret à Bob, met son message sous la forme d'un polynôme m avec des coefficients {-1,0,1}". Je veux savoir comment je peux faire de mon message un polynôme. Je vous remercie.

Answer 1

Vous pouvez le faire comme vous le souhaitez. Peut-être la façon la plus simple est de convertir votre message à une représentation ternaire

"Hello" -> 72, 101, 108, 108, 111 -> 02200, 10202, 11000, 11000, 11010 

Je suis convertir les personnages à leur représentation ASCII, puis convertir ces représentations à leur représentation ternaire (en supposant que je suis limité à la Espace ASCII de 7 bits, j'ai seulement besoin de cinq chiffres ternaires).

ensuite convertir la représentation ternaire à un polynôme sur {-1, 0, 1} en mappant le chiffre ternaire 0-0, le chiffre ternaire 1-1 et le chiffre ternaire 2 à -1 et en supposant que le chiffre correspondant à 3^k est le coefficient de x^k :

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 

et mon message est

p1(x) + x^5 * p2(x) + (x^5)^2 * p3(x) + (x^5)^3 * p4(x) + (x^5)^4 * p5(x) 

pour que mon coefficients de polynôme sont

(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). 

Quelle que soit la façon dont vous le faites, le point est que vous pouvez représenter votre message comme un polynôme comme bon vous semble. Il est juste préférable que vous trouviez une bijection de votre espace de message à l'espace des polynômes sur {-1, 0, 1} qui est facilement calculé et a un inverse facilement calculé.

Ceci est le noeud de la transformation. Un certain nombre ternaire à cinq chiffres a4aa32a1a0 correspond exactement à l'évaluation du polynôme a4* x^4 + a3* x^3 + a2* x^2 +a1* x + a0* x^0 à x = 3. Il y a donc une correspondance bi-univoque entre les polynômes sur {-1, 0, 1} et les nombres ternaires.

Answer 2

Je travaille pour NTRU, donc je suis content de voir cet intérêt.

La norme IEEE 1363.1-2008 spécifie comment implémenter NTRUEncrypt avec les jeux de paramètres les plus courants.Procédé pour qu'il spécifie binary-> conversion ternaire est:

convertir chaque quantité de trois bits à deux coefficients ternaires comme suit, et les concaténer ternaires résultant pour obtenir des quantités [sortie].

{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} 

reconvertir:

convertir chaque ensemble de deux ternaires coefficients à trois bits comme suit, et concaténer le bit résultant quantités pour obtenir [sortie]:

{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} 

Notez que pour e crypter un message en toute sécurité vous ne pouvez pas simplement convertir le message en trinaire et appliquer le cryptage NTRU brut. Le message doit être pré-traité avant le chiffrement et le post-traitement après le chiffrement pour se protéger contre les attaquants actifs qui pourraient modifier le message en transit. Le traitement nécessaire est spécifié dans la norme IEEE 1363.1-2008 et discuté dans notre document de 2003 "NAEP: sécurité possible en présence d'échecs de décryptage" (disponible à partir de http://www.ntru.com/cryptolab/articles.htm#2003_3, sachant que cette description est destinée aux polynômes binaires plutôt qu'aux trinaires) .

Espérons que cela aide.

@Bert: à plusieurs reprises, nous avons recommandé des polynômes binaires ou trinaires. Les polynômes trinaires permettent la même sécurité avec des clés plus courtes. Cependant, dans le passé, nous pensions que les polynômes binaires permettaient q (le grand module) d'être 256. Cela était intéressant pour les processeurs 8 bits. Nous avons depuis établi que prendre q = 256 réduit la sécurité de manière inacceptable (en particulier, cela rend les échecs de décryptage trop probables). Comme nous n'avons plus de petit q comme objectif, nous pouvons tirer parti des polynômes trinaires pour donner des clés plus petites dans l'ensemble.