Getting 1 byte extra in the modulus RSA Key and sometimes for exponents also

Question

Here is my code snippet:

 int eValue = 79, t;
 int bitLength = 1024; // KeySize
 BigInteger e = new BigInteger(Integer.toString(eValue));
 KeyPairGenerator kpg = KeyPairGenerator.getInstance("RSA");
 kpg.initialize(bitLength);
 KeyPair kp = kpg.generateKeyPair();
 KeyFactory kfactory = KeyFactory.getInstance("RSA");
 RSAPublicKeySpec kspec = (RSAPublicKeySpec) kfactory.getKeySpec(kp.getPublic(),
 RSAPublicKeySpec.class);
 System.out.println("Byte Length is : " + kspec.getModulus().toByteArray().length);
 String testString;
   try {
        testString = new String (kspec.getModulus().toByteArray() , "ISO-8859-1");
        StringBuilder tt  = new StringBuilder();
        for(t =0 ; t< testString.length() ; t++)
            {
                tt.append((int) testString.charAt(t)+",");
            }
            String encryptedBytes = tt.toString();
        System.out.println("Mod is : " + encryptedBytes);
    }catch (Exception ex) {
            // TODO: handle exception
 }

And here is the output:

Byte Length is : 129
Mod is : 0,190,193,141,230,128,124,6,201,254,135,66,162,65,147,160,76,160,181,7,141,113,8,57,193,185,206,42,125,9,169,209,124,74,233,151,10,128,180,35,24,206,213,32,48,4,39,178,60,10,249,151,50,218,220,11,124,72,64,148,135,251,133,23,54,171,25,202,157,28,21,39,239,234,48,56,79,36,127,59,203,108,189,232,216,231,237,237,90,253,19,118,29,18,142,126,254,193,189,82,15,126,139,136,45,31,133,242,187,81,62,52,5,23,11,217,171,233,7,137,115,30,93,206,236,31,196,111,153

For 1024 bit lenght key modulus should be 128 bytes and for 2048 it should be 256, but I am getting one byte extra (Adding 0 always at the very first byte), Need Help to reslove this..

Thanks, Pawan

Garrett

I suspect the conversion from ByteArray to string, try another conversion : #332579 – Psychologist

Answer 1

The reason for the 00h valued byte at the start is because BigInteger.toByteArray() returns the signed representation. As long as the key length in bits is N*8 (or key length % 8 = 0) then the signed representation of an RSA modulus will always feature a 00h valued byte at the start.

Simply remove the initial byte if it is zero by copying it into an array of the key length in bytes. Note that if you have a private exponent, it might also be shorter than the key length in bytes, so copy it to the end of the new byte array. Normally, this kind of method is known as I2OS or I2O (integer to octet string), where the octet sting (byte array in java) has a specified length.

/**
 * Encodes the given value as a unsigned Big Endian within an octet string
 * of octetStringSize bytes.
 * 
 * @param i
 *            the integer to encode
 * @param octetStringSize
 *            the number of octets in the octetString returned
 * @return the encoding of i
 * @throws IllegalArgumentException
 *             if the given integer i is negative
 * @throws IllegalArgumentException
 *             if the octetStringSize is zero or lower
 * @throws IllegalArgumentException
 *             if the given BigInteger does not fit into octetStringSize
 *             bytes
 */
public static byte[] integerToOctetString(final BigInteger i,
        final int octetStringSize) {

    // throws NullPointerException if i = null
    if (i.signum() < 0) {
        throw new IllegalArgumentException(
                "argument i should not be negative");
    }

    if (octetStringSize <= 0) {
        throw new IllegalArgumentException("octetStringSize argument ("
                + octetStringSize
                + ") should be higher than 0 to store any integer");
    }

    if (i.bitLength() > octetStringSize * Byte.SIZE) {
        throw new IllegalArgumentException("argument i (" + i
                + ") does not fit into " + octetStringSize + " octets");
    }

    final byte[] signedEncoding = i.toByteArray();
    final int signedEncodingLength = signedEncoding.length;

    if (signedEncodingLength == octetStringSize) {
        return signedEncoding;
    }

    final byte[] unsignedEncoding = new byte[octetStringSize];
    if (signedEncoding[0] == (byte) 0x00) {
        // skip first padding byte to create a (possitive) unsigned encoding for this number 
        System.arraycopy(signedEncoding, 1, unsignedEncoding,
                octetStringSize - signedEncodingLength + 1,
                signedEncodingLength - 1);

    } else {
        System.arraycopy(signedEncoding, 0, unsignedEncoding,
                octetStringSize - signedEncodingLength,
                signedEncodingLength);
    }
    return unsignedEncoding;
}

/**
 * Returns a BigInteger that is the value represented by the unsigned, Big
 * Endian encoding within the given octetString.
 * 
 * @param octetString
 *            the octetString containing (only) the encoding
 * @return the value represented by the octetString
 */
public static BigInteger octetStringToInteger(final byte[] octetString) {
    // arguments are signum, magnitude as unsigned, Big Endian encoding
    return new BigInteger(1, octetString);
}

/**
 * Returns the minimum number of bytes required to directly store the given
 * number of bits.
 * 
 * @param bitSize
 *            the bitSize
 * @return the size as a number of bytes
 * @throws IllegalArgumentException
 *             if the given bitSize argument is negative
 */
public static int bitSizeToByteSize(final int bitSize) {
    if (bitSize < 0) {
        throw new IllegalArgumentException("bitSize (" + bitSize
                + " should not be negative");
    }

    return (bitSize + Byte.SIZE - 1) / Byte.SIZE;
}

What

PS haven't unit tested the given methods yet, but should be ok according to "good" scenarios – What

Answer 2

You can use Arrays.deepToString() to print a byte array directly:

String encryptedBytes = Arrays.deepToString(new Object[] { kspec.getModulus().toByteArray() })

I suspect you are having trouble with signed vs. unsigned numbers. The 128-bit modulus is unsigned, but to store it in a BigInteger might sometimes take 129 bits, hence the extra byte.

Marcasite

Hmm, I always use a toHex helper method myself, which uses a StringBuilder of the byte array length times two, and then sb.append(String.format("%02X")) for each byte. Hexadecimals are more usefull I think. – What

you're right about hex being better. There's always commons-codec's Hex.encodeHexString of course. – Marcasite

it prints only upto 127, for greater than 128 it prints -ve number, also 0 is there if first byte is 128 or greater. – Garrett

perform <byte value> & 0xFF to get a positive integer with the right value, e.g. String.format("%02X", data[i] & 0xFF)... sorry for that. – What

Answer 3

As Maarten Bodewes has answered, the extra byte is space for the BigInteger's sign.

If the expected size is known and Hex is acceptable, i would use something like this:

System.out.printf("Mod is : %0256x%n" , kspec.getModulus());

Alyshaalysia

Answer 4

This question is best answered in the following Stackoverflow link. The solution is also very simple and applies to all cryptography applications because the length of all crypto keys are exact multiples of 8.

BigInteger to byte[]

Dellora