Public Key Cryptography

Dr. Greg Bernstein

October 12th, 2021

Asymmetric Cryptography


Big Applications

The Key Distribution Problem

Securing Communications I

How many symmetric keys are needed for N nodes to communicate?

N Nodes

Securing Communications II

\(N(N-1)/2\) keys

N Nodes Connected

How to Distribute the Keys?

We’ve got a problem…

  • Need a secure channel to distribute the key

  • Need a key to create a secure channel

  • If a key is compromised there is no security

Public Key Cryptography History IA

From Wikipedia: Public Key Cryptography classified history

  • 1970: James H. Ellis, a British cryptographer at the UK Government Communications Headquarters (GCHQ), conceived of the possibility of “non-secret encryption”, (now called public key cryptography), but could see no way to implement it.

  • 1973: Clifford Cocks (GCHQ) implemented what has become known as the RSA encryption algorithm, giving a practical method of “non-secret encryption”,

Public Key Cryptography History IB

From Wikipedia: Public Key Cryptography classified history

  • 1974 another GCHQ mathematician and cryptographer, Malcolm J. Williamson, developed what is now known as Diffie–Hellman key exchange.

These discoveries were not publicly acknowledged for 27 years, until the research was declassified by the British government in 1997

Public Key Cryptography History IIA

From Wikipedia: Public Key Cryptography Public Discovery

  • 1976: an asymmetric key cryptosystem was published by Whitfield Diffie and Martin Hellman who disclosed a method of public key agreement. This method of key exchange, which uses exponentiation in a finite field, came to be known as Diffie–Hellman key exchange. This was the first published practical method for establishing a shared secret-key over an authenticated (but not confidential) communications channel without using a prior shared secret.

Public Key Cryptography History IIB

From Wikipedia: Public Key Cryptography Public Discovery

  • 1977: a generalization of Cocks’ scheme was independently invented by Ron Rivest, Adi Shamir and Leonard Adleman, all then at MIT. The latter authors published their work in 1978 in Martin Gardner’s Scientific American column, and the algorithm came to be known as RSA.

Asymmetric Cryptography Concepts

Two Keys: Public and Private

From Wikipedia: Public Key Cryptography

Key Generation

Sending a Message with a Public Key

From Wikipedia: Public Key Cryptography

Sending a message

Public Key Cryptography Properties

  • Very hard to determine private key from public key, i.e., like symmetric cryptography
  • Very hard to determine private key from messages, i.e., like symmetric cryptography
  • Can openly share public key so that others can send private message to you

How Many Keys do we need?

Only \(N\) Keys! No secure channel needed!

N Nodes

Public Key Families

  • RSA – based on properties of large prime numbers
  • Elliptic Curve – based on the “algebraic structure of elliptic curves over finite fields”, caution see SafeCurves
  • ElGamal – based on difficulty of computing discrete logarithms.

Python Hands On Pubic Key Encryption

RSA Algorithm Imports

Some Imports

from cryptography.hazmat.primitives.asymmetric import rsa
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import padding
from cryptography.hazmat.primitives import hashes

Alice’s Key Generation

See Python Cryptography RSA for recommended parameters

alice_private_key_rsa = rsa.generate_private_key(public_exponent=65537, key_size=2048)
alice_public_key_rsa = alice_private_key_rsa.public_key()

Bob’s Key Generation

See Python Cryptography RSA for recommended parameters

bob_private_key_rsa = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key_rsa = bob_private_key_rsa.public_key()

Set Padding Algorithm

See Python Cryptography RSA for recommended approach

myPad = padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()), 
                     algorithm=hashes.SHA256(), label=None)

Alice Sends Message to Bob

Alice uses Bob’s public key to encrypt

message = b"Hi Bob, Alice here. I got your public key from trusted source. Just testing!"
bob_ciphertext = bob_public_key_rsa.encrypt(message, myPad)

Looking at the Ciphertext

def bytes2ascii(bs):
    # Printable ASCII is 32-126
    outstring = ""
    for b in bs:
        if b >= 32 and b <= 126:
            outstring += chr(b)
            outstring += "X"
    return outstring

Ciphertext for Bob


