Converting byte array to biginteger?

[Tushar Goel]

It's my work assignment, i am trying to convert some byte array into BigInteger.

Originally, i am trying to implement same functionality as "BN_bin2bn" provides in openssl library. As per openssl docs, "BN_bin2bn() converts the positive
integer in big-endian form of length len at s into a BIGNUM and places it in ret. If ret is NULL, a new BIGNUM is created."

BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret);

I tried to use BigInteger and provide the same value but both are returning different value:

1) Hex value : 53ABA93B9131C439D2942C7CBC483FA5
2) Java way:

  BigInteger  output =  new BigInteger(1, Base64.decodeBase64("53ABA93B9131C439D2942C7CBC483FA5"));
  String value = output.toString();

it returns value = 111217238859577568889117274385450287013;

but when i passed same hex value in BN_bin2bn(), it returns 15173801958764481957

any idea, what i am doing wrong?

[Paweł Baczyński]

Is full name of Base64 your are using org.apache.commons.codec.binary.Base64?

import org.apache.commons.codec.binary.Base64;
import java.math.BigInteger;

public final class Temp {
    public static void main(String args[]) {
        BigInteger output = new BigInteger(1, Base64.decodeBase64("53ABA93B9131C439D2942C7CBC483FA5"));
        String value = output.toString();
        System.out.println(value);
    }
}

This prints 5674831367621323064086805923944011128819378588560572305465 on my PC.


This prints 111217238859577568889117274385450287013.

import java.math.BigInteger;

public final class Temp {
    public static void main(String args[]) {
        BigInteger output = new BigInteger("53ABA93B9131C439D2942C7CBC483FA5", 16);
        String value = output.toString();
        System.out.println(value);
    }
}

By the way, Base64 is not the same as hexadecimal notation.

[Campbell Ritchie]

Too difficult for this forum: moving.

[Henry Wong]

Paweł Baczyński wrote:
By the way, Base64 is not the same as hexadecimal notation.

The original definition doesn't mention either Base64 or hexadecimal notation either. Heck, it doesn't even mentions the usage of String (ie. ASCII notation).

It was described as a "positive integer in big-endian form". This describes a binary format to me.

Henry

[Jesper de Jong]

I agree with Henry - why are to using Base64? The hexadecimal number has nothing to do with Base64.

You can solve this very easily with one line of code. Look in the API documentation of BigInteger. You just have to pass the hex string and the appropriate other argument to one of the constructors of BigInteger.

Try it and let us know what you found...

[Tushar Goel]

Sorry for confusion...

My original input is in byte array itself. I have changed it to hex format so that i can share the input with you guys but I created confusion. I am sorry again.

I have used BigInteger one of the constructor but result doesn't match with BN_bin2bn

import java.math.BigInteger;

public final class Temp {
public static void main(String args[]) {
BigInteger output = new BigInteger("53ABA93B9131C439D2942C7CBC483FA5", 16);
String value = output.toString();
System.out.println(value);
}
}

As per the definition i have done the same thing above but still no luck. Any idea?

[Campbell Ritchie]

You are giving input in hex and printing it in decimal
System.out.printf("%d = %<X%n", new BigInteger("53ABA93B9131C439D2942C7CBC483FA5", 0x10));
Output:
111217238859577568889117274385450287013 = 53ABA93B9131C439D2942C7CBC483FA5

So you have actually got the same number.>

[Tushar Goel]

Omg!! I dint notice it. Sorry. any idea why it didnt match with the output of bin2bn method of OpenSSL library i mentioned earlier? I spent several hours but dint figured it out

[Tushar Goel]

Any suggestion?

[Jesper de Jong]

We don't know what different things you tried, so we can't tell you why you didn't succeed immediately. One thing is clear, it has nothing to do with Base64 encoding, so if you've been trying to use this then it's no wonder you didn't get the expected result.

[Tushar Goel]

Whatever i tried earlier was wrong as suggested by Campbell..

