Possible to generate BigInteger value collision?

Question

I am implementing a digital signature system on files represented by BigInteger Values. Unfortunately the empty file cannot be converted via byte[] to BigInteger, because of the Exception "Zero Length BigInteger".

So I represent the empty file with:

bigmesssage = new BigInteger ("0");

My concern is now: is there a value collision possible for any file that will be represented as BigInteger("0"), when I read the file "test1" as in the program BigIntegerTest.java below!

Program output yields for file "test1" containing a single "0":

0: 0
test1: 12298

Thanks a lot Gerrit

import  java.io.*;
import  java.math.BigInteger;
import  java.security.NoSuchAlgorithmException;


public class BigIntegerTest {



/**
 * @param args
 * @throws NoSuchAlgorithmException 
 */
public static void main(String[] args) throws NoSuchAlgorithmException {
    // TODO Auto-generated method stub

    byte[] message1;
    BigInteger bigmessage1 = null;
    BigInteger bigmessage2=new BigInteger ("0");        

    System.out.println("0: "+bigmessage2);

    String filename="./bin/test1";

    message1 = To_Byte_Array(filename);

    bigmessage1= new BigInteger (message1);

    System.out.println("test1: "+ bigmessage1);

}

public static byte[] To_Byte_Array (String filename) throws java.security.NoSuchAlgorithmException {
      //Liest die Nachricht, die in der Datei filename gespeichert ist, ein und
      //speichert sie als byte-Array in message.

      //lokale Variablen:
      byte[] data = null;
     // MessageDigest hash = MessageDigest.getInstance("SHA-512");//SHA2 //removed

      //Streams, in:
      File textFile;//Textdatei
      FileInputStream in;//Dateieingabe-Stream

      try {

          textFile = new File(filename);
          in = new FileInputStream(textFile);
          int size = (int)textFile.length(); // Dateilaenge
          int read = 0;    // Anzahl der gelesenen Zeichen
          data = new byte[size];      // Lesepuffer
          // Auslesen der Datei
          while (read < size)
            read =+ in.read(data, read, size-read);
          in.close();
          // Schreiben des Lesepuffers in Instanz von MessageDigest und speichern des Hash-Werts in message
          //hash.update (data);//removed
          //message=hash.digest ();//removed


      }//try
      catch (IOException ex) {
        ex.printStackTrace();
      }
      return data;//added
    }//To_Byte_Array


}

Answer 1

It should be possible to create a BigInteger that will not be equal to any other BigInteger.

Internally a BigInteger stores a int signum (to indicate the sign of the number) and an int[] mag containing the bytes that represent the binary value of the number.

However, BigInteger.ZERO contains an int[] mag = new int[0] and a signum = 0 (to ensure 0 == 0 in all cases). If you craft a special zero containing the same mag but a signum of '1' you will have a unique BigInteger that is not equal to BigInteger.ZERO but will, mathematically act exactly like BigInteger.ZERO.

This seems to create a BigInteger that does not equal ZERO but doing math on it seems to upset the BigInteger math.

public void test() throws Exception {
    BigInteger NAN = bigNAN();
    System.out.println("NAN==ZERO " + NAN.equals(BigInteger.ZERO));
    System.out.println("NAN+0 " + NAN.add(BigInteger.ZERO));
}

public static BigInteger bigNAN() throws Exception {
    BigInteger NAN = new BigInteger(new byte[]{0});
    Field hack = BigInteger.class.getDeclaredField("signum");
    hack.setAccessible(true);
    hack.set(NAN, 1);
    return NAN;
}

prints

NAN==ZERO false
java.lang.ArrayIndexOutOfBoundsException: 0
...

Answer 2

Use the constant BigInteger.ZERO, which won't be == to any other "zero" instance.

You can then use == to test if a file is empty:

if (bigmesssage == BigInteger.ZERO)
    // the file is empty

Answer 3

I found no way to generate an unique BigInteger value that behaves like all other BigInteger values. I was thinking of an unique value as computed by the hash function sha256sum:

leder@leder-HP-Pavilion-dv7-Notebook-PC:~/workspace1/gmr-digital-signature-2$ sha256sum test1
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855  test1

test1 being the empty file as well as:

leder@leder-HP-Pavilion-dv7-Notebook-PC:~/workspace1/gmr-digital-signature-2$ echo -ne '' | sha256sum 
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855  -

In contrast to the ASCII value ^@ or \x00:

leder@leder-HP-Pavilion-dv7-Notebook-PC:~/workspace1/BigIntegerTest/bin$ echo -ne '\x00' | sha256sum 
6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d  -

Therefore I ruled the empty file out of my system!

The collision would have been to use the value '0' twice: for the empty file and for echo -ne '\x00' > test1a. As can be seen in the following demo with side effects on BigInteger calculation:

import  java.io.*;
import  java.math.BigInteger;
import java.security.NoSuchAlgorithmException;


public class BigIntegerTest {



/**
 * @param args
 * @throws NoSuchAlgorithmException 
 */
public static void main(String[] args) throws NoSuchAlgorithmException {
    // TODO Auto-generated method stub

    byte[] message3;
    BigInteger bigmessage1 = null;
    BigInteger bigmessage2 = null;      
    BigInteger bigmessage3 = null;



    bigmessage1 = BigInteger.ZERO; 

    System.out.println("BigInteger.ZERO: "+bigmessage1);

    System.out.println("null: "+bigmessage2);

    String filename="./bin/test1a";

    message3 = To_Byte_Array(filename);

    bigmessage3= new BigInteger (message3);

    System.out.println("test1a: "+ bigmessage3);

    String comp = null;

    if (bigmessage1==bigmessage3) {comp="true";} else {comp="false";};

    System.out.println("bigmessage1==bigmessage3: " + comp);

    if (BigInteger.ZERO==BigInteger.ZERO) {comp="true";} else {comp="false";};

    System.out.println("BigInteger.ZERO==BigInteger.ZERO: " + comp);

}

public static byte[] To_Byte_Array (String filename) throws java.security.NoSuchAlgorithmException {
      //Liest die Nachricht, die in der Datei filename gespeichert ist, ein und
      //speichert sie als byte-Array in message.

      //lokale Variablen:
      byte[] data = null;
     // MessageDigest hash = MessageDigest.getInstance("SHA-512");//SHA2 //removed

      //Streams, in:
      File textFile;//Textdatei
      FileInputStream in;//Dateieingabe-Stream

      try {

          textFile = new File(filename);
          in = new FileInputStream(textFile);
          int size = (int)textFile.length(); // Dateilaenge
          int read = 0;    // Anzahl der gelesenen Zeichen
          data = new byte[size];      // Lesepuffer
          // Auslesen der Datei
          while (read < size)
            read =+ in.read(data, read, size-read);
          in.close();
          // Schreiben des Lesepuffers in Instanz von MessageDigest und speichern des Hash-Werts in message
          //hash.update (data);//removed
          //message=hash.digest ();//removed


      }//try
      catch (IOException ex) {
        ex.printStackTrace();
      }
      return data;//added
    }//To_Byte_Array


}

----------generated output:

BigInteger.ZERO: 0
null: null
test1a: 0
bigmessage1==bigmessage3: false
BigInteger.ZERO==BigInteger.ZERO: true