BigNum

Week 0x5

Author

Affiliation

Prof. Calvin

Crypto

Announcements

Welcome to variously CS 276/CS 540
- This is the original “BigNum”
- Now after the theoretical “Finite”
- Lecture with exercise (instead of “pure” lab).
Action Items:
- SHA-256 due this week.

Apocryphal Quote

I cannot find it, but I believe a philosopher one jested:

I am a weapons-grade finitist. I don’t believe in numbers larger than two.

Arrays of such numbers are sufficient for computation of arbitrary precision.
We can not capture the infinite, but we may model it.

Today

Review
- Finite sets, rings
New
- Arbitrary/high precision integers
- Arithmetic operations
- Function types

Rings

As far as I know (not a mathematician) the uints and ints in C are rings
- They have addition and multiplication
They aren’t fields - zero is divisible
- Spoiler alert, but \(2^{\frac{n}{2}} \times 2^{\frac{n}{2}} \equiv 0 \pmod{2^n}\)

Rings vs Integers

Rings have some “goofy” features
- \(a, b \in\) uint\(n\)_t \(\nRightarrow a + b > a\)
- Same with multiplication.
Let’s look at an example.

Checkers

num.c

#include <stdlib.h>
#include <stdint.h>

int main(int argc, char **argv) {
    uint8_t x, y;
    x = atoi(argv[1]);
    y = atoi(argv[2]);
    return x + y;
}

atoi - alphabetical to int
From <stdlib.h> per man atoi, but might work without that.

Do some additions

$  ./a.out 100 100 ; echo $?
200
$ ./a.out 200 100 ; echo $?
44

44? From whence?

uint8_t is finite

>>> 200 + 100
300
>>> 2 ** 8
256
>>> 300 - 256
44
>>> 300 % 256
44

Operations on uint8_t values are equivalent to operations on the natural numbers modulo \(2^8\) \[ \mathbb{N}/(2^8) \]

4096 bits

Modern security recommendations are for 4096 bit cryptographic keys.
- 2048 is generally considered “okay” or “acceptable”

NAME
     ssh-keygen — OpenSSH authentication key utility

SYNOPSIS
     ssh-keygen [-q] [-a rounds] [-b bits]

Big Values

Soon, we will implement RSA
- We’ll talk about what it is then.
This week, we need a way to deal with integers that big.
We will use modular arithmetic.
- Finite uint64_t models infinite \(\mathbb{N}\)

Simple Example

Recall this example from a data application.
We had a data set for which we determined a mean height in inches.
We converted it to inches and feet.

>>> 69.3 // 12, 69.3 % 12
(5.0, 9.299999999999997)

Addition is easy

WNBA MVP and Olympic Gold Medalist A’ja Wilson is 6 ft 4 in
How much taller is that than 5 ft 9.3 in
- Can convert to non-integer inches, but…
- We already had the .299… problem

Difference

We perform “long subtraction”
It’s fun!

	ft	in.	.in
A’ja	6	4	0
Mean	5	9	3

Difference

\(0 - 3 \equiv 7 \pmod{10}\)
Tenths of inches

	ft	in.	.in
A’ja	6	4	0
Mean	5	9	3
Diff			7

Difference

But wait - 3 is more than 0
Track via a “carry”

	ft	in.	.in
A’ja	6	4	0
Mean	5	9	3
Carry	0	1	0
Diff			7

Difference

\(4 - 9 - 1 \equiv 6 \pmod{12}\)
12 in = 1 ft

	ft	in.	.in
A’ja	6	4	0
Mean	5	9	3
Carry	0	1	0
Diff		6	7

Difference

Another carry.
12 in = 1 ft

	ft	in.	.in
A’ja	6	4	0
Mean	5	9	3
Carry	1	0	0
Diff		6	7

Difference

\(6 - 5 - 1 = 0\)
Nonmodular - feet has no max.

	ft	in.	.in
A’ja	6	4	0
Mean	5	9	3
Carry	1	0	0
Diff	0	6	7

Conclusion

Iconic living legend A’ja Wilson is tall af.
We can do addition and substraction on larger values than UINT_MAX or ULONG_MAX by:
- Breaking numbers in smaller ranges
  - A tenths digit
  - A ones digit
  - A twelves digit

Exercise

Make a height adder, try man scanf

hadder.c

#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>