as BN_bin2bn() method definition "BN_bin2bn() converts the positive integer in big-endian form " i tried now is convert each byte into unsigned positive but
then again result is not matching. This steps result matches with my wrong outputs.

byte[] arrayValue = hexToByteArray("53ABA93B9131C439D2942C7CBC483FA5");  

BigInteger op = BigInteger.ZERO;
 
		while (n-- > 0) {
			int temp1 = 0xFF & arrayValue[k++];
			op = op.shiftLeft(8).or(new BigInteger(String.valueOf(temp1)));
			System.out.println(op);
		}

It prints:

83
21419
5483433
1403758907
359362280337
91996743766321
23551166404178372
6029098599469663289
1543449241464233802194
395123005814843853361812
101151489488600026460623916
25894781309081606773919722620
6629064015124891334123448990908
1697040387871972181535602941672520
434442339295224878473114353068165183
111217238859577568889117274385450287013

[Campbell Ritchie]

Try printing the number in hex; I tried it and it does seem to give the correct output.

[Richard Tookey]

The hex number "53ABA93B9131C439D2942C7CBC483FA5" has 32 hex digits. The decimal number 15173801958764481957 has 20 decimal digits. Except for a single digit a hex representation is always more compact than a decimal representation so either BN_bin2bn() is faulty or you are using it wrongly. Since you have not shown the BN_bin2bn() code I'm betting you are using it wrongly. Post the BN_bin2bn() code making sure you post enough that you show the data definitions.

[Tushar Goel]

I checked with my senior, he gave me wrong output. The output from the bin2bn is "3158851493".

I have written small C code to have the same functionality as bin2bn is having (considered only positive case). Here most important part is while loop. all work is done in their only.

#include <stdio.h>
#include "openssl/bn.h"

int main() {
int ij=0;
unsigned int i,m;
unsigned int n = 16;
BIGNUM tmp ;
BIGNUM *ret ;
BN_ULONG l = 0;
unsigned char s[] = {0x53, 0xAB, 0xA9, 0x3B, 0x91, 0x31, 0xC4, 0x39, 0xD2, 0x94, 0x2C, 0x7C, 0xBC, 0x48, 0x3F, 0xA5};

BN_init(&tmp);
ret = &tmp;
i=((n-1)/8)+1;
m=((n-1)%(8));
        if (bn_wexpand(ret, (int)i) == NULL)
                {
                return NULL;
                }
printf("i = %d , m = %d\n",i, m);
while (n--)
{
   l=(l<<8L) | (s[ij++]);
    printf("%u\n",l);// here is showing different output
  if (m-- == 0)
  {
       ret->d[--i]=l;
       l=0;
       m=7;
   }

}
        bn_correct_top(ret);
}

The output is:

i = 2 , m = 7
83
21419
5483433
1403758907
2879994769
2839253297
999371204
2435957817
210
53908
13800492
3532926076
2485943484
746372168
2092714047
3158851493

When i compare with my output only first 4 matches.. Rest are not matches. I understand that after 7 bit it is resetting the variable at line 30. So that changes i have to do
otherwise first 7 should match.

I also tried to use long instead of BigInteger as they using the same but still only first 4 matches, Rest are not matching.

[Campbell Ritchie]

Why on earth are you printing those numbers in decimal? Print them in hex and you will be able to see what is happening.

[Tushar Goel]

It has to be decimal only. I am trying to check the feasibility of FPE algorithm which uses decimal as input/output only.

Also openSSL library(bin2bn method) returns decimal only.

[Campbell Ritchie]

Yes, but you can display the number in decimal and hex. When you know you have got it working, simply remove the hex displays.
And the number is probably not in decimal at all. It is in binary.

[Richard Tookey]

Tushar Goel wrote:I checked with my senior, he gave me wrong output. The output from the bin2bn is "3158851493".

Sorry that that can't be right. How can a 32 hex character number be represented by only 10 decimal digits?

