Finite

Week 0x4 ∪ 0x5

Prof. Calvin

Crypto

Announcements

  • Welcome to variously CS 276/CS 540
    • Composite multi-session lecture.
  • Action Items:
    • Broadly supports SHA, RSA, and mixed precision arithmetic, concurrent assignments with this lecture.

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.

These Slides

  • Reintroduce the technologies
    • stdint
  • New
    • Finite sets, rings
    • Arbitrary/high precision integers
    • Arithmetic operations
    • Function types

What are integers?

  • Denote integers as the mathematical symbol \(\mathbb{Z}\)
    • Something to do with the German/Deutsch
  • Not particular useful in cryptography, actually
    • We tend to want the naturals, denoted \(\mathbb{N}\)
    • Counting numbers, \(0\) and up.

In Python

  • We can write them in Python with itertools
fields.py
from itertools import count
N = count()
make_z = lambda n : n // 2 if n % 2 else -n // 2
Z = (make_z(n) for n in count(1))
# We can see elements of these infinite collections with
[next(N) for _ in range(5)], [next(Z) for _ in range(5)]
  • What do you see?
([0, 1, 2, 3, 4], [0, -1, 1, -2, 2])

Aside

  • It is moderately controversial to assert: \[ 0 \in \mathbb{N} \]
    • Enderton, Herbert B. (1977). Elements of set theory. New York: Academic Press. p. 66. ISBN 0122384407.
  • Fortunately this is a CS class.
assert(0 in count())

\(\mathbb{N}\) is akin to uint

  • The natural numbers \(\mathbb{N}\) probably look a lot like the unsigned integers.
  • There’s only one real problem.
  • We don’t have the unsigned integers in C
    • We don’t have them in Python either, but for a different reason.

The Problem

  • Python has been lying to us for years that its integer have no upper limit.
    • We say \(\nexists n : n \notin\) count()
    • Let’s just try a reasonably sized number, say googolplex \(= 10^{10^{100}}\)

Test with -c

  • We use the -c flag to Python to run a script directly at command line.
python3 -c "print('hello world')"
  • Perform multi-line calculuations using ;
    • Oh - like C. 🤔
python3 -c "from itertools import count; print(0 in count())"

Time it

  • Running on Linux
    • podman start -l ; podman exec -it -l
  • We can use time to… time things.

Pivot to bash

  • Looks nicer in /bin/bash
  • We could argue it takes .013 seconds to check
  • Or .013 seconds to find itertools on a SDD

Bigger Numbers

  • Check e.g. 1000
  • Trivial.

Test it

  • Try a few powers yourself. What do you find?

10^\(n\) real
1 00.012
2 00.012
3 00.012
4 00.013
5 00.013
6 00.027
7 00.164
8 01.498
9 16.810
  • Expect: \[ t(10^{10}) \in [140,170] \]
  • Expect for \(n \gt 9\) \[ t(10^n) \in [14,17] \times 10^{n-9} \]
  • Expect \(10^{10^{100}}\) in
    • (Googol - 9) seconds
    • 316 novemvigintilion years

C for Clear

  • C is a little more forthright about how big its numbers get.
max.c
#include <stdio.h>
#include <stdint.h>

int main() {
    uint32_t n = 0;
    while ((n + 1) > n) {
        n++;
    }
    printf("n = %u\n", n);
    return 0;
}

C fast

  • For me, this took 5.19s on uint32_t
    • Same value in Python was 1m9.32s
  • How long for uint64_t?
    • In Python?
  • How would speed up the code?
    • What assumptions did you make?
  • How many base 10 digits does the largest number we can store in 32 bytes have?

limits.h

  • C discloses the maximum values it can tolerate in <limits.h>
num.c
#include <stdio.h>
#include <limits.h>

int main() {
    printf("n = %u\n", UINT_MAX);
    return 0;
}
  • The correct answer was binary search.
    • The incorrect answer (so far) was subtraction.

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

  • 44? From whence?

uint8_t is finite

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

In practice

  • \(\exists\) INT_MAX, UINT_MAX, CHAR_MAX, etc.
    • They use C names, not stdint names
  • Sums and products less than these values are unaffected
  • Sums and products greater than these values are taken modulo said max.
  • \(\forall a, b \in\) uint\(n\)_t \(: a + b \equiv a + b \pmod {2^n}\)

Problem Statement

  • Quoth GitHub

ssh-keygen -t rsa -b 4096 -C "your_email@example.com"

  • Wait a minute.
  • What does that 4096 stand for?
    • For what does that 4096 stand?

4096 bits

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

These Slides

  • ✓ Reintroduce the technologies
    • ✓ stdint
  • New
    • ✓ Finite sets, rings
    • Arbitrary/high precision integers
    • Arithmetic operations
    • Function types

Big Values

  • Soon, we will implement RSA
    • We’ll talk about what it is then.
  • First, 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!

These Slides

  • ✓ Reintroduce the technologies
    • ✓ stdint
  • New
    • ✓ Finite sets, rings
    • ✓ 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?
  • 16

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.

These Slides

  • ✓ Reintroduce the technologies
    • ✓ stdint
  • New
    • ✓ Finite sets, rings
    • ✓ Arbitrary/high precision integers
    • ✓ 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.

These Slides

  • ✓ Reintroduce the technologies
    • ✓ stdint
  • New
    • ✓ Finite sets, rings
    • ✓ 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;
}