Arithmetic for IT

This is the main page for the AFIT project proposed to first year student at Epita. You’re welcome to roam around if you’re here for a visit. You’re expected to roam around if this is within you syllabus!

Danger

Project marks are included within the Maths Module overall grade. You’re invited to ask your teachers for the exact coefficient corresponding to AFIT.

The AFIT (Standing for Arithmetic for IT) project has for aim to build first standard ciphering algorithms ; main aim being RSA and ElGamal cryptosystems. You’re expected to go through the maths documentation you’ve been given and understand relevant parts needed to implement your algorithms. You can find pdf versions of the maths documentation at the following links

Attention

You are expected to handout your work before deadline: Sunday December 18th at 23:42.

Listed hereby are the portions of notional contents the maths documentation gets you through and the different stages the project is composed of. All students are expected to go through Level 1 ; you’re encouraged to go through Level 2 and you’re expected to try last level if you’ve passed by the first two. The list of notional contents is there to help you in your potential bibliographical searches. Feel free to roam the internet, but be smart about it.

Notional content

  • Manipulating basic arithmetic operations and functions on natural numbers:

    • Quotient, modulo operations and Euclidian division.

    • GCD computation and extended efficient GCD algorithm giving Bézout coefficients.

    • Prime numbers, relative primality and Bézout Theorem.

  • Modular arithmetic:

    • Definition of modulo of an integer with respect to some given positive natural number. Equality of two integers modulo a positive natural number.

    • Compatibility of modulo operation to addition and multiplication.

    • Given an integer \(n > 1\) the \(\mathbb{Z}/n\mathbb{Z}\) notation and underlying addition and multiplication.

    • Fermat’s Little Theorem.

    • Chinese Remainder Theorem in practice.

    • Notion of invertible element and inverse of an element in \(\mathbb{Z}/n\mathbb{Z}\).

    • Order of an element in \(\mathbb{Z}/n\mathbb{Z}\). Multiplicative generators of \((\mathbb{Z}/n\mathbb{Z})^\times\).

    • Extension of Fermat’s Little Theorem to the case of a product of two primes.

  • Bit-wise operations:

    • Addition, subtraction, multiplication and division of integers in binary representation.

Levels

Project is structured to enable each and every single student to find themselves a working cryptosystem (as naive as it might be) by deadline.

Level 1

Uses built-in int types. Implementing GCD, Bézout, (modular) exponentiations, primality and pseudo-primality tests, brute force generating primes with specific properties, encoding/decoding message, Caesar, RSA and ElGamal cryptosystems.

Level 2

Observe that built-in implementation doesn’t enable any seriously sized exchange of information. Use non-size-predefined integers through OCaml lists as containers for \(1\) and \(0\) dummy bits. First bit being a sign bit. Implement addition, subtraction, multiplication and integer division on new integer type. Re-implement first stage functions to enable RSA encryption. Execute code to generate cryposystem having a higher number of bits than built-in integers.

Level 3

Observe that Level 2 implementation is highly time consuming. Try out the use of a an efficient data structure available within the module Zarith implemeting big integers. This stage is mostly about reading documentation, understanding the alcotest testing framework and thoroughly testing your code.

Table of Contents

Indices and tables