Natural numbers module
[Cryptographic functions]

Natural numbers processing. More...

Data Structures
struct	BC_NANU_CONS
	Structure for constants. More...
Defines
#define	BC_NANU_POOL(depth) (((depth)*2+10)
	Size of the pool administrative data.
Enumerations
enum	{ BC_NANU_NANU = 0, BC_NANU_SUND = -1, BC_NANU_SOVR = -2, BC_NANU_NANN = -3, BC_NANU_OMEM = -4, BC_NANU_SIZE = -5, BC_NANU_ITEM = -6, BC_NANU_NEXT = -7 }
	Return codes. More...
enum	{ BC_NANU_LT, BC_NANU_LE, BC_NANU_EQ, BC_NANU_GE, BC_NANU_GT, BC_NANU_NE }
	Comparison conditions. More...
Functions
int	BC_NanuComp (BC_NANU nanu, int test)
	Compares the two top elements of the stack.
int	BC_NanuCons (BC_NANU nanu, const BC_NANU_CONS *cons)
	Pushes a constant onto the stack.
int	BC_NanuDrop (BC_NANU nanu)
	Deletes the top item of the stack.
int	BC_NanuDupl (BC_NANU nanu)
	Duplicates the top item of the stack.
int	BC_NanuMadd (BC_NANU nanu)
	Modular addition.
int	BC_NanuMexp (BC_NANU nanu)
	Modular exponentiation.
int	BC_NanuMmul (BC_NANU nanu)
	Modular multiplication.
int	BC_NanuMsub (BC_NANU nanu)
	Modular subtraction.
BC_NANU	BC_NanuInit (int *buff, unsigned short size, unsigned char item)
	Initialises the natural number library.
int	BC_NanuOver (BC_NANU nanu)
	Pushes a copy of the second item onto the stack.
int	BC_NanuPick (BC_NANU nanu, unsigned item)
	Pushes a copy of the n-th item of the stack onto the stack.
int	BC_NanuPull (BC_NANU nanu, void *buff, int size)
	Stores the top of the stack at a given location.
int	BC_NanuPush (BC_NANU nanu, const void *buff, int size)
	Pushes a new item onto the stack.
int	BC_NanuRadd (BC_NANU nanu)
	Regular addition.
int	BC_NanuRexp (BC_NANU nanu)
	Regular exponentiation.
int	BC_NanuRmod (BC_NANU nanu)
	Regular modulus.
int	BC_NanuRmul (BC_NANU nanu)
	Regular multiplication.
int	BC_NanuRoll (BC_NANU nanu, int n)
	Rolls a given number of elements on the stack.
int	BC_NanuRsub (BC_NANU nanu)
	Regular subtraction.
int	BC_NanuShft (BC_NANU nanu, int shift)
	Shifting of a number.
int	BC_NanuSize (BC_NANU nanu)
	Returns the length of the topmost element of the stack.
int	BC_NanuSwap (BC_NANU nanu)
	Exchanges the top two items on the stack.
int	BC_NanuTail (BC_NANU nanu)
	Number of trailing 0 bits of a number.
int	BC_NanuTuck (BC_NANU nanu)
	Pushes a copy of the top item to under the second item on the stack.

Detailed Description

Natural numbers processing.

Certain cryptographic functions, most prominently the RSA public key cryptography and the Diffie-Hellman key exchange algorithm depend on number theory problems that are computationally very hard to solve. These functions are all working on natural numbers, that is, non-negative integers (we consider 0 as a natural number). Quite often the operations involve calculating the remainder of division by a large number. The maths behind the whole thing is the finite field theory and if you want to understand how (and why) the algorithms work, you should get a finite field textbook.
In practice, the numbers you deal with tend to be several hundred or a few thousand bits long and the most prominent operation is modular exponentiation.

If you consider that a 2048 bit number is roughly 600 decimal digits, you can appreciate the computational demand of raising a 600 digit number to a 600 digit power, resulting in a number almost 400,000 decimal digits long, then calculating the remainder of dividing that 400 thousand digit number by a 600 digit number. Fortunately, the properties of finite fields allow you to do that efficiently, without any hundreds-of-thousands-of-digits numbers and 600 digit divisions. That's what this library gives you: efficient algorithms (and reasonably fast implementation) of elementary arithmetic functions operating on large natural numbers.

