Crytography

Introduction

Cryptography gives us way to interact securely in an insecure communication line.

Methods To Identify Compromise

• data confidentiality – encryption algorithms hide the content of messages;
• data integrity – integrity check functions provide the means to detect whether a message has been changed;
• data origin authentication – message authentication codes or digital signature algorithms provide the means to verify the source and integrity of a message

Symmetric and Asymmetric Cryptography

Symmetric cryptography utilises the same secret key for both encryption and decryption, functioning like a vault where one key is needed to both store and retrieve information. In contrast, public-key cryptography (asymmetric) uses two distinct keys: a public key for encryption and a private key for decryption, which is analogous to a private letter box where anyone can drop a document in, but only the owner can open it

Finally, because public-key algorithms are computationally more expensive and slower than symmetric ones, they are rarely used for bulk data encryption. Instead, they are typically used in hybrid applications to securely establish short-term session keys, while the faster symmetric algorithms are used to protect the actual data being transmitted.

Modular Arithmetic

a = b mod m if and only if a − b = λ · m for some integer λ.

(a)m = {b | a = b mod m} , 0 ≤ a < m.

Properties

• (a mod m) + (b mod m) = (a + b) mod m
• (a mod m) · (b mod m) = (a · b) mod m
• for every a  = 0 mod p, p prime, there exists an integer a−1 so that a · a−1 = 1 mod p

Fermet’s Little Theorem

Discrete Logarithm Problem

The Discrete Logarithm Problem (DLP) is a fundamental mathematical challenge used as the algebraic basis for many modern cryptographic algorithms. In terms of modular arithmetic, the problem is defined as follows: given a prime modulus p, a basis a, and a value y, the goal is to find an integer x such that y=axmodp.

Hard Mathematical Problems in Cryptography

The security of many cryptographic algorithms relies on the computational difficulty of solving specific problems within modular arithmetic:

• Discrete Logarithm Problem (DLP): Given a prime p, a basis a, and a value y, find an integer x such that y=a^xmodp
• nth Root Problem: Given integers m, n, and a, find an integer b such that a=b^nmodm
• Factorization: Given a large integer n, find its prime factors

1. Euler’s Totient Function Φ(n)

Counts integers up to n that are relatively prime to n.

• General Formula: Φ(n)=n∏p∣n​(1−p1​)

• For Prime Powers: Φ(pk)=pk−pk−1

• For Primes: Φ(p)=p−1

2. Modular Multiplicative Inverse

The value x such that:

• Equation: ax≡1(modm)

• Existence: Only exists if gcd(a,m)=1.

• Notation: x=a−1(modm)

3. Fermat’s Little Theorem

If p is prime and a is not divisible by p:

• Formula: ap−1≡1(modp)

• Useful Corollary: ak(modp)=ak(modp−1)(modp)

4. Linear Congruence

To solve ax≡b(modm):

1. Find a−1(modm).

2. Multiply both sides: x≡b⋅a−1(modm).