Cryptography Project - Adding Arbitrary Precision Integers
Last semester I took a very interesting course with Prof. Alexander Russell at the University of Connecticut about Cryptography. The course was focused overwhelmingly on the theory and the mathematics behind Cryptography, so I am ashamed to say that I did not do as well as I would have liked. The course was split between graduate and senior undergraduate students and, in the words of the professor himself, was "the most theoretically rigorous course of our curriculum". However, to allow graduate students to get credit for the course there was a project that we had to implement. This is where I actually managed to climb back up to a decent grade because the objective was to implement a series of functions and objects that could be used to then implement a pseudorandom generator - a fundamental cryptographic primitive which I will attempt to describe in later posts.
Please Note: This series of posts should not be used as any kind guide on how to implement a cryptographic library for use in an actual setting. This is simply a series of posts that I wanted to write up about my experience developing this peice of software for a school project. It was never tested against any kind of rigorous adversary, it was only ever graded by a TA. Typically these kinds of thing come with the standard GPL statement "THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE." However, in this case I am explicitly stating that this program is unfit for any purpose other than learning and even that's questionable.
When this project was assigned, the allowed languages were Java and C++. I requested to be allowed to do this in C and the professor had no issue with that. I should note that while I like to think I know C reasonably well and actually like to program in it, but C++ scares me - there's just too much to it and from my point of view they keep adding more and more to it to make up for some questionable decisions very early on. I felt a lot more comfortable with C and this was a good opportunity to expand my experience.
The entire source code has been posted here: https://github.com/Abraxos/fun-stuff/tree/master/Cryptography_Project within my "fun-stuff" repository on github which I use as a place to store some interesting school/personal projects that I wanted to show off.
Setting Up The Project - TDD FTW
While I've known about Test-Driven Development for a while, I never really had the time or the discipline to actually do it. Little did I know the irony that TDD really saves more debugging time in the long run - unfortunately you couldn't tell me that at 23:30 before a homework assignment was due. I actually started this particular project with a lot of time to spare, so I figured that if I worked hard and made sure to plan everything well before the deadlines, I should be able to do test-drive development. I think the biggest lesson of this project is that test-driven development is probably the best approach to software development. I like to think that I am good with C, but the truth is that I would have never been able to finish this project if I did not rigorously test every single component and run almost all the tests every time I built the code.
I've never had the chance to do rigorous testing throughout the project development before and all I can say is that my experience was kind of like when I discovered what a decent IDE is for the first time. Over time I came to use a mix of Emacs, Sublime Text, and JetBrains IDEs, but the real advantages of an IDE are that they detect errors very early on. For example, typically, if you forget a semi-colon at the end of a line it will highlight it red and will refuse to build partially removing the frustration of having to repeately compile, fail, and repeat until all the stupid syntax errors have been repaired and you can get to work on debugging the real errors. This is wonderful, right? Especially when you are a young computer science student and just spent your first semester fixing stupid bugs in a program that prints out the day of the week that you were born on. TDD is just like that except for much more complex errors. The whole point is that TDD allowed me to catch errors extremely quickly in much the same way that an IDE would have, except that this time, instead of basic syntax and type-errors, TDD allows you to catch all sorts of logical and syntactic errors. As strange as it sounds, developing with lots of tests was a joy. I really began to appreciate rigorous testing after this project.
All that being said, I looked around for a testing framework for C and ended up setting on CMocka. I had a little bit of trouble making it build properly, but I got some help on the CLion Forum from Anna Fillipova and everything started to work just fine. If you would like to see detailed examples of how to build the code, I recommend looking through the README in the fun-stuff repo which explains how to build the code with and without tests (depending on whether you want to install CMocka).
Arbitrary Precision Integers
So what are arbitrary precision integers? Well, normally, when we program a computer we use integers that are either 32 or 64 bits in width. Assuming the integers are unsigned we can represent any number from 0 to 4,294,967,295 with a 32-bit integer and any number from 0 to 18,446,744,073,709,551,615[1]. But what if we want to represent a much larger value. An integer with thousands of digits? Well, that's where we would use arbitrary precision integers.
The goal is to somehow chain some effectively unlimited number of integers together in memory and treat them as one number for basic operations such as addition, subtraction, multiplication, and so on. This presents many different challenges: We are typically used to basic operations being provided for us by operators like +, -, /, and * and we do not really care what happens inside the processor to make those operations work. Furthermore, we are used to working with 32/64-bit integers that are so much smaller than the maximum value (seriously when was the last time you did a computation on 18 quitillion of anything?) and the possiblity of overflow was so remote that we never bothered with it.
The first problem was chaining the integers together in memory efficiently. I ended up making a linked list data structure where each node had a uint32 and two pointers more_significant and less_significant which pointed respectively to the more significant and the less significant integer components. These are the structs that describe the arbitrary precision integer in its entirety:
typedef struct ap_int_component_t
{
struct ap_int_component_t* more_significant;
struct ap_int_component_t* less_significant;
uint32_t integer;
} ap_int_component;
typedef struct ap_int_t
{
ap_int_component* most_significant;
ap_int_component* least_significant;
uint64_t size;
} ap_int;
There are a couple of things to note:
-
I could've used uint64's to represent the integer inside the
ap_int_component, however, for the sake of making the project easier to test on large numbers, I decided to stick with 32-bit integers. The program should work, however, with 64-bit integers as well so long as all the types are correctly adjusted and one runs the tests to be sure. -
The
ap_intclass has pointers to the most significant and least significant components. It is effectively a very simple doubly-linked list that we all learned in data structures. -
The
ap_intclass has a 64-bit size which means that theap_intis not a true AP-Integer, but its good enough considering that an integer with 18 quitillion digits would use up all the usable memory.
Detecting Overflow
In my opinion, the key element to making an arbitrary precision integer library work is to first work out the means by which you detect overflow for addition and multiplication. So I focused on that first.
I am not sure whether this would work on a processor with a different architecture, but it did work for me on an intel architecture. Specifically, I used the way overflowed integers react to detect them - when an integer value grows beyond 32 bits, it overflows and simply comes "back around". So for example if we have the following value: 1111 1111 1111 1111 1111 1111 1111 1111 and we added 0000 0000 0000 0000 0000 0000 0000 0001 to it, the result would be 0000 0000 0000 0000 0000 0000 0000 0000 because the number overflows and comes back to 0. If we added 0000 0000 0000 0000 0000 0000 0000 0010 (two in binary) to the all-ones integer, the result would be 0000 0000 0000 0000 0000 0000 0000 0001.
We can use this to our advantage because we know that the result of an addition operation of two non-negative numbers should never be smaller than either of the two numbers involved. Potentially we could use the following algorithm:
BOOL addition_will_overflow(uint32_t a, uint32_t b)
{
if (a == 0 || b == 0) return FALSE;
else return (a + b <= MAX(a,b));
}
Note that we need not bother performing the operation if either of the values are zero. Otherwise we check whether the sum of A and B is smaller than or equal to the max of either A or B and return the result.
These are the tests that I made to make sure that program is correct:
static void test_addition_overflow_detection(void** state)
{
uint32_t a = 4294967290;
uint32_t b = 8;
uint32_t c = 5;
uint32_t d = 4294967295;
uint32_t e = 4294967295;
uint32_t f = 0;
assert_true(addition_will_overflow(a,b));
assert_true(addition_will_overflow(b,a));
assert_false(addition_will_overflow(a,c));
assert_false(addition_will_overflow(c,a));
assert_true(addition_will_overflow(d,e));
assert_true(addition_will_overflow(e,d));
assert_false(addition_will_overflow(d,f));
assert_false(addition_will_overflow(f,d));
}
Detecting overflow in multiplication is slightly more complex but the same general principle applies: When the integer overflows under multiplication, something weird will happen that would not be possible otherwise. The property in question here is that if we multiply one integer by another, the product ought to be divisible by either of those integers and the result of the division should be the other integer. Therefore, the following algorithm came about:
BOOL multiplication_will_overflow(uint32_t a, uint32_t b)
{
if (a == 0 || b == 0 || a == 1 || b == 1) return FALSE;
else {
uint32_t c = a * b;
return (c / a != b);
}
}
First we check whether any of the numbers is a 0 or a 1 which means there would never be an overflow, then if that's not the case, we multiply A by B and then try to divide by A. If the result is not B, then the computation has overflowed. This is how I tested the method to make sure:
static void test_multiplication_overflow_detection(void** state)
{
uint32_t a = 4294967290;
uint32_t b = 8;
uint32_t c = 1;
uint32_t d = 2147483649;
uint32_t e = 2147483648;
uint32_t f = 4294967295;
assert_true(multiplication_will_overflow(a,b));
assert_true(multiplication_will_overflow(b,a));
assert_false(multiplication_will_overflow(a,c));
assert_false(multiplication_will_overflow(c,a));
assert_true(multiplication_will_overflow(d,3));
assert_true(multiplication_will_overflow(e,3));
assert_true(multiplication_will_overflow(a,a));
assert_true(multiplication_will_overflow(f,f));
}
Addition
So how do we do addition now that we have the ap_int struct as described above? Furthermore, how do we do it quickly? (linear time in relation to the number of bits). We begin by creating two new functions below. The first one allows us to add an integer value to a component and returns true if the addition overflows. The second prepends an ap_int_component to an ap_int with a given value as the most significant component.
BOOL ap_int_component_plus_uint32(ap_int_component* ac, uint32_t b)
{
uint32_t a = ac->integer;
ac->integer = b + a;
return addition_will_overflow(b, a);
}
void ap_int_add_component(ap_int* a, uint32_t integer)
{
ap_int_component* new_component = (ap_int_component*)malloc(sizeof(ap_int_component));
new_component->integer = integer;
new_component->more_significant = NULL;
new_component->less_significant = a->most_significant;
a->most_significant->more_significant = new_component;
a->most_significant = new_component;
a->size ++;
}
Once we have those two functions we can actually implement addition. The general idea is that we loop over the two AP-Integers from least significant to most significant simultaneously and trying to add each pair of components to produce a third, new component and prepend it to a new AP-Integer called C. This is literally based on the method of long addition that we all learned in school. More specifically we create a new AP-Integer called C, and three pointers to the current ap_int_component so that we can loop over them, hereby referred to as CA, CB, and CC. We also create an overflow bit to keep track of whether there is an overflow.
The main part of the algorithm is a while loop that continues until both CA and CB point to NULL (the more_significant pointer of the most_significant component). If CA exists, we add the integer inside of it to CC and check whether the operation overflows. If there is an overflow, we add a new component to C with the value of one. We also increment CA to its more significant component. Then if CB exists, we again add its value to CC and check if the operation overflows. If there is an overflow then we add 1 to CC's more significant component (creating it if it does not exist). Please note that the maximum value of cc->more_significant at this point is two so there should never be an overflow at that step, however, for assumptions like that its always good to put an assertion in your code to make sure that it stays the case and you have no bugs that you may have overlooked when making that assumption. We then increment CB to its more significant component as well. Finally, if both CA and CB exist, but we have not yet created CC (probably because both CA and CB were zero) we should make sure to create a CC, then we can safely increment CC.
Notably, there are other ways, arguably more consice ways, to implement this, but this example mirrors the long addition behavior pretty well and it retains a linear runtime which is the critical part.
ap_int* ap_int_plus_ap_int(ap_int* a, ap_int* b) // runtime O(n)
{
ap_int* c = init_ap_int_with_uint32(0);
// loop over the components of a and b simultaneously from least to most significant
ap_int_component* ca = a->least_significant, * cb = b->least_significant, * cc = c->least_significant;
BOOL overflow;
while (ca || cb)
{
if (ca)
{
overflow = ap_int_component_plus_uint32(cc, ca->integer);
if (overflow)
{
ap_int_add_component(c,1);
}
ca = ca->more_significant;
}
if (cb)
{
overflow = ap_int_component_plus_uint32(cc, cb->integer);
if (overflow)
{
if (!cc->more_significant)
{
ap_int_add_component(c,0);
}
overflow = ap_int_component_plus_uint32(cc->more_significant,1);
// this operation should never result in an overflow since at this point the maximum value of cc->more_significant is 2
assert(!overflow);
}
cb = cb->more_significant;
}
if ((ca || cb) && !cc->more_significant)
{
ap_int_add_component(c,0);
}
cc = cc->more_significant;
}
return c;
}
Testing this method was a little bit difficult because when I wrote this part I did not have a constructor that could actually take a string and turn it into an AP-Integer which meant that the only way to produce a large enough integer was to add elements together to form a larger value. Eventually I expanded the tests when I wrote the init_ap_int_with_decimal_string() method which will be described in a later post. Furthermore to confirm the values I had to create the debug string value which uses a bitwise interator:
static void test_ap_int_addition(void** state)
{
ap_int* a = init_ap_int_with_uint32(4294967295);
ap_int_plus_uint32(a, 1);
printf("A: ");
print_ap_int(a);
ap_int* b = init_ap_int_with_uint32(4294967295);
ap_int_plus_uint32(b, 4294967295);
ap_int_plus_uint32(b, 4294967295);
printf("B: ");
print_ap_int(b);
ap_int* c = ap_int_plus_ap_int(a,b);
printf("C: ");
print_ap_int(c);
const char* debug_str = ap_int_to_debug_str(c);
assert_string_equal("00000000000000000000000000000011 <-> 11111111111111111111111111111101 <-> ", debug_str);
free((void*)debug_str);
free_ap_int(a); free_ap_int(b); free_ap_int(c);
// Testing addition of differently-sized ap-integers
a = init_ap_int_with_uint32(4294967295);
printf("A: ");
print_ap_int(a);
b = init_ap_int_with_uint32(4294967295);
ap_int_plus_uint32(b, 4294967295);
ap_int_plus_uint32(b, 4294967295);
printf("B: ");
print_ap_int(b);
c = ap_int_plus_ap_int(a,b);
printf("C: ");
print_ap_int(c);
debug_str = ap_int_to_debug_str(c);
assert_string_equal("00000000000000000000000000000011 <-> 11111111111111111111111111111100 <-> ", debug_str);
free((void*)debug_str);
free_ap_int(a); free_ap_int(b); free_ap_int(c);
a = init_ap_int_with_decimal_string("987230987450129387412341098");
b = init_ap_int_with_decimal_string("987230987450129387412341098");
c = ap_int_plus_ap_int(a,b);
debug_str = ap_int_to_binary_str(c);
assert_string_equal(debug_str, "000001100110000100111100100101100010001001000011100110011100011000111001111100101000001011010100");
free((void*)debug_str);
free_ap_int(a); free_ap_int(b); free_ap_int(c);
}
So there it is, that's how I implemented and tested AP-Integers, overflow detection, and addition. Hopefully you find that pretty interesting and useful. The next post on this subject will describe how I did multiplication and bitwise iteration over the ap_int which is useful for certain kinds of constructors and arithmetic operations.
Thanks for reading.