The natural numbers module is part of the cryptographic library because the RSA implementation uses it, but it is a self-contained unit. It provides the basic arithmetic operations on large positive integers. It actually offers more than what RSA needs, so that you can, if you want, implement more advanced cryptographic operations with it.

The module needs a chunk of memory as its workspace. You pass that memory to the initialisation function and you shall not touch that memory until you finished all operations. The operations are all performed on a stack. If you have used RPN (Reverse Polish Notation) calculators or programmed in the FORTH language then you will find the functions in this library very familiar. If not, here's a quick run-down:

Numbers are pushed to a stack. The arithmetic operations are carried out by removing the operator's operands from the top of the stack, perform the operation on the operands and pushing the result back to the stack. Therefore, if you want to calculate a - b then you push a to the stack first, then you push b and then you subtract. The subtract operation will pop both a and b from the stack, calculate the difference and push that onto the stack.
Since any operation thus destroys its operands, you have a handful of operators that manipulate the stack itself. You can duplicate elements, swap them, destroy them and so on, so that you don't have to push and pop numbers all the time. Normally you do not need external temporary storage, because the stack manipulation operations are powerful enough to let you use the stack itself for temporary storage - that's the whole idea, actually, that you perform all operations on the stack.
You never see the stack itself. The only interface between your code and the stack is pushing a number and popping a number, to and from the top of the stack. You can not take a look at, let alone modify, the third element of the stack, or any element of it, for that matter. If you have never worked with stack machines, then it looks weird at first, but you can get used to it very quickly.

The function descriptions all contain a diagram of what they do to the stack. The left hand side of the "==>" symbol indicates the stack before the operation and the right hand side of "==>" is how the stack looks after the operation. The numbers on the stack are repsesented by a symbol or an expression, separated by space. The leftmost such element is the top of the stack (note that this is the opposite of the convention used for FORTH words!). The ... is used to indicate some other stack elements that are not relevant for the operation; it does not matter what they are or if they exist at all, they have no effect on the operation and the operation doesn't affect them. For example, when you add two numbers, a and b, your stack behaves like this:

           before              after

          +-------+
          |   b   |
          +-------+          +-------+
          |   a   |          |  a+b  |
          +-------+          +-------+
          |  ...  |          |  ...  |
          |  ...  |          |  ...  |

and that will be represented by the stack diagram:

          b a ... ==> a+b ...

Every function returns an integer error code. If there was an error, then the returned value is negative. The error codes are defined in the header. If there was no error and the function gives you some result, it is always a non-negative integer. If the function does not have a return value as such, it will return BC_NANU_NANU^*, which is a non-negative number.

Note: If an error occurs, then the entire stack is emptied and the state is of the whole natutal number engine is reset. You should check the returned code for each operation.

^* Hommage to Robin Williams.

To use these functions, you need to include crypto/nanu.h.

Define Documentation

#define BC_NANU_POOL ( depth ) (((depth)*2+10)

Size of the pool administrative data.

The macro returns the number of words that the library will reserve from its memory pool for administrative purposes if the stack is set to depth deep when calling the BC_NanuInit() function.

Enumeration Type Documentation

anonymous enum

Return codes.

Enumerator:

BC_NANU_NANU	Greetings, Earthling, it's all fine!
BC_NANU_SUND	Stack underflow.
BC_NANU_SOVR	Stack overflow.
BC_NANU_NANN	Result is not a natural number.
BC_NANU_OMEM	Out of memory.
BC_NANU_SIZE	External object size is out of bounds.
BC_NANU_ITEM	Out of variable descriptors.
BC_NANU_NEXT	Next unused error code.

anonymous enum

Comparison conditions.

Enumerator:

BC_NANU_LT	Less than.
BC_NANU_LE	Less than or equal to.
BC_NANU_EQ	Equal to.
BC_NANU_GE	Greater than or equal to.
BC_NANU_GT	Greater than.
BC_NANU_NE	Not equal to.

Function Documentation

int BC_NanuComp	(	BC_NANU	nanu,
		int	test
	)

