January 20, 2015
Swiftly Secure, Part 1 – Large Number Multiplication
I have a swift iOS project where I want users to be able to communicate between their devices by sharing data via a server. I want their communications to be encrypted in such a way that no one can decrypt them except the two parties communicating. In fact, I want their communications to be encrypted end-to-end without them being de-cryptable when they are on the server. To accomplish this, I’ve decided on using the Socialist Millionaire protocol since it handles both encryption and authentication.
Doing encryption of this type means I’m going to need to multiply integers that are too large to fit in any of the standard Swift or Objective-C integers. I explored some existing large number libraries in C, but the most commonly used ones appear to be GPL or LGPL licensed. I won’t use libraries under those licenses in a closed source app so I decided to create something of my own.
In this posting I’m going to show you a part of what I’m creating — how to multiply numbers in swift without encountering overflow problems. Overflow issues aren’t very common in business situations, numbers there tend to be small compared to the size of a 64 bit signed integer, but in some scientific computation situations and in my Socialist Millionaire implementation encryption overflow is an issue. Sampling from a random number stream and multiplying the results is another source of overflow situations. In fact, random sampling and multiplying has a very high probability of overflow if the random number generator yields results that are close to being evenly distributed.
I want to keep the example in this post simple, so I will show you an implementation of the grade school method. Multiplying 99 x 99 the way I was taught in grade school (multiply, carry, and then add) is a good place to start.
There is an alternative way of doing this same multiplication (multiply, add, then carry). In this example each time 9 is multiplied by 9 the result is written on a new line. All except the first partial product are shifted left — one place for the second and third product, two places for the fourth product.
The second method is the one I’m going to show in this posting. An example of bits being manipulated is helpful. To make it easier to understand we’ll stick with 8 bit numbers where each nibble (4 bits) represents one ‘digit’ for multiplication purposes.
Following the second grade school multiplication method using nibbles, lets multiply 255 x 255. Multiplying those two numbers should overflow an 8 bit result but we’ll keep that from happening without loosing any data.
Keep in mind that 0b1111 x 0b1111 = 0b11100001 (15 x 15 = 225).
The two part base 256 product, one 8 bit number representing the ones place and the other representing the 256’s place, is the result of left shifting the upper half of two nibble pairs and adding them to their corresponding bottom halves,
1111 << 4 + 1110 yields 11111110 and
0000 << 4 + 0001 yields 00000001.
The code example below follows the same pattern as the 8 bit multiplication without overflow table and uses the constant and variable names listed in the first column.
/* * I did this big endian since it was easier to think about this part of the algorithm this way */ func multiplyWithOverflow(multiplicand:UInt64, multiplier:UInt64) ->[UInt64]{ //multiply to get all addends let lowerLowBits = (multiplier & bottomHalfBitMask) * (multiplicand & bottomHalfBitMask) let lowerHighBits = (multiplier & bottomHalfBitMask) * (multiplicand >> 32) let upperLowBits = (multiplier >> 32) * (multiplicand & bottomHalfBitMask) let upperHighBits = (multiplier >> 32) * (multiplicand >> 32) //get the 4 bit sums of the addends. There are 4. Some may be zero let bottom = lowerLowBits & bottomHalfBitMask let middleBottom = (lowerLowBits >> 32) + (lowerHighBits & bottomHalfBitMask) + (upperLowBits & bottomHalfBitMask) + (bottom >> 32) let middleTop = (lowerHighBits >> 32) + (upperLowBits >> 32) + (upperHighBits & bottomHalfBitMask) + (middleBottom >> 32) let top = (upperHighBits >> 32) + (middleTop >> 32) //combine the 32 bit sums to make two 64 bit values let bottom2N64 = (middleBottom << 32) + bottom let top2N64 = (top << 32) + (middleTop & bottomHalfBitMask) return [top2N64,bottom2N64] }
If you want to use this overflow protection in a situation where overflow is infrequent, business, games, some simulations, etc., you will want to add an if statement to this code or allow the multiplication to overflow and then handle the situation as an error. Checking to see if two numbers will overflow before multiplying them turns out to be fairly easy. All you have to do is find the location of the highest bit in both numbers and add those locations together. If the location sum is greater that 63 the two numbers will overflow when multiplied.
In my next post, I’ll show how to represent huge numbers as arrays of UInt64’s and multiply those together, another component I need when implementing the Socialist Millionaire protocol.
Teton Technical 