The Mathematical Foundations of Modern Cryptography: Exactness, Prime Numbers, and the Greatest Common Divisor

-

Welcome to the first post of this blog, dedicated to my academic journey in cryptography. The goal of this post is to introduce the fundamental mathematical concepts that guarantee the security of our digital communications.

It is important to underline that the mathematics used in cryptography is profoundly different from what we apply in our daily routines.

The absolute need for exactness

In everyday life, the use of approximations is very common. For example, if a product costs $1.99, we naturally consider it as $2.00. However, in the field of modern cryptography, there is no tolerance for rounding errors.

If a cryptographic algorithm approximates a value even by a microscopic fraction, the entire system fails. The digital "key" used to encrypt a message would no longer be able to decrypt it, making the information permanently inaccessible. For this reason, cryptography abandons decimal numbers and operates exclusively with integers (such as -1, 0, 1, 2, 3). Devoid of decimal points, integer mathematics guarantees the absolute precision required to keep data secure.

Prime numbers: the indivisible elements

To create a secure system, cryptographers use mathematical problems that are extremely difficult for a computer to solve without a specific key. The main components used to build these problems are prime numbers.

  • Prime numbers: An integer greater than 1 that is divisible only by 1 and itself (for example, 2, 3, 5, 7, 11). We can consider them as the elementary atoms of mathematics because they cannot be divided into smaller integer components.
  • Composite numbers: Integers obtained by multiplying prime numbers. For example, the number 15 is the product of 3 and 5.

This concept introduces the Fundamental Theorem of Arithmetic, which states that every integer greater than 1 has a unique and unrepeatable prime factorization. This mathematical "fingerprint" is an essential feature used to generate secure cryptographic keys.

The Greatest Common Divisor (GCD) and coprime numbers

Furthermore, for cryptography algorithms to work correctly, it is necessary to select numbers that interact in a specific way. In this context, the Greatest Common Divisor (GCD) is a crucial tool. The GCD is the largest positive integer that divides two numbers without leaving a remainder.

The GCD is particularly useful for determining whether two integers are relatively prime (also defined as coprime). Two numbers are relatively prime if their GCD is exactly equal to 1. This means they do not share any common prime factor.

For example, the number 8 (which is 2 × 2 × 2) and the number 15 (which is 3 × 5) are relatively prime. The selection of coprime numbers is a fundamental procedure in modern algorithms. It is the mathematical mechanism that allows a system to correctly reverse an operation, ensuring that a message can be securely encrypted and subsequently decrypted by the legitimate recipient.

References and further reading

  • Coursera: Mathematical Foundations of Cryptography (Course lectures and transcripts).
  • Shiu, P. (2024). Number Theory with Computations. Springer. (For fundamental concepts of discrete mathematics and arithmetic theorems).
  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press. (For an in-depth look at the algorithmic applications of the GCD and primality testing).
  • Venturi, D. (2012). Crittografia nel Paese delle Meraviglie. Springer. (For a comprehensive academic overview of modern cryptographic schemes).

Comments

Post a Comment

Popular posts from this blog

How to Install Ubuntu 24.04 WSL on Windows 10 and 11

-
Introduction This guide shows you step-by-step how to install Ubuntu 24.04 LTS using WSL (Windows Subsystem for Linux) on Windows 10 or Windows 11. It's a great solution to run Linux without dual boot or virtual machines. Requirements Windows 10 (version 2004 or later) or Windows 11 Internet connection Administrator access 1. Enable WSL Open PowerShell as administrator and run this command: wsl --install This command enables the necessary features, installs the WSL platform, and downloads Ubuntu (usually the latest stable version). 2. Install Ubuntu 24.04 Manually (if needed) If you want to install Ubuntu 24.04 specifically, you can do it manually: wsl --install -d Ubuntu-24.04 Or if WSL is already installed: wsl --list --online wsl --install -d Ubuntu-24.04 3. First Launch and Setup After installation, open Ubuntu from the Start Menu. The first time you launch it, y...
Read more

Introduction to Rust: Writing Your First "Hello, World!"

-
Getting Started with Rust: A Beginner’s Guide Getting Started with Rust: A Beginner’s Guide Published on July 20, 2025 Setting Up the Workspace First, we need to establish a directory to store our code. While Rust is indifferent to its location, it is good practice to keep your projects well-organized. Open a terminal (or command prompt) and create a directory for your project. For Linux, macOS, and PowerShell (on Windows): # Create a "projects" directory in your home directory mkdir ~/projects # Enter the newly created directory cd ~/projects # Create the directory for our specific project mkdir hello_world # Enter the project directory cd hello_world For the Windows Command Prompt (CMD): > mkdir "%USERPROFILE%\projects" > cd /d "%USERPROFILE%\projects" > mkdir hello_world > cd hello_world Writing and Executing the P...
Read more

Getting Started with Cargo in Rust: A Beginner-Friendly Guide

-
Getting Started with Cargo in Rust: A Beginner-Friendly Guide Cargo is the default build tool and package manager for Rust. It helps you build your code, download libraries (called dependencies ), and keep everything organized. 1. What Is Cargo? When you use Cargo, you don’t have to compile your code manually with rustc . Cargo makes everything easier, especially for bigger projects. You can: Build your code Add external libraries (dependencies) Run your program Check for compile-time errors 2. Check if Cargo is Installed If you installed Rust using the official method ( rustup ), Cargo is already installed. To check, run this command in your terminal: $ cargo --version If you see a version number, you're ready! 3. Create a New Project Now, let’s create a new Rust project using Cargo: $ cargo new hello_cargo $ cd hello_cargo This creates a folder named hello_cargo with two important things inside: Car...
Read more