CryptoBook
  • CryptoBook
  • Book Plan
  • Style Guide
    • Sample Page
  • Contributors
  • Fundamentals
    • Mathematical Notation
    • Division and Greatest common divisor
      • Euclidean Algorithm
    • Modular Arithmetic
      • Theorems of Wilson, Euler, and Fermat
        • Fermat's Little Theorem in Detail
        • Euler's Theorem in Detail
      • Quadratic Residues
    • Continued Fractions
  • Number Theory
  • Ideals
  • Polynomials With Shared Roots
  • Integer Factorization
    • Pollard rho
    • Sieves
  • Abstract algebra
    • Groups
      • Another take on groups
      • Discrete Log Problem
    • Rings
    • Fields
    • Polynomials
  • Elliptic Curves
    • Untitled
  • Lattices
    • Introduction
    • LLL reduction
      • Gram-Schmidt Orthogonalization
      • Lagrange's algorithm
      • LLL reduction
    • Lattice reduction
      • Minkowski reduced
      • HKZ reduced
      • LLL reduced
    • Applications
      • Coppersmith algorithm
      • Extensions of Coppersmith algorithm
    • Hard lattice problems
    • Lattices of interest
    • Cryptographic lattice problems
      • Short integer solutions (SIS)
      • Learning with errors (LWE)
      • Ring-LWE
      • NTRU
    • Interactive fun
    • Resources and notations
  • Asymmetric Cryptography
  • RSA
    • Proof of correctness
    • RSA application
    • Low Private Component Attacks
      • Wiener's Attack
      • Boneh-Durfee Attack
    • Common Modulus Attack
    • Recovering the Modulus
  • Diffie-Hellman
    • MITM
  • Elliptic Curve Cryptography
  • Symmetric Cryptography
    • Encryption
    • The One Time Pad
    • AES
      • Rijndael Finite Field
      • Round Transformations
  • Hashes
    • Introduction / overview
    • The Birthday paradox / attack
  • Isogeny Based Cryptography
    • Introduction to Isogeny Cryptography
    • Isogenies
    • Isogeny and Ramanujan Graphs
  • Appendices
    • Sets and Functions
    • Probability Theory
Powered by GitBook
On this page
  • I- Introduction:
  • II- Arithmetic for RSA
  • III- Key generation
  • IV- Signature
  • V- Format

Was this helpful?

Export as PDF

RSA

Will be introduced in this page the fundamentals of RSA, mathematical requirement and also some application with python and openSSL.

PreviousResources and notationsNextProof of correctness

Last updated 3 years ago

Was this helpful?

This page is pretty long, probably could be split up

Edit: I haved deleted the last part, application with RSA, and i made a special part for this. Maybe we can do the same with the second part: Arithmetic for RSA.

I- Introduction:

RSA is a that is widely used in the world today to provide a secure transmission system to millions of communications, is one of the oldest such systems in existence. The RSA comes from the surnames of , , and , who publicly described the algorithm in 1977. An equivalent system was developed secretly, in 1973 at (the British agency), by the English mathematician . That system was in 1997.

All public-key systems are based on the concept of , functions that are simple to compute in one direction but computationally hard to reverse without knowledge of some special information called the trapdoor. In RSA, the trapdoor function is based on the . The function involves the use of a public keyNN Nto encrypt data, which is (supposed to be) encrypted in such a way that the function cannot be reversed without knowledge of the prime factorisation ofNN N, something that should be kept private. Except in certain cases, there exists no efficient algorithm for factoring huge integers.

Further reading:

Formalize the introduction and include a discussion of the security based on the hardness of factoring integers.

II- Arithmetic for RSA

Before starting to introducing you RSA, a few arithmetic notions need to be introduce to understand perfectly other steps.

III- Key generation

  • We pick two primes ppp and qqq

  • Using ppp and qqq, we calculate modulus n=p×qn = p\times qn=p×q and its Euler's totient ϕ(n)=(p−1)×(q−1)\phi(n) = (p-1) \times (q-1)ϕ(n)=(p−1)×(q−1)

  • Now, choose the public exponent e\mathbb{e}esuch as gcd(e,ϕ(n))=1\mathbb{gcd(e, \phi(n)) = 1}gcd(e,ϕ(n))=1

  • By using the Extended Euclidean algorithm, we compute the invert d\mathbb{d}d of emod  n\mathbb{e \mod n}emodn :d≡e−1mod  ϕ(n)d \equiv e^{-1} \mod \phi(n)d≡e−1modϕ(n) which is our private exponent.

  • Public key: n,en, en,e

  • Private key: n,dn, dn,d

  • Now, chose a message m\mathbb{m}mthat you convert into integers

  • We can encrypt this plaintext mmm and receive a ciphertext c≡memod  nc \equiv m^e \mod nc≡memodn

  • We can decrypt a ciphertext ccc with m≡cdmod  nm \equiv c^d \mod nm≡cdmodn

IV- Signature

A digital signature is a proof of the authenticity of a message, i.e. a proof that the message has not been tampered with. RSA allows us to sign messages by "encrypting" them using the private key, the result being a signature that anyone can verify by "decrypting" it with the public key and comparing it to the associated message. Any attempt to tamper with the message will result in it no longer matching the signature, and vice-versa. Futhermore, a signature can only be generated using the private key, making it a secure and efficient method of confirming the authenticity of messages.

V- Format

Say Alice wants to send a message to Bob, but does not want Mallory, who has established herself as a middleman, to make changes to the message or swap it out entirely. Fortunately, Bob knows Alice's public key, and since eee and ddd are inverses such that ed≡1mod  ϕ(n)ed \equiv 1\mod \phi(n)ed≡1modϕ(n), Alice can sign her message mmm by "encrypting" it with the private key such that s≡mdmod  ns \equiv m^d \mod ns≡mdmodn, where sss is the signature verifying that the message came from Alice. Alice can now send mmm and sss to Bob, who is now able to check the authenticity of the message by checking if m≡semod  nm \equiv s^e \mod nm≡semodn. If Mallory tries to change mmm, this congruence no longer holds, and since she does not have the private key, she is also unable to provide a maching sssfor her tampered message.

public-key cryptosystem
acronym
Ron Rivest
Adi Shamir
Leonard Adleman
GCHQ
signals intelligence
Clifford Cocks
declassified
trapdoor functions
hardness of factoring integers
Shor's algorithm