Asymmetric-key Cryptography

2.6. Asymmetric-key Cryptography#

In asymmetric cryptography (public-key cryptography) there are two keys, which form a key-pair. One key is used to encrypt the plaintext to ciphertext and one key is used to decrypt the ciphertext to plaintext. Note that you cannot encrypt and decrypt using the same key. If you encrypt with one key you can only decrypt it with the other key.

../../_images/plaintext_ciphertext_asymmetric.png

Simple Example If you’re wondering how asymmetric cryptography works, it all comes down to maths, specifically using the power and modulo operator.

It turns out, you can pick values \(x\), \(y\) and \(z\) such that

\[c = p^x\mod z\]

\[p = c^y\mod z\]

where \(p\) is the plaintext and \(c\) is the ciphertext. This means that the public key consists of the values \(x\) and \(z\) and the private key consists of values \(y\) and \(z\). There are clever ways to pick \(x\), \(y\), and \(z\), which we won’t go into, but lets say we had

\[x=3, y=7, z=33\]

Recall that letters can be stored as numbers in the computer:

A	B	C	D	E	F	G	H	I	J	K	L	M	N
1	2	3	4	5	6	7	8	9	10	11	12	13	14

O	P	Q	R	S	T	U	V	W	X	Y	Z	!	?
15	16	17	18	19	20	21	22	23	24	25	26	27	28

Suppose we had the plaintext

M E S S A G E

We can represent this using the numbers

13 5 19 19 1 7 5

We’ll now encrypt with our public key information (3, 33) the formula \(p^2 \mod 33\) and apply this to the numbers 13 5 19 19 1 7 5.

for letter in [13, 5, 19, 19, 1, 7, 5]:
    print(letter**3 % 33)

We get the ciphertext

19 26 28 28 1 13 26

which correspond to

S Z ? ? A M Z

Now we’ll try to decrypt using our private key information (7, 33) formula \(c^7 \mod 33\) and apply this to the numbers 19 26 28 28 1 13 26.

for letter in [19, 26, 28, 28, 1, 13, 26]:
    print(letter**7 % 33)

We get 13 5 19 19 1 7 5 which corresponds to MESSAGE.

Note that this was a simple demonstration of how asymmetric keys work. Real cryptographic algorithms are much more complicated than this.

2.6.1. Sending Encrypted Messages#

Suppose Stevie wants to send Alice an encrypted message. This can be challenging using symmetric ciphers where both Stevie and Alice need to secretly communicate the key before they can send encrypted messages. So how is this solved with asymmetric ciphers?

Well Alice will generate two keys, a private key and public key.

The public key will be used for encryption
The private key will be used for decryption

Alice will post the public key for everyone (including Stevie) to see. This means that the whole world can encrypt messages using the public key. For most people this won’t be useful because they’ll be able to encrypt a message, but they won’t be able to decrypt the message since they don’t have the second key, i.e. the private key. Only Alice will be able to decrypt messages because she is the only person with the private key. This means that Stevie can encrypt a secret message and send it to Alice knowing only Alice will be able to decrypt it!

Similarly, if Alice wants to send encrypted messages to Stevie, Stevie can create his own set of public/private keys and share the public key with Alice in plaintext. This means when Alice encrypts messages with Stevie’s public key, she know that only Stevie will be able to decrypt it.

2.6.2. Proof Of Identity#

Asymmetric cryptography can also be used to prove identity. For example, if Alice wants to publish something and guarantee that she is the author, she can encrypt it with her private key. Now everyone else in the world will be able to decrypt her work using the public key, but in doing so, they will know that Alice must have been the person to have originally encrypt it because she is the only person who knows her private key.

2.6.3. In Practice#

Unlike symmetric encryption, which relies on confusion and diffusion through substitution-permutation networks to scramble data, asymmetric encryption secures data by leveraging mathematical problems that are easy to compute in one direction but extremely difficult to reverse. These problems are known as one-way functions they are simple to perform but infeasible to invert without a secret key.

2.6.4. RSA Encryption#

RSA is named after its inventors Rivest, Shamir, and Adleman. The security of RSA is based on the difficulty of factoring large prime numbers. Currently, factoring a large number into two prime factors is not feasible.

Encryption

To encrypt a plaintext message \(p\), convert it to a number and compute:

\[c = p^x \mod z\]

Decryption

Using the private key, the recipient recovers the plaintext:

\[p = c^x \mod n\]

Key Generation

Keys for RSA are generated by:

Randomly generating two large numbers
Calculating \(n = p \times q\)
Selecting the public key \(x\) according to a fixed rule
Selecting the private key \(y\), which is the modular inverse of \(x\)

2.6.5. Elliptic Curve Cryptography#

ECC is based on the mathematics of elliptic curves. The key idea of ECC is that moving along these curves is extremely difficult to predict.

