2
\$\begingroup\$

I'm working my way through the finger exercises in John Guttag's book Introduction to Python Programming, third edition. The following finger exercise on page 143 describes encryption/decryption with a book cipher. The first exercise was to implement decoder and decrypt in the same style as encryption is working.

The book mentions this bug and gives the task to implement a solution like they hinted at:

The bug:

When a character occurs in plain text but not in the book, something bad happens. The code_keys dictionary assigns -1 to each such character, and decode_keys assigns -1 to the last character in the book, whatever that may be.

The solution:

Create a new book by appending something to the original book.

My solution new_book uses a lambda function to be in line with the rest of the code. But this overturns the principle of encryption, if the plain text is needed during encryption and decryption

# Mapping individual, unique letters of plaintext to index number
gen_code_keys = (lambda book, plain_text:
                 {c: str(book.find(c)) for c in plain_text})

# Slicing operator at the end to remove the first '*' at the beginning
encoder = (lambda code_keys, plain_text:
           "".join(["*" + code_keys[c] for c in plain_text])[1:])

# Encrypt plain_text by giving the encoder a book for indexing
encrypt = (lambda book, plain_text:
           encoder(gen_code_keys(book, plain_text), plain_text))

# Decode key generator analogue to gen_code_keys
gen_decode_keys = (lambda book, cipher:
                   {c: book[int(c)] for c in cipher.split("*")})

# Implement decoder by looping through all numbers in cipher
decoder = (lambda decode_keys, cipher:
           "".join((decode_keys[c] for c in cipher.split("*"))))

# Decrypting the cipher analog to encrypt function
decrypt = (lambda book, cipher:
           decoder(gen_decode_keys(book, cipher), cipher))

Don_Quixote = "In a village of La Mancha, the name of which I have no " \
    "desire to call to mind, there lived not long since one of those " \
    "gentlemen that keep a lance in the lance-rack, an old buckler, a lean " \
    "hack, and a greyhound for coursing."

# --------------- My Solution --------------- #
# Creating new book with missing letters in book to fix cipher bug
new_book = (lambda book, plain_text:
            book + "".join([c for c in plain_text if c not in book]))

# plain text contains the letters: !ABENQjx
plain_text = "No joke, Abraham Boston had six beer. Everyone it Q!"

# Create new book by appending missing letter from plain_text
book = new_book(Don_Quixote, plain_text)

print(plain_text)
cipher = encrypt(book, plain_text)
print(cipher)
print(decrypt(book, cipher))

Ok, so I changed my code so far that I create the updated book with the missing characters appended before encrypting/decrypting. Thus I removed the function call new_book inside the encrypt and decrypt function. With that at least I don't need the plain_text in my decrypt function.

Are there further improvements I could make?

\$\endgroup\$
7
  • \$\begingroup\$ Just to be clear, the bug is in the original code that Guttag gives, and you are showing us your solution for that bug. Is that correct? \$\endgroup\$
    – Teepeemm
    Commented Nov 6, 2022 at 1:14
  • \$\begingroup\$ You’ll need to rethink your fix. If you and I agree on a book, and I send you an encrypted message, with characters that are not in the book, you won’t have my new book since it depends on the message I’m sending you, which I’ve only sent in encrypted form. You can’t decode it without know a-priori what the message is. \$\endgroup\$
    – AJNeufeld
    Commented Nov 6, 2022 at 2:16
  • \$\begingroup\$ @Teepeemm Exactly, the encryption implementation is given like this, the decryption is implemented by me. The bug is pointed out in the book. \$\endgroup\$
    – Wolric
    Commented Nov 6, 2022 at 10:36
  • \$\begingroup\$ @AJNeufeld that exactly is my issue. The book cipher decides on a book before. But if I change the book i need to communicate it to the receiver \$\endgroup\$
    – Wolric
    Commented Nov 6, 2022 at 10:46
  • \$\begingroup\$ Your implementation requires a new book with each message. The “book” should be agreed upon/exchanged through other means, not sent along with each and every encrypted message which is sent, as that totally breaks any resemblance of any security. Hence, the “need to rethink your fix,” such as (for example) by directly injecting the unencryptable characters directly in the cypher text: N*34*123*j*… But then: what if you want to encrypt numbers, and your book doesn’t contain all of the digits? \$\endgroup\$
    – AJNeufeld
    Commented Nov 6, 2022 at 16:45

