Graduate
  1. Real Analysis  1.1. Set Theory and Logic  1.1.1. Sets and Operations  1.1.2. Relations and Functions  1.1.3. Logic and Quantifiers  1.1.4. Cardinality of Sets  1.2. Metric Spaces  1.2.1. Open and Closed Sets  1.2.2. Convergence of Sequences  1.2.3. Continuous Functions in Metric Spaces  1.2.4. Compactness and Completeness in Metric Spaces in Real Analysis  1.3. Sequence and Series  1.3.1. Convergence of Sequences  1.3.2. Infinite Series  1.3.3. Uniform Convergence  1.3.4. Power Series  1.4. Differentiation  1.4.1. Mean Value Theorems  1.4.2. Taylor Series  1.4.3. Functions of Several Variables  1.4.4. Partial Derivatives  1.5. Integration  1.5.1. Riemann and Lebesgue Integration  1.5.2. Improper Integrals  1.5.3. Measure Theory  1.5.4. Fubini’s Theorem  1.6. Functional Analysis  1.6.1. Banach Spaces  1.6.2. Hilbert Spaces  1.6.3. Operators on Spaces  1.6.4. Spectral Theory
  2. Abstract Algebra  2.1. Groups  2.1.1. Definitions and Examples in Groups in Abstract Algebra  2.1.2. Group Homomorphisms  2.1.3. Normal Subgroups  2.1.4. Sylow Theorems  2.2. Rings and Fields  2.2.1. Ideals and Factor Rings  2.2.2. Field Extensions  2.2.3. Galois Theory  2.2.4. Polynomial Rings  2.3. Modules  2.3.1. Module Homomorphisms  2.3.2. Free Modules  2.3.3. Tensor Products  2.3.4. Exact Sequences  2.4. Linear Algebra  2.4.1. Vector Spaces  2.4.2. Eigenvalues and Eigenvectors  2.4.3. Inner Product Spaces  2.4.4. Diagonalization
  3. Topology  3.1. General Topology  3.1.1. Open and Closed Sets  3.1.2. Compactness and Connectedness  3.1.3. Continuous Maps  3.1.4. Separation Axioms  3.2. Algebraic Topology  3.2.1. Fundamental Groups  3.2.2. Homotopy and Homology  3.2.3. Simplicial Complexes  3.2.4. Exact Sequences in Homology  3.3. Differential Topology  3.3.1. Manifolds  3.3.2. Smooth Functions  3.3.3. Tangent and Cotangent Spaces  3.3.4. Vector Bundles
  4. Differential Equations  4.1. Ordinary Differential Equations  4.1.1. First-Order Equations  4.1.2. Second-Order Linear Equations  4.1.3. Systems of Differential Equations  4.1.4. Stability Analysis  4.2. Partial Differential Equations  4.2.1. Classification of PDEs  4.2.2. Fourier Series  4.2.3. Green's Functions  4.2.4. Method of Characteristics  4.3. Dynamical Systems  4.3.1. Stability Theory  4.3.2. Limit Cycles  4.3.3. Chaos Theory  4.3.4. Bifurcation Theory
  5. Probability and Statistics  5.1. Probability Theory  5.1.1. Random Variables  5.1.2. Probability Distributions  5.1.3. Law of Large Numbers  5.1.4. Central Limit Theorem  5.2. Statistical Inference  5.2.1. Hypothesis Testing  5.2.2. Confidence Intervals  5.2.3. Bayesian Methods  5.2.4. Maximum Likelihood Estimation  5.3. Stochastic Processes  5.3.1. Markov Chains  5.3.2. Brownian Motion  5.3.3. Poisson Processes  5.3.4. Martingales
  6. Numerical Analysis  6.1. Numerical Solutions of Equations  6.1.1. Root Finding  6.1.2. Iterative Methods  6.1.3. Convergence Analysis  6.1.4. Error Bounds in Numerical Solutions of Equations  6.2. Numerical Linear Algebra  6.2.1. Matrix Factorizations  6.2.2. Eigenvalue Computations  6.2.3. Sparse Matrices  6.2.4. Preconditioning Techniques  6.3. Numerical Integration and Differentiation  6.3.1. Quadrature Methods  6.3.2. Finite Differences  6.3.3. Error Analysis in Numerical Integration and Differentiation  6.3.4. Adaptive Methods
  7. Complex Analysis  7.1. Complex Numbers  7.1.1. Polar Form  7.1.2. Complex Conjugates  7.1.3. Exponential Form  7.1.4. Roots of Unity  7.2. Analytic Functions  7.2.1. Cauchy-Riemann Equations  7.2.2. Power Series  7.2.3. Conformal Mappings  7.2.4. Harmonic Functions  7.3. Integration in the Complex Plane  7.3.1. Cauchy’s Theorem  7.3.2. Residue Theorem  7.3.3. Contour Integration  7.3.4. Integral Transforms
  8. Mathematical Logic and Foundations  8.1. Propositional Logic  8.1.1. Truth Tables  8.1.2. Logical Equivalences  8.1.3. Proof Techniques in Propositional Logic  8.1.4. Resolution  8.2. Predicate Logic  8.2.1. Quantifiers in Predicate Logic  8.2.2. Formal Systems in Predicate Logic  8.2.3. Completeness and Soundness  8.2.4. Model Theory  8.3. Set Theory  8.3.1. Cardinality and Ordinality  8.3.2. Axiomatic Systems  8.3.3. Zermelo-Fraenkel Set Theory  8.3.4. Forcing
  9. Optimization  9.1. Linear Programming  9.1.1. Simplex Method  9.1.2. Duality in Linear Programming  9.1.3. Sensitivity Analysis  9.1.4. Interior Point Methods  9.2. Nonlinear Programming  9.2.1. Gradient Descent  9.2.2. Lagrange Multipliers  9.2.3. Convex Optimization  9.2.4. Quadratic Programming  9.3. Combinatorial Optimization  9.3.1. Graph Algorithms  9.3.2. Integer Programming  9.3.3. Network Flows  9.3.4. Approximation Algorithms
  10. Discrete Mathematics  10.1. Graph Theory  10.1.1. Graph Representations  10.1.2. Planarity and Coloring  10.1.3. Shortest Path Algorithms  10.1.4. Network Flows  10.2. Combinatorics  10.2.1. Permutations and Combinations  10.2.2. Generating Functions  10.2.3. Recurrence Relations  10.2.4. Inclusion-Exclusion Principle  10.3. Cryptography  10.3.1. Number Theory Applications in Cryptography  10.3.2. Symmetric and Asymmetric Cryptography  10.3.3. RSA and Elliptic Curve Cryptography  10.3.4. Post-Quantum Cryptography

