Programme in Information Theory,

Coding and Cryptography (ITCC)

Programmes .

Email:

Check it out at:

Coding and Cryptography (ITCC)

programme. Of these fourteen have continued in academia and are

lecturers, six are pursuing PhD studies, two are employed as

engineers. Eight more students are due to graduate in November

2010. At present there are ten students on the programme.

to PhD Studies in Coding Theory:

**Dr Khumbo Kumwenda graduated in 2011 with a PhD in Coding****Theory****from the University of the Western Cape in South Africa****Dr Ezekiel Kachisa graduated with a PhD from Dublin City****University in****Ireland in 2011****Michael Zimba is doing his PhD at the College of****Computer and****Communication, Hunan University, China****.****M****rs Mwai Nyirenda-Kayuni is pursuing PhD studies in****Cryptography in****the UK.****Mr Dalison Nyirenda is pursuing PhD studies in South Africa.**

Italy) spent two months during 2013 on MZUNI campus giving input to

the programme.

2) Since the programme began in 2004 no less than eight international

experts have come to Mzuzu and given courses in Coding Theory.

Their stay at Mzuzu varied from three months to thirteen months.

3) Prof Eric Mwambene, University of the Western Cape, is acting as an

advisor to the programme.

4) Prof Ed Schaefer, Santa Clara University, USA, acts as an advisor to

the programme.

as Coding Theory, is a very young branch of mathematics having its origins in the

celebrated 1948 Shannon paper. It is a live and exciting area of research today. The

great advances in all types of electronic communication over the past few years are, in

part, due to the continuing developments in Coding Theory. Coding Theory is right at the

cutting edge of technology. The whole subject is fast becoming an integral part of

mathematics in many universities today as it is now included, as an introductory course,

in even undergraduate mathematics courses.

However, as in many other areas, Africa seems to be lagging behind. In the 2,169 pages

of the Two Volume 1998 Handbook of Coding Theory there is no contribution from

Africa. Mzuzu University hopes to change this scenario and make a significant

contribution to Coding Theory

reasons why information would need to be coded.

**One reason is to hide it, or make it inaccessible for unauthorised users. Such****codes are the subject of Cryptology.****Some cryptographic codes (public key)****form****the basis of security of passwords and PIN numbers, which have****become****very****common in E-commerce.****Another reason would be to compress the information in order to reduce the****amount****of space needed to store it.****An example of such codes would be the 'zip'****codes used****to compress files on computer hard-disks. This****compressing is also****considered****essential for the effective transmission of video signals. All this****comes under the****heading of Data Compression.****A third reason is to increase safety and accuracy in the storage or transfer of****information. Electronic equipment****used to store, transfer and manipulate data is****prone to errors of various kinds. Such an error will for example cause****the****character****‘1’ to become ‘0’ while being transferred from one place to another,****consequently****causing the****information to be misinterpreted. Remember, in digital****transmission all****data is stored as a series of ‘1s’ and ‘0s’. It is****therefore desirable****to have some way****of detecting --and if possible, correcting-- such errors. That is****what Error****Correcting****Codes are about.**

practical problems. In former times Pure Mathematics was considered more of an ‘Arts

subject’ rather than a ‘Science subject’ because it was considered abstract (pure) and

not practical. In some quarters a ‘practical application’ was even considered as a

‘tainting or diluting’ of the Art of Pure (Abstract) Mathematics. It was as if ‘Art’ had

nothing to do with ‘practical things’. Coding Theory has blown this myth. Coding Theory is

now recognised as an extraordinary beautiful practical application of Pure

Mathematics. It is the ‘perfect marriage’ of Abstract Theory and the Practical.

what is possible and what is not possible. Part of Shannon’s genius was to prove in 1948

that efficient codes existed long before such codes were discovered. It is in fact only in

the last couple of years that codes were found to meet the bounds given by Shannon.

reliable, and secure systems for information transmission and storage. Applications

include mobile telephony, high density computer and optical disks, digital audio, DVD,

