Cryptography
Authors: Matthew, Jerry
What is the problem?
The problem is to explore cryptography with Prolog. Specifically features such as implementing hash functions to assess integrity of data, digital signatures to declare and assess authenticity of data, etc.
What is the something extra?
We will implement a symmetric encryption algorithm that we can secure files such that another user can decrypt such files if they have the corresponding password/key. We wish to explore how Prolog can handle cryptography tasks in general.
What did we learn from doing this?
We learned some of the strengths and weaknesses of using Prolog to implement common cryptography tasks.
For example, low-level data manipulation and bitwise operations are not natively supported by Prolog and are completed in more roundabout ways. Other languages like C are more verbose in this area and allow direct memory access and bit manipulation, which will be optimized by the compiler to be more efficient than Prolog. However, Prolog code is generally more readable and abstract, making it quicker to understand and easier to reason about its correctness. Specifically, Prolog relies heavily on recursion and list manipulation, which are inherently slower than direct memory access.
What is the bottom-line? Is logic programming suitable for (part-of) the task? Make sure you include the evidence for your claims.
From our experience in the project, it seems Prolog is better suited for cryptanalysis as opposed to cryptography due to its backtracking and pattern matching strengths. Prolog's ability to perform backtracking and pattern matching would likely be useful in tasks such as trying several keys or analyzing patterns in encrypted texts. Since Prolog is highly abstract, it may also be practical instead to develop quick proof-of-concepts.
However, for implementing production-grade security, it would seem that other languages are better-suited. If encrypted data is very large and performance-intensive, the inefficiencies of Prolog may start to compound whereas low-level imperative languages such as C can complete the same tasks more efficiently and reliably.
Work division
We will discuss with the TA.