Number Theory and Public Key Cryptography

Introduction to Number Theory

Modular Arithmetic

addition
a+b mod n
subtraction
a-b mod n = a+(-b) mod n
multiplication
a.b mod n
division
a/b mod n

Exponentiation in GF(p)

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

see Sebbery p9 Fig2.1 + example

Discrete Logarithms in GF(p)

Seberry examples p10

Greatest Common Divisor

GCD (a,n) is given by:
   let g0=n
       g1=a
       gi+1 = gi-1 mod gi  
   when gi=0 then (a,n) = gi-1 
eg find (56,98)
   g0=98
   g1=56
   g2 = 98 mod 56 = 42
   g3 = 56 mod 42 = 14 
   g4 = 42 mod 14 = 0 
hence (56,98)=14

see Seberry Fig 2.2 p11 GCD alg [2]

Inverses and Euclid's Extended GCD Routine

  Inverse(a,n) is given by:
    g0=n  u0=1  v0=0
    g1=a  u1=0  v1=1
  let
    y = gi-1 div gi
    gi+1 = gi-1 - y.gi = gi-1 mod gi
    ui+1 = ui-1 - y.ui 
    vi+1 = vi-1 - y.vi 
 when gi=0 then Inverse(a,n) = vi-1 
Example

eg: want to find Inverse(3,460):

 
i          y          g          u          v          
0          -          460        1          0          
1          -          3          0          1          
2          153        1          1          -153       
3          3          0          -3         460        


	hence Inverse(3,460) = -153 = 307 mod 460

see Seberry Fig 2.3 p14 Inverse alg [3]

Euler Totient Function [[phi]](n)

	p (p prime)	[[phi]](p) =p-1
	pr (p prime)	[[phi]](p) =pr-1(p-1)
	p.q (p,q prime)	[[phi]](p.q) =(p-1)(q-1)

see Seberry Table 2.1 p13

Computing with Polynomials in GF(qn)

Multiplication with Polynomials in GF(qn)

Seberry Table 2.3 p20

Complexity Theory - A Potted Intro

Complexity Theory - Some Terminolgy

Public-Key Ciphers

Digital Signatures and Signature Schemes

Diffie-Hellman Public-Key Distribution Scheme

W Diffie, M E Hellman, "New directions in Cryptography", IEEE Trans. Information Theory, IT-22, pp644-654, Nov 1976 W Diffie, M E Hellman, "Privacy and Authentication: An Introduction to Cryptography", Proc. of the IEEE, Vol 67 No 3, pp 397-427, Mar 1979

RSA Public-Key Cryptosystem

R L Rivest, A Shamir, L Adleman, "On Digital Signatures and Public Key Cryptosystems", Communications of the ACM, vol 21 no 2, pp120-126, Feb 1978 if R = pq where p, q are distinct large primes then
	X [[phi]](R) = 1 mod R
		for all x not divisible by p or q
		and [[Phi]](R) = (p-1)(q-1)

RSA Example

		e.d [[equivalence]] 1 mod [[phi]](R),	0 <= d <= R,
	given e=3, R=11*47=517, [[phi]](R)=10*46=460
	then d=Inverse(3,460) by Euclid's alg:
	  i    y    g    u    v
	  0    -  460    1    0
	  1    -    3    0    1
	  2  153    1    1 -153
	  3    3    0   -3  460
	ie:	d = -153, or 307 mod 517
	M = 26
	C = 263 mod 517 = 515
	M = 515307 mod 517 = 26

Security of RSA

operations on number R whose largest prime factor is p

Decimal Digits in R                          #Bit Operations to Factor R                  
  20                                         7200                                         
  40                                         3.11e+06                                     
  60                                         4.63e+08                                     
  80                                         3.72e+10                                     
100                                          1.97e+12                                     
120                                          7.69e+13                                     
140                                          2.35e+15                                     
160                                          5.92e+16                                     
180                                          1.26e+18                                     
200                                          2.36e+19                                     

Multi-Precision Arithmetic

Faster Modulo Reduction

* Chivers (1984) noted a fast way of performing modulo reductions whilst doing multi-precision arithmetic calcs

Given an integer A of n characters (a0, ... , an-1) of base b

then

ie: this implies that the MSD of a number can be removed and its remainder mod m added to the remaining digits will result in a number that is congruent mod m to the original.

* Chivers algorithm for reducing a number is thus:

1. Construct an array R = (bd, 2.bd, ... , (b-1).bd)(mod m)

2. FOR i = n-1 to d do

WHILE A[i] != 0 do

j = A[i];

A[i] = 0;

A = A + bi-d.R[j];

END WHILE

END FOR

where A[i] is the ith character of number A

R[j] is the jth integer residue from the array R

n is the number of symbols in A

d is the number of symbols in the modulus

Speeding up RSA - Alternate Multiplication Techniques

RSA and the Chinese Remainder Theorem

	M = Cd mod R
as follows:
	M1 = M mod p = (C mod p)d mod (p-1) 
	M2 = M mod q = (C mod q)d mod (q-1) 
then the pair of equations
	M = M1 mod p	M = M2 mod q 
has a unique solution by the CRT, given by:
	M = [((M2 +q - M1)u mod q] p + M1
where
		p.u mod q = 1 

Primality Testing and RSA

RSA Implementation in Practice

El Gamal

T. ElGamal, "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms", IEEE Trans. Information Theory, vol IT-31(4), pp469-472, July 1985.

Other Public-Key Schemes

(all of which are patented in North America)


[1] examples: 7^5 -> a=7, e={101}
[2] more examples: GCD(84,60)=12; GCD(323,238)=17; GCD(323,299)=1;
[3]more examples: Inv(299,323)=148 show trace of g=u.n+v.a
[4] show examples: eg [[phi]] of 3, 3.3, 3.5
[5] example: a=x^2+1, find a^2 mod (x^3+x+1)=x^2+x+1 showing modulo reduction process
[6] follow with examples of multiple precision arithmetic
[CSC Info]
Lawrie.Brown@adfa.oz.au / 24-Apr-96