I have written small C code to have the same functionality as bin2bn is having (considered only positive case).

How to you know it has the same functionality?

Here most important part is while loop. all work is done in their only.

#include <stdio.h>
#include "openssl/bn.h"

int main() {
int ij=0;
unsigned int i,m;
unsigned int n = 16;
BIGNUM tmp ;
BIGNUM *ret ;
BN_ULONG l = 0;
unsigned char s[] = {0x53, 0xAB, 0xA9, 0x3B, 0x91, 0x31, 0xC4, 0x39, 0xD2, 0x94, 0x2C, 0x7C, 0xBC, 0x48, 0x3F, 0xA5};

BN_init(&tmp);
ret = &tmp;
i=((n-1)/8)+1;
m=((n-1)%(8));
        if (bn_wexpand(ret, (int)i) == NULL)
                {
                return NULL;
                }
printf("i = %d , m = %d\n",i, m);
while (n--)
{
   l=(l<<8L) | (s[ij++]);
    printf("%u\n",l);// here is showing different output
  if (m-- == 0)
  {
       ret->d[--i]=l;
       l=0;
       m=7;
   }

}
        bn_correct_top(ret);
}

The output is:

i = 2 , m = 7
83
21419
5483433
1403758907
2879994769
2839253297
999371204
2435957817
210
53908
13800492
3532926076
2485943484
746372168
2092714047
3158851493

When i compare with my output only first 4 matches.. Rest are not matches. I understand that after 7 bit it is resetting the variable at line 30. So that changes i have to do
otherwise first 7 should match.

I also tried to use long instead of BigInteger as they using the same but still only first 4 matches, Rest are not matching.

I'm at a loss as to what this is trying to prove! Since you are providing a hex number as argument I think you should be using BN_hex2bn() and not BN_dec2bn() !

Note - it sound to me like you are not checking the openssl error code. Always check error codes when working with C.

[Tushar Goel]

Sorry that that can't be right. How can a 32 hex character number be represented by only 10 decimal digits?

It can. I have working C code which can do so. I am trying to figured it out the same in Java. It's FPE algorithm. After getting output from the bin2bn, we have to
find the modulus on this output then doing modulus addition again gives the desired output.

How to you know it has the same functionality?

I have compared the final output from both of them and its same.

I'm at a loss as to what this is trying to prove! Since you are providing a hex number as argument I think you should be using BN_hex2bn() and not BN_dec2bn() !

I am trying to match the output from my original solution with the C function. Why output matches for first 4 byte not others, if i do the same thing in Java. Possible
reason i thought is in C they have used unsigned long so it can store 8 extra byte data. So total data it can store is 8+8bytes. But Java doesn't support unsigned values,
so if i am use long variable and perform operation then for first 4 bytes it stores it into the next 4 bytes but after that 4-8 byte can't be stored. So after that it will signed output.
(which is negative) But i am not sure why it is not giving correct output for BigInteger, as it is 16 bytes long and can store the value. Still in this case first 4 bytes data matches
as i pasted i above post.

[Tushar Goel]

as per openssl documentation this is bin2bn method:

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

If i am consider all the positive scenario then control will come to while loop.

[Richard Tookey]

Tushar Goel wrote:

Sorry that that can't be right. How can a 32 hex character number be represented by only 10 decimal digits?

It can.

Sorry but it can't ! A 32 hex character number (with a non-zero leading digit) will have at least 32 decimal digits! Last time I looked 32 was greater than 10.

Are you checking the error codes resulting from the openssl big number method calls you are using?

[Tushar Goel]

there are no error codes. It is working fine. No issue is coming..

[Richard Tookey]

Tushar Goel wrote:there are no error codes. It is working fine. No issue is coming..

The source of BN_bin2bn() indicates that no hex or character conversion is being done on the input array. Though specified as unsigned char it is not treated as char but just as bytes. The bytes are packed into an unsigned long array presumably so that the maths can be more efficient.

