Cryptography - Lecture 13 - Random Numbers, Number Theory

This lesson discusses the importance of random number in cryptography, and then provides a brief introduction to number theory, and concepts related to performing calculations in a galois field modulo a prime.

1. Random Number Generation

lots of uses for real random numbers in cryptography
- as keystream for a one-time pad
- for session keys
- for public key generation
- for nonces (random no's) in protocols to prevent replays
in all cases its critical that these values be
- unpredictable (independent)
- statistically random
hence want to base on natural random sources if possible
or at least seed a pseudorandom generator with enough unpredictable information to make guessing difficult
nb. using time & process id is not sufficient

2. Published Sources

there are a few published collections of random numbers
Rand Co in 1955 published a book of 1 million numbers
generated using an electronic roulette wheel
has been used in some cipher designs cf Khafre
earlier Tippett in 1927 published a collection
real issue is that these are limited, and too available for most uses

3. Natural Random Noise

best source is to tap natural randomness in real world
find a regular but random event and monitor
do generally need special h/w to do this
eg. radiation counters, radio noise, audio noise, thermal noise in diodes, leaky capacitors, mercury discharge tubes etc
starting to see this in new CPU's
without special h/w must use whats available
eg. time between keystrokes, mouse positions, disk latency, clock interactions etc
also have problems of bias or uneven distribution in signal
have to compensate for this when sample and use
best to only use a few noisiest bits from each sample
whatever is used must be unpredictable (ie time of day & process no is not!)

4. Distilling Randomness

start with a certain amount of random information
and then "distill" it to obscure the original sources
generally by feeding through a PRG, hash function, block cipher etc

5. An Introduction to Number Theory

will now provide an introduction to some number theory concepts
want to work with a discrete set of "numbers"
manipulate them by adding and multiplying
eg. integers: 5 + 9 = 14; 5 × 3 = 5 + 5 + 5 = 15
eg. polynomials: x²+1 + x = x²+x+1; x × x²+1 = x³+x

6. Overview

in particular need to be able to do computations:
- with integers modulo some number
- with polynomials modulo some polynomial
also need to know how to do compute
- exponentiation
- inverses
- Euler Totient Function
need these to understand public key crypto algorithms

7. Divisors

say a number b!=0 divides number a if for some m have a=mb (a,b,m all integers)
that is b divides into a with no remainder
denote this b|a
and say that b is a divisor of a
eg. all of 1,2,3,4,6,8,12,24 divide 24

8. Prime Numbers and Irreducible Polynomials

a number is prime if its only divisors are 1 and itself
that is it cannot be written as a product of other numbers
nb. 1 is prime, but is generally not of interest
eg. 2,3,5,7 are prime, 4,6,8,9,10 are not
similarly have irreducible (prime) polynomials
which cannot be written as a product of other polynomials
eg. x²+x = x × x+1 is not irreducible; x³+x+1 is irreducible

9. Prime Numbers

The list of prime number less than 200 is:

2   3   5   7   11  13  17  19  23  29  
31  37  41  43  47  53  59  61  67  71  
73  79  83  89  97  101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199

10. Prime Factorisation

to factor a number n its written as a product of other numbers, eg n=a × b × c
note that factoring a number is relatively hard
compared to multiplying the factors together to generate the number
the prime factorisation of a number n is when its written as a product of prime numbers
eg. 91 = 7 × 13 ; 3600 = 2⁴ × 3² × 5²

11. Relatively Prime Numbers

say two numbers a, b are relatively prime if they have no common divisors apart from 1
eg. 8 & 15 are relatively prime since factors of 8 are 1,2,4,8 and of 15 are 1,3,5,15 and 1 is the only common factor

12. Modulo Arithmetic

modulo arithmetic is 'clock arithmetic'
have a finite number of values (eg 0..6) and loop back from either end
use the term congruence for a = b mod n
this says when divided by n that a and b have the same remainder
eg. 100 = 34 mod 11
b is called the residue of a mod n
usually have 0<=b<=n-1
eg. -12mod7 = -5mod7 = 2mod7 = 9mod7
can do arithmetic with integers modulo n with all results between 0 and n

13. Modulo Arithmetic Example

eg. when working modulo 7 have the following:

...
-21 -20 -19 -18 -17 -16 -15
-14 -13 -12 -11 -10  -9  -8
 -7  -6  -5  -4  -3  -2  -1
  0   1   2   3   4   5   6
  7   8   9  10  11  12  13
 14  15  16  17  18  19  20
 21  22  23  24  25  26  27
 28  29  30  31  32  33  34
...

all numbers in a column are equivalent (have same remainder), vis:

-12 = -2 x 7 + 2
 -5 = -1 x 7 + 2
  2 =  0 x 7 + 2
  9 =  1 x 7 + 2 etc

14. Modulo Arithmetic Operations

addition

a+b mod n

subtraction

a-b mod n = a+(-b) mod n

ie addition with the additive inverse

multiplication

a.b mod n

derived from repeated addition
can get a.b=0 where neither a,b=0
eg 2.5 mod 10

division

a/b mod n

is multiplication by multiplicative inverse of b: a/b = a.b^-1 mod n
if n is prime b^-1 mod n exists s.t b.b^-1 = 1 mod n
eg 2.3=1 mod 5 hence 4/2=4.3=2 mod 5

15. Modulo Reductions

perform modulo reduction by finding remainder after dividing by the modulus
ie to find r = a mod n compute a = d.n + r
eg. 33 mod 7 = 4.7 + 5; ie answer is 5
note that r is usually assumed to be positive
hence for negative numbers "overshoot and come back"
eg. -18 mod 7 = -3.7 + 3; ie answer is 3
all congruences are equivalent, answer will remain the same
hence can chose whether to do an operation and then reduce modulo n
or reduce then do the operation
a+/-b mod n = [a mod n +/- b mod n] mod n
mathematically "reduction is a homomorphism from the ring of integers to the ring of integers modulo n"

16. Modulo Reduction Example

eg. -11+3=-8; -4+3=-1; 3+3=6; 10+3=13 all the same answer (6) mod 7.

can either reduce then compute, or compute then reduce:

compute -11 + 3 = -8, reduce to 6       <- same answer
-11 reduce to 3, compute 3 + 3 = 6      <- same answer

17. Laws of Arithmetic

modulo arithmetic works like normal arithmetic
integers modulo n with addition and multiplication form a commutative ring
with mathematic laws:

Associativity
(a+b)+c = a+(b+c) mod n
Commutativity
a+b = b+a mod n
Distributivity
(a+b).c = (a.c)+(b.c) mod n
Identity
0+w = w mod n
1×w = w mod n
the above laws also hold for multiplication

18. Groups, Rings, Fields

these are terms which define how sets of numbers compute
a group is:
- a set of numbers
- with some addition operation whose result is also in the set (closure)
- obeys associative law, has an identity, has inverses
- if also is commutative its an abelian group
a ring is:
- an abelian group with a multiplication operation also
- multiplication is associative and distributive over addition
- if multiplication is commutative, its a commutative ring
- eg. integers mod N for any N
a field is:
- an abelian group for addition
- a ring
- an abelian group for multiplication (ignoring 0)
- eg. integers mod P where P is prime

19. Galois Fields

if n is constrained to be a prime number p
then we say arithmetic modulo p forms a Galois Field modulo p
denoted GF(p)
and all the normal laws associated with integer arithmetic work

20. Exponentiation in GF(p)

many encryption algorithms use exponentiation
raising a number a (base) to some power e (exponent) mod p
b = a^e mod p
exponentiation is basically repeated multiplication
eg. 7⁵ = 7.7.7.7.7
which takes O(n) multiples for a number n
a better method is the square and multiply algorithm

21. Square and Multiply Algorithm

a fast, efficient algorithm for doing exponentiation
idea is to repeatedly square the base
and multiply in the ones that are needed to compute the result
find this by looking at binary representation of exponent
only takes O(log₂ n) multiples for a number n

eg.

7⁵ = 7⁴.7 = 3.7 = 10 mod 11;
3¹²⁹ mod 11 = 4

  let base = a, result =1
  for each bit e_i (LSB to MSB) of exponent   
     if e_i=0 then
        square base mod p
     if e_i=1 then
        multiply result by base mod p
        square base mod p (except for MSB)
  at end the required answer is result

22. Square and Multiply Example

7⁵ = 7⁴.7 = 3.7 = 10 mod 11

base            res             exp (5=101₂)
7               1               initialise
7.7=49=5        1.7=7           1 (so result=result x base, square base)
5.5=25=3        7               0 (square base)
3.3=9           7.3=21=10       1 (result=result x base, square base)

23. Summary

Random number generation
modulo arithmetic with integers
how to compute exponentiation using "square & multiply"

24. Exercises

Compute the following exponentiations using the "square and multiply" algorithm, including details of modulo reductions as needed:
```
3³³ mod 17
5⁶ mod 13
5³⁵ mod 17
7⁶ mod 19
7¹¹ mod 17
7¹⁹ mod 23
```

[Back to CCS3 Lectures]

Lawrie.Brown@adfa.edu.au / 7 Febn 2001