# IA174: Fundaments of Cryptography

## Table of Contents

## Course overview & Prerequisites

In this course, we will cover fundamental topics of cryptography: typology and constructions of basic cryptographic primitives (ciphers, hash functions, MACs, digital signatures), theoretical notions of security, and topics from modern cryptography, such as post-quantum cryptography.

Prerequisites of the course are discussed on a separate page.

## Schedule

The lectures are scheduled for **Tuesdays, 16:00 in lecture room A217.**

## Recommended resources

The part on symmetric-key cryptography is to a large degree based on the Stanford course of Dan Boneh, which is accompanied by a great and freely accessible book (Boneh & Shoup). Note however, that we will not cover all topics mentioned there, as this would be time-prohibitive: we instead focus on some which we will cover in more detail.

Another possibility is the textbook by Katz & Lindell.

For those who do not shy away from some proper math, the Intensive introduction to cryptography (under construction) by Boaz Barak is an excellent resource.

The Handbook of Applied Cryptography (Menezes, Oorschot, Vanstone) is a freely-accessible classic, though it already shows its age. Some algorithms it covers as "up-to-date" were since shown to be insecure and replaced by better ones.

## Teacher's material

The slides can be found in study materials in IS. There are two sub-folders: *Before lecture* contains slides in the form in which I bring them to the lecture. A sort of "early access" to those who want to have a paper/electronic copy of slides during the lecture. At the start of the course, the folder will contain slides from the previous year, though be aware that I will continually update and correct them and the final version might appear only shortly before the lecture. The *Annotated* sub-folder contains slides with my tablet annotations from the lecture (provided that the tech in D3 will be stable enough to let me connect my tablet, otherwise I'll resort to good old blackboard). These will be uploaded continually throughout the semester.

I will also try to publish pointer's to individual slides in the interactive syllabus, though this will likely happen with some delay.

Regarding videos: I am happy to publish lecture videos as long as I am happy with the level of lecture attendance. (The previous statement is deliberately ambiguous.) Note however, that the recording technology in the lecture rooms shows its age and tends to malfunction from time to time.

## Grading

**IMPORTANT: To get to the exam, you need at least 12 points from regular homeworks. If you get less than that, you will get the (failing) grade X without the opportunity to attend the exam.**

The final grade will be determined by the number of points on the following scale: >=116 for A, 102-115 for B, 88-101 for C, 74-87 for D, 60-73 for E.

There are several ways of accumulating the points:

- final written exam
**(up to 120 points)** - 3 regular homeworks
**(up to 30 points, 10 points each)**-> however, there is a restriction on how these points are transferred to the final grading. We use the system of**hard**and**soft**points, see below for an explanation. - 1 bonus howework
**(up to 10 points)**-> similar restriction, see below.**Caution**: these points do not add to the 12 HW point requirement needed to attend the exam.

### Transfer of points from HWs to the final grading

For each of the three regular homeworks, the first **4 points** that you obtain are **hard points**. These are added to your final grade **irrespective of the outcome of the written exam.**

All the other points you obtain during the homeworks (including any points from the bonus homework) are **soft** points. These are added to your final grade if and only if your **written exam result + your hard points are >= 60**. That is, soft points are only added once you have enough exam + hard points to get at least E. In yet another words, the soft points will not help you pass the course, but if you pass it, they can improve your grade.

**Example:** Alice got 9 points from HW01, 6 points from HW02, and 3 points from HW03. That is, total of 11 hard points (4+4+3) and 7 soft points (5+2+0). She got 57 points from her written exam. Her exam + hard point total is 68 >= 60, so she passes the course. The 7 soft points are added to her point total, yielding 75 points, enough for D.

**Example 2:** Bob got 10 points from HW01, 3 points from HW02, and 1 point from HW03. That is, total of 8 hard points (4+3+1) and 6 soft points (6+0+0). He got 50 points from his written exam. His exam + hard point total is 58 < 60, so he fails the exam and needs to retake it (provided there are exam terms available).

## Homework assignments

### General information

The typical form of the homework is to find an idea on how to break a given flawed cryptographic construction and then implement the idea into an attack. Rudimentary programming skills are required.

The assignments will be posted at their dedicated webpages:

Homework link | Submission page | Published | Deadline for submission | |
---|---|---|---|---|

HW01 | TBA | Tuesday, Oct 15, 18:00 | Tuesday, Oct 29, 23:59 | |

HW02 | TBA | Tuesday, Oct 29, 18:00 | Tuesday, Nov 12, 23:59 | |

HW03 | TBA | Tuesday, Nov 26, 18:00 | Tuesday, Dec 10, 23:59 | |

bonus HW | TBA | TBA | TBA |

### Submission guidelines

- Follow the instructions at the assignment webpages. In particular, you are allowed to submit at most one
**.zip**file (any resubmission must overwrite the original file). - The
**deadlines are strict.**The submission vaults will close automatically once the deadline passes and there will be no other opportunity for submission. You are strongly advised to submit at least a day in advance so as to preclude possible issues with network connection etc. - Each homework has a guarantor indicated in the assignment webpage. The guarantor can help you with technical issues, though you should primarily ask about such issues in the discussion forum in IS.
- The preferred language of text submissions is
**English.**Submissions in Czech or Slovak will also be accepted, but will incur a symbolic**penalty**of 0.5 points. - We do not
*a priori*specify which programming language you should use in your implementation. We prefer that you stick to some of these languages: Python (incl. Sage), C++, C#, Java, Rust, JavaScript. Computer algebra systems, such as Magma, are also suitable for some of the HWs. Beyond the aforementioned list, each HW guarantor has a certain "degree of tolerance" for what you can submit. This might be indicated on the assignment page, or just ask the guarantor directly if you want to venture outside of the aforementioned list of languages. - If you need clarification about the assignment, please use the discussion forum as well. You must however
**not**indicate, in any way, any idea about the possible solution of the HW. - Use of AI tools (in particular, large language models; LLMs) is permitted, but it must be declared. Consult the individual assignments for rules on how to cite the output of LLMs.

### Honor code

By submitting your solution you confirm that:

- You have adhered to the MU study and exam regulations.
- You have solved the assignment entirely on your own, without soliciting help from any other person (i.e.,
**cheating is prohibited**). - Whenever you have used some literature and other resources (including webpages, textbooks, videos, etc.), you have
**referenced**such a resource in the*description.txt*file (i.e.,**misappropriation of work is prohibited**). The only exception to this rule are the course slides and lecture recordings, as well as reference guides for the programming language(s) you used in your implementation. - If doubts arise about the authenticity of your submission, you will reply to our inquiries truthfully and honestly.

Violations of the above honor code will be reported to the FI disciplinary committee.

## Exams

Please note that due to the general difficulty in preparing suitable exams for this type of course **there will be exactly 3 exam dates** held in the exam period. Exceptional circumstances (long-term illnesses etc.) will be handled individually (a note from a medical doctor will be required).

### Format

The exams will be written. Each exam will consist of a multiple-choice test (40 points) and four open questions (ca. 80 points).

### Content

The exam will cover all the lectures as well as the 3 regular homeworks. This is a theoretical course, so the exam will mostly test whether you
know **and understand** the concepts and constructions presented. We definitely do
not want you to memorize minuscule technical details of the concrete algorithms.
E.g. for AES, I would expect you to know:

- that it is a block cipher;
- the high level scheme (that there is some key schedule and some round permutations that are applied repeatedly);
- high-level description of round permutations (that there are three operations, which one is non-linear, which one consists of computations over the Galois field, what is a Galois field);
- how is non-linearity achieved (i.e. some intuition behind S-boxes).

Note that you **are** expected to know and understand the mathematical definitions and abstract concepts presented at the
lectures, including security definitons via attack games.

### Structure

The exam will be structured roughly as follows:

- a "simpler" multiple choice test (8 questions, one answer correct, 20 points total, there will be a
**penalty**for**wrong**answers, though not for missing answers); - a "harder" multiple choice test (4 questions, one answer correct, 20 points total, penalties as above);
- a "describe" question: describe a concept/algorithm/attack presented at the lecture (20 points);
- a "flaw" question: you will be given a cipher/algorithm/scheme with a security flaw, your task is to describe how to exploit the flaw to break the security of the given system (20 points);
- a "HW" question: a question testing your understanding of concepts related to some of the homeworks (20 points);
- a "proof" question: describe a security reduction proving the security of some construction that did not appear at the lecture (20 points).

### Exam rules

- You can bring an
**A4 cheat sheet**containing any material you want. The cheat sheet has to be**written by hand**and**signed**and you will**submit it at the end of the exam**along with your solutions. You can write on both sides of the sheet. Note: this is not meant to replace studying for the exam, only to help you to remember some technical details. The exam itself aims to test your understanding of the topics, so merely re-writing notes from your cheat sheets will probably not suffice to succeed. - Other than that, no material is allowed. On your desk, you can have writing utensils, an ID, your cheat sheet, and refreshments. Do not bring any other papers, you will get papers for writing from us.
- In particular, manipulating with any piece of digital technology during the test is
**strictly forbidden**. This pertains in particular to phones, tablets, computers, etc.: you**must not have these on your desk at all**. You can wear smart watches, but restrict yourself to checking time on them. Any extended manipulation with them will be deemed suspicious. - At the end of the exam, when the proctors tell you to stop writing, you have to follow the order. Failure to do so is regarded as cheating.
- The exam proctors have the authority to investigate any suspicious behaviour. If such a behaviour is detected, you will be warned to cease it. If the suspect behaviour continues (or if an outright cheating is discovered), you will be expelled from the exam, get a grade F, and, if applicable, be referred to a disciplinary board.
- You must bring a valid
**photo ID**(national ID, ISIC, passport, driving license,…) to prove your identity.

- The exam assignments are a
**copyrighted material**and it is prohibited to take pictures of them or disseminate them further in any form. Violations will be referred to the faculty disciplinary board.

### Technical information

- The exam is allocated 150 minutes.
- The exam uses standard MU machine-readable answer sheets. In case you have not encountered them yet, familiarize yourself with them here: https://is.muni.cz/auth/help/student/skenovani?lang=en;setlang=en#s_sken_nahlizeni
- Note in particular that for the multiple choice test you need to mark the answer in the machine-readable header of the answer sheet, otherwise the answer does not count. You
**will not**be able to get new answer sheets for the multiple choice tests, since each sheet has a unique sample of questions. Hence, be careful when marking the final answer (you can, e.g. use a pencil and eraser). - The open-ended questions will be assigned on a separate sheet of paper. Together with it, you will get four additional machine readable-sheets to write down your answers to these questions. Extra sheets can be provided on demand, but you are advised to write on both sides and be concise enough so as not to need an extra sheet.
- You can write in
**English**,**Czech**, or**Slovak**.

## Office hours

Office hours are available on demand: please write me an email to schedule a consultation with me.