Asymmetric Encryption

---

An Asymmetric encryption refers to the use of different algorithms for encryption and decryption, which each use different keys.

• aka public key cryptography
• uses different but related public and private keys in a key pair
  • Use the public key to encrypt data
    • public key can be openly shared
    • often included in email signatures, posted on servers, etc.
  • Private keys are used to decrypt messages
    • kept secret to the holder
• keys are mathematically linked
  • using an algorithm relying on one-way functions
  • e.g.,
    • Rivest, Shamir, Adelman (RSA)
      • requires a 2,048-bit private key for acceptable level of security
    • Elliptical Curve Cryptography (ECC)
      • uses 256-bit private key for equivalent of 3,072-bit RSA key
• keys are generated in a way that it makes it impossible to derive the private key from the public key
• asymmetric key cannot reverse the operation it performs
  • i.e., public key cannot decrypt what it has encrypted
• both encryption and decryption algorithms use the same cryptovariables
  • may include a seed value or parameter
• asymmetric encryption is typically used to encrypt a symmetric key
  • symmetric key is used for the data encryption
  • when used in this way, symmetric key is called session key
    • new key each session
• came into use due to 3 problems in inherent in symmetric encryption:
  • key distribution and management
  • improved security
  • trust relationships

Advantages over symmetric key cryptography:

• Don’t need to share private key, just the public one
  • increased security
• provides digital signatures, so authentication can be assured

Drawback

• involves substantial computing overhead
• inefficient for large amounts of data at rest or in transit

Structure of Asymmetric Cryptosystem

How Asymmetric Encryption Works

3 Classes

• Integer Factorization Cryptography
• Finite Field Cryptography
  • based on computations over finite fields
• Elliptic Curve Cryptography
  • based on computations over elliptic curves

Trapdoor Functions

One-way function is a function that is easy to compute in one direction, but difficult to compute in the opposite direction.

• public key cryptography is based on functions that are believed to be one-way, but no function has mathematically proven to be so

Theoretical Definition

Let be function, which receives input and returns output.

• is said to be one-way, if
  • it is easy to compute for
  • but is computationally infeasible to find a preimage given

Example

• Given two large primes and , it is easy to find the product , while given , it is not easy to find and , such that
  • known as factorization problem
• Given three integers , , and , it is easy to compute , such that , while it is not easy to find , such that , when , , and are given
  • referred to as discrete logarithm problem
• Any hash function is a one-way function, because given , it is easy to compute , such that , while given , it is not easy to find , such that

Trapdoor function is a one-way function for which the inverse direction is easy to compute if some specific information is known, but difficult otherwise.

• the specific information is called a trapdoor
• asymmetric encryption relies on trapdoor functions
  • relatively easy and straightforward to compute in one direction
  • but the logical inverse is essentially impossible to compute in the other direction
• public key gives information about the particular instance of the function
• private key gives information about the trapdoor
  • anyone who knows the trapdoor can computer the function in both directions
  • anyone who does not know the trapdoor can only easily perform the function in the forward direction
    • forward direction (i.e. public key) is used for encryption and signature verification
    • reverse direction (i.e. private key) is used for decryption and signature generation
• two categories:
  • discrete logarithm
  • integer factorization

Discrete Logarithm Problems

• first described in a paper by Whitfield Diffie and Martin Hellen
  • based their concepts from Ralph Merkle
• capitalizes on the problem of computing discrete logarithms
  • for any given number base , the logarithm is the value of the exponent that must be raised to in order to produce the required result
    
• it is computationally difficult to compute discrete logarithms for any particular value , when is a member of a particular type of group or set
• details on how you choose a set of values for , , and , and how you put them to work are part of each protocol’s unique approach
• e.g.,
  • Diffie-Hellman, Elliptical Curve, ElGammel, and DSA

Factoring Problems

• involves factoring extremely large semiprime numbers
  • is the product of two prime numbers
• simple to multiply two primes to get a semiprime
• very computationally complex to factor (calculate the prime factors) of a very large semiprime
  • can be no better than brute force or guessing
  • factoring a 232-digit number required 1,500 processors in 2009
• the two prime factors and the semiprime become elements in the encryption and decryption system
• e.g.,
  • RSA and LUC

Asymmetric Key Algorithms

• RSA
• Elliptic Curve Cryptography (ECC)
• ElGamal
• Diffie-Hellman
• Digital Signature Standard (DSS)
• Pretty Good Privacy (PGP)
  • for securing messages and files
• SSL and TLS
  • for common internet traffic
• VoIP

Asymmetric Algorithms

Algorithm name	Computational efficiency	Power consumption	Typical key size (bits)	Basis of security
RSA	Low	High	1024	Difficulty of factoring the product of two large prime numbers
ElGamal	Medium	Medium	1024	Difficulty of computing discrete logarithms
ECC	High	Low	160	Difficulty of computing elliptic curve discrete logarithms