What determines the BIGNUM size in different crypto algorithms?

Question

I play with OpenSSL. I see that different openssl types use the BIGNUM type.

For example:

1. DSA signature

typedef struct DSA_SIG_st {
    BIGNUM *r;
    BIGNUM *s;
} DSA_SIG;

2. ECDSA signature

typedef struct ECDSA_SIG_st {
    BIGNUM *r;
    BIGNUM *s;
} ECDSA_SIG;

3. elliptic curve private key

struct ec_key_st {
    int version;
    EC_GROUP *group;
    EC_POINT *pub_key;
    BIGNUM *priv_key;
    unsigned int enc_flag;
    point_conversion_form_t conv_form;
    int references;
    int flags;
    EC_EXTRA_DATA *method_data;
} /* EC_KEY */ ;

4. RSA structure

struct rsa_st {
    /*
     * The first parameter is used to pickup errors where this is passed
     * instead of aEVP_PKEY, it is set to 0
     */
    int pad;
    long version;
    const RSA_METHOD *meth;
    /* functional reference if 'meth' is ENGINE-provided */
    ENGINE *engine;
    BIGNUM *n;
    BIGNUM *e;
    BIGNUM *d;
    BIGNUM *p;
    BIGNUM *q;
    BIGNUM *dmp1;
    BIGNUM *dmq1;
    BIGNUM *iqmp;
    /* be careful using this if the RSA structure is shared */
    CRYPTO_EX_DATA ex_data;
    int references;
    int flags;
    /* Used to cache montgomery values */
    BN_MONT_CTX *_method_mod_n;
    BN_MONT_CTX *_method_mod_p;
    BN_MONT_CTX *_method_mod_q;
    /*
     * all BIGNUM values are actually in the following data, if it is not
     * NULL
     */
    char *bignum_data;
    BN_BLINDING *blinding;
    BN_BLINDING *mt_blinding;
};

BIGNUM in OpenSSL is:

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

I can't understand how to pick bignums for particular algorithm and what about size of bignum array?

Answer 1

First you don't allocate the actual bn->d value yourself; the BN_* routines do it, and redo/change it as needed, for you. For nonobsolete versions of OpenSSL these structures (and nearly all others) are opaque and you can't access them directly at all, although I can understand wanting to know about them.

For cryptographic algorithms that use numbers (rather than just bitpatterns) the numbers you use depend on the algorithm. For RSA see the wikipedia article and if the PKCS1 link to RSA Labs no longer works (post EMC and Dell) use the stable IETF duplicates RFCs 2313, 2437, 4347, 8047 instead. There are other standards for RSA from ANSI/X9 and ISO, but they are less used and not significantly different. For DSA see again wikipedia and the (free) FIPS. For ECDSA you can see paid X9.62 or free SEC1 from SECG, but really it's just the straightforward adaptation of DSA to a (large) class of Weierstrass-form elliptic curves. For both DSA and ECDSA the values that appear in the signatures are computed, never picked, although they are affected by the per-operation nonce k which can be and usually is picked at random, uniformly in [1, n-1] where n is the subgroup order (size). Note for the 'prime' curves most commonly used with ECDSA, like P-256 and P-384, the curve was designed so that the subgroup order equals the curve order, which in turn is close to but not the same as the modulus of the underlying prime field. However, this is a property of those particular curves, not of ECDSA or ECC in general.

In practice keys for all algorithms should either be generated (in OpenSSL) by calling the appropriate key-generation functions either directly or by using the EVP_PKEY_* API, or else imported from some other software or system which generated them by a correctly-implemented process. Similarly signatures should be created by calling the functions for signature directly or via EVP, or received from something else that created them correctly. All of the OpenSSL code is free (both speech and beer), so you can look at it and see what it does; some people (including me) find it helpful at least sometimes to compile such code in a system with a good source-level debugger and step through it to watch what it does.

Standard caution: if you just want to play with crypto, or a particular implementation like OpenSSL, knock yourself out. If you are going to write software intended to provide security, DON'T do it by guesswork or trial and error; either use (existing) software written by people who know what they are doing, or hire or consult such people. It is very easy to write 'security' software that appears to work and passes testing but is actually insecure, and the people who (unlike you) actually understand the subject and know how to find these flaws will be your or your users' enemies.