2

NTRUEncrypt 公開鍵暗号システムを実装する必要があるプロジェクトを行っています。これは、暗号化のガイドによると、最初のステップです - 「ボブに秘密のメッセージを送信したいアリスは、彼女のメッセージを係数 {-1,0,1} の多項式 m の形式にします。」メッセージを多項式にする方法を知りたいです。ありがとうございました。

4

2 に答える 2

6

好きなようにできます。おそらく最も簡単な方法は、メッセージを3進表現に変換することです。

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

したがって、文字をASCII表現に変換してから、それらの表現を3進表現に変換します（7ビットのASCIIスペースに制限されていると仮定すると、5桁の3進数のみが必要です）。

次に、3進数字をに、3進数字をに、3進数字をに{-1, 0, 1}マッピングし、3^kに対応する数字がx^k 1の係数であると仮定して、3進表現を多項式に変換します。00112-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

そして私のメッセージは

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

私の多項式の係数が

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

どのように行うかに関係なく、重要なのは、メッセージを多項式として好きなように表現できるということです。メッセージ空間から多項式の空間への全単射を見つけて、{-1, 0, 1}それを簡単に計算でき、逆関数を簡単に計算できるようにすることをお勧めします。

1これが変革の核心です。5桁の3進数は、での多項式の評価に正確に対応します。したがって、上の多項式と3進数の間には明らかな1対1の対応があります。a4a3a2a1a0a4 * x^4 + a3 * x^3 + a2 * x^2 +a1 * x + a0 * x^0x = 3{-1, 0, 1}

于 2009-10-13T20:06:04.410 に答える
3

私はNTRUで働いているので、この関心を見てうれしいです.

IEEE 標準 1363.1-2008 では、最新のパラメーター セットを使用して NTRUEncrypt を実装する方法が指定されています。2 進数から 3 進数への変換に指定する方法は次のとおりです。

各 3 ビット量を次のように 2 つの 3 進係数に変換し、得られた 3 進量を連結して [出力] を取得します。

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

元に戻すには:

2 つの 3 値係数の各セットを次のように 3 ビットに変換し、結果のビット量を連結して [出力] を取得します。

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

メッセージを安全に暗号化するには、単純にメッセージを 3 進数に変換して生の NTRU 暗号化を適用することはできないことに注意してください。メッセージは、転送中にメッセージを変更する可能性のあるアクティブな攻撃者から保護するために、暗号化の前に前処理し、暗号化後に後処理する必要があります。必要な処理は IEEE Std 1363.1-2008 で指定されており、2003 年の論文「NAEP: 復号化失敗の存在下での証明可能なセキュリティ」( http://www.ntru.com/cryptolab/articles.htm#2003_3から入手可能) で説明されています。ただし、この説明は 3 進多項式ではなく 2 進多項式を対象としていることに注意してください)。

お役に立てれば。

@Bert: さまざまな時期に、2 進多項式または 3 進多項式を推奨してきました。3 項多項式は、より短い鍵で同じセキュリティを可能にします。しかし、以前は、バイナリ多項式では q (大きな係数) を 256 にすることができると考えられていました。これは、8 ビット プロセッサにとって魅力的でした。それ以来、q = 256 を使用するとセキュリティが容認できないほど低下することを確認しました (具体的には、復号化の失敗の可能性が高くなります)。目標として小さな q がなくなったので、3 項多項式を利用して全体的に小さなキーを与えることができます。

于 2010-03-08T20:43:09.920 に答える