Skip to content
UoL CS Notes

Number Theory & Cryptography

COMP202 Lectures

Symmetric Key Cryptography

This topic has been covered before in:

One-Time Pad

This is one of the most secure ciphers known.

For this encryption scheme Alice and Bob share a random bit string K that is as long as any message that are going to send.

This key K is the symmetric key that is used for the encryption and decryption process.

Although is is very secure and fast to compute, Alice and Bob must share very long keys K which are used only once. This gives a lot of overhead.

One-Time Pad Encryption

  1. To encrypt the message M, Alice computes:

    C=MK

    is the exclusive or (XOR) operation.

  2. Alice then sends C to Bob on any reliable communication channel. The communication is secure because C is computationally indistinguishable from a random bit string.

    This relies highly on the fact that K was selected randomly.

One-Time Pad Decryption

Bob can easily decrypt the cipher-text C to recover M using the following:

CK=(MK)K=M(KK)=M0=M

where 0 represents the all-zero string with the same length as M.

Number Theory

The following methods allow us to devise a solution for public key cryptography.

Divisibility

Given integers a and b, we use the notation a|b to denote that b is a multiple of a.

If a|b then there is another integer k such that b=a×k. We note the following properties about this divisibility relationship:

Theorem: Let a,b,c be integers:

  1. If a|b and b|c then a|c (transitivity).
  2. If a|b and a|c then a|(i×b+j×c) for all integers i and j.
  3. If a|b and b|a then either a=b or a=b.

Prime Numbers and Composite Numbers

Integers that are not prime are composite.

Theorem: Let n>1 be an integer. Then there is a unique set of prime numbers p1,,pk and positive integers e1,,ek such that:

n=p1e1××pkek

The product p1e1××pkek is known as the prime decomposition of n. It is unique, up to the ordering of the primes in the factorisation.

Greatest Common Divisor

Let a and b denote positive integers. The greatest common dividor of a and b, denoted gcd(a,b), is the largest integers that divides both a and b.

If gcd(a,b)=1, then we say that a and b are relatively prime.

The definition of the GCD can be extended like so:

  • If a>0, then gcd(a,0)=gcd(0,a)=a.
  • gcd(a,b)=gcd(|a|,|b|) if a and/or b is negative.
  • gcd(0,0) is undefined as there is no largest integer that divides 0.

Theorem: If d=gcd(a,b), then there exist integers j and k such that:

d=j×a+k×b

In other words, the greatest common divisor of a and b is expressible as a linear combination of a and b:

Function Expression
gcd(56,24)=8 8=1×56+(2)×(24)
gcd(25,32)=1 1=5×25+(4)×31
gcd(45,25)=5 5=(1)×45+2×25
gcd(57,363)=3 3=57×51+(8)×363

Modulo Operator

For b>0, the modulo operator, denoted by amodb, defines the remainder of a when divided by b. That is r=amodb means that:

r=aabb

This means that r is always an integer in the set 0,1,,b1 (even when a is negative), and there is an integer q such that:

a=q×b+r

Congruences

a is congruent to b modulo n if the following is true:

amodn=bmodn

We can write this as:

ab(modn)

In other words, if ab(modn), then ab=kn for some integer k. We can see this in the following example:

168(mod2)

as 168 is a multiple of 2.

Euclid’s Algorithm

Euclid’s algorithm is a method to fine the greatest common divisor of two integers a and b. This algorithm relies on the following property:

Theorem: Suppose ab>0, then:

gcd(a,b)=gcd(b,amodb)

Euclid’s Algorithm Pseudo-Code

EuclidGCD(a, b)

Input: a and b are non-negative and not both zero.
Output: gcd(a,b)

while b != 0 do
	(a, b) = (b, a mod b)
return a

If b=0, this routine will return the value of a. This is correct under our assumption that a and b are not both zero.

Euclid’s Algorithm Example

We can display this algorithm in a table:

  1 2 3 4 5 6 7
a 412 260 152 108 44 20 4
b 260 152 108 44 20 4 0

hence gcd(412,260)=4.

Euclid’s Algorithm Time Complexity

For i>0, let ai denote the first element of the ordered pair during the ith step in the while loop. The second argument is equal to aa+1, so:

ai+2=aimodai+1

This implies that, after the first time through the loop, the sequence ai is strictly deceasing.

We can show that ai+2<12×ai. This lead the following result:

Theorem: Let a,b be two positive integers. Euclid’s algorithm computes gcd(a,b) by executing:

O(log(max(a,b)))

arithmetic operations.

Extended Euclidean Algorithm

If d=gcd(a,b), there are integers j and k such that d=j×a+k×b.