Compares the two top elements of the stack.

Compares the topmost two elements of the stack and returns a flag whether the specified test was true or not. The stack remains unchanged. The following comparisons are supported:

BC_NANU_GT returns true if the second element is larger than the topmost
BC_NANU_GE returns true if the second element is larger than or equal to the topmost
BC_NANU_EQ returns true if the second element is equal to the topmost
BC_NANU_NE returns true if the second element is not equal to the topmost
BC_NANU_LE returns true if the second element is smaller than or equal to the topmost
BC_NANU_LT returns true if the second element is smaller than the topmost

Parameters:

	nanu	The natural number machine state descriptor
	test	The comparison to perform

Return values:

	1	The test was successful and the result is 'true'
	0	The test was successful and the result is 'false'
	BC_NANU_SUND	The stack didn't have at least two items on it
	BC_NANU_SIZE	The test parameter was not a valid test

Stack image: a b ... ==> a b ...

int BC_NanuCons	(	BC_NANU	nanu,
		const BC_NANU_CONS *	cons
	)

Pushes a constant onto the stack.

Creates a new number on the top of the stack. The value of the new number will be that of the number represented by the argument. The argument is a pointer to a structure. The first element of the structure is the length of the constant, in 32-bit words. It is followed by a number of unsigned ints that represent the constant in little-endian order. The most significant word must not be 0; if it is, then the function returns with a size error and the stack is flushed. The only exception is if you want to push a constant 0, which is allowed.
This function actually does not create a copy of the item, it just stores a reference to the external data. Therefore, the structure describing the constant must not be modified as long as this constant is on the stack. In addition, although the constant itself is not pushed onto the stack, a reference is, therefore this routine can still return an out of memory error.

Parameters:

	nanu	The natural number machine state descriptor
	cons	Pointer to the constant descriptor

Return values:

	BC_NANU_NANU	The operation succeeded
	BC_NANU_SOVR	The stack was full
	BC_NANU_SIZE	The size parameter is invalid
	BC_NANU_OMEM	There's not enough memory in the pool to store the number.

Stack image: ... ==> const ...

int BC_NanuDrop ( BC_NANU nanu )

Deletes the top item of the stack.

Parameters:

nanu

The natural number machine state descriptor

Return values:

	BC_NANU_NANU	The operation succeeded
	BC_NANU_SUND	The stack was empty

Stack image: a b ... ==> b ...

int BC_NanuDupl ( BC_NANU nanu )

Duplicates the top item of the stack.

Parameters:

nanu

The natural number machine state descriptor

Return values:

	BC_NANU_NANU	The operation succeeded
	BC_NANU_SUND	The stack was empty
	BC_NANU_SOVR	The stack was full

Stack image: a b ... ==> a a b ...

BC_NANU BC_NanuInit	(	int *	buff,
		unsigned short	size,
		unsigned char	item
	)

Initialises the natural number library.

Parameters:

	buff	Pointer to a (word aligned) memory area that will be used as a workspace for the library.
	size	The size of the memory pool in words. The pool should be large enough to store all the numbers that you want simultaneously be in use, plus enough space to hold the library's own administration data. The macro BC_NANU_POOL() can be used to calculate the space needed for the administration. The library has a limited memory handling capability, it can deal with at most 65535 words (i.e. 256KB). Naturally, you are not to touch the memory pool while the natual numbers library is using it.
	item	How deep you want your stack to be. The minimum is 2, the maximum is 127.

Returns:: A BC_NANU object, which is an opaque pointer to the natural number state. You will have to pass this object to every natural number function you call. If you specified a memory area that is not large enough to even hold the private administrative data of the library or if you specified a stack depth outside the allowed bounds, then NULL is returned.

int BC_NanuMadd ( BC_NANU nanu )

Modular addition.

Adds the second and third elements of the stack together and calculates the remainder after dividing the sum with the topmost element.

Parameters:

nanu

The natural number machine state descriptor

Return values:

	BC_NANU_NANU	The operation succeeded
	BC_NANU_SUND	There were less that 3 elements on the stack
	BC_NANU_NANN	The topmost element was 0
	BC_NANU_OMEM	There's not enough memory in the pool to store the result.

