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" をインクルードする.
関数
関数群は,機能により幾つかのグループに分けられる.各関数に共通的な仕様を示す.
以下,主な関数を示す.
- 生成/解放
- 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*(2n).
- 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/(2n)).
- 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 が返る.
- その他