Cybersecurity - CS1302

CS1302 Introduction to Computer Programming

%reload_ext divewidgets

Python is a popular tool among hackers and engineers. In this lab, you will learn Cryptology in cybersecurity, which covers

Cryptography: Encryption and decryption using a cipher.
Cryptanalysis: Devising an attack to break a cipher.

Caesar symmetric key cipher¶

We first implement a simple cipher called the Caesar cipher.

The Caesar cipher

Encrypt/decrypt a character¶

How to encrypt a character?

The following code encrypts a character char using a non-negative integer key.

cc_n = 1114112


def cc_encrypt_character(char, key):
    """
    Return the encryption of a character by an integer key using Caesar cipher.

    Parameters
    ----------
    char: str
        a unicode (UTF-8) character to be encrypted.
    key int:
        secret key to encrypt char.
    """
    char_code = ord(char)
    shifted_char_code = (char_code + key) % cc_n
    encrypted_char = chr(shifted_char_code)
    return encrypted_char

For example, to encrypt the letter 'A' using a secret key 5:

cc_encrypt_character("A", 5)

The character 'A' is encrypted to the character 'F' as follows:

ord(char) return the integer 65, which is the code point (integer representation) of the unicode of 'A'.
(char_code + key) % cc_n cyclic shifts the code by the key 5.
chr(shifted_char_code) converts the shifted code back to a character, which is 'F'.

Encryption
`char`	...	A	B	C	D	E	F	...
`ord(char)`	...	65	66	67	68	69	70	...
`(ord(char) + key) % cc_n`	...	70	71	72	73	74	75	...
`(chr(ord(char) + key) % cc_n)`	...	F	G	H	I	J	K	...

You may learn more about ord and chr from their docstrings:

help(ord)
help(chr)

How to decrypt a character?

Mathematically, we define the encryption and decryption of a character for Caesar cipher as

\begin{aligned} E(x,k) &:= x + k \mod n & \text{(encryption)} \\ D(x,k) &:= x - k \mod n & \text{(decryption),} \end{aligned}

(1)

where $x$ is the character code in $\{0,\dots,n\}$ and $k$ is the secret key. mod operator above is the modulo operator. In Mathematics, it has a lower precedence than addition and multiplication and is typeset with an extra space accordingly.

The encryption and decryption satisfy the recoverability condition

D(E(x,k),k) = x

(2)

so two people with a common secret key can encrypt and decrypt a character, but others without the key cannot. This defines a symmetric cipher.

The following code decrypts a character using a key.

def cc_decrypt_character(char, key):
    """
    Return the decryption of a character by the key using Caesar cipher.

    Parameters
    ----------
    char: str
        a unicode (UTF-8) character to be decrypted.
    key: int
        secret key to decrypt char.
    """
    char_code = ord(char)
    shifted_char_code = (char_code - key) % cc_n
    decrypted_char = chr(shifted_char_code)
    return decrypted_char

For instance, to decrypt the letter 'F' by the secret key 5:

cc_decrypt_character("F", 5)

The character 'F' is decrypted back to 'A' because (char_code - key) % cc_n reverse cyclic shifts the code by the key 5.

Encryption									Decryption
`char`	...	A	B	C	D	E	F	...	`(chr(ord(char) - key) % cc_n)`
`ord(char)`	...	65	66	67	68	69	70	...	`(ord(char) - key) % cc_n`
`(ord(char) + key) % cc_n`	...	70	71	72	73	74	75	...	`ord(char)`
`(chr(ord(char) + key) % cc_n)`	...	F	G	H	I	J	K	...	`char`

YOUR ANSWER HERE

Encrypt a plaintext and decrypt a ciphertext¶

Of course, it is more interesting to encrypt a string instead of a character. The following code implements this in one line.

def cc_encrypt(plaintext, key):
    """
    Return the ciphertext of a plaintext by the key using the Caesar cipher.

    Parameters
    ----------
    plaintext: str
        A unicode (UTF-8) message to be encrypted.
    public_key: int
        Public key to encrypt plaintext.
    """
    return "".join([chr((ord(char) + key) % cc_n) for char in plaintext])

The above function encrypts a message, referred to as the plaintext, by replacing each character with its encryption.
This is referred to as a substitution cipher.

def cc_decrypt(ciphertext, key):
    """
    Return the plaintext that encrypts to ciphertext by the key using Caesar cipher.

    Parameters
    ----------
    ciphertext: str
        message to be decrypted.
    key: int
        secret key to decrypt the ciphertext.
    """
    # YOUR CODE HERE
    raise NotImplementedError()

# tests
assert cc_decrypt(r"bcdefghijklmnopqrstuvwxyz{", 1) == "abcdefghijklmnopqrstuvwxyz"
assert cc_decrypt(r"Mjqqt1%\twqi&", 5) == "Hello, World!"

# HIDDEN

Brute-force attack¶

Create an English dictionary¶

You will launch a brute-force attack to guess the key that encrypts an English text. The idea is simple:

You try decrypting the ciphertext with different keys, and
see which of the resulting plaintexts make the most sense (most English-like).

