[erlang-questions] crypto:mod_exp/3 returns wrong result?

Nanitous <>
Mon May 30 20:17:22 CEST 2011


Hi Jesper, Hanfei,

For the purpose in cryptographical applications this is not a problem, where in practivce only positive number are considered (actually elements from a group Z_p).

Of course one can debate whether Erlang should faithfully conserve the negative sign between libraries. But, as said before, for the crypto applications of mod_exp, it doesn't matter.


kr


Twan.



I went into the source code (see below) and the following happens:

0. The OpenSSL Big Number representation is a structure in which whether a number is negative is a separate flag in the structure:

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

typedef struct bignum_st BIGNUM;

From the openSSL bn.h:

/** BN_set_negative sets sign of a BIGNUM
 * \param  b  pointer to the BIGNUM object
 * \param  n  0 if the BIGNUM b should be positive and a value != 0 otherwise 
 */
void	BN_set_negative(BIGNUM *b, int n);
/** BN_is_negative returns 1 if the BIGNUM is negative
 * \param  a  pointer to the BIGNUM object
 * \return 1 if a < 0 and 0 otherwise
 */
#define BN_is_negative(a) ((a)->neg != 0)


1. The conversion of Erlang "big number" to openSSL "big numbers" ignores whether the binary big number representation of Erlang signifies a negative number:

static int get_bn_from_mpint(ErlNifEnv* env, ERL_NIF_TERM term, BIGNUM** bnp)
{
    ErlNifBinary bin;
    int sz;
    if (!enif_inspect_binary(env,term,&bin)) {
	return 0;
    }
    ERL_VALGRIND_ASSERT_MEM_DEFINED(bin.data, bin.size);
    sz = bin.size - 4;
    if (sz < 0 || get_int32(bin.data) != sz) {
	return 0;
    }
    *bnp = BN_bin2bn(bin.data+4, sz, NULL);
    return 1;
}


2. The reverse conversion when the openSSL function BN_mod_exp has computed its result, the conversion from the openSSL representation to the Erlang representation ignores again any negative results.


From Erlang: crypto.c

static ERL_NIF_TERM mod_exp_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
{/* (Base,Exponent,Modulo) */
    BIGNUM *bn_base=NULL, *bn_exponent=NULL, *bn_modulo, *bn_result;
    BN_CTX *bn_ctx;
    unsigned char* ptr;
    unsigned dlen;      
    ERL_NIF_TERM ret;

    if (!get_bn_from_mpint(env, argv[0], &bn_base)
	|| !get_bn_from_mpint(env, argv[1], &bn_exponent)
	|| !get_bn_from_mpint(env, argv[2], &bn_modulo)) {

	if (bn_base) BN_free(bn_base);
	if (bn_exponent) BN_free(bn_exponent);
	return enif_make_badarg(env);
    }
    bn_result = BN_new();
    bn_ctx = BN_CTX_new();
    BN_mod_exp(bn_result, bn_base, bn_exponent, bn_modulo, bn_ctx);
    dlen = BN_num_bytes(bn_result);
    ptr = enif_make_new_binary(env, dlen+4, &ret);
    put_int32(ptr, dlen);
    BN_bn2bin(bn_result, ptr+4);
    BN_free(bn_result);
    BN_CTX_free(bn_ctx);
    BN_free(bn_modulo);
    BN_free(bn_exponent);
    BN_free(bn_base);
    return ret;
}

From: openSSL: bn_lib.h:

BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
	{
	unsigned int i,m;
	unsigned int n;
	BN_ULONG l;
	BIGNUM  *bn = NULL;

	if (ret == NULL)
		ret = bn = BN_new();
	if (ret == NULL) return(NULL);
	bn_check_top(ret);
	l=0;
	n=len;
	if (n == 0)
		{
		ret->top=0;
		return(ret);
		}
	i=((n-1)/BN_BYTES)+1;
	m=((n-1)%(BN_BYTES));
	if (bn_wexpand(ret, (int)i) == NULL)
		{
		if (bn) BN_free(bn);
		return NULL;
		}
	ret->top=i;
	ret->neg=0;
	while (n--)
		{
		l=(l<<8L)| *(s++);
		if (m-- == 0)
			{
			ret->d[--i]=l;
			l=0;
			m=BN_BYTES-1;
			}
		}
	/* need to call this due to clear byte at top if avoiding
	 * having the top bit set (-ve number) */
	bn_correct_top(ret);
	return(ret);
	}