int main() {
        int buf[6];
        printf("Insert 2 heights as XftY.Zin, each on their own line\n");
        scanf("%dft%d.%din", &buf[0], &buf[1], &buf[2]);
        scanf("%dft%d.%din", &buf[3], &buf[4], &buf[5]);

        printf("%dft%d.%din\n", buf[0], buf[1], buf[2]);

        return 0;
}

Usefulness

We can now do arithmetic correctly
- @Python
What else can we do?
- Arbitrary (not infinite) precision.

FAQ

Can we use this to add numbers bigger than \(2^n\) using adds over at most \(n\) bits at a time?
- Sure! Change the modulos and you’re set.
  - Get it? Because the numbers form a set?
Can we do this for more than 3 fields?
- Sure! Just put the middle (both consumes and produces a carry bit) in a loop!

Today

✓ Review
- Finite sets, rings
New
- ✓ Arbitrary/high precision integers
- Arithmetic operations
- Function types

Easy Mode

Addition and subtraction are easy.
For some value of easy.
- Cut a too-big number into chunks.
- Add or subtract within chunks of the same index/offset/significance.
- Only wrinkle is a carry bit.
Identical to digit-based addition.
- uint8_ts as digits in base 256 arithmetic

Hard Mode

Some cryptographical algorithms, however, use two extremely advanced arithmetic operations:
- Multiplication, and
- Division, and
- Modulo
Fortunately this only two operations (need a combined divmod)

Example

Imagine an engineering team lead for:
- 14 MS-level Computer Scientists
  - 9-12 hrs/wk
  - 14 week contract
- 34 BS-level Computer Scientists
  - 6-9 hrs/wk
  - 15.5 week contract
How many person hours is this?

Napkin Math

I’d say
- \(14 \times 12 \times 14\)
- \(34 \times 9 \times 15.5\)
I… can’t quite do that in one fell swoop.
- \(14 \times 12\) is trivially \(12^2 + 24 = 168\)
- \(9 \times 15.5\) is trivially \(155 - 15.5 = 139.5\)

\(34 \times 139.5\)

That just isn’t easy
(140 * 34 isn’t bad, but we need a motivating example).
Express digit-wise:

	1	3	9	5
3	-	-	-	-
4	-	-	-	-

\(34 \times 139.5\)

Compute all products over single-digit factors

	1	3	9	5
3	3	9	27	15
4	4	12	36	20

These:
- Aren’t single digit
- Aren’t of the same signficance

\(34 \times 139.5\)

Include sigificance

	100	30	9	.5
30	3000	900	270	15
4	400	120	36	2

Dear Watson

	100	30	9	.5
30	3000	900	270	15
4	400	120	36	2

\[ \begin{align*} 5& \times 4 \times 10^{-1} &= 2&\\ +5& \times 3 \times 10^{0} &= 15&\\ +9& \times 4 \times 10^{0} &= 36&\\ +9& \times 3 \times 10^{1} &= 270&\\ +3& \times 4 \times 10^{1} &= 120&\\ +3& \times 3 \times 10^{2} &= 900&\\ +1& \times 4 \times 10^{2} &= 400&\\ +1& \times 3 \times 10^{3} &= 3000&\\ \end{align*} \]

Express as

\[ \begin{align*} 139.5& = &1 * 10^2 + &3 * 10^1 + &9 * 10^0& + 5 * 10^{-1}\\ 34& = &&3 * 10^1 + &4 * 10^0&\\ \end{align*} \]

Take \(x = 10\) \[ \begin{align*} 139.5& = &1 * x^2 + &3 * x + &9& + 5 * x^{-1}\\ 34& = &&3 * x + &4&\\ \end{align*} \]
That is polynomial; can work with those.

Polynomial

\[ (x^2 + 3x + 9 + 5x^{-1})(3x + 4) \]

\[ (x^2 + 3x + 9 + 5x^{-1})(3x) + (x^2 + 3x + 9 + 5x^{-1})(4) \]

\[ (3x^3 + 9x^2 + 27x + 15) + (4x^2 + 12x + 36 + 20x^{-1}) \]

\[ 3x^3 + 13x^2 + 39x + 51 + 20x^{-1} \]

Aside

I think this is covered around ~8th grade
I don’t want to assume the integrity to US public school system
- Or anything school system
- Shout out school
The point of this class isn’t middle/high school math
- That’s the point of life itself /s

Considerations

It is natural to express multiplication of e.g. 4096 bit integers as a polynomial over, say, 64 bit integers.
One teeny problem:
- Overflow.

