Modular Arithmetic

Modular arithmetic is 'clock arithmetic' a congruence a = b mod n says when divided by n that a
and b have the same remainder
100 = 34 mod 11
usually have 0<=b<=n-1
-12mod7 = -5mod7 = 2mod7 = 9mod7
b is called the residue of a mod n
can do arithmetic with integers modulo n with all results between 0 and n
Addition
a+b mod n

Subtraction

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

Multiplication

a.b mod n

derived from repeated addition

can get a.b=0 where neither a,b=0
o eg 2.5 mod 10
Division
a/b mod n

-1
is multiplication by inverse of b: a/b = a.b mod n
-1 -1
if n is prime b mod n exists s.t b.b = 1 mod n
o eg 2.3=1 mod 5 hence 4/2=4.3=2 mod 5
integers modulo n with addition and multiplication form a commutative ring with the laws
of
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

also can chose whether to do an operation and then reduce modulo n, or reduce then do the
operation, since reduction is a homomorphism from the ring of integers to the ring of integers
modulo n
o a+/-b mod n = [a mod n +/- b mod n] mod n

o (the above laws also hold for multiplication)

if n is constrained to be a prime number p then this forms a Galois Field modulo p denoted
GF(p) and all the normal laws associated with integer arithmetic work
Exponentiation in GF(p)
many encryption algorithms use exponentiation - raising a number a (base) to some power b
(exponent) mod p
e
o b = a mod p
exponentiation is basically repeated multiplication, which take s O(n) multiples for a number n
a better method is the square and multiply algorithm
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
only takes O(log2 n) multiples for a number

n see Sebbery p9 Fig2.1 + example

Discrete Logarithms in GF(p)
the inverse problem to exponentiation is that of finding the discrete logarithm of a number
modulo p
x
o find x where a = b mod p
Seberry examples p10
whilst exponentiation is relatively easy, finding discrete logarithms is generally a hard problem,
with no easy way
 in this problem, we can show that if p is prime, then there always exists an a such that there is
always a discrete logarithm for any b!=0
o successive powers of a "generate" the group mod p
such an a is called a primitive root and these are also relatively hard to find

2.1.3 Greatest Common Divisor

the greatest common divisor (a,b) of a and b is the largest number that divides evenly into both a
and b
Euclid's Algorithm is used to find the Greatest Common Divisor (GCD) of two numbers a and n,
a<n
o use fact if a and b have divisor d so does a-b, a-
2b 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

Inverses and Euclid's Extended GCD Routine

unlike normal integer arithmetic, sometimes a number in modular arithmetic has a unique
inverse
-1 -1
o a is inverse of a mod n if a.a = 1 mod n
o where a,x in {0,n-1}
o eg 3.7 = 1 mod 10
if (a,n)=1 then the inverse always exists
can extend Euclid's Algorithm to find Inverse by keeping track of gi = ui.n + vi.a

Extended Euclid's (or Binary GCD) Algorithm to find Inverse of a number a mod n (where
(a,n)=1) is:
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 - [Link] = gi-1 mod gi
ui+1 = ui-1 - [Link]
vi+1 = vi-1 - [Link]
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

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
o eg for n=10,

o 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[4]:
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
several important results based on [[phi]](n) are:

Theorem (Euler's Generalization)

o let gcd(a,n)=1 then

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

Fermat's Theorem
o let p be a prime and gcd(a,p)=1 then
p-1
o a mod p = 1
-1
Algorithms to find Inverses a mod n
-1 -1
search 1,...,n-1 until an a is found with a.a mod n
if [[phi]](n) is known, then from Euler's Generalization

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

otherwise use Extended Euclid's algorithm for inverse

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
n
Field GF(q )
its elements are polynomials of degree (n-1) or lower
n-1 n-2
o a(x)=an-1x +an-2x +...+a1x+a0

have residues for polynomials just as for integers

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

o 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)
n
addition in GF(q ) just involves summing equivalent terms in the polynomial modulo q (XOR if
q=2)
n-1
o a(x)+b(x)=(an-1+bn-1)x +...+(a1+b1)x+(a0+b0)

Multiplication with Polynomials in GF(qn)

n
multiplication in GF(q ) involves [5]
o multiplying the two polynomials together (cf longhand multiplication; here use
shifts & XORs if q=2)