Graduate → Discrete Mathematics → Cryptography ↓


RSA and Elliptic Curve Cryptography


Coding and encryption are at the core of modern digital communications. The two most well-known methods for secure communications, RSA and Elliptic Curve Cryptography (ECC), are based on the principles of discrete mathematics. This article will go deeper into these cryptographic systems and help clarify how we use mathematical principles to encrypt data, so that it stays safe from curious eyes.

RSA cryptography

RSA is named after its developers, Ron Rivest, Adi Shamir, and Leonard Adleman, who introduced it in 1977. It is a form of public-key cryptography, which uses two keys – a public key used for encryption and a private key used for decryption.

Basic principles of RSA

The security of RSA depends on the difficulty of factoring large integers. It works like this:

  1. Key creation:
    • Choose two different prime numbers p and q.
    • Calculate n = p * q. The number n is used as the modulus for both public and private keys. Its length, usually expressed in bits, is the length of the key.
    • Calculate φ(n) = (p-1)(q-1).
    • Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1. The number e is the public exponent.
    • Define d as d ≡ e -1 (mod φ(n)), which means that d is the modular multiplicative inverse of e modulo φ(n).
    The public key is (e, n), and the private key is (d, n).
  2. Encryption:
    • The message M is encrypted with the recipient's public key: C ≡ M e (mod n), where C is the ciphertext.
  3. Decryption:
    • The ciphertext C is decrypted using the private key: M ≡ C d (mod n), giving back the original message M.

Illustrative examples

Suppose we choose prime numbers p = 61 and q = 53, then n = 61 * 53 = 3233.

The total is φ(n) = (61-1)(53-1) = 3120.

Choose e = 17, which is coprime to 3120.

