BIGNUM ライブラリ

概要

OpenSSL ライブラリには，RSA や DH などの公開鍵暗号アルゴリズムを実現するために多倍長整数演算のライブラリ関数が用意されている (crypto ライブラリ：OpenSSL bn(3)を参照)

このライブラリでは，データ構造の格納に動的メモリ確保が行われており，扱える数値に上限はない．ただし，メモリ確保エラーが発生した場合に備え，関数の戻り値のチェックは必要である．

このライブラリの基本オブジェクト(構造体) は以下の BIGNUM であり，1 つの多倍長整数を保持するために用いられる．この構造体を直接参照したり，変更してはいけない．

 typedef struct bignum_st {
    int top;	/* Index of last used d. */
    BN_ULONG *d;/* Pointer to an array of 'BITS2' bit chunks. */
    int max;	/* Size of the d array. */
    int neg;
 } BIGNUM;

多倍長整数は，動的に確保された BN_ULONG 型の配列に格納される．BN_ULONG は，16, 32, 64 ビットの何れかである．

ライブラリ関数の幾つかは，実行時にテンポラリな BIGNUM 型の変数を必要とする．この BIGNUM の動的確保のオーバヘッドを避けるために，BN_CTX 個の BIGNUM を含む BN_CTX 構造体が用いられる．

 #define BN_CTX	12
 typedef struct bignum_ctx {
    int tos;             /* top of stack */
    BIGNUM *bn[BN_CTX];  /* The variables */
 } BN_CTX;

なお，BIGNUM ライブラリを用いるときは，"openssl/bn.h" をインクルードする．

関数

関数群は，機能により幾つかのグループに分けられる．各関数に共通的な仕様を示す．

戻り値が int 型の関数は，特に指定の無い限り，成功時 1，エラー時 0 が返る．エラーは常にチェックされるべきである．
多くの算術演算関数は，第1引数に演算結果を返す．この第1引数は，明示的に示されない限り，関数のパラメータの一つと同じであっても良い．
関数の引数に BN_CTX *ctx を持つものがある．この ctx は，関数の実行時に必要なテンポラリな BIGNUM を保持するために用いられ，関数内部でのメモリ確保のオーバヘッドを避けるためのものである．
以下の変数が定義されている．値 1 の BIGNUM である．この変数は，比較や代入の際に有用である．
　extern BIGNUM *BN_value_one;

以下，主な関数を示す．

生成/解放
- BIGNUM *BN_new ()
  新しい BIGNUM オブジェクトを返す．値は，初期値として 0 を持つ．エラーの場合，NULL が返る．
- void BN_free (BIGNUM *a)
  BIGNUM を解放する．
- void BN_clear (BIGNUM *a)
  a の値を 0 に設定し，未使用の確保メモリ領域をゼロクリアする．この関数は，秘匿すべきデータをクリアする時に用いられる．
- void BN_clear_free (BIGNUM *a)
  a により使用されていたのメモリ領域をゼロクリアし，解放する．この関数は，秘密鍵のような秘匿すべきデータをクリアする時に用いられる．
- BN_CTX *BN_CTX_new (void)
  新しい BN_CTX を返す．エラーの場合は，NULL を返す．
- void BN_CTX_free (BN_CTX *c)
  BN_CTX 構造体を解放する．c における BIGNUM は，BN_clear_free() される．
- BIGNUM *BN_copy(BIGNUM *to, const BIGNUM *from)
  BIGNUM from が to へコピーされる．エラーの場合 NULL が，さもなくば to が返る．
- BIGNUM *BN_dup (const BIGNUM *a)
  a の値を持つ新しい BIGNUM が生成され返される．エラーの場合 NULL が返る．
サイズ取得
- int BN_num_bits (const BIGNUM *a)
  a のビット長を返す．
- int BN_num_bytes (BIGNUM *a)
  a のバイト長を返す． BIGNUM をバイト列に変換する際の占有するバイトの長さである．
代入操作
- int BN_one (BIGNUM *a)
  a に 1 を設定する．
