Home | | Cryptography and Network Security | Introduction to Number Theory

Chapter: Cryptography and Network Security

Introduction to Number Theory

1 Primality Testing and RSA 2 Euler Totient Function [[phi]](n) 3 Computing with Polynomials in GF(qn)



1 Primality Testing and RSA


The first stage of key-generation for RSA involves finding two large primes p, q


Because of the size of numbers used, must find primes by trial and error


Modern primality tests utilize properties of primes eg:


an-1 = 1 mod n where GCD(a,n)=1


all primes numbers 'n' will satisfy this equation


some composite numbers will also satisfy the equation, and are called pseudo-primes.


Most modern tests guess at a prime number 'n', then take a large number (eg 100) of numbers 'a', and apply this test to each. If it fails the number is composite, otherwise it is is probably prime.


There are a number of stronger tests which will accept fewer composites as prime than the above test. eg:


RSA Implementation in Practice


Software implementations


generally perform at 1-10 bits/second on block sizes of 256-512 bits


two main types of implementations:

- on micros as part of a key exchange mechanism in a hybrid scheme


- on larger machines as components of a secure mail system


Harware Implementations


generally perform 100-10000 bits/sec on blocks sizes of 256-512 bits


all known implementations are large bit length conventional ALU units


2 Euler Totient Function [[phi]](n)


if consider arithmetic modulo n, then a reduced set of residues is a subset of the complete set of residues modulo n which are relatively prime to n

eg for n=10,


the complete set of residues is {0,1,2,3,4,5,6,7,8,9} o the reduced set of residues is {1,3,7,9}


the  number  of  elements  in  the  reduced  set  of  residues  is  called  the  Euler Totient function [[phi]](n)


there is no single formula for [[phi]](n) but for various cases count how many elements are excluded:


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)


several important results based on [[phi]](n) are:


Theorem (Euler's Generalization)


let gcd(a,n)=1 then

a[[phi]](n) mod n = 1


Fermat's Theorem


let p be a prime and gcd(a,p)=1 then


ap-1 mod p = 1


Algorithms to find Inverses a-1 mod n


search 1,...,n-1 until an a-1 is found with a.a-1 mod n


if [[phi]](n) is known, then from Euler's Generalization

a-1 = a[[phi]](n)-1 mod n


3.      otherwise use Extended Euclid's algorithm for inverse

3 Computing with Polynomials in GF(qn)


have seen arithmetic modulo a prime number GF(p)


also can do arithmetic modulo q over polynomials of degree n, which also form a Galois


Field GF(qn)


its elements are polynomials of degree (n-1) or lower




have residues for polynomials just as for integers




and this is unique if deg[r(x)]<deg[d(x)]


if r(x)=0, then d(x) divides p(x), or is a factor of p(x)


addition in GF(qn) just involves summing equivalent terms in the polynomial modulo q (XOR if q=2)



Multiplication with Polynomials in GF(qn)


multiplication in GF(qn) involves


multiplying the two polynomials together (cf longhand multiplication; here use shifts & XORs if q=2)


then finding the residue modulo a given irreducible polynomial of degree n


an irreducible polynomial d(x) is a 'prime' polynomial, it has no polynomial divisors other than itself and 1


modulo reduction of p(x) consists of finding some r(x) st: p(x)=q(x)d(x)+r(x)


nb. in GF(2n) with d(x)=x3+x+1 can do simply by replacing x3 with x+1


eg in GF(23) there are 8 elements:


0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1


with irreducible polynomial d(x)=x3+x+1* arithmetic in this field can be summarised as:


can adapt GCD, Inverse, and CRT algorithms for GF(qn)


[[phi]](p(x)) = 2n-1 since every poly except 0 is relatively prime to p(x)


arithmetic in GF(qn) can be much faster than integer arithmetic, especially if the irreducible polynomial is carefully chosen


eg a fast implementation of GF(2127) exists

has both advantages and disadvantages for cryptography, calculations are faster, as are methods for breaking


RSA and the Chinese Remainder Theorem


a significant improvement in decryption speed for RSA can be obtained by using the Chinese Remainder theorem to work modulo p and q respectively

since p,q are only half the size of R=p.q and thus the arithmetic is much faster


CRT is used in RSA by creating two equations from the decryption calculation:


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




p.u mod q = 1

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Cryptography and Network Security : Introduction to Number Theory |

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.