Computational Number Theory and Asymmetric Cryptography

• ECTS credits10
• Teaching semesterAutumn
• Course codeINF245
• Number of semesters1
• LanguageEnglish
• Resources

10

Autumn.

Objectives and Content

Objectives
Asymmetric crypto-systems as public key ciphers, digital signatures, authentication protocols are deployed and used worldwide in security protocols in retail trade, banking, payments over the Internet, access control, and generally in any kind of digital communication and constitute a security basis for the modern society. The systems are called asymmetric as, roughly speaking, only one of the parties in communication possesses a secret key.

Many of asymmetric crypto systems are based on one of the following hard computational problems: solving non-linear equation systems over finite fields, computing discrete logarithms in finite fields and on elliptic curves, integer factorisation and various computational problems from lattices as finding a shortest non-zero vector in a large dimension lattice. Those problems are within Algebra and Number Theory. Solving the hard problem breaks a relevant crypto-system and undermines the security of the applications.

The course gives introduction to Computational methods in Algebra and Number Theory with focus on known approaches to solve the above problems and analysis of relevant asymmetric crypto-systems.

Some of them (as HFE) are broken, some (RSA, DSA) are widely used and some (as NTRU) have potential to be deployed in the future if quantum computers come in use and conventional crypto-systems as RSA, DSA get broken.

Content
The course incorporates four chapters.

• solving systems of linear and non-linear equations over finite fields, analysis of HFE (Hidden Field Equation) crypto-system.
• basic methods for computing discrete logarithms and factoring integers, analysis of RSA (Rivest-Shamir-Adleman) crypto-system and DSA(Digital Signature Algorithm).
• arithmetic and algorithms in elliptic curves.
• lattice reduction algorithms, analysis of NTRU crypto-system.

Learning Outcomes

Knowledge

On completion of the course the student should have the following learning outcomes defined in terms of knowledge, skills and general competence.

The student should have knowledge of

• computational methods in Algebra and Number Theory,
• mathematical foundations for security of modern cryptography,
• asymmetric crypto-systems based on hard computational problems from Algebra and Number Theory,
• analysis and applications of asymmetric crypto-systems.

Skills

The student is able to

• solve common computational problems in Algebra and Number Theory,
• explain main cryptography applications of asymmetric crypto-systems,
• digest and explain how asymmetric crypto-systems work,
• locate issues in security protocols relevant to asymmetric cryptography.

General competence

The student

• is familiar with new ideas and innovation processes,
• can exchange opinions with others with relevant background and participate in discussions concerning the development of good practice.

Required Previous Knowledge

At least 60 ECTS in Computer Science and at least 10 ECTS in mathematics

Recommended Previous Knowledge

INF100 similar courses are recommended, In addition: INF240, MAT121, STAT110 ,INF140, INF142, INF143

Compulsory Assignments and Attendance

Assignments. Compulsory assignments are valid for one subsequent semester.

Forms of Assessment

The forms of assessment are:

Written examination or Digital written examination (3 hours). Mandatory assignments may be graded and included in the final grade.

Due to the measures taken to avoid the spread of Covid-19, UiB is closed for on-campus assessment. As a consequence, the following changes is made to assessment autumn semester 2020:

• Written home examination instead of written examination

Examination Support Material

Non-programmable calculator, according to the faculty regulations.

Assessment Semester

Examination both spring semester and autumn semester. In semesters without teaching the examination will be arranged at the beginning of the semester.

The reading list will be available within June 1st for the autumn semester and December 1st for the spring semester.

Course Evaluation

The course will be evaluated by the students in accordance with the quality assurance system at UiB and the department.

Programme Committee

The Programme Committee is responsible for the content, structure and quality of the study programme and courses.

Course Coordinator

Course coordinator and administrative contact person can be found on Mitt UiB, or contakt studieveileder@ii.uib.no

The Faculty of Mathematics and Natural Sciences represented by the Department of Informatics is the course administrator for the course and study programme.

Contact

Studieveileder@ii.uib.no

Telephone: 55 58 42 00

Exam information

• For written exams, please note that the start time may change from 09:00 to 15:00 or vice versa until 14 days prior to the exam.

• Type of assessment: Written examination

Date
16.02.2021, 09:00
Duration
8 hours