I will bow out of this thread since I really don't understand what your aim is and think you are totally on the wrong track what ever your aim.

[Tushar Goel]

I am sorry for the confusion. My real aim is to implement bin2bn equivalence in java so that i can get the desired result. I have input in 16 byte bytes array and want
to convert it to the same as this method does.

[Richard Tookey]

Tushar Goel wrote:My real aim is to implement bin2bn equivalence in java so that i can get the desired result. I have input in 16 byte bytes array and want
to convert it to the same as this method does.

In Java BigInteger has a constructor that takes a byte array containing the number as bytes (there is another optional argument to force it to be positive). This does exactly the same as your bin2bn() method. Neither bin2bn() or the BigInteger constructor can ever create 15173801958764481957 from 0x53ABA93B9131C439D2942C7CBC483FA5 however it is decoded. Based on what you have posted I think the code using the bin2bn() that you are trying to match is flawed.

I have used the openssl C interface for many years and never had a problem with matching BIGNUM values with Java BigInteger. What algorithm (not code) is this being used in? RSA?

[Tushar Goel]

Not RSA. FPE(Format preserving encryption). It is new algorithm. I have gdb logs as well. You can see, it gives the output i mentioned:

     data_in=0x9442160 "\001\002\003\004\005\006\a\b\t", data_out=0x94421b8 "", data_len=10)
    
	if( BN_bin2bn( temp_output, cipher_block_len, &output ) == NULL )
Current language:  auto; currently c++
(gdb) p temp_output
$1 = (unsigned char *) 0x9442170 "S▒▒;\2211▒9▒\224,|▒H\215▒ey"
(gdb) p cipher_block_len
$2 = 16
(gdb) p output
$3 = {d = 0x0, top = 0, dmax = 0, neg = 0, flags = 0}
(gdb) p temp_output
$4 = (unsigned char *) 0x9442170 "S▒▒;\2211▒9▒\224,|▒H\215▒ey"
(gdb) x temp_output
0x9442170:      0x3ba9ab53
(gdb) p temp_output[0]
$5 = 83 'S'
(gdb) p temp_output[1]
$6 = 171 '▒'
(gdb) p/x temp_output
(gdb) p/x temp_output[0]
$11 = 0x53
(gdb) p/x temp_output[1]
$12 = 0xab
(gdb) p/x temp_output[2]
$13 = 0xa9
(gdb) p/x temp_output[3]
$14 = 0x3b
(gdb) p/x temp_output[4]
$15 = 0x91
(gdb) p/x temp_output[5]
$16 = 0x31
(gdb) p/x temp_output[6]
$17 = 0xc4
(gdb) p/x temp_output[7]
$18 = 0x39
(gdb) p/x temp_output[8]
$19 = 0xd2
(gdb) p/x temp_output[9]
$20 = 0x94
(gdb) p/x temp_output[10]
$21 = 0x2c
(gdb) p/x temp_output[11]
$22 = 0x7c
(gdb) p/x temp_output[12]
$23 = 0xbc
(gdb) p/x temp_output[13]
$24 = 0x48
(gdb) p/x temp_output[14]
$25 = 0x8d
(gdb) p/x temp_output[15]
$26 = 0xa5
(gdb) p/x temp_output[16]
$27 = 0x65
(gdb) n
2293            if ((i%2)==0)
(gdb) p output
$28 = {d = 0x9442438, top = 4, dmax = 4, neg = 0, flags = 0}
(gdb)
$29 = {d = 0x9442438, top = 4, dmax = 4, neg = 0, flags = 0}
(gdb) p output->d
$30 = (unsigned int *) 0x9442438
(gdb) p/x output->d
$31 = 0x9442438
(gdb) p *output->d
$32 = 3158871461
(gdb) p temp_output
$33 = (unsigned char *) 0x9442170 "S▒▒;\2211▒9▒\224,|▒H\215▒ey"

[Richard Tookey]

Tushar Goel wrote:Not RSA. FPE(Format preserving encryption). It is new algorithm.