ECC is mostly used to establish a shared secret between two parties, which can be used as or to create a symmetric encryption key to transfer data.

Key Generation

Choose a large random integer \(d\), which is the private key
Compute the public key \(Q\) by multiplying \(d\) with a predefined starting point \(G\) on the curve i.e. \(Q=dG\)

Importantly the multiplication is not normal multiplication, instead it is a translation of the point along the curve according to specific rules.

Encryption

Suppose Alice and Bob want to establish a shared secret.

Alice uses Bob’s public key \(Q_B\) and her private key \(d_A\) to compute \(S = d_AQ_B\)
Bob uses Alice’s public key \(Q_A\) and his private key :math`d_B` to compute \(S = d_BQ_A\)

Both Bob and Alice now have a shared secret \(S\).

2.6.6. Speed#

Asymmetric encryption is typically slower than symmetric encryption because the operations involved such as modular exponentiation or elliptical curve multiplication are computationally expensive.

Therefore asymmetric encryption is generally not suitable for cases where high speed encryption is required such as encrypting whole files or transmitting data over a network.

2.6.7. Data Size and Key Size#

Both RSA and ECC can only encrypt as many bits are used for the key e.g. if the key is 128 bits then only 128 bits of data can be encrypted.

Therefore asymmetric encryption is generally not suitable for cases with large amounts of data such as encrypting whole files.

2.6.8. Combining Asymmetric and Symmetric Encryption#

Because of the issues with asymmetric encryption the usual protocol is to:

Use an asymmetric encryption algorithm to establish a symmetric key between two parties
Encrypt and decrypt the bulk of the data using the symmetric key

2.6.9. Recommended Video#

Demo: Crypto Module - Asymmetric

We’ve provided you with an updated crypto module that also that implements Asymmetric-key encryption. This page serves to explain how to use these new features

Note

A copy of this module has been provided in the files for this page.

Generating Keys

The static method Asymmetric.generate_keys returns:

a new randomly generated private key as a str
a new randomly generated public key as a str

Example

from crypto import Asymmetric

private_key, public_key = Asymmetric.generate_keys()

print(public_key)

Encrypting

The static method Asymmetric.encrypt(message, public_key):

accepts two parameters:
- message which is the str to encrypt
- public_key which is a public key str previously generated by Asymmetric.generate_keys
returns the cipher text as a str.

Example

from crypto import Asymmetric

message = "SECRET"
public_key = "1xzcBiDwPPAsUVScnms_3aw8APdFz9C1e_jrxm0rXhM="

ciphertext = Asymmetric.encrypt(message, public_key)

print(ciphertext)

Decrypting

The static method Asymmetric.decrypt(encrypted, private_key):

accepts two parameters:
encrypted which is the cipher text
private_key which is a private key str previously generated by Asymmetric.generate_keys
returns the cipher text as a str.

Example

from crypto import Asymmetric

ciphertext = "gAAAAABnxp7a2nQKoa87xg6So-XyEN7DYHU-0g1OS_PWSra2Fkp54eukT1OMYQKoGhkHuAeLrSO1p_6Ktz21gVIF631oyT8Ldg=="
private_key = "1xzcBiDwPPAsUVScnms_3aw8APdFz9C1e_jrxm0rXhM="

plaintext = Asymmetric.decrypt(ciphertext, private_key)

print(plaintext)

Code Samples

demo.py#

from crypto import Asymmetric

# Generate keys
private_key, public_key = Asymmetric.generate_keys()
print("Public key:", public_key)
print("\nPrivate key:", private_key,)

# Encrypting
message = "SECRET"
ciphertext = Asymmetric.encrypt(message, public_key)
print("\nCiphertext:", ciphertext)

# Decrypting
plaintext = Asymmetric.decrypt(ciphertext, private_key)
print("\nPlaintext:", plaintext)

crypto.py

crypto.py#

from typing import List
from cryptography.hazmat.primitives.asymmetric import rsa, padding as asym_padding
from cryptography.hazmat.primitives import hashes, serialization
import base64
from cryptography.fernet import Fernet

class Symmetric:
    @staticmethod
    def generate_key() -> str:
        # Returns a Base64-encoded key as an ASCII string
        return Fernet.generate_key().decode('ascii')

    @staticmethod
    def encrypt(message: str, key: str) -> str:
        if not isinstance(message, str):
            raise TypeError("message must be a string")
        if not isinstance(key, str):
            raise TypeError("key must be a string")
        if len(message) == 0:
            raise ValueError("message must not be empty")

        try:
            message_bytes = message.encode('ascii')
        except Exception as e:
            raise ValueError("Failed to encode message in ASCII") from e

        try:
            key_bytes = key.encode('ascii')
        except Exception as e:
            raise ValueError("Failed to encode key in ASCII") from e

        return Fernet(key_bytes).encrypt(message_bytes).decode('ascii')

    @staticmethod
    def decrypt(encrypted: str, key: str) -> str:
        if not isinstance(encrypted, str):
            raise TypeError("encrypted must be a string")
        if not isinstance(key, str):
            raise TypeError("key must be a string")

        try:
            encrypted_bytes = encrypted.encode("ascii")
        except Exception as e:
            raise ValueError("Failed to encode encrypted message in ASCII") from e

        try:
            key_bytes = key.encode('ascii')
        except Exception as e:
            raise ValueError("Failed to encode key in ASCII") from e

        return Fernet(key_bytes).decrypt(encrypted_bytes).decode('ascii')


