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

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