I am familiar with FPE but have never used it. There are several FPE algorthms so which one is this? Where did you get the C source code from? Can it be posted?

[Tushar Goel]

Our tech team wrote this. Sorry i can't share the code. It is confidential.

If you see the output of bin2bn() it is "3158871461" where as input is "53 AB A9 3B 91 31 C4 39 D2 94 2C 7C BC 48 3F A5". If i add print statement in while method
present in the method then it will show all the iteration output and final output i pasted earlier. And if i passed the same input in BigInteger constructors then answer
doesn't match. I know may be i am doing something wrong but i can't figured it out.

I hope i am clear now.

[Richard Tookey]

Tushar Goel wrote:Our tech team wrote this. Sorry i can't share the code. It is confidential.

If you see the output of bin2bn() it is "3158871461" where as input is "53 AB A9 3B 91 31 C4 39 D2 94 2C 7C BC 48 3F A5". If i add print statement in while method
present in the method then it will show all the iteration output and final output i pasted earlier. And if i passed the same input in BigInteger constructors then answer
doesn't match. I know may be i am doing something wrong but i can't figured it out.

I hope i am clear now.

I understand now but, as I have said before, you still cannot get "3158871461" from "53 AB A9 3B 91 31 C4 39 D2 94 2C 7C BC 48 3F A5" since the hex type number has too many digits to fit into the decimal number. The log trace says nothing and without even a code fragment showing how the bin2bn() is used I cannot help.

[Tushar Goel]

Thanks Richard.. You have tried your best to help me. I appreciate that..

They have called it directly like below:

 if( BN_bin2bn( temp_output, cipher_block_len, &output ) == NULL )
        {
            rc = -1;
            goto end;
 }

temp_output is input which i mentioned, cipher_block_len is 16 and output is BIGNUM which is just initialized and passed into this to work as an output
buffer. After executing this mentioned result is coming as debug logs showing.

May be i have to see any where else or think some thing else.

[Tushar Goel]

I have tried to use bn_hex2bn method as well as suggested by others and it returns the same output as bin2bn returns.

int number = BN_hex2bn(&output, "53ABA93B9131C439D2942C7CBC483FA5");
printf(" number = %lu ", *output->d);

output:
number = 3158851493

[Richard Tookey]

Tushar Goel wrote:I have tried to use bn_hex2bn method as well as suggested by others and it returns the same output as bin2bn returns.

int number = BN_hex2bn(&output, "53ABA93B9131C439D2942C7CBC483FA5");
printf(" number = %lu ", *output->d);

output:
number = 3158851493

I'm not certain but I'm pretty sure that you can't use printf directly to print the content of a BIGNUM. I think you are only printing 8 internal bytes as a long. You need to use BN_bn2dec() (or BN_bn2hex()) to create a string representation and then print that string with printf.

[Tushar Goel]

You need to use BN_bn2dec()

Wow!!! It works. Thank you very much. You saved me.

Can you please tell me if i have to convert Java output to the C output how can i do that? I have to give the output in same format as C output is.

[Richard Tookey]

Tushar Goel wrote:
Can you please tell me if i have to convert Java output to the C output how can i do that? I have to give the output in same format as C output is.

Might be able to if you tell me what the decimal value should be. Note - the resulting decimal value MUST MUST MUST have more than 32 decimal digits. If it hasn't then it is not right.

[Tushar Goel]

Yes it is longer than 32 bit. Decimal value i am getting is "111217238859577568889117274385450287013". I also wanted to ask why it is more than
32 bits? Doesn't understand the logic behind.

[Richard Tookey]

Tushar Goel wrote:Yes it is longer than 32 bit. Decimal value i am getting is "111217238859577568889117274385450287013".

If you allow signed values then

        String hexValue = "53ABA93B9131C439D2942C7CBC483FA5";
        BigInteger number = new BigInteger(hexValue, 16);
        System.out.println(number.toString(10));