- int BN_zero (BIGNUM *a)
  a に 0 を設定する．
- int BN_set_word (BIGNUM *a, BN_ULONG w)
  a に w の BN_ULONG 値を設定する．
- BN_ULONG BN_get_word (const BIGNUM *a)
  a を BN_ULONG で返す．a がワード長よりも大きい場合は，0xffffffffL が返る．
比較とテスト
- int BN_is_zero (BIGNUM *a)
  a が 0 ならば 1 を，さもなくば 0 を返す．
- int BN_is_one (BIGNUM *a)
  a が 1 ならば 1 を，さもなくば 0 を返す．
- int BN_is_word (BIGNUM *a, BN_ULONG w)
  a が w と等しければ 1 を，さもなくば 0 を返す．
- int BN_cmp (const BIGNUM *a, const BIGNUM *b)
  a が b より小さい場合 -1，a と b が等しい場合 0，a が b より大きい場合 1 が返る．符号付の比較である．
- int BN_ucmp (const BIGNUM *a, const BIGNUM *b)
  数値の符号を無視することを除き，BN_cmp と同じである．
算術演算
- int BN_add (BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
  r = a + b.
- int BN_sub (BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
  r = a - b.
- int BN_mul (BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx);
  r = a * b.
- int BN_sqr (BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
  r = a * a.
  この関数は，BN_mul(r, a, a) より高速である．
- int BN_div (BIGNUM *dv, BIGNUM *rem, const BIGNUM *a, const BIGNUM *d, BN_CTX *ctx)
  dv = int (a / d), rem = a % d.
  dv と rem のどちらか一方は，その値が必要ないならば NULL であっても良い．
- int BN_exp (BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
  r = a ^p.
- int BN_gcd (BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
  a と b の最大公約数 r を計算する．
- int BN_lshift (BIGNUM *r, const BIGNUM *a, int n)
  a を n ビット左シフトする．すなわち，r = a*(2ⁿ)．
- int BN_lshift1 (BIGNUM *r, const BIGNUM *a)
  a を 1 ビット左シフトする．すなわち，r = a*2．
  BN_lshift(r, a, 1) よりは効率が良い.
- int BN_rshift (BIGNUM *r, const BIGNUM *a, int n)
  a を n ビット右シフトする．すなわち，r = int(a/(2ⁿ))．
- int BN_rshift1 (BIGNUM *r, const BIGNUM *a)
  a を 1 ビット右シフトする．すなわち，r = int(a/2)．
  BN_rshift(r, a, 1) よりは効率が良い．
剰余演算
- int BN_mod (BIGNUM *rem, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
  rem = a % m.
  dv を NULL とした BN_div と同じである．
- int BN_nnmod (BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
  r = a % m.
  r は正の数である．
- int BN_mod_add (BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
  r = (a + b) mod m.
- int BN_mod_sub (BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
  r = (a - b) mod m.
- int BN_mod_mul (BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
  r = (a * b) mod m.
- int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
  r = (a * a) mod m.
- int BN_mod_exp (BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, BN_CTX *ctx)
  r = (a^p) mod m.
- BIGNUM *BN_mod_inverse (BIGNUM *r, const BIGNUM *a, const BIGNUM *n,BN_CTX *ctx)
  a の mod n における逆元を r に設定する ((a * r) % n == 1)．r が NULL ならば，新たな BIGNUM が生成される．戻り値は，正常終了時は逆元，エラー時は NULL である．
- BIGNUM *BN_mod_sqrt(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
  r = (√a) mod m.
ワード操作
これらの関数は，通常の算術演算関数よりはるかに効率的である．
- int BN_add_word (BIGNUM *a, BN_ULONG w)
  a += w.
- int BN_sub_word (BIGNUM *a, BN_ULONG w)
  a -= w.
- int BN_mul_word (BIGNUM *a, BN_ULONG w)
  a *= w.
- BN_ULONG BN_div_word (BIGNUM *a, BN_ULONG w)
  a /= w とし，余りを返す．
- BN_ULONG BN_mod_word (BIGNUM *a, BN_ULONG w)
  a % w を返す．
ビット操作
- int BN_is_bit_set (const BIGNUM *a, int n)
  ビット n がセットされていれば 1，さもなくば 0 を返す．
- int BN_set_bit (BIGNUM *a, int n)
  a のビット n を 1 に設定する．
  a &= ~(1 << n).
- int BN_clear_bit (BIGNUM *a, int n)
  a のビット n を 0 に設定する． a が n ビットより小さいならば 0，さもなくば 1 を返す．
  a &= ~(1 << n).
- int BN_mask_bits (BIGNUM *a, int n)
  a を n ビットに切り詰める．
  a &= ~((~0)<< n).
形式変換
- BIGNUM *BN_bin2bn (const unsigned char *s, int len, BIGNUM *ret)
  s からの len バイトを正の BIGNUM に変換し，ret に格納する． ret が NULL ならば，新しい BIGNUM が生成される．この新しい BIGNUM または ret が戻される．
  s の数値は，ビッグエンディアン形式とみなされる．
- int BN_bn2bin (const BIGNUM *a, unsigned char *to)
  a の絶対値をビッグエンディアン形式のバイト列に変換し to に格納する．格納されたバイトの長さが返される．
- char *BN_bn2hex (const BIGNUM *a)
  a を ASCII 16進文字列に変換する．メモリ確保した文字列へのポインタとして返る．値は，ビッグエンディアンである．値が負の場合は，先頭に '-' が付く．文字列は，OPENSSL_free() を用いて解放しなければならない．.
- int BN_hex2bn (BIGNUM **a, const char *str)
  ASCII 16進文字列 str を BIGNUM に変換し，a に設定する．BN_bn2hex の逆変換である．
  エラーの場合，0 が返る．*bn が NULL の場合，BIGNUM が生成される．
- int BN_print_fp (FILE *fp, const BIGNUM *a)
  a をファイルポインタ fp に出力する．BN_bn2hex() の出力と同じ形式である．エラーの場合 0，さもなくば 1 が返る．
その他
- int BN_rand (BIGNUM *rnd, int bits, int top, int bottom)
  ビット長が bits の擬似乱数 rnd を返す． bottom が 1 ならば奇数が返る．top が -1 ならば，乱数の MSB は 0 になりうる．top が 0 ならば，MSB は 1 になる．また，top が 1 ならば，乱数の先頭の 2 ビットは 1 になる．このとき，2 つの乱数の積のビット長は，2 * bits になる．
- int BN_rand_range (BIGNUM *rnd, const BIGNUM *range)
  0 <= rnd < range の擬似乱数 rand を生成する．
- int BN_is_prime (const BIGNUM *a, int checks, void(*callback)(int, int, void *), BN_CTX *ctx, void *cb_arg)
  BIGNUM p が素数か否かを判定する．素数の判定には，確率的素数判定法である Miller-Rabin 法が用いられる． p が合成数の時は 0，確率的 (0.25^checks 以下のエラー確率) に素数の時は 1，エラーの時は -1 が返る．
  callback は素数の判定に用いられるコールバック関数である (cb はその第3引数)．NULL でも良い．
  checks は，Miller-Rabin 法の繰り返し数のパラメータである．BN_prime_checks をデフォルトで用いることが推奨される．
- BIGNUM *BN_generate_prime (BIGNUM *ret, int num, int safe, BIGNUM *add, BIGNUM *rem, void (*callback)(int, int, void *), void *cb_arg)
  ビット長 num の高い確率で素数である擬似乱数を生成し，戻り値として返す．エラーの場合は，NULL が返る．ret が NULL でなければ，ret に生成された素数が格納される．
  callback は素数の判定に用いられるコールバック関数である (cb はその第3引数)．NULL でも良い．
  add が NULL でなければ，素数は次の条件を満たす．
  
  p % add == rem (p % add == 1 if rem == NULL)
  safe が真ならば，安全な素数 ((p - 1)/2 もまた素数) を生成する．