Stack image: m a b ... ==> (a+b)%m ...

int BC_NanuMexp ( BC_NANU nanu )

Modular exponentiation.

Raises the third element on the stack to the power of the second element of the stack and calculates the remainder of dividing the result with the topmost element. All three elements are discarded and the remainder is pushed onto the stack.

Parameters:

nanu

The natural number machine state descriptor

Return values:

	BC_NANU_NANU	The operation succeeded
	BC_NANU_SUND	The stack didn't have at least two items on it
	BC_NANU_SOVR	Stack overflow occured during calculations
	BC_NANU_OMEM	Out of memory pool space
	BC_NANU_NANN	The modulus was less than 2

Stack image: m e a ... ==> a^e%m ...

int BC_NanuMmul ( BC_NANU nanu )

Modular multiplication.

Multiplies the second and third elements of the stack, then divides the result with the topmost element. All three are discarded and the remainder of the division is pushed onto the stack.

Parameters:

nanu

The natural number machine state descriptor

Return values:

	BC_NANU_NANU	The operation succeeded
	BC_NANU_SUND	The stack didn't have at least 3 items on it
	BC_NANU_SOVR	Stack overflow occured during calculations
	BC_NANU_OMEM	Could not allocate temporaries
	BC_NANU_NANN	The modulus was 0

Stack image: m b a ... ==> (a*b)%m ...

int BC_NanuMsub ( BC_NANU nanu )

Modular subtraction.

Subtract the second elemen from the third and calculate the remainder of dividing the result with the topmost element. Note that if the subtraction result would be negative, then the modulus is added to it until it becomes positive. Therefore, while it is an error to subtract a number from a smaller one (since the result is not a natural number), it is allowed for modular subtraction. the modular subtraction of 'b' from 'a' modulo 'm' returns a number, 'y', which is smaller than the modulus, so that the following equation is true:

a mod m = ( b + y ) mod m

Parameters:

nanu

The natural number machine state descriptor

Return values:

	BC_NANU_NANU	The operation succeeded
	BC_NANU_SUND	There were less that 3 elements on the stack
	BC_NANU_NANN	The modulus was 0
	BC_NANU_OMEM	There's not enough memory in the pool to store the result.

Stack image: m b a ... ==> (a-b)%m ...

int BC_NanuOver ( BC_NANU nanu )

Pushes a copy of the second item onto the stack.

Parameters:

nanu

The natural number machine state descriptor

Return values:

	BC_NANU_NANU	The operation succeeded
	BC_NANU_SUND	The stack didn't have at least two items on it
	BC_NANU_SOVR	The stack was full

Stack image: a b ... ==> b a b ...

int BC_NanuPick	(	BC_NANU	nanu,
		unsigned	item
	)

Pushes a copy of the n-th item of the stack onto the stack.

The top of the stack is the 0-th item, the one pushed before that is the 1st item and so on. This function gets the n-th item and pushes a copy of it to the stack. Thus, calling the function with a parameter 0 is equivalent to BC_NanuDupl(), calling it with 1 is the same as BC_NanuOver().

Parameters:

	nanu	The natural number machine state descriptor
	item	The index of the item to pick

Return values:

	BC_NANU_NANU	The operation succeeded
	BC_NANU_SUND	The stack didn't have at least n+1 elements
	BC_NANU_SOVR	The stack was full

Stack image: x0 x1 ... xn ... ==> xn x0 x1 ... xn ...

int BC_NanuPull	(	BC_NANU	nanu,
		void *	buff,
		int	size
	)

Stores the top of the stack at a given location.

If the size parameter is negative, then the buffer size is taken as the absolute value of the parameter and the result will be stored in little-endian order. Otherwise, the result is stored in big-endian order. The stored item is removed from the stack. If the buffer given is larger than the required size, then it is zero-padded so that the entire buffer, interpreted in the given endianness, represents the actual result. The function returns the number of significant bytes of the result, that is, the padding zeroes are not counted. Note, that if the number to store is 0 it counts as one significant byte, thus the function never returns 0.