Overflow

The point of calculating this was to get things down to single digit:

\[ 3x^3 + 13x^2 + 39x + 51 + 20x^{-1} \]

13, 39, 51, and 20 are all not compliant (debatably 20 is okay)
Essentially, 1-digit multiply may produce a 2-digit product.

Uh oh

/bin/sh

$ cat num.c
#include <stdlib.h>
#include <stdint.h>

int main(int argc, char **argv) {
    uint8_t x, y, z;
    x = atoi(argv[1]);
    y = atoi(argv[2]);
    z = x * y;
    return z;
}
$ gcc num.c ; ./a.out 30 30 ; echo $?
132
$ gcc num.c ; ./a.out 3 3 ; echo $?
9
$ python3 -c "print(30 * 30 % 2 ** 8)"
132

Size of ints

Say we have two integers of 8 bits of precision.
We multiple them together.
What is the largest number we can get, and
How many bits does it require?

python3 -c "x = 2 ** 8 - 1 ; x = x * x ; print(x.bit_length())"

Carrys for mults

When we are doing big multiplications:
- We must multiply chunks of at most half the size of our biggest integer.
- We must keep track of significance - their position in an imagined larger integer
- We must perform adds over these terms, using big addition

One Technique

I Made a pointer to a uint32_t
- uint32_t *alias;;
Set it equal to the location of some array of uint64_t
- uint32_t *alias = &array;
Copied elements of the “alias” into 64 bit values.
- uint64_t tmp = alias[5];
Multiplied, tracking significance.

Division

Remember long division?
- Align the highest digits.
  - I took the log base 2.
- Divide.
- Keep track of significance.
  - Difference between logs.
- Calculate remainder.
- Loop.
The final remainder is the mod.

Today

Review
- ✓ stdint
- ✓ Finite sets, rings
- ✓ Arbitrary/high precision integers
New
- ✓ Arithmetic operations
- Function types

A 4096 bit type

It’s not too bad to pass around 4096 bits.
- An array of 64 uint64_ts or 128 uint32_ts
Here’s an example function declaration:

bigadd

uint64_t bigadd(uint64_t *in0, uint64_t *in1, uint64_t *sum);

Usage

Before call this function, declare three arrays:

uint64_t in0[64], in1[64], sum[64];
bigadd(in0,in1,sum);

You can recycle the arrays, as needed.
- An astute student would be able to implement “in-place add”
- Sum overrights (either) operand
```
uint64_t in0[64], in1[64], sum[64];
bigadd(in0,in1,in0);
```

Usage

Remember this is banned:

uint64_t *whatever(uint64_t *in0, uint64_t *in1) {
    uint64_t sum[64];
    /* much code */
    return sum;
}

My uint64_t value returned the carry value (it was nice to keep track of)

FAQ

Isn’t there a way to return the value from the function, rather than write a value to the memory location at a provided argument.
- Yes.
- This form of coding we use here is memory-safe
- It was endorsed by the White House from 26 Feb 24 to 19 Jan 25
- Read more

FAQ

How do we deal with integers that aren’t of known length.
- Ask me after the midterm.
- Read more
- Read more

Today

✓ Review
- ✓ stdint
- ✓ Finite sets, rings
✓ New
- ✓ Arbitrary/high precision integers
- ✓ Arithmetic operations
- ✓ Function types

Stinger

/* print the big value as a string */
void seebig(uint64_t *a) {
    size_t i;
    for (i = S-1; i < S ; i--) {
        printf("%016lx ", a[i]); 
        if ((i % 8 == 0 && i)) {
            printf("\n");
        }       
    }
    printf("\n\n");
    return;
}

Other Formats

Announcements

Apocryphal Quote

Today

Rings

Rings vs Integers

Checkers

Do some additions

uint8_t is finite

4096 bits

Big Values

Simple Example

Addition is easy

Difference

Difference

Difference

Difference

Difference

Difference

Conclusion

Exercise

Usefulness

FAQ

Today

Easy Mode

Hard Mode

Example

Napkin Math

\(34 \times 139.5\)

\(34 \times 139.5\)

\(34 \times 139.5\)

Dear Watson

Express as

Polynomial

Aside

Considerations

Overflow

Uh oh

Size of ints

Carrys for mults

One Technique

Division

Today

A 4096 bit type

Usage

Usage

FAQ

FAQ

Today

Stinger