o 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)
n 3 3
o nb. in GF(2 ) with d(x)=x +x+1 can do simply by replacing x with x+1
 3
eg in GF(2 ) there are 8 elements:
2 2 2 2
o 0, 1, x, x+1, x , x +1, x +x, x +x+1
3
with irreducible polynomial d(x)=x +x+1* arithmetic in this field can be summarised as:
Seberry Table 2.3 p20
n
can adapt GCD, Inverse, and CRT algorithms for GF(q )
n
o [[phi]](p(x)) = 2 -1 since every poly except 0 is relatively prime to p(x)
n
arithmetic in GF(q ) can be much faster than integer arithmetic, especially if the irreducible
polynomial is carefully chosen
127
o eg a fast implementation of GF(2 ) exists
has both advantages and disadvantages for cryptography, calculations are faster, as are methods for
breaking

Public-Key Ciphers
traditional secret key cryptography uses a single key shared by both sender and receiver if this key is
disclosed communications are compromised
also does not protect sender from receiver forging a message & claiming is sent by sender, parties
are equal
public-key (or two-key) cryptography involves the use of two keys:

o a public-key, which may be known by anybody, and can be used to encrypt

messages, and verify signatures
o a private-key, known only to the recipient, used to decrypt messages, and sign
(create) signatures
 the public-key is easily computed from the private key and other information about the cipher
(a polynomial time (P-time) problem)
however, knowing the public-key and public description of the cipher, it is still computationally
infeasible to compute the private key (an NP-time problem)
thus the public-key may be distributed to anyone wishing to communicate securly with its owner
(although secure distribution of the public-key is a non-trivial problem - the key distribution
problem)
have three important classes of public-key algorithms:
Public-Key Distribution Schemes (PKDS) - where the scheme is used to securely exchange a
single piece of information (whose value depends on the two parties, but cannot be set).
o This value is normally used as a session key for a private-key scheme
Signature Schemes - used to create a digital signature only, where the private-key signs (create)
signatures, and the public-key verifies signatures
Public Key Schemes (PKS) - used for encryption, where the public-key encrypts messages, and
the private-key decrypts messages.
o Any public-key scheme can be used as a PKDS, just by selecting a message which is the
required session key
o Many public-key schemes are also signature schemes (provided encryption&
decryption can be done in either order)
RSA Public-Key Cryptosystem
best known and widely regarded as most practical public-key scheme was proposed by Rivest,
Shamir & Adleman in 1977:
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
it is a public-key scheme which may be used for encrypting messages, exchanging keys, and
creating digital signatures
is based on exponentiation in a finite (Galois) field over integers modulo a prime
3
o nb exponentiation takes O((log n) ) operations
its security relies on the difficulty of calculating factors of large numbers
log n log log n
o nb factorization takes O(e ) operations

o (same as for discrete logarithms)

the algorithm is patented in North America (although algorithms cannot be patented elsewhere in
the world)
o this is a source of legal difficulties in using the scheme
RSA is a public key encryption algorithm based on exponentiation using modular arithmetic

to use the scheme, first generate keys:

Key-Generation by each user consists of:
o selecting two large primes at random (~100 digit), p, q

o calculating the system modulus R=p.q p, q primes

o selecting at random the encryption key e,

o e < R, gcd(e, F(R)) = 1

o solving the congruence to find the decryption key d,

o e.d [[equivalence]] 1 mod [[phi]](R) 0 <= d <= R

o publishing the public encryption key: K1={e,R}

o securing the private decryption key: K2={d,p,q}

Encryption of a message M to obtain ciphertext C is:

e
C = M mod R 0 <= d <= R
Decryption of a ciphertext C to recover the message M is:

o M = Cd = Me.d = M1+n.[[phi]](R) = M mod R

the RSA system is based on the following result:
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
usually the encryption key e is a small number, which must be relatively prime to [[phi]](R) (ie
GCD(e, [[phi]](R)) = 1)
typically e may be the same for all users (provided certain precautions are taken), 3 is suggested the decryption
key d is found by solving the congruence:
e.d [[equivalence]] 1 mod [[phi]](R), 0 <= d <= R,
an extended Euclid's GCD or Binary GCD calculation is done to do this.
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
a sample RSA
encryption/decryption
calculation is: M = 26
C = 263 mod 517 = 515
M = 515307 mod 517 = 26