financial and internet services, video-conferencing, digital television, miniaturization in

electronic devices, ATM cards and other smart cards. Graduates from this course will

be equipped with the theoretical knowledge, which will enable them to become involved

at the highest levels of research and development in these areas. They will also be able

to work in a range of careers within the engineering and computing sectors.

Classification) which contains a high level content of mathematics.

and Semester 10 in the first year and Semester 11 and Semester 12 in the second

year). Semester 9 will be devoted to a Bridging Course which will be offered to all

students. However those students who have covered comprehensively both Abstract

Algebra and Number Theory and have good grades in their first degree in these areas

may be exempted from this Bridging Course. Semesters 10 and 11 will be devoted to

four taught modules (two modules per semester). Semester 12 will be devoted to

project work. Examination of the taught modules will take place at the end of each

semester on the completion of the module. The project will be submitted by the end of

year two. If necessary a student may apply to the Coordinator of the Programme for an

extension of the date for the submission of the thesis. This extension will normally be

three months.

(28h lectures + 14h tutorials each module)

MSC5900 Computer Programming:

MSC5091 Abstract Algebra:

Basic Algebra of Polynomials and Binomial Expansion, Sets, Vectors and Matrices ,

Permutations and Symmetric Groups, Groups: Lagrange's Theorem, Euler's Theorem,

Rings, Cyclotomic Polynomials, Primitive roots, Group Homomorphisms, Cyclic

Groups, Cauchy’s Theorem, Quotient Groups and the Isomorphism Theorems, Sylow’s

Theorems, Product Groups and Direct Sum Groups, Linear Congruences, Systems of

Linear Congruences, Ideals in Rings, Principal, Euclidean and Maximal Ideals , Finite

Fields, Vector Spaces, Linear independence, Bases for Vector Spaces, Subspaces,

Vector Space Isomorphisms and Homomorphisms. Manipulating some of the above

with Magma Programming.

MSC5092 Number Theory:

Induction and the Well-Ordering Principle, Some Counting Principles, Permutations and

Combinations, The Integers, Divisibility, Bezout’s identity, Linear Diophantine Equations,

Unique Factorization into Primes, Distribution of the Primes, Algorithm for

Exponentiation, The Group of Units, Primitive Roots, Exponents, Linear Congruences,

Systems of Linear Congruences, Abstract Sun Ze Theorem and the Chinese Remainder

Theorem, Fermat's Theorem, Primality Tests, Public-Key Ciphers, Implementing some

of the above with C++ Programming.

MSC5103 Error Correcting Codes I

Communicarions Chanels, Error Detection and Correction, Maximum Liklihood Decoding,

Hamming Distance, Nearest Neighbour/Minimum Distance Decoding, Linear Codes,

Distance of a Linear Code, Hamming Weight, Generator Matrix and Parity Check Matrix,

Equivalence of Linear Codes, Encoding with a Linear Code, Decoding of Linear Codes,

Coset Decoding, Nearest Neighbourhood Decoding, Syndrome Decoding, Bounds in

Coding Theory, Lower bounds, Sphere covering bound, Gilbert-Vashamov bound,

Hamming bound and perfect codes, Binary Hamming codes, q-ary Hamming codes,

Golay codes, Singleton bound and MDS codes, Plotkin bound, Greismer bound The Main

Coding Theory Problem, Creating and Manipulating some of the above with Magma

Programming.

MSC5104 Cryptography I

Introduction, vocabulary, terms, history, Number theory review, simple cryptosystems,

modern stream ciphers, finite fields 1, RC4, self-synchronizing stream cipher, one-time

pads, finite fields II, Introduction to Advanced Encryption Standard (AES), Simplied AES,

the real AES, Modes of operation for a block cipher, analysis of simplied AES - (design

rationale, security, efficiency), attacks on block ciphers, repeated squares algorithm,

Running time of algorithms. Public Key cryptography: RSA, use of the Chinese remainder

theorem to speed up RSA decryption, finite field discrete logarithm problem, Diffie-

