Extended Integer Support

Several years ago I wrote, largely as an exercise, a general purpose extended precision integer class for C++. Knowing that extended precision integers were needed for certain cryptographic algorithms, I later translated my C++ class into Ada with the intention of using it with ACO.

My original Ada version followed my C++ class's design and featured support for signed integers of arbitrary size. This is fine as far as it goes, but the implementation also used dynamic memory allocation (via the Ada 2005 Vectors package). When I decided to implement the core algorithms in ACO using SPARK I needed to rework my extended integer package to conform to SPARK rules. I removed the ability to dynamically resize the integers and I also dropped support for negative integers. I don't believe I will need negative values in my intended cryptographic applications (but we'll see).

The result is a package providing a type Very_Long that, currently, only supports 160-bit unsigned values. All operations on a Very_Long object are implicitly done modulo 2¹⁶⁰. My choice of 160-bit values is tied to my immediate need. I anticipate soon adding support in ACO for elliptic curve based (ECC) public key algorithms. Such algorithms do their computations in an underlying field such as F_p for some large prime p. It turns out that 160-bit field sizes provides reasonable security with ECC algorithms. Focusing on that size should be sufficient for now.

Ultimately I would like to support various field sizes, of course, and also use Very_Long objects to support other public key schemes besides ECC. A secure application of the RSA algorithm, for example, needs much larger integers. However, writing generalized SPARK code is a little tricky because SPARK currently supports neither generics nor object oriented techniques. Since everything in SPARK needs to be statically sized it seems likely that a general purpose Very_Long type would need to always allocate enough memory for the largest values that would ever be needed. Of course this is an inefficient use of memory for applications that need only small values. My plan is to address this issue at a later time.