lab5-extra¶

`reverse_dic(d)`¶

Implement a function reverse_dic(d) that takes a dictionary d as the input argument and returns a dictionary r. If the dictionary d has a key k and an associated value v, then the dictionary r should have a key v and a value k.

(This is only expected to work for dictionaries that have a unique set of values although you do not need to check for this.)

Example:

>>> d = {'key1': 'value1'}
>>> r = reverse_dic(d)
>>> r
{'value1': 'key1'}
>>> reverse_dic({'dog': 10, 'cat': 20})
{10: 'dog', 20: 'cat'}

`encode(code, msg)`¶

Cryptography

Background¶

In this part of the practical, we work with simple cryptographic codes. Imagine Alice wants to send a secret message to Bob and does not want third parties to be able to understand the message. Here, we imagine that Alice and Bob can agree on a particular code before they need to exchange messages. The particular code is called the shared (secret) key.

Alice and Bob will use the same key to (i) encode a message (i.e. change from plain text to something less readable) and later (ii) decode the encoded message back into plain text. This is known as Symmetric-key cryptography, where the same key is used both for encryption (=encoding) and decryption (=decoding).

A code in this lab is a mapping that takes a (input) letter of the alphabet and maps it to a different (output) letter. We can represent such a code in Python through a dictionary where the keys of the dictionary are the input characters and the values the output characters.

For example, let’s consider the trivial code that replaces the letter ‘e’ in the input data with the letter ‘x’ in the output, and simultaneously replaces the letter ‘x’ in the input data with the letter ‘e’ in the output. This could be written as $\mathrm{e} \mapsto \mathrm{x}$ and $\mathrm{x} \mapsto \mathrm{e}$.

This can be represented by the dictionary {'x': 'e', 'e': 'x'}. The function code1() provides exactly this dictionary:

In [ ]: mycode = code1()

In [ ]: print(mycode)
{'x': 'e', 'e': 'x'}

We use the convention that if a character is not found in the keys of the dictionary, the character should not be changed by the code.

We now encode the string Hello World using the mapping described by mycode, and obtain the string Hxllo World.

(If we want to encode information without losing data, we need to make sure that no two keys map to the same value, i.e. the mapping has to be injective. Later, we want to reverse the mapping—to decode a coded message—and will need that the mapping has to be bijective, i.e. there has to be a one-to-one correspondence between input and output sets.)

Exercise (`encode`)¶

Write a function encode(code, msg) which takes the arguments:

code: this is a dictionary describing a code
msg: this is a string

The function should apply the mapping to each character of the string as described above and return the encoded output string.

We provide the example codes (code1(), code2(), …) below: you can copy and paste them to help with experimentation and the exercises.

Examples

In [  ]: code = code1()

In [  ]: print(code)
{'x': 'e', 'e': 'x'}

In [  ]: encode(code, "Hello World")
Out[  ]: 'Hxllo World'

In [  ]: encode(code, "Jimi Hendrix")
Out[  ]: 'Jimi Hxndrie'

In [  ]: encode(code, "The name xenon (Xe) is derived from greek for strange.")
Out[  ]: 'Thx namx exnon (Xx) is dxrivxd from grxxk for strangx.'

The sentence “the quick brown fox jumps over the lazy dog” contains all letters of the English alphabet, and might be useful here as an example:

In [ ]: msg = "the quick brown fox jumps over the lazy dog"

In [ ]: encode(code1(), msg)
Out[ ]: 'thx quick brown foe jumps ovxr thx lazy dog'

Let us try some other codes, for example code2() which maps $\mathrm{i} \mapsto \mathrm{s}$ and $\mathrm{s}\mapsto \mathrm{g}$ and $\mathrm{g}\mapsto \mathrm{i}$:

In [ ]: code2()
Out[ ]: {'g': 'i', 'i': 's', 's': 'g'}

In [ ]: encode(code2(), msg)
Out[ ]: 'the qusck brown fox jumpg over the lazy doi'

Moving on from these education examples, the code provided by function code3() makes the encoded message fairly unreadable:

In [22]: print(code3())
  {'!': '?', ' ': '$', '#': '.', '$': ' ', '.': '#', '?': '!', 'A': 'B', 'C': 'D',
   'B': 'C', 'E': 'F', 'D': 'E', 'G': 'H', 'F': 'G', 'I': 'J', 'H': 'I', 'K': 'L',
   'J': 'K', 'M': 'N', 'L': 'M', 'O': 'P', 'N': 'O', 'Q': 'R', 'P': 'Q', 'S': 'T',
   'R': 'S', 'U': 'V', 'T': 'U', 'W': 'X', 'V': 'W', 'Y': 'Z', 'X': 'Y', 'Z': 'A',
   'a': 'b', 'c': 'd', 'b': 'c', 'e': 'f', 'd': 'e', 'g': 'h', 'f': 'g', 'i': 'j',
   'h': 'i', 'k': 'l', 'j': 'k', 'm': 'n', 'l': 'm', 'o': 'p', 'n': 'o', 'q': 'r',
   'p': 'q', 's': 't', 'r': 's', 'u': 'v', 't': 'u', 'w': 'x', 'v': 'w', 'y': 'z',
   'x': 'y', 'z': 'a'}