We can modify Euclid’s algorithm to fine these numbers j and k wehile we compute $\text{gcd}(a,b). This is called the extended Euclidean algorithm.

Extended Euclidean Algorithm Pseudo-Code

ExtendedEuclidGCD(a, b)

Input: Non-negative integers a and b (not both zero).
Output: d=gcd(a,b), integers j,k where d=j×a+k×b.

if b = o then
	return (a, 1, 0)
r = a mod b
q = floor(a / b)	// Let q be the integers such that a = q * b + r
(d, j, k) = ExtendedEuclidGCD(b,r)
return (d, k, j - kq)

Extended Euclidean Algorithm Example

We can represent gcd(412,260) in the following table:

  1 2 3 4 5 6 7
a 412 260 152 108 44 20 4
b 260 152 108 44 20 4 0
q=ab 1 1 1 2 2 5 *
r=amodb 152 108 44 20 4 0 *
j 12 -7 5 -2 1 0 1
k -19 12 -7 5 -2 1 0

Note that a,b,q and r are filled from left to right, while j and k are filled from right to left. This means that the final answer for j and k are in column 1.

This produces the result of:

12×412+(19)×260=4

Public-Key Cryptography

A public-key cryptosystem consists of an encryption function E and a decryption function D. For any message M, the following properties must hold:

  1. Both E and D are easy to compute for the following:

    D(E(M))=ME(D(M))=M
  2. It is computationally infeasible to derive D from E.
  3. The knowledge of the encryption method gives no information about the decryption scheme. Anybody can send a private message to the hold of the function D, but only that person knows how to decrypt it.

    For this reason E is referred to as a one-way, or trapdoor, function.

    In this kind of encryption method E is made public and D is kept private.

  4. The recipient of a message should be able to verify that it came from the sender, assuming that the sender is the only person who has a the private key.

    This is referred to as digital signatures.

RSA

RSA Encryption

The main idea of the RSA method is as follows:

  1. Let p and q denotes two large distinct prime numbers.
  2. Let n=p×q and define ϕ(n)=(p1)(q1).
  3. We can then choose two numbers e and d such that:
    1. 1<e<ϕ(n)
    2. e and ϕ(n) are relatively prime (gcd(e,ϕ(n)))
    3. ed1(modϕ(n))

      We can use the Extended Eculidean algorithm to find d, given e.

Assume that we have a message to send. We can split this message up into block of at most n characters. We can then encrypt these messages M and concatenate them back together later.

0<M<n

The plain-text M is encrypted using the public keys e and n by the following operation:

C=Memodn

RSA Decryption

Decryption of the received cipher-text C is handled by modular exponentiation:

M=Cdmodn

This is correct as for every integer 0<x<n we have:

xedx(modn)

RSA Encryption Strength

Even knowing e doesn’t allow us to figure out d, unless we know ϕ(n).

Most cryptographers believe that breaking RSA required the computation of ϕ(n), which in turn requires factoring n. Factoring has not been proven to be difficult but it can take a long time to solve.

As the ability to factor large numbers increases, we simple have to choose larger primes p and q so that n=p×q is outside of the current factoring capabilities.

RSA Time Complexity

Using fast exponentiation, the size of the operands is never more than O(logn) bits, and it takes O(logk) arithmetic operations to find xkmodn.

This leads to the following result:

Theorem: Let n be the modulus of the RSA algorithm. Then RSA encryption, decryption, signature and verification each take O(logn) arithmetic operations per block.

Digital Signatures

RSA supports digital signatures. Suppose that Bob sends a message M to Alice and that Alice wants to verify that it was Bob who sent it. Bob can create a signature using the decryption function applied to M:

S=Mdmodn

Alice verifies the digital signature using the encryption function, by checking that:

MSe(modn)

Since only Bob knows the decryption function, this will verify that it was indeed Bob who sent the message.

Any person can use the encryption function as well to reconstruct the message M, so this is not a method to secretly pass information from Bob to Alice.

Fast Exponentiation

A possible bottleneck in the RSA algorithm is computing expressions of the form:

xkmodn

The naive approach is to calculate x2modn, then use that to get x3modn and so on.

We can do much better with an algorithm based on repeated squaring. For example, if we wanted to compute x16, we could first find x2 and keep squaring to get x16

If we are performing modular exponentiation, like in RSA, after each step we can find ximodn to keep the results small (between 0 and n1).

Fast Exponentiation Pseudo-Code

FastExponentation(x, k, n)

Input: Integers x,k0, and n>0
Output: r=xkmodn

r = 1
t = x
while k != 0 do
	if k is odd then
		r = r * t mod n
	t = t^2 mod n
	k = floor(k / 2)
return r