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

**INTRODUCTION TO NUMBER THEORY**

**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:

a^{n-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

a^{p-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(q ^{n})**

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

a(x)=a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+...+a_{1}x+a_{0}

have
residues for polynomials just as for integers

p(x)=q(x)d(x)+r(x)

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(q^{n}) just involves summing equivalent terms in the polynomial
modulo q (XOR if q=2)

a(x)+b(x)=(a_{n-1}+b_{n-1})x^{n-1}+...+(a_{1}+b_{1})x+(a_{0}+b_{0})

**Multiplication with Polynomials in GF(qn)**

multiplication
in GF(q^{n}) 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(2^{n}) with d(x)=x^{3}+x+1 can do simply by
replacing x^{3} with x+1

eg in
GF(2^{3}) there are 8 elements:

0, 1, x, x+1, x^{2}, x^{2}+1, x^{2}+x, x^{2}+x+1

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

can adapt
GCD, Inverse, and CRT algorithms for GF(q^{n})

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

arithmetic
in GF(q^{n}) can be much faster than integer arithmetic, especially if
the irreducible polynomial is carefully chosen

eg a fast implementation of GF(2^{127}) 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

where

p.u mod q
= 1

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Cryptography and Network Security : Introduction to Number Theory |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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