/* ignore negative */
int BN_bn2bin(const BIGNUM *a, unsigned char *to)
	{
	int n,i;
	BN_ULONG l;

	bn_check_top(a);
	n=i=BN_num_bytes(a);
	while (i--)
		{
		l=a->d[i/BN_BYTES];
		*(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff;
		}
	return(n);
	}










On 30 mei 2011, at 08:39, Jesper Pettersson wrote:

> Writing a small example in C using the bignum library in openssl (used by the Erlang crypto driver) shows that the result there is 1 as well.
> 
> #include <stdio.h>
> #include <openssl/crypto.h>
> #include <openssl/bn.h>
> 
> int main(int argc, char *argv[])
> {
>         static const char b[] = "-2";
>         static const char e[] = "3";
> 	static const char m[] = "3";
> 
>         BIGNUM *bnb = NULL;
>         BIGNUM *bne = NULL;
>         BIGNUM *bnm = NULL;
> 	BIGNUM *res = BN_new();
> 
>         BN_CTX *ctx = BN_CTX_new();
> 
>         BN_dec2bn(&bnb, b); /* convert the string to BIGNUM */
>         BN_dec2bn(&bne, e);
>         BN_dec2bn(&bnm, m);
> 
>         BN_mod_exp(res, bnb, bne, bnm, ctx); 
> 
>         char *result_str = BN_bn2dec(res); /* convert the res BIGNUM to string */
> 
>         printf("%s\n", result_str);
> 
>         OPENSSL_free(result_str);
> 
>         BN_free(bnb);
>         BN_free(bne);
>         BN_free(bnm);
>         BN_CTX_free(ctx);
> 
>         return 0;
> }
> 
> $ gcc -o bn -lcrypto bn.c
> $ ./bn
> 1
> 
> /Jesper Pettersson
> Klarna AB
> 
> On Sat, May 28, 2011 at 8:22 PM, Hanfei Shen <> wrote:
> Hi all,
> 
> As the doc says:
> 
> mod_exp(N, P, M) -> Result
> 
> Types:
> N, P, M, Result = Mpint
> Mpint = binary()
> 
> This function performs the exponentiation N ^ P mod M, using the crypto library.
> 
> Now, assume: N = -2, P = 3, M = 3
> Then: N ^ P mod M = (-2) ^ 3 mod 3
>                   = (-8) mod 3
>                   = (-3) * 3 + 1
>                or = (-3) * 2 + (-2)
> So: the remainder should be 1 or -2
> (Remainder, From Wikipedia, http://en.wikipedia.org/wiki/Remainder)
> 
> But I got a TWO from crypto:mod_exp/3... Is there some wrong...?
> And I did more tests with erlang, python and ruby.
> The result:
> 
> Erlang R14B02 (erts-5.8.3) [source] [64-bit] [smp:2:2] [rq:2] [async-threads:0] [kernel-poll:false]
> 
> Eshell V5.8.3  (abort with ^G)
> 1> crypto:mod_exp(-2, 3, 3).
> 2
> 2> crypto:mod_exp(2, 3, 3).
> 2
> 3> crypto:mod_exp(-2, 3, -3).
> 1
> 4> crypto:mod_exp(2, 3, -3).
> 8
> 
> Python 2.7.1 (r271:86832, Mar 25 2011, 15:07:46)
> 
> In [1]: pow(-2, 3, 3)
> Out[1]: 1
> 
> In [2]: pow(2, 3, 3)
> Out[2]: 2
> 
> In [3]: pow(-2, 3, -3)
> Out[3]: -2
> 
> In [4]: pow(2, 3, -3)
> Out[4]: -1
> 
> Welcome to IRB. You are using ruby 1.9.2p180 (2011-02-18 revision 30909) [x86_64-linux]. Have fun ;)
> irb(main):001:0> (-2) ** 3 % 3
> 1
> irb(main):002:0> 2 ** 3 % 3
> 2
> irb(main):003:0> (-2) ** 3 % (-3)
> -2
> irb(main):004:0> 2 ** 3 % (-3)
> -1
> 
> 
> Regards,
> Hanfei
> 
> _______________________________________________
> erlang-questions mailing list
> 
> http://erlang.org/mailman/listinfo/erlang-questions
> 
> 
> 
> 
> -- 
> Jesper Pettersson
> 
> Klarna AB
> Norra Stationsgatan 61
> 113 43 Stockholm, Sweden
> Tel:         +46 8 - 120 120 00
> Mob:       +46 70 - 001 27 25
> Fax:        +46 8 - 120 120 99
> E-mail:     
> Web:        www.klarna.com
> _______________________________________________
> erlang-questions mailing list
> 
> http://erlang.org/mailman/listinfo/erlang-questions

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20110530/461366f5/attachment.html>


More information about the erlang-questions mailing list