class Asymmetric:
    @staticmethod
    def generate_keys() -> List[str]:
        # Generate a new RSA key pair
        private_key_obj = rsa.generate_private_key(
            public_exponent=65537,
            key_size=1024
        )
        public_key_obj = private_key_obj.public_key()

        # Serialize the private key to DER format
        der_private = private_key_obj.private_bytes(
            encoding=serialization.Encoding.DER,
            format=serialization.PrivateFormat.PKCS8,
            encryption_algorithm=serialization.NoEncryption()
        )

        # Serialize the public key to DER format
        der_public = public_key_obj.public_bytes(
            encoding=serialization.Encoding.DER,
            format=serialization.PublicFormat.SubjectPublicKeyInfo
        )

        # Encode the DER bytes into Base64 strings
        b64_private = base64.b64encode(der_private).decode('utf-8')
        b64_public = base64.b64encode(der_public).decode('utf-8')

        return b64_private, b64_public

    @staticmethod
    def encrypt(message: str, public_key: str) -> str:
        if not isinstance(message, str):
            raise TypeError("message must be a string")
        if not isinstance(public_key, str):
            raise TypeError("public_key must be a string")

        message_bytes = message.encode('utf-8')


        # Validate and decode the Base64 public key string
        try:
            der_public_bytes = base64.b64decode(public_key)
        except Exception as e:
            raise ValueError("public_key is not valid Base64") from e

        try:
            loaded_public_key = serialization.load_der_public_key(der_public_bytes)
        except Exception as e:
            raise ValueError("Failed to load public key from DER bytes") from e

        # Determine maximum allowed message length.
        # The formula for RSA OAEP is: key_size_in_bytes - 2 * (hash digest size) - 2.
        hash_algo = hashes.SHA256()
        max_length = (loaded_public_key.key_size // 8) - 2 * hash_algo.digest_size - 2

        if len(message_bytes) > max_length:
            raise ValueError(
                "Message too long for RSA encryption with a {}-bit key and SHA256 OAEP padding; "
                "maximum is {} bytes, got {} bytes".format(
                    loaded_public_key.key_size, max_length, len(message_bytes)
                )
            )

        encrypted_message = loaded_public_key.encrypt(
            message_bytes,
            asym_padding.OAEP(
                mgf=asym_padding.MGF1(algorithm=hashes.SHA256()),
                algorithm=hashes.SHA256(),
                label=None
            )
        )

        return base64.b64encode(encrypted_message).decode('utf-8')

    @staticmethod
    def decrypt(encrypted: str, private_key: str) -> str:
        if not isinstance(encrypted, str):
            raise TypeError("encrypted must be a string")
        if not isinstance(private_key, str):
            raise TypeError("private_key must be a string")

        # Validate and decode the Base64 encrypted message string
        try:
            encrypted_bytes = base64.b64decode(encrypted)
        except Exception as e:
            raise ValueError("encrypted message is not valid Base64") from e

        # Validate and decode the Base64 private key string
        try:
            der_private_bytes = base64.b64decode(private_key)
        except Exception as e:
            raise ValueError("private_key is not valid Base64") from e

        try:
            loaded_private_key = serialization.load_der_private_key(
                der_private_bytes,
                password=None
            )
        except Exception as e:
            raise ValueError("Failed to load private key from DER bytes") from e

        decrypted_bytes = loaded_private_key.decrypt(
            encrypted_bytes,
            asym_padding.OAEP(
                mgf=asym_padding.MGF1(algorithm=hashes.SHA256()),
                algorithm=hashes.SHA256(),
                label=None
            )
        )

        return decrypted_bytes.decode('utf-8')

Asymmetric-key Cryptography

Contents

2.6. Asymmetric-key Cryptography#

2.6.1. Sending Encrypted Messages#

2.6.2. Proof Of Identity#

2.6.3. In Practice#

2.6.4. RSA Encryption#

2.6.5. Elliptic Curve Cryptography#

2.6.6. Speed#

2.6.7. Data Size and Key Size#

2.6.8. Combining Asymmetric and Symmetric Encryption#

2.6.9. Recommended Video#