[OTR-dev] working with the libgcrypt mpi type and getting the actual integer value

[Bjorn Kuiper]

On 2/28/2013 6:27 AM, otr-dev-request at lists.cypherpunks.ca wrote:
> Date: Wed, 27 Feb 2013 12:18:01 -0600
> From: Ileana <ileana at fairieunderground.info>
> Subject: Re: [OTR-dev] working with the libgcrypt mpi type and getting
> 	the actual integer value
> Cc: otr-dev at lists.cypherpunks.ca
> Message-ID: <20130227121801.7bc18484 at hpsetup>
> Content-Type: text/plain; charset=US-ASCII
>
> On Tue, 26 Feb 2013 18:04:23 -0500
> Bjorn Kuiper <bjorn at kuiper.nu> wrote:
>
>> Hi,
>>
>> I'm trying to develop a C# implementation of the Off-the-record
>> library, but I'm having some problems with the libgcrypt library.
>>
>> Can somebody explain to me how you can print out the actual integer
>> value of an hex'd MPI ?
>>
>> Basically i want to know the integer value of this 'private' key
>>
>> 48BFDA215C31A9F0B226B3DB11F862450A0F30DA
>>
>> I think it is
>>
>> 415325779662433871844955547383752003988573073626
>>
>> but I'm unable to find a way to confirm this using libgcrypt
>>
>> I tried the following code:
>>
>> -- code snippit
>> gcry_mpi_t cript_prime;
>> char buffer[50] = {0};
>> char number[50] = {0};
>>
>> cript_prime = gcry_mpi_new(50);
>>
>> strcpy(number,"415325779662433871844955547383752003988573073626");
>
> So you are storing the 'number' as a string.  At this point its not
> even a number.  You can't convert it directly to hex because that
> requires divisions of a strings by 16. You can't divide strings by
> 16, but you can divide numbers.  You can't just use shift because you
> will lose the remainders.
>
> But since you must store it as binary anyway, what you are doing is
> converting to binary, then binary to hex string.  Remember in computers
> everything is in binary.
>
> Most processor integer division puts dividends in one register, and
> remainders in another.  So you are not going to beat the built in
> implementation unless you plan on assembly code.  And once you do
> that you see how difficult it is dividing a number larger then
> your register size.  (Maybe your compiler will help you?)
>
> Alternately, you can create a table array which indexes ascii
> representations into integer equivalents.  The unfortunate space
> complexity of this constant time operation is O(n*log(n)).  Normally we
> think O(n*log(n)) is a nice number, but in this case, we want
> O(log16(n)), which is an even nicer number.  :)
>
> So you might as well just use BigInteger (or c# equiv) to store the
> value as binary in ram, and print out as hex.
>
> But maybe your private key is already sitting in ram as a binary
> number!  But with what endianness and what representation?  If you can
> directly access that ram, you can simply do the binary to decimal
> conversion directly!
>
> And what do you know?
> http://msdn.microsoft.com/en-us/library/dd268207.aspx
>
> What a weird question.  I don't think I will use the C# otr...
>

First of all sorry, I'm not sure how to respond to e-mail digests, so I 
hope this message will be added correctly in the thread.

Thank Ileana for your response. I'm actually using BigInteger, but I 
wanted to make sure that I converted the value in the otr.private_key 
file to its correct value. So reading the value from the file, making 
sure the endian is correct and then converting it to a byte[] as input 
for BigInteger. Then BigInteger lets me display the actual value. I 
wanted to make sure this value matches the actual value generated by 
libgcrypt.

It seems I was on the right track.

Greetings Bjorn