Hellman key agreement, Lesser used public key cryptosystems - (RSA for message

exchange, ElGamal message exchange, Massey-Omura message exchange), elliptic

curves, elliptic curve discrete logarithm problem, elliptic curve cryptosystems.

MSC6115 Error Correcting Codes II

Non linear codes, Construction of Linear Codes, Propagation Rules, Reed Muller Codes,

Subfield codes, MacWilliams identities, Polynomial Podes, BCH codes, Cyclic Codes,

Quadratic Residue Codes, Generalized Reed Solomon Codes, Alternant Codes, Goppa

Codes, Irreducible Goppa Codes, Goppa Codes defined by a single Field Element,

Equivalence of Goppa Codes, LDPC codes, Convolutional Codes, Automorphism Group of

a Code, Codes used in Public-Key Cryptography.

MSC6116 Goppa Codes

Goppa Codes, Irreducible Goppa Codes, Goppa Codes defined by a single field element,

Affine Sets, Orbits under the Frobenius Automorphism, Equivalence of Goppa Codes,

Upper Bound on the number of Goppa codes, Quasicyclic Goppa codes, Goppa codes in

Cryptography, Use of Magma in Coding Theory.

MSC6117 Cryptography II

Hash functions (MD5) and message authentication codes (MACs), the MD5 hash

algorithm, signatures and authentication, signatures with RSA, ElGamal signature,

Variants of ElGamal signature scheme - ( Schnorr authentication and signature scheme,

Digital Signature Algorithm (DSA), Elliptic curve DSA ), Time-stamping, Kerberos, PKI,

Certificates, PGP, Internet security, Secure Sockets Layer (SSL), IPSec, Key

management, Quantum cryptography, pairing based cryptography for digital signatures,

secret sharing. Cryptanalysis Introduction, types of cryptanalysis, Vigenere cipher, the

Kasiski test, the Friedman test, cryptanaylsis of modern stream ciphers, -(b=p random

bit generator, Linear shift register keystream generator), cryptanalysis of block ciphers

- Linear and differential cryptanalysis of one-round simplified AES, attribute to Pollard,

factoring, Fermat factorization, number bases, continued fraction factoring, H.W.

Lenstra Jr.'s elliptic curve method of factoring, number fields, number field sieve,

solving for DLP in a finite field, the Pollig- Helman algorithm, index calculus algorithm.

MSC6118 Practical Cryptography

Implementation aspects of cryptography. Efficient algorithms and their implementation

in C++. A 64-bit crypto library. Implementation of efficient algorithms for Jacobi symbol,

modular exponentiation, Chinese remainder theorem, prime number generation,

modular inversion and greatest common divisor. Implementations of some classic

public key schemes (RSA,E1 Gamal, Diffie-Hellman). A C++ class for finite field

arithmetic. A C++ class for elliptic curve points. Implementation of Elliptic Curve

Cryptography. Counting points on an elliptic curve. Implementations of some algorithms

for integer factorisation and discrete logarithms. Digital Signature, X509 certificates and

SSL. DSA and ECDSA. Identity based encryption. An introduction to pairing-based

cryptography.

Notes:

**MSC5900 will follow notes left by Prof Scott****Both MSC5901 and MSC5902 follow the book ‘Introduction to Abstract Algebra’****by****Paul Garret and available online at http://www.math.umn.edu/~garrett/****MSC5103 follows the first four chapters of ‘Coding Theory, A first Course’**

**MSC5104 follow closely written notes by Prof E. Schaefer****MSC5115 follows the last five chapters of ‘Coding Theory, A first Course’**

**MSC5117 follows closely written notes by Prof E. Schaefer****MSC6118 follows notes left by Prof Michael Scott.**

current applications will form a major part of the course. The project will have to be of a

high standard, preferably containing some research, which is deemed publishable in

some reputable journal.

Semester 9.

Modules MSC 5103 and MSC 5104 will be taken during Semester 10. These two

modules will be common to all students.