For example, if the number on top of the stack is 0x1234 then:

    BC_NANU nanu;
    char buff[ 5 ];

    Call                                Buffer
    BC_NanuPull( nanu, buff, +5 )       00 00 00 12 34
    BC_NanuPull( nanu, buff, -5 )       34 12 00 00 00

Parameters:

	nanu	The natural number machine state descriptor
	buff	Pointer to the buffer
	size	The size of the buffer

Return values:

	>0	The number of significant bytes in the result.
	BC_NANU_SUND	The stack was empty
	BC_NANU_SIZE	The size was less than needed to store the number

Stack image: a ... ==> ...

int BC_NanuPush	(	BC_NANU	nanu,
		const void *	buff,
		int	size
	)

Pushes a new item onto the stack.

Creates a new number on the top of the stack. The value of the new number will be that of the number represented by the series of bytes at the location identified by the data argument. The number of bytes that represent the number is given in the size argument. If size is a positive number, then the bytes will be interpreted in a big-endian order, if it is negative, then the length of the number is taken as the absolute value of size and the bytes will be processes in little-endian order.
The size of the number can not be 0.

Parameters:

	nanu	The natural number machine state descriptor
	buff	Pointer to the byte stream of the data
	size	The number of bytes in the data

Return values:

	BC_NANU_NANU	The operation succeeded
	BC_NANU_SOVR	The stack was full
	BC_NANU_SIZE	The size parameter is invalid
	BC_NANU_OMEM	There's not enough memory in the pool to store the number.

Stack image: ... ==> new_number ...

int BC_NanuRadd ( BC_NANU nanu )

Regular addition.

Removes the topmost and second elements from the stack and pushes back the sum of the two elements.

Parameters:

nanu

The natural number machine state descriptor

Return values:

	BC_NANU_NANU	The operation succeeded
	BC_NANU_SUND	There was less that 2 elements on the stack
	BC_NANU_OMEM	There's not enough memory in the pool to store the result.

Stack image: a b ... ==> a+b ...

int BC_NanuRexp ( BC_NANU nanu )

Regular exponentiation.

Raises the second element on the stack to the power of the topmost element, then discards both and pushes the result onto the stack.

Parameters:

nanu

The natural number machine state descriptor

Return values:

	BC_NANU_NANU	The operation succeeded
	BC_NANU_SUND	The stack didn't have at least two items on it
	BC_NANU_SOVR	Stack overflow occured during calculations
	BC_NANU_OMEM	Out of memory pool space

Stack image: e a ... ==> a^e ...

int BC_NanuRmod ( BC_NANU nanu )

Regular modulus.

Divides the second element of the stack with the topmost one, discards both elements and pushes the remainder onto the stack; the quotient is discarded.

Parameters:

nanu

The natural number machine state descriptor

Return values:

	BC_NANU_NANU	The operation succeeded
	BC_NANU_SUND	The stack didn't have at least two items on it
	BC_NANU_SOVR	The stack was full
	BC_NANU_OMEM	Could not allocate
	BC_NANU_NANN	The divisor was 0

Stack image: m a ... ==> a%m ...

int BC_NanuRmul ( BC_NANU nanu )

Regular multiplication.

Multiplies the the topmost two elements of the stack, discards both and pushes the multiplication result onto the stack.

Parameters:

nanu

The natural number machine state descriptor

Return values:

	BC_NANU_NANU	The operation succeeded
	BC_NANU_SUND	There was less that 2 elements on the stack
	BC_NANU_OMEM	There's not enough memory in the pool to store the result.

Stack image: a b ... ==> a*b ...

int BC_NanuRoll	(	BC_NANU	nanu,
		int	n
	)

Rolls a given number of elements on the stack.

Rotates the topmost n-1 elements of the stack. The signum of n determines the direction of the rotation. If the number if positive, then all elements from the top to the n-1 -th element will be pushed down so that the top of the stack moves from position 0 to position 1, the element under it from position 1 to 2 and so on, element n-1 moving to the n-th slot of the stack. The n-th element is moving up to the 0-th position, vacated by the topmost element. For a negative number the rotation is in the opposite direction, the n-th element (where n is the absolute value of the argument) will move up to the n-1 -th slot and so on, the 1st element moving to the top while the former top element will move to the n-th slot.