To check whether a plaintext is English-like, we need to have a list of English words. One way is to type them out but this is tedious. Alternatively, we can obtain the list from the Natural Language Toolkit (NLTK):

!pip install nltk

import nltk

nltk.download("words")
from nltk.corpus import words

words.words() returns a list of words. We can check whether a string is in the list using the operator in.

for word in "Ada", "ada", "Hello", "hello":
    print("{!r} in dictionary? {}".format(word, word in words.words()))

However, there are two issues:

Checking membership is slow for a long list.
Both 'Hello' and 'ada' are English-like but not in the words list.

# YOUR CODE HERE
raise NotImplementedError()

# tests
assert isinstance(dictionary, set) and len(dictionary) == 234377
assert all(word in dictionary for word in ("ada", "hello"))
assert all(word not in dictionary for word in ("Ada", "hola"))

# HIDDEN

Identify English-like text¶

To determine how English-like a text is, we calculate the following score:

\frac{\text{number of English words in the text}}{\text{number of tokens in the text}}

(3)

where tokens are substrings, not necessarily English words, separated by white space characters in the text.

def tokenizer(text):
    """Returns the list of tokens of the text."""
    return text.split()


def get_score(text):
    """Returns the fraction of tokens which appear in dictionary."""
    tokens = tokenizer(text)
    words = [token for token in tokens if token in dictionary]
    return len(words) / len(tokens)


# tests
get_score("hello world"), get_score("Hello, World!")

As shown in the tests above, the code fails to handle text with punctuations and uppercase letters properly.
In particular,

while get_score recognizes hello world as English-like and returns the maximum score of 1,
it fails to recognize Hello, World! as English-like and returns the minimum score of 0.

Why? Every word in dictionary

are in lowercase, and
have no leading/trailing punctuations.

import string


def tokenizer(text):
    """Returns the list of tokens of the text such that
    1) each token has no leading or trailing spaces/punctuations, and
    2) all letters in each token are in lowercase."""
    # YOUR CODE HERE
    raise NotImplementedError()

# tests
assert tokenizer("Hello, World!") == ["hello", "world"]
assert get_score("Hello, World!") >= 0.99999
assert tokenizer("Do you know Jean-Pierre?") == ["do", "you", "know", "jean-pierre"]
assert get_score("Do you know Jean-Pierre?") >= 0.99999

# HIDDEN

Launch a brute-force attack¶

def cc_attack(ciphertext, threshold=0.6):
    """Returns a generator that generates the next guess of the key that
    decrypts the ciphertext to a text with get_score(text) at least the threshold.
    """
    # YOUR CODE HERE
    raise NotImplementedError()

# tests
ciphertext = cc_encrypt("Hello, World!", 12345)
key_generator = cc_attack(ciphertext)
key_guess = next(key_generator)
assert key_guess == 12345
text = cc_decrypt(ciphertext, key_guess)
print("guess of the key: {}\nscore: {}\ntext :{}".format(key_guess, get_score(text), text))

# HIDDEN

Challenge¶

Another symmetric key cipher is columnar transposition cipher. A transposition cipher encrypts a text by permuting instead of substituting characters.

Exercise 6

Study and implement the irregular case of the columnar transposition cipher as described in the Wikipedia page. Define the functions

ct_encrypt(plaintext, key) for encryption, and
ct_decrypt(ciphertext, key) for decryption.

You can assume the plaintext is in uppercase and has no spaces/punctuations.

Hint

See the test cases for examples of plaintext, key, and the corresponding ciphertext. The following is a solution template:

def argsort(seq):
    '''A helper function that returns the tuple of indices that would sort the
    sequence seq.'''
    return tuple(x[0] for x in sorted(enumerate(seq), key=lambda x: x[1]))


def ct_idx(length, key):
    '''A helper function that returns the tuple of indices that would permute 
    the letters of a message according to the key using the irregular case of 
    columnar transposition cipher.'''
    seq = tuple(range(length))
    return [i for j in argsort(key) for i in ___]


def ct_encrypt(plaintext, key):
    '''
    Return the ciphertext of a plaintext by the key using the irregular case
    of columnar transposition cipher.

    Parameters
    ----------
    plaintext: str
        a message in uppercase without punctuations/spaces.
    key: str
        secret key to encrypt plaintext.
    '''
    return ''.join([plaintext[i] for i in ct_idx(len(plaintext), key)])


def ct_decrypt(ciphertext, key):
    '''
    Return the plaintext of the ciphertext by the key using the irregular case
    of columnar transposition cipher.

    Parameters
    ----------
    ciphertext: str
        a string in uppercase without punctuations/spaces.
    key: str
        secret key to decrypt ciphertext.
    '''
    return ___

# YOUR CODE HERE
raise NotImplementedError()

# tests
key = "ZEBRAS"
plaintext = "WEAREDISCOVEREDFLEEATONCE"
ciphertext = "EVLNACDTESEAROFODEECWIREE"
assert ct_encrypt(plaintext, key) == ciphertext
assert ct_decrypt(ciphertext, key) == plaintext

# HIDDEN