If you want to force unsigned, as you probably will do for your encryption, then you will need to use

        String hexValue = "53ABA93B9131C439D2942C7CBC483FA5";
        byte[] byteValue = <some hex decoder>(hexValue);
        BigInteger number = new BigInteger(1, byteValue);
        System.out.println(number.toString(10));
 

I also wanted to ask why it is more than
32 bits? Doesn't understand the logic behind.

32 bits is 8 hex characters. You have 32 hex characters which is 4 times the length of 32 bits!

[Tushar Goel]

Yeah thanks Richard. I am able to achieve this but can we transfer decimal output "111217238859577568889117274385450287013" into "3158851493" which
is bignum output.

I understand both are same but in different format but can we changed decimal output to bignum output format.

[Campbell Ritchie]

No.

We have spent all week trying to explain to you that the decimal number 111217238859577568889117274385450287013 and the hexadecimal number 53ABA93B9131C439D2942C7CBC483FA5 are the same.
I don't know where you get 3158851493 from. Is it an unsigned representation of that hex number cast to an int?

import java.math.BigInteger;

class BigIntegerTruncateDemo
{
    public static void main(String... args)
    {
        BigInteger i = new BigInteger(args[0], 0x10);
        System.out.printf("i = 0x%x or%n      %<d%n", i);
        System.out.printf("The bottom 32 bits of i unsigned are %d%n",
                i.longValue() << 0x20 >>> 0x20);
    }
}

java BigIntegerTruncateDemo 53ABA93B9131C439D2942C7CBC483FA5 i = 0x53aba93b9131c439d2942c7cbc483fa5 or 111217238859577568889117274385450287013 The bottom 32 bits of i unsigned are 3158851493So, yes that latter number appears to be the unsigned representation of the bottom 32 bits of that number.

Good grief! Print the whole number in hex and get 53ab…3fa5 until you have got your number parsing sorted out. Then you can revert to decimal. It is much easier to have the numbers in the same format (=hex), and you can see what is happening.

[Richard Tookey]

Tushar Goel wrote:Yeah thanks Richard. I am able to achieve this but can we transfer decimal output "111217238859577568889117274385450287013" into "3158851493" which
is bignum output.

I understand both are same but in different format but can we changed decimal output to bignum output format.

I despair! We have established that the value "3158851493" is most definitely not the result of "bignum output format". You got that number from the flawed use of printf by printing some part (possibly the first 8 bytes treated as a long) of the bignum. If your technical people have been using this in the generation of format preserving encryption then they need to be shot. Without seeing your format preserving encryption proprietary C code one can say no more.

What I find interesting is that you don't seem able to say which FPE algorithm you are using. OK the code used might be proprietary but the actual algorithm of any encryption technique should never be. Kerckhoffs's principle says that the security is always in the secrecy of key and not the secrecy of the algorithm.

[Tushar Goel]

Campbell says..
We have spent all week trying to explain to you that the decimal number

Agree and well understood. Sorry it took me long to understand this and keep asking same question. Problem is this thing is very new to me and also am
unable to understand it. That's why i keep asking same question. Do you know some tutorials to understand this? I googled it but not get any good document or
i overlook it.

Campbell says..
System.out.printf("The bottom 32 bits of i unsigned are %d%n", i.longValue() << 0x20 >>> 0x20);

Why you did this? How did you think this? As per you previous post here , you are trying to
divide it into 2 parts. First you move 0x20(32) position to the left and makes it signed then you right shift it 32 position and makes it unsigned. Can you please
explain this? I am totally lost in such operations.

Richard says..
OK the code used might be proprietary but the actual algorithm of any encryption technique should never be.

I am sorry, i am new to this. My seniors told me not to tell anything that's why i refrain myself to telling it. Sorry for that. We are using Ingenico BPS algorithm.

Richard says..
If your technical people have been using this in the generation of format preserving encryption then they need to be shot.

Let me speak to them. May be they understand.