2

OpenSSL の BIGNUM ライブラリを使用して「正しい答え」を考え出すには、いくつかの問題があります。私は OpenSSL 1.0.1c を使用しています (2012 年 5 月、標準の Mint リポジトリで利用可能な最新のパッケージ)。

有限体 (別名ガロア体) を使用する暗号化プロジェクトに BIGNUM を使用しています。基本的に、大きな素数 (q) と安全な素数 (p、p = 2q + 1) があります。私のフィールドは次数 q の Fp です。

「g」を生成する必要があります。これを行う最も簡単な方法は、ランダムな "h" (1 < h < p-1) を選択してから、g = h^((p-1)/q) mod p を実行することです。「g」を使用すると、g^q mod p = 1 を実行することで、それが FF にあることを証明できるはずです。

紙の上で合理的な小さな数に対してこれを行うと、それは当てはまります。ただし、OpenSSL と大きな素数を使用して行うと、機能しません! g^q mod p == 1 の結果をテストすると、BN_is_one() を使用して常に失敗します。値を出力すると、それは常に大きな無関係な素数です。

何が起こっている？ここで何が起こっているのかわからない、または何かを誤解している場合。

以下の私のコードのスニペット：

BN_generate_prime(q, KEYSIZE - 1, 0, 0, 0, 0, 0); //generate "q"

// Calculate "p" = 2q + 1 
BN_lshift1(p, q);
BN_add(p, p, one);  //one = BN_one()

// 1: gExp = (p-1)/q
// 2: h =>   1 < h < (p-1)
// 3: g = h^gExp mod p
BN_div(gExp, NULL, pMinusOne, q, ctx);      // (1)
BN_pseudo_rand_range(h, pMinusOne);         // (2)
BN_mod_exp(g, h, gExp, p, ctx);             // (3)

BN_mod_exp(temp, g, q, p, ctx); // g^q mod p = 1, or it should
4

1 に答える 1

1

スニペットで計算しているため、p必ずしも素数ではなく、素数を含む形式の数値にすぎませ2*q+1んq。の多くの小さな値のq場合、これpはたまたま素数ですが、それはほとんどの場合偶然であり、チェックすると、生成している がテストに合格しないことがBN_is_prime わかります。p

代わりに、パラメーターをp設定して直接生成し、右シフトで計算します。素数は必要な形式になり、最下位ビットを切り取ると素数が得られます。safeBN_generate_primeqsafeq

于 2012-09-05T20:35:31.490 に答える