Asymmetric Cryptography

• Use different keys for the encryption and decryption operations

• One key can be made public while the other key is kept secret (and is called privatekey)

• Can grow more easily to worldwide scale and more easily permit unaffiliated persons to communicate securely

• Can be used to provide digital signatures

Diffie-Hellman Key Exchange

• Used to securely exchange a key

• Requires two system-wide parameters:

  • A prime number p

  • A special number g (a generator)

• Why does this work?

  • $(X_b)^a = (g^b)^a = (g^a)^b = (X_a)^b$

• Why is it secure?

  • Discrete logarithm problem is hard. (i.e., for known elements a,b and p, find an element x such that $a^x \equiv b\,mod\,p$ )
    

    

Examples of Public Key Encryption Systems

• El Gamal

  • Security depends on hardness of the discrete logarithm problem

• Rabin

  • Security depends on hardness of integer factorisation

RSA

• Security depends on hardness of integer factorisation

  • Given an integer $N=p\cdot q$ , find p and q, where p and q are primes

• Named after Ron Rivest, Adi Shamir and Len Adleman

• Published in 1978

• Still one of the most widely used public-key cryptosystems in use today

Generating an RSA Keypair

• Generate the public key

  1. Choose two prime numbers p and q

  2. Let $n = p\cdot q$

  3. Choose an element e that is coprime to (p-1)(q-1)

• The public key is pk = (n,e)

• Generate the secret key sk

  • Let d be a modular inverse of e such that $e\cdot d \equiv 1\, mod\, (p-1)(q-1)$

• The private key is sk=d

Encryption and Decryption

• To encrypt a message using public key pk = (n,e)

  • $c=m^e\,mod\,n$

• To decrypt a ciphertext using secret key sk=d

  • $m=c^d\,mod\,n$

Security of RSA

• There are several ways to attempts to break RSA

  • Recover the decryption key from the encryption key

    • If the modulus 𝑁 is chosen large enough (i.e., ≈ 2048 bits) recovery of the decryption key is hard (if factoring is hard)

  • Decrypt the ciphertext without the secret decryption key

    • This is equivalent to breaking the RSA problem, another mathematically hard problem

• RSA is a deterministic algorithm

• A padding scheme must be used to achieve a probabilistic encryption system

RSA-OAEP (Optimal Asymmetric Encryption Padding)

• Let h_1 and h_2 be two hash functions and let r be randomness generated using a random number generator

• To encrypt a message m using public key pk=(n,e)

  • $a=h_1(r)\oplus m$

  • $b=h_2(a)\oplus r$

  • $c=(a||b)^e\,mod\,n$

• To decrypt a ciphertext c using secret key sk = d

  • $a||b=c^d\,mod\,n$

  • $h_2(a)\oplus b=r$

  • $h_1(r)\oplus a=m$

Strengths

• Doesn't require secure key exchange

• no need for Symmetric Trust

Weaknesses

• Slow encryption speeds

• Security issues when encrypting long plaintexts

Towards Post-Quantum Public Key Cryptography

• PROBLEM: If an attacker can access a quantum computer, none of the problems upon which public-key cryptography is based will be hard

• Shor’s algorithm can factor a number in O(b^3) where b is the number of bits

• We need post-quantum cryptography that is based on problems that are believed to be hard even with access to a quantum computer!

  • NIST standarisation efforts

Maths Background

• Modular arithmetic (mod):

  • $a\,mod\,b = c \Rightarrow a$ divided by $b$ leaves remainder $c$

    • For example,$5\,mod\,3=2$

  • $a \equiv c\, mod\,b \Rightarrow a$ and $c$ leave the same remainder when divided by $b$

    • For example, $8\equiv 5\,mod\,3$

• Coprimality

  • Two integers are coprime if they have no divisors in common other than 1

  • Determined by the Euclidean algorithm

• Modular inverse

  • Given a and N,x is a modular inverse of a if $a\cdot x \equiv 1\, mod\, N$

  • A modular inverse exists if a and N are coprime

  • Determined by the Extended Euclidean algorithm

• Modular exponentiation

  • Given a,x and N, compute $a^x\, mod \, N$