Clinale's Blog
0%

OpenSSL BN 大数库分析

发表于 更新于 分类于

大数表示方法

对于大数 $A$，其基于底层数据类型 BN_ULONG 可以被表示为：

其中，底数 $b= 1 << sizeof(BN_UNLOG)$。

对于 LP64 系统，unsigned long 和 pointer 数据类型长度为 64 比特，BN 定义了如下基本宏定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// crypto/bn/bn_lcl.h
/*
 * 64-bit processor with LP64 ABI
 */
# ifdef SIXTY_FOUR_BIT_LONG
#  define BN_ULLONG       unsigned long long
#  define BN_BITS4        32
#  define BN_MASK2        (0xffffffffffffffffL)
#  define BN_MASK2l       (0xffffffffL)
#  define BN_MASK2h       (0xffffffff00000000L)
#  define BN_MASK2h1      (0xffffffff80000000L)
#  define BN_DEC_CONV     (10000000000000000000UL)
#  define BN_DEC_NUM      19                              // 64-bit ~ 19-dec
#  define BN_DEC_FMT1     "%lu"
#  define BN_DEC_FMT2     "%019lu"
# endif

// include/openssl/bn.h
# ifdef SIXTY_FOUR_BIT_LONG
#  define BN_ULONG        unsigned long
#  define BN_BYTES        8
# endif
# define BN_BITS2       (BN_BYTES * 8)					// 64
# define BN_BITS        (BN_BITS2 * 2)					// 128
# define BN_TBIT        ((BN_ULONG)1 << (BN_BITS2 - 1))  // 1 << 63

# define BN_FLG_MALLOCED         0x01
# define BN_FLG_STATIC_DATA      0x02

在定义大数的基本存储类型之后，BN 定义了 BIGNUM 结构体如下：

1
2
3
4
5
6
7
8
9
// crypto/bn/bn_lcl.h
struct bignum_st {
    BN_ULONG *d;                /* Pointer to an array of 'BN_BITS2' bit chunks. */
    int top;                    /* Index of last used d +1. */
    /* The next are internal book keeping for bn_expand. */
    int dmax;                   /* Size of the d array. */
    int neg;                    /* one if the number is negative */
    int flags;
};

基于上述定义的大数，其十进制表示为：

此外，在 crypto/bn/bn_lcl.h 文件中还定义了 bn_mont_ctx_st bn_recp_ctx_st 和 bn_gencb_st 三种用于大整数乘法和除法的上下文。