Creating 'Mpint' Value in Java (The Secure Shell (Ssh) Protocol Architecture - Rfc 4251)
I'm Trying to Create Mpint String Using Biginteger as Specified in Rfc4251: Mpint Represents Multiple Precision Integers in Two's Complement Format, Stored as...
I'm trying to create mpint string using BigInteger as specified in RFC4251:
mpint
Represents multiple precision integers in two's complement format, stored as a string, 8 bits per byte, MSB first. Negative numbers have the value 1 as the most significant bit of the first byte of the data partition. If the most significant bit would be set for a positive number, the number MUST be preceded by a zero byte. Unnecessary leading bytes with the value 0 or 255 MUST NOT be included. The value zero MUST be stored as a string with zero bytes of data.
By convention, a number that is used in modular computations in Z_n SHOULD be represented in the range 0 <= x < n.
Examples:
value (hex) representation (hex) ----------- -------------------- 0 00 00 00 00 9a378f9b2e332a7 00 00 00 08 09 a3 78 f9 b2 e3 32 a7 80 00 00 00 02 00 80 -1234 00 00 00 02 ed cc -deadbeef 00 00 00 05 ff 21 52 41 11
Everything almost clear, but how to explain "Unnecessary leading bytes with the value 0 or 255 MUST NOT be included."?
And the second question is about this line: "By convention, a number that is used in modular computations in Z_n SHOULD be represented in the range 0 <= x < n.". How to explain it?
EDIT:
My first suggestion is:
/**
* Write 'mpint' to output stream including length.
*
* @param dos output stream
* @param bi the value to be written
*/
public static void writeMPInt(DataOutputStream dos, BigInteger bi) throws IOException {
byte[] twos = bi.toByteArray();
dos.writeInt(twos.length);
dos.write(twos);
}
Does this method is valid according mentioned above rules?
2 Answers
Unnecessary leading bytes with the value 0 or 255 MUST NOT be included.
Do not pad the front of numbers with extra 00 or ff bytes.
80stored as00 00 00 03 00 00 80has an extra leading00byte.-deadbeefstored as00 00 00 06 ff ff 21 52 41 11has an extra leadingffbyte.
In both cases, the numbers are technically correct but have unnecessary leading bytes.
By convention, a number that is used in modular computations in Z_n SHOULD be represented in the range 0 <= x < n.
Z_n is an ASCII way of writing the bold math notation for integers modulo n. (see Modular arithmetic)
This means, you should not store a number x greater than the modulus n to be used, or less than zero.
You wish to store the number 123.
You know that number will be modulo 100 for sure. That is,
123 % 100.You should store 23 instead.
Does this method is valid according mentioned above rules?
No, write() does not check if the values in your byte array conform to the above rules.
I do not fully agree with Jay Jun and because I did not understand it the first time I will try to give a different (hopefully simpler) answer (in code):
Unnecessary leading bytes with the value 0 or 255 MUST NOT be included.
The following code snippet will output the long (8 bytes) for the values: 0x80 and -0xdeadbeef
//long has 8 bytes
long l = 0x80L;
System.out.println("0x80 = "+String.format("%02X ", (l>>56) & 0xFF)+" "+String.format("%02X ", (l>>48) & 0xFF)+" "+String.format("%02X ", (l>>40) & 0xFF)+" "+String.format("%02X ", (l>>32) & 0xFF)+String.format("%02X ", (l>>24) & 0xFF)+" "+String.format("%02X ", (l>>16) & 0xFF)+" "+String.format("%02X ", (l>>8) & 0xFF)+" "+String.format("%02X ", (l) & 0xFF));
l = -0xdeadbeefL;
System.out.println("-0xdeadbeef = "+String.format("%02X ", (l>>56) & 0xFF)+" "+String.format("%02X ", (l>>48) & 0xFF)+" "+String.format("%02X ", (l>>40) & 0xFF)+" "+String.format("%02X ", (l>>32) & 0xFF)+String.format("%02X ", (l>>24) & 0xFF)+" "+String.format("%02X ", (l>>16) & 0xFF)+" "+String.format("%02X ", (l>>8) & 0xFF)+" "+String.format("%02X ", (l) & 0xFF));
The output is:
0x80L = 00 00 00 00 00 00 00 80
-0xdeadbeefL = FF FF FF FF 21 52 41 11
As we can see 0x80L is positive and has 7 leading 0 bytes but only 6 must not be included because the leading bit of 80 (binary value = 10000000) is 1 and therefore according to:
If the most significant bit would be set for a positive number, the number MUST be preceded by a zero byte
we have to precede 0x80 with one 0-byte. The result is therefore "00 80".
Vice versa for -0xdeadbeef we have 4 leading 255 bytes but only 3 must not be included because the most significant bit of "21" is "0" and therefore we need 1 leading 255 byte before "21 52 41 11" and the result is "ff 21 42 41 11"
All this leading byte problematic is handled when using BigInteger:
byteArray = new byte[]{(byte) 0x80};
bigInteger = new BigInteger(+1, byteArray);
byteArray = bigInteger.toByteArray();
byteArray = new byte[]{(byte) 0xde, (byte) 0xad, (byte) 0xbe, (byte) 0xef};
bigInteger = new BigInteger(-1, byteArray);
byteArray = bigInteger.toByteArray();
So coming back to the question:
Does this method is valid according mentioned above rules?
I would say yes.
PS: the only rule that BigInteger is not handling correctly is:
The value zero MUST be stored as a string with zero bytes of data
byteArray = new byte[]{};
bigInteger = new BigInteger(0, byteArray);
byteArray = bigInteger.toByteArray();
will actually return 1 byte with the value of 0 instead of an empty array.
Elena Rostova holds a Master's degree in Public Health Journalism. She covers groundbreaking medical research, holistic wellness trends, mental health awareness, and nutritional science.