However, there will be two different routes for the second year (Semesters 11 and 12) of

the MSc, namely 1) the Error Correcting Codes route and 2) the Cryptography route.

Each cohort of students, in consultation with the Dean, Coordinator of ITCC and Head of

Mathematics, will decide (depending on numbers of students and available resources,

normally a minimum of three interested students will be required for a route to be

implemented) whether the whole class will take one of the two routes or whether the

class can be divided where some would take the Error Correcting Codes route while

others would take the Cryptography route. The Error Correcting Codes route involves

modules MSC 6115 and MSC 6116 and will be taught during Semester 11 while the

Cryptography route involves MSC 6117 and MSC 6118 and will also be taught during

Semester 11. The project work of Semester 12 will correspond with the route the

student has taken.

• Distinction

• Credit

• Pass

Details of the assessment process can be found at

Steven Roman

Springer-Verlag 1992

ISBN 0-387-97812-7

ISBN 3-540-97812-7

Cryptography, Theory and Practice, by

Douglas R Stinson

CRC Press 1995

ISBN 0-8493-8521-0

Introduction to Information Theory and Data Compression, by

Darrel Hankerson, Greg A Harris and Peter D. Johnson

CRC Press 1998

ISBN 0-8493-3985-5

Introduction to Cryptography with Coding Theory, by

Wade Trappe and Lawrence C. Washington

The Theory of Error Correcting Codes, by

F J MacWilliams and N J A Sloane

Elsevier Science B.V. 1977

ISBN 0-444-85193-3

Introduction to Coding Theory, by

J H van Lint

Springer-Verlag 1992

ISBN 0-387-54894-7

ISBN 3-540-54894-7 (Berlin)

Convolutional Codes, An Algebraic Approach, by

Philippe Piret

The MIT Press 1988

ISBN 0-262-16110-9

Handbook of Coding Theory Volumes 1 and 2, by

V S Pless and W C Huffman, Editors

Elsevier 1998

ISBN 0-444-50088-X

A First Course in Coding Theory, by

Raymond Hill

Clarendon Press, Oxford, 1986

ISBN

Coding and Information Theory,

Richard W.Haming

Prentice-Hall Inc.,1986

Introduction to The Theory of Error-Correcting Codes, by

Vera Pless

John Wiley & Sons, Inc., 1982

Error-Correcting Codes and Finite Fields, by

Oliver Pretzel

Clarendon Press, 1992

ISBN 0-19-269067-1

Error Correcting Codes, a first course, by

Henk van Tilborg

Chartwell Brat, 1993

ISBN 0-86238-338-2

Elements of Algebraic Coding Theory

Lekh R. Vermani

Chapman and Hall, London, 1996

ISBN 0-412-57380-6

Coding Theory, A first Course

San Ling and Chaoping Xing

Cambridge University Press 2004

ISBN 0-521-52923-9

Algebraic Codes for Data Transmission

Richard E Blahut

Cambridge University Press 2003

ISBN 0-521-55374-1

Information Theory, Inference and Learning Algorithms

David J C MacKay

Cambridge University Press 2003

ISBN 0-521-64298-1

**In formulating this MSc course, useful discussions were held with Prof P.****Fitzpatrick****of University College****Cork (UCC) of the National University of Ireland****(NUI). The****course outline follows closely a similar MSc****course given at UCC,****which was****coordinated by Prof Fitzpatrick.****We also wish to acknowledge the immense contribution which Prof E Schaefer of****Santa Clara University,****USA, has made and is continuing to make to this****programme.****In 2009 Prof Michael Scott introduced the module Practical Cryptography which****is****helping us to make the practical application in banking institutions and****industry. We****thank him for that important contribution.**

Mzuni

Maths

Coding

C

o

d

i

n

g

T

h

e

o

r

y

o

d

i

n

g

T

h

e

o

r

y

I

n

f

o

r

m

a

t

i

o

n

T

h

e

o

r

y

n

f

o

r

m

a

t

i

o

n

T

h

e

o

r

y