In [23]: msg
Out[23]: 'the quick brown fox jumps over the lazy dog'

In [24]: encode(code3(), msg)
Out[24]: 'uif$rvjdl$cspxo$gpy$kvnqt$pwfs$uif$mbaz$eph'

Appendix: example code mappings¶

def code0():
    """A trivial code - no change."""
    return {}


def code1():
    """A very simple example (symmetric)."""
    return {"e": "x", "x": "e"}


def code2():
    """A simple example i->s, s->g and g->i."""
    return {"i": "s", "s": "g", "g": "i"}


def code3():
    """A more complicated code."""
    dic = {}
    # lower case letters
    dic["z"] = "a"
    for i in range(ord("a"), ord("z")):
        dic[chr(i)] = chr(i + 1)
    # upper case letters
    dic["Z"] = "A"
    for i in range(ord("A"), ord("Z")):
        dic[chr(i)] = chr(i + 1)
    # space, stop and some other special characters
    dic[" "] = "$"
    dic["."] = "#"
    dic["#"] = "."
    dic["$"] = " "
    dic["?"] = "!"
    dic["!"] = "?"
    return dic


def check_code_is_reversible(dic):
    """Given a dictionary used as a code mapping, this function checks
    whether the set of keys is the same set of values: if the elements
    in the keys are the same unique set as those in the values, then
    this mapping is bijective (the set of values is then actually a
    permutation of the set of input values) and can be inverted.

    If this is not the case, some debug information is printed, and a
    ValueError exception raised.
    """

    unique_keys = set()
    unique_vals = set()
    for key, val in dic.items():
        unique_keys.add(key)
        unique_vals.add(val)
    if unique_vals != unique_keys:
        print("Code is not reversible:")
        print("keys are   %s", sorted(unique_keys))
        print("values are %s", sorted(unique_vals))
        raise ValueError("Code is not reversible - stopping here")
    return True


def test_codes():
    """Check that codes defined above are reversible."""
    for c in (code0(), code1(), code2(), code3()):
        assert check_code_is_reversible(c)


secretmessage \
    = "Zpv$ibwf$tvddfttgvmmz$efdpefe$uijt$tfdsfu$nfttbhf#$Dpohsbuvmbujpot?"

`decode(code, encoded_mesg)`¶

Decoding an encrypted message (decode)

Write a function decode(code, encoded_msg) that takes a dictionary code that contains the mapping dictionary with which the string encoded_msg has been encoded. The function decode should return the decoded message.

Example:

In [ ]: msg = "the quick brown fox jumps over the lazy dog"

In [ ]: code2()
Out[ ]: {'g': 'i', 'i': 's', 's': 'g'}

In [ ]: x = encode(code2(), msg)

In [ ]: x
Out[ ]: 'the qusck brown fox jumpg over the lazy doi'

In [ ]: decode(code2(), x)
Out[ ]: 'the quick brown fox jumps over the lazy dog'

In [ ]: y = encode(code3(), msg)

In [ ]: y
Out[ ]: 'uif$rvjdl$cspxo$gpy$kvnqt$pwfs$uif$mbaz$eph'

In [ ]: decode(code3(), y)
Out[ ]: 'the quick brown fox jumps over the lazy dog'

Hints: Once you have the function reverse_dic and encode defined, you can decode a coded message by using the reversed code dictionary in the encode function:

In [ ]: msg = "the quick brown fox jumps over the lazy dog"

In [ ]: encoded = encode(code2(), msg)

In [ ]: encoded
Out[ ]: 'the qusck brown fox jumpg over the lazy doi'

In [ ]: code2_reversed = reverse_dic(code2())

In [ ]: encode(code2_reversed, encoded)
Out[ ]: 'the quick brown fox jumps over the lazy dog'

Can you now decode the message:

Zpv$ibwf$tvddfttgvmmz$efdpefe$uijt$tfdsfu$nfttbhf#$Dpohsbuvmbujpot?

which has been encoded with the mapping provided by function code3?

Please include the extra tasks in your file lab5.py and submit as lab5 assignment.

Back to lab5.

End of lab5-extra.

lab5-extra¶

reverse_dic(d)¶

encode(code, msg)¶