To find d, the extended Euclidean algorithm gives d = 2753.

Encrypting a message

Let M = 65 encrypted messages C:

C = 65 17 mod 3233

Using fast exponentiation, we get C = 2790.

Decrypting the message

To retrieve M:

M = 2790 2753 mod 3233

Once again, using efficient computation we return to M = 65.

Security of RSA

The strength of RSA lies in the size of the modulus n. The larger the value, the more difficult it is to divide n into its prime components, p and q. This computational difficulty ensures the security of the private key. In addition, choosing a sufficiently large exponent e plays a role in making RSA robust against specific types of attacks.

Elliptic curve cryptography (ECC)

Elliptic curve cryptography is a modern method of cryptography. It uses the properties of elliptic curves over finite fields. ECC is praised for its efficiency as it provides security equivalent to RSA, but with much smaller key sizes.

Understanding elliptic curves

An elliptic curve is defined by the following equation:

y 2 = x 3 + ax + b

For cryptography purposes, we focus on elliptic curves over finite fields, especially fields of prime order.

y 2 = x 3 + ax + b over finite fields

Consider a finite field F p where p is a prime number. Then the elliptic curve consists of the points (x, y) that satisfy the curve equation, which includes a special point at infinity denoted as O

Point operations on elliptic curves

Operations on elliptic curves are governed by the rules of point addition and scalar multiplication. These operations operate under modular arithmetic of finite fields.

Adding digits

Given two points P = (x 1 , y 1) and Q = (x 2 , y 2), their sum R = P + Q = (x 3 , y 3) is calculated as follows:

  • If P ≠ Q, then use: 
    λ = (y 2 - y 1) / (x 2 - x 1) mod px 3 = λ 2 - x 1 - x 2 mod py 3 = λ(x 1 - x 3) - y 1 mod p
  • If P = Q, then use: 
    λ = (3x 1 2 + a) / 2y 1 mod px 3 = λ 2 - 2x 1 mod py 3 = λ(x 1 - x 3) - y 1 mod p

Scalar multiplication

This operation is important in ECC. If k is a scalar and P is a point on the curve, then kP is the result obtained by adding P to itself k times.

ECC key generation

ECC uses scalar multiplication to generate keys. Here is a simple outline of generating an elliptic curve key pair:

  1. Choose a prime number p and parameters a and b to define the curve.
  2. Choose the base point G in the curve.
  3. Select a random integer d as the private key.
  4. Calculate Q = dG, where Q is the public key.

Example of ECC public key generation

Consider an elliptic curve at F p where p = 17, a = 2, and b = 2. Let us choose G = (5,1).

Suppose d = 7, then we calculate:

Q = 7G = G + G + G + G + G + G + G

By repeatedly adding the points, we get Q

ECC security

The security of ECC is based on the Elliptic Curve Discrete Logarithm Problem (ECDLP). Given two points P and kP, determining k is computationally impossible. This is similar to the problem of factoring large prime numbers in RSA.

Comparison between RSA and ECC

While RSA and ECC serve the same purpose in terms of encrypting, signing, and verifying data, they do so through different mathematical principles. Here are some key differences:

  • Key size: ECC offers greater strength per bit than RSA, which means smaller keys for the same level of security.
  • Performance: ECC can be more efficient in terms of computational cost, especially for mobile devices and resource-limited environments.
  • Longevity: Since RSA will require larger key sizes to maintain security in the future, ECC is a more promising candidate for long-term cryptographic security.

Visual representation

Consider how these principles work in the graphical representation of an elliptic curve.

Hey

In this example, the blue curve represents an elliptic curve, while the point labeled O represents the point at infinity, an essential concept in elliptic curve arithmetic.

Both RSA and ECC represent important cryptographic achievements based on discrete mathematics. RSA relies heavily on integer factorization, while ECC relies on the geometric properties of elliptic curves. Together, they provide robust solutions for securing data in the digital age, each with its own unique strengths and applications.


Graduate → 10.3.3


U
username
0%
completed in Graduate

← Prev (10.3.2)
Symmetric and Asymmetric Cryptography
Next (10.3.4) →
Post-Quantum Cryptography

Comments 



RSA and Elliptic Curve Cryptography

https://www.buddymath.com/g/10.3.3?bmal=en