Rolling 0 elements is a no-op and rolling 1 or -1 elements is the same as BC_NanuSwap().

Parameters:

	nanu	The natural number machine state descriptor
	n	The index of the deepest element to roll

Return values:

	BC_NANU_NANU	The operation succeeded
	BC_NANU_SUND	The stack does not have enough elements

Stack image: In the image below k=|n|
x₀ x₁ x₂ ... x_k-1 x_k ... ==> x_k x₀ x₁ x₂ ... x_k-1 ... (n > 0)
x₀ x₁ x₂ ... x_k-1 x_k ... ==> x₁ x₂ ... x_k-1 x_k x₀ ... (n < 0)

int BC_NanuRsub ( BC_NANU nanu )

Regular subtraction.

Subtract the topmost element from the element under it, discards both and pushes the result onto the stack. Note that negative numbers are not natural numbers, therefore if you want to subtract a number from a smaller one, you will get an arror.

Parameters:

nanu

The natural number machine state descriptor

Return values:

	BC_NANU_NANU	The operation succeeded
	BC_NANU_SUND	There was less that 2 elements on the stack
	BC_NANU_NANN	The result of the subtraction is not a natural number (i.e. it is negative)
	BC_NANU_OMEM	There's not enough memory in the pool to store the result.

Stack image: b a ... ==> a-b ...

int BC_NanuShft	(	BC_NANU	nanu,
		int	shift
	)

Shifting of a number.

The function shifts the number on the top of the stack to the left by the number of bits specified in the shift argument. If the argument is negative, then the number is shifted to the right by the absolute value of shift number of bits. Thus, this operation is equivalent to
TOS <- TOS * 2^shift
where TOS is the top of the stack.

Parameters:

	nanu	The natural number machine state descriptor
	shift	The number of left shifts (in bits), if negative then shifting will be towards the right.

Return values:

	BC_NANU_NANU	Success
	BC_NANU_SUND	The stack was empty
	BC_NANU_OMEM	Out of memory
	BC_NANU_ITEM	Out of descriptors

Stack image: x ... ==> x*2^shift ...

int BC_NanuSize ( BC_NANU nanu )

Returns the length of the topmost element of the stack.

The function returns the length of the topmost element of the stack, in bits. That is, it returned value is the smallest non-negative integer such that
2^return_value > number_on_top_of_the_stack
The stack is not changed.

Parameters:

nanu

The natural number machine state descriptor

Return values:

	>=0	The length of the topmost element
	BC_NANU_SUND	The stack was empty

Stack image: x ... ==> x ...

int BC_NanuSwap ( BC_NANU nanu )

Exchanges the top two items on the stack.

Parameters:

nanu

The natural number machine state descriptor

Return values:

	BC_NANU_NANU	The operation succeeded
	BC_NANU_SUND	The stack didn't have at least two items on it

Stack image: a b ... ==> b a ...

int BC_NanuTail ( BC_NANU nanu )

Number of trailing 0 bits of a number.

Returns the number of trailing zero bits of the number on the top of the stack. For example, if the number on the top of the stack is 11552, which is binary 10110100100000, the function will return 5. If the number on the top of the stack is 0, then the function returns the largest positive signed int, i.e. 0x7fffffff (MAX_INT).

Parameters:

nanu

The natural number machine state descriptor

Return values:

	BC_NANU_SUND	The stack was empty
	0x7fffffff	The number on the top of the stack is 0
	>=0	The number of trailing 0 bits in the number

Stack image: a ... ==> a ...

int BC_NanuTuck ( BC_NANU nanu )

Pushes a copy of the top item to under the second item on the stack.

Parameters:

nanu

The natural number machine state descriptor

Return values:

	BC_NANU_NANU	The operation succeeded
	BC_NANU_SUND	The stack didn't have at least two items on it
	BC_NANU_SOVR	The stack was full

Stack image: a b ... ==> a b a ...

Natural numbers module [Cryptographic functions]

Data Structures

Defines

Enumerations

Functions

Detailed Description

Define Documentation

Enumeration Type Documentation

Function Documentation

Natural numbers module
[Cryptographic functions]