This page is a brief backgrounder on the LibTom Projects. I plan to put more details, thoughts, theories, and other notions into the third book project starting in a couple months. But for those curious as to where these projects came from, why I’m starting them, and more importantly how I’d love to see people take the gauntlet and run with it, please keep reading.
The projects started very humbly as the LibTomCrypt project in December of 2001. In fact, it was actually originally called “MyCrypt” which meant literally “my crypto library.” A fateful USENET suggestion later and LibTomCrypt was born. The project was originally designed solely to be my way of contributing a passable crypto library to the open source community. Little did I know it would expand into other cooler projects, expanding out of the digital realm of software into meatspace, having a real effect on people.
LibTomCrypt was originally written to develop and support a free crypto library. Shortly into the projects life I gained quite a few real users. If there is anything I can look back at as important was the feedback they would provide over the course of the next few years. When the project started, I can honestly say I had no clue how to write or support a professional product of any calibre.
Through the course of the first two years I learned the art of release engineering, debugging, verification and documentation. What was originally a small ensemble of C source and a .bat file to build it all became a fully automated, organized, and highly portable crypto library.
What’s more, throughout the course of developing the library I was forced to either teach myself new algorithms, or use what help I could get in the domain. What started off as a “coding” project quickly became a “research” project. The first target on the board was the exponentiation code. Originally I used a library known as MPI to work with large integers. This library was fairly portable, compact, and easy to work with. Unfortunately, it was slow. Real slow.
I started writing patches against MPI to speed it up. I switched out the binary square-multiply exponentiator for a full k-ary sliding window technique. This gave me a fairly non-trivial boost in speed but I was still far behind the likes of GMP and OpenSSL. Part of the problem was that MPI works with 15-bit digits. This means that even on a 32-bit or 64-bit machine you only manipulate 15-bits at a time.
Originally, I attempted to patch MPI to use larger digits but the code wasn’t having any of that and thus LibTomMath was born.
Armed with another holiday season (Dec 2002) I wrote the first version of LibTomMath. I chose the MPI design for the function parameters but re-wrote all of the code from scratch. In the end, I had a library that was drop-in replaceable with MPI but much faster. I chose to use 28 bits per digit (60 for 64-bit platforms) which greatly reduced the number of digits required per multiplication. I also implemented comba multipliers, various reduction techniques and so on.
LibTomMath was a great research project for me simply because I had to learn the techniques and algorithms to ensure that the end result was even useful. While I was writing, researching, testing, and observing the techniques I realized that the ensemble of projects could serve a much broader purpose than just being open source.
While working on the LibTomMath project I realized that while I was getting very familiar with the coding/testing of a bignum library I wasn’t very familiar with the guts of the algorithms I was implementing. It’s like cooking from a recipe. You may vary the preparation but you’re not really fully aware of what’s going on. To that end, I decided to write my first significant text. I started during my summer off in 2003, and by August I had a draft prepared for publication.
While writing the preface for the draft I thought up a motto which summarizes what I decided to dedicate myself to.
Open Source. Open Academia. Open Minds.
Which literally means through the publication of open source, the pursuit of academia, we shall open minds.
Throughout the life of the projects I had been publishing my results in various forms, from mailing lists to USENET. The goal was to share my hypothesis with the audience, the method which I would test it, and finally the results. This can be found in the numerous sci.crypt postings I have authored where I share cycle counts and memory sizes of algorithms that I found useful or interesting.
Stallman had very good ideas when he started the FSF. His heart was definitely in the right place. The problem though, he assumed the target audience would be seasoned developers. The FSF, and certainly most OSS advocates, look to share source, to make it distributable, and modifiable. Which are all honourable goals. I personally disagree with the copyleft on the grounds that only free software is truly free. But lets focus on the immediate failure of the FSF minded folk.
Suppose you’re a student and you want to see how an OS Kernel works. Is the Linux Kernel a good candidate? Not likely. It’s very messy, often poorly commented or documented. One of the repeated criticisms of the Kernel is that the pool of actual core maintainers is fairly small. Mostly because they wrote the majority of the core. But that’s just one example. Consider GCC, Mozilla, KDE, and so on. Worse is crypto code. For some reason, folk like the GPG and OpenSSL folk assume that completely abhorrent and messy source code is ok, so long as it works.
The LibTom Projects aims to change this line of thinking.
Goals of The LibTom Projects
The goals of the LibTom Projects are to distribute professional quality source code, documentation, and training material in whatever domain we pursue. Currently, it happens to be cryptography and algebraic number theory. That could easily change in the future.
The goal is not simply to have free software available to the public. It’s to ensure that students who pick up the projects can learn from them, ideally develop with them, and given sufficient training expand and improve upon them. My saddest thoughts are of projects like the LibTom Projects simply being deprecated due to age and being unfit for professional consideration.
It’s also a goal of the project to promote academia. Not in the, I wear a robe, thus am holier than thou sense, but in the I pursue truth and am unashamed to share it sense. We fund stipends for students to attend conferences, provide unpaid support and training to all those who seek it, and spread the idea of the Open Academia world. We want to see all open source projects become vehicles of knowledge not just functionality.
Think of how cool it would be if very influential and prominent tools such as GCC and Mozilla could be if learning were one of their primary goals.
Source as a Research Vehicle
I mentioned already that source could be a vehicle for education. Indeed, in my case certainly that has been the case. I had to learn either by reading previously published results, or figuring out on my own how to implement what has come to be known by many as a well put together, competitive, stable, function, and efficient set of cryptographic libraries. Throughout, the projects there have been numerous studies performed, to name a few
Binary vs. k-ary exponentiation Fixed vs. Sliding windows Comba Multipliers Diminished Radix Reduction Techniques Fixed Point Math Cross-Platform Configurable Assembler Driven Bignum (TFM project) TomsFastMath was a research project based on porting LibTomMath to something that could run much faster. Pluggable Math ECC fixed point multipliers ECC DSA Shamir’s Trick Configurable symmetric crypto (LTC build flags)
And certainly there are more I can’t think of off the top of my head. At every corner, where I can find a chance to make something smaller or faster a new research study is waiting. The point though is the projects aren’t perfect. There is room for improvement and this is where students come in to the picture.
We definitely want to encourage future development from outsiders. Not only by accepting any new code and documentation, but actively mentoring, guiding, and supporting future development. We already provide support for users of the projects, supporting students is the next logical level.
Starting around March/April 2007 the third book project will start. It will not be published, at least not without ensuring that public domain copies are available. The purpose of the book is to explain the projects in greater detail as well as collect all of the results throughout the years. Effectively, if I ever wrote a dissertation about free software and cryptography this would be it.
The project entails three parts, to be written over at least the next three years. The first part discusses the philosophy of open source and open academia. The thesis being that for the long term stability of the OSS movement, software must be both functional and educational. It requires a fairly heft radical thought process change on the behalf of quite a few OSS developers but is definitely worth the effort.
The second part discusses the art of software development, more specifically, from the point of view from a very small development team. I discuss what I’ve learned in the fields of design, verification, testing, release engineering, documentation, coding style, API design, and support. The thesis being that collectively documentation and source code can contribute to the educational qualities of a project. For this to be effective, the code must not only be clean (e.g. well indented), and commented, but designed in a logical and consistent fashion.
The third part discusses the science behind the projects. Here is where I try to collect as many experiments from yesteryear and bind them together in a cohesive treatment of cryptographic development. The thesis is many-fold as we cover the dozens of experiments that show how software can morph over time with proper design into something both maintainable and efficient.
As a whole the book is due to be released sometime in early 2010 at the latest. It’ll likely be released prior to that as individual components as they are written. Editors, contributors, and proof-readers are more than welcomed to contact me to get involved.
For those who want to know about me … :-)
I’m a Canadian, from Ottawa, the nations capital. I was born in 1982, raised, educated, and live here in town. I hold an associates degree (equiv) from Algonquin College in computer science and engineering. I grad’ed from college in 2004. I’m the published author of two texts on cryptography, as well as the lead author of a half-dozen open source projects, three of which are fairly prominent in the community (my users include several large corporations, OSS projects such as OLPC and Tcl, universities such as Harvard and EPFL, etc.).
I study the piano. I used to play when I was younger, took a near decade break and now am back into the study. I only play conservatory pieces :-) and hope to someday regain my talent from my youth and perform in public once again.
I’m a dedicated fan of the Toorcon conference scene. I’ve given talks there for the last three years as well as sponsor stipends and other activities (such as parties). As a policy I refuse to attend IACR conferences due to the excessive costs which exclude many students from attending. I prefer the small conference scene, but can see myself liking defcon one day.
I originally wanted to go the formal academia route and become a professor, realizing that was a lofty goal I devoted my energies to the projects (and a healthy respect for having a good time). Finally if you wanted to see what I look like, the following is a photo from Toorcon in 2006. Keep in mind this is Sunday afternoon, after a solid weekend (plus Friday) of partying :-)