Create MPIs in Java
August 7, 2009 2 Comments
I use GPG frequently and have a few of my friends I correspond with on a regular basis. We’re all paranoid and hence tend to use GPG. What I sorely lack is a GPG client on my BlackBerry. Sure, there’s Atmoichelix, but CAD $49.50 for a 1 year license, I mean, really? GPG should be free. I agree that perhaps a lot of work went into creating the Atomichelix product, but I think its about time a free implementation existed. So I began writing one. Best place to start, IMHO, would be by reading RFC 4880. There’s also a great utility and site that dumps (or parses) packets from PGP blocks. They’re both wonderful tools for learning the insides of PGP messages.
I’m keeping up a fairly good pace considering I have a day job, wife and child. I mean, who needs 5 hours of sleep a day when you can get by on 3 right? 😉 I recently tweeted about my accomplishment with creating Multi Precision Integers or MPIs. I think they are probably really straightforward to implement in C, but in Java, its another story. While bit manipulation exists in Java, I believe the code you need to write to get the job done is ugly. I’ll let you, my loyal reader, decide.
According to RFC 4880, item 3.2:
3.2. Multiprecision Integers
Multiprecision integers (also called MPIs) are unsigned integers used
to hold large integers such as the ones used in cryptographic
calculations.
An MPI consists of two pieces: a two-octet scalar that is the length
of the MPI in bits followed by a string of octets that contain the
actual integer.
These octets form a big-endian number; a big-endian number can be
made into an MPI by prefixing it with the appropriate length.
Examples:
(all numbers are in hexadecimal)
The string of octets [00 01 01] forms an MPI with the value 1. The
string [00 09 01 FF] forms an MPI with the value of 511.
Additional rules:
The size of an MPI is ((MPI.length + 7) / 8 ) + 2 octets.
The length field of an MPI describes the length starting from its
most significant non-zero bit. Thus, the MPI [00 02 01] is not
formed correctly. It should be [00 01 01].
Unused bits of an MPI MUST be zero.
Also note that when an MPI is encrypted, the length refers to the
plaintext MPI. It may be ill-formed in its ciphertext.
Here’s the Java code to do that. This code is specific to BlackBerry handhelds given its use of the DataBuffer. It would be trivial to change it to use J2SE:
private static byte[] makeMPI(byte[] num) throws IOException { DataBuffer db = new DataBuffer(); int bit_ctr = 0; int byteVal = 0; int byte_ctr = 0; for(int q=0;q0;k--) { if((byteVal & 0x80) == 0) { byteVal <<= 1; bit_ctr++; } else { break; } } break; } else { byte_ctr++; } } int mpi_len = ((num.length-byte_ctr)*8)-bit_ctr; db.writeChar(mpi_len); db.write(num); return db.toArray(); }