Bob Deciphers the Message

Bob uses his private key to decrypt

plaintext = bob_private_key_rsa.decrypt(bob_ciphertext, myPad)

Key Exchange

Performance of Public Key Encryption

Nothing is Perfect

  • Public Key based Encryption is much slower than similarly secure symmetric algorithms
  • Hence public key algorithms are not directly used for bulk encryption
  • Instead they are used in key exchange, signing, and verification

Diffie-Hellman Key Exchange

Using public and private information securely come up with a common secret key for symmetric key cryptography algorithms such as AES. The algorithm takes advantage of the difficulty in computing discrete logarithms.

Diffie-Hellman Diagram

From Diffie-Hellman Key Exchange

DH key exchange

Python Hands On Key Exchange

Generation of Ed25519 Pairs

from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey
alice_private_key = X25519PrivateKey.generate()
alice_public_key = alice_private_key.public_key()
bob_private_key = X25519PrivateKey.generate()
bob_public_key = bob_private_key.public_key()

Alice Symmetric Key Generation

# Alice creates a symmetric key with her private key and Bob's public key
shared_key_alice =

Bob Symmetric Key Generation

# Bob creates a symmetric key with her private key and Alice's public key
shared_key_bob =
shared_key_alice == shared_key_bob

Man-in-the-middle (MITM) Attack

From NCyTE Applied Cryptography

MITM Key Exchange

Missing Pieces

  • Authenticity how do we know who really sent the message?
  • Integrity how do we know that the message hasn’t been modified?

Public Key Cryptography in the Real World Part I

What does TLS 1.3 Support?

From RFC8446

/* RSASSA-PKCS1-v1_5 algorithms */

/* ECDSA algorithms */

/* RSASSA-PSS algorithms with public key OID rsaEncryption */

/* EdDSA algorithms */

/* RSASSA-PSS algorithms with public key OID RSASSA-PSS */

SSH with No Password

  • How can we log into a remote server without always typing passwords?
  • Use public key cryptography!
  • Really? Yup. How do I do that?

What does SSH Support

SSH Public Keys

SSH References/Sites

SSH Key Generation I

See man page: ssh-keygen

  • Key options (-t): dsa, ecdsa, ecdsa-sk, ed25519, ed25519-sk, rsa
  • Out to file: -f filename
  • Usage example: ssh-keygen -f keyFile
  • Usage example: ssh-keygen -t ed25519 -f keyFile2

SSH Key Generation II

SSH Ken generation
ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIA5E8II0QJ/2Pd9Wjky8DMG+Xf9AQH61lITQkwLvBS1t greg@DESKTOP-71U86TK

Server SSH Files

From sshd the server can have an “authorized key file”

  • Default ~/.ssh/authorized_keys and ~/.ssh/authorized_keys2
  • Each line of the file contains one key (empty lines and lines starting with a ‘#’ are ignored as comments).
  • Public keys consist of the following space-separated fields: options, keytype, base64-encoded key, comment. The options field is optional.

Example authorized_keys file

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQC5X6gfWaQnc1PRKYC3t3U7dCEkN5wE+1HqnH6OwTtH0YMcvc3liILwp0qoao52NV1e3zRQiTeIWXa278UdSEiDmn9+VtFcZRNJYYlop5CuGOIvDt30vRrxeMNLI2Cg+zvcNOFaLxpnmJyajklScgnJwJj3qN6fCj6Wn6I+H8VYyBzRguaT3We0XSKZ5PzsW7tWRuFut/cBpMcbUWbgtBZvIGoU7LXnsNvDE+DLqAnEjeLJdBKRvjiLLHKcZVVS2j2Ua1U1mVFtNC0d2TO03LGqB4CNQhJ91y1n2TN8FS7764VbSjK1TFKNUJUN/1a+yU4BBNZWtHy8rxVw/Xx60VJJ gregb@DESKTOP-NOE6DKP

Add your Key to the Server

  • Manually add your public key that you generated on your machine to the authorized_keys file on the server.

  • Use the ssh-copy-id command to help you do this without the manual file editing.

  • Example use: ssh-copy-id -i keyFile2 greg@

// reveal.js plugins