1 Answer 1

1
\$\begingroup\$

It is difficult to answer this question. There is so much about the code I hate, but I have to restrict my review to only your code: the code after the # —- My solution -- # comment marker.

Forget lambda

lambda functions have their uses. This is not one of them. Compare this:

new_book = (lambda book, plain_text:
            book + "".join([c for c in plain_text if c not in book]))

with this:

def new_book(book, plain_text):
    return book + "".join([c for c in plain_text if c not in book])

They both do exactly the same thing: they create a function accepting two parameters, and assign that function to the identifier new_book. In my opinion, the latter is clearer; the reader can immediately tell a function is being defined. The indentation is less, and a level of parentheses has been removed.

Additionally, several language features are available with the def version - type-hints and """docstrings""" - which can further improve understandability.

def new_book(book: str, plain_text: str) -> str:
    """
    Create a new “book” to use for encryption and decryption,
    will is a duplicate of the original book, plus any letters
    in the `plain_text` message which are missing from the original
    book.
    """

    return book + "".join([c for c in plain_text if c not in book])

O(mn)

Your book has a certain number of characters. Let’s call that m. Your plain_text has a certain number of characters. Let’s call than n.

[c for c in plain_text if c not in book]

This loops n times, going through all of the letters of plain_text, and for each letter, it searches book for an occurrence of that letter. If a letter is not found in book, that is only determined after scanning through all m letters of the book. n outer loops iterations with up to m iterations in the inner loop means this is has a worst case of \$O(m*n)\$ operations. Potentially quite slow!

This worse case bound can be improved, but it requires a bit of preprocessing … which is easy with the def version of the function:

def new_book(book, plain_text):
    book_letters = set(book)
    return book + "".join([c for c in plain_text if c not in book_letters])

Turning book into a set of letters is an \$O(m)\$ operation. With that, c not in book_letters becomes an \$O(1)\$ operation. Repeated in the loop n times makes it \$O(n)\$, so the entire function becomes \$O(m + n)\$ … considerably faster.

But wait! While we’re at it, what is with the temporary list of characters [c …]? It is created just to be iterated over in the join(…). Why not just iterate without the temporary list creation?

def new_book(book, plain_text):
    book_letters = set(book)
    return book + "".join(c for c in plain_text if c not in book_letters)

Better solutions

Why add plain_text to the book? If you and you friend (or spy) have exchanged a book, and then you need to send a message with letters which were not in the book, you have to send a complete new_book to your friend (spy) … which could be intercepted making the encryption useless.

Plus, if a second message is sent with still different letters, yet another book would be necessary. A third message would require a third book, and so on! Decoding the cipher would require knowing which book was used to encode it (book1, book2, book3, …) — information which is not given.

It is a simple matter to expand the book without relying on plain_text. Just unconditionally add string.printable to the original book. This easily takes care of your missing !ABENQjx characters.

Except, it is still not a complete solution. Résumé would still result in -1 encodings. Adding the entire Unicode character set to book would be required, if you stayed with this approach. Instead, why not record the maximum value your book encoder returns, and return that value plus ord(c) for characters not in the book? When an encoded value exceeds the maximum value the book can decode, subtract that maximum, and use chr(#) to convert it back to the required character.

\$\endgroup\$
3
  • \$\begingroup\$ Exclusive use of lambda functions I consider good only in this task as a restriction, otherwise I agree with you that the function definition is cleaner and much better. Appending string.printable at the end didn't occur to me. At least that solves the problem for ascii characters. \$\endgroup\$
    – Wolric
    Commented Nov 8, 2022 at 23:29
  • \$\begingroup\$ By record the maximum value do you mean the max value found in the dictionary created by gen_code_keys for sending along or maybe attach to the cipher either at the beginning or at the end? Thus, requiring re-write of encoder and decoder to check of values of -1 when encoding and values greater than max value when decoding. \$\endgroup\$
    – Wolric
    Commented Nov 8, 2022 at 23:50
  • \$\begingroup\$ Yes, sort of. If you passed book as the plain_text to gen_code_keys, there is a maximum value it can generate, which would be up to len(book). No, not for sending along or attaching to cypher. Both sender and receiver have the book (singular), and can independently compute the value. \$\endgroup\$
    – AJNeufeld
    Commented Nov 9, 2022 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.