[SOLVED] CSE220-Programming Assignment 2

For this assignment you will be implementing several algorithms for working with ASCII strings, as well as encryption and decryption algorithms for a variant of the homophonic substitution ciphe​              r. In this​              cipher, some of the letters from the plaintext​      ​ (the input message) can be replaced with one of several different possible letters to generate the ciphertext​       ​ (the encrypted output message). This is in contrast with a traditional substitution cipher, wherein there is only one option to substitute for each plaintext letter. If you are unfamiliar with substitution ciphers, we recommend you briefly review the Wikipedi​   a article on the topic.​

 

As a concrete example, suppose the plaintext alphabet​ ​ is:

 

aaaaaaabcdeeeeeeeeefghhiiiijklmnnnnnoooooopqrrrsttttttttuvwxyz

 

and the ciphertext alphabet​ ​ is:

 

WhatsSewolfImAOF20BUCVD19ZEdinbcgjkpqruvxyzGHJKLMNPQRTXY345678

 

The above alphabets indicate that ‘a’ can be replaced any of the characters “WhatsSe​         ” in the​ ciphertext; ‘n’ can be replaced with any of the characters “cgjkp​               ”, and so on;​

 

In our cipher, encryption and decryption require two secret pieces of information: a keyphrase​         ​, which is intended to be an easily-remembered phrase or sentence, and a longer corpus​     ​, which is at least several sentences of text from a document that can be easily obtained (e.g., from a library, the Web, etc.) In a homophonic substitution cipher, the idea is that a letter which occurs frequently in English text can be substituted with any of several possible characters, not just the same character every time. This makes it harder to crack the code. Less-frequently occurring letters might be substituted with only a handful of letters in the ciphertext, or perhaps only even one. The corpus text is used in the frequency analysis to decide how many different possible substitutions could be performed for each plaintext letter. The keyphrase determines the order of the symbols in the ciphertext alphabet, which contains the characters which will be substituted for the plaintext letters. All of this will become clearer as we work through an example.

 

Encryption Phase 1: Create the Ciphertext Alphabet using the Keyphrase

 

Our ciphertext alphabet contains 62 symbols that will be used to replace the plaintext letters: 26 lowercase letters, 26 uppercase letters and 10 digit characters provide the 62 symbols.

 

1. Initialize an empty ciphertext alphabet consisting of 62 bytes.
2. Draw letters and digit characters one at a time from the keyphrase, left-to-right, possibly adding each character to the ciphertext alphabet. Ignore spaces and punctuation marks.
   1. If a drawn character has not already been added to the ciphertext alphabet, then add it to the end.
   2. Otherwise, skip that character and move on to the next character of the keyphrase.
3. After drawing all alphanumeric characters from the keyphrase, determine which lowercase letters do not appear in the ciphertext alphabet. Add these missing letters in alphabetical order to the ciphertext alphabet.
4. Repeat step 3, but for uppercase letters.
5. Repeat step 3. but for digit characters.

 

As an example, suppose the keyphrase is:

 

What’s a Seawolf? I’m a SeAwOlF! Fall 2020 SBU: COVID-19 Zoom Edition

 

After step 2, the (incomplete) ciphertext alphabet will consist of these characters:

 

WhatsSewolfImAOF20BUCVD19ZEdin

 

After step 3, the missing lowercase letters have been appended to yield:

 

WhatsSewolfImAOF20BUCVD19ZEdinbcgjkpqruvxyz​

 

After step 4, the missing uppercase letters have been appended to yield:

 

WhatsSewolfImAOF20BUCVD19ZEdinbcgjkpqruvxyz​  GHJKLMNPQRTXY​

 

After step 5, the missing digit characters have been appended to yield the final ciphertext alphabet:

 

WhatsSewolfImAOF20BUCVD19ZEdinbcgjkpqruvxyz​  GHJKLMNPQRTXY​                                                                   345678​

 

Encryption Phase 2: Compute the Frequency of Letters in the Corpus and Assign Substitutions

 

In this phase, we first count the number of times each letter occurs in the corpus, ignoring case. Then, we sort the letters into descending order by count. In other words, the most frequently occurring letters are placed near the front of the sorted alphabet. If two letters have the same frequency, the one with the lower ASCII value is placed in front of the other.

 

Consider the following text, used as the corpus:

 

Four score and seven years ago our fathers brought forth on this continent a new nation, conceived in Liberty, and dedicated to the proposition that all men are created equal. Now we are engaged in a great civil war, testing whether that nation or any nation so conceived and so dedicated, can long endure. We are met on a great battle-field of that war. We have come to dedicate a portion of that field, as a final resting place for those who here gave their lives that that nation might live. It is altogether fitting and proper that we should do this.

 

This text generates the following case-insensitive counts:

 

a 46   b 3   c 14   d 21   e 57   f 9   g 13   h 23   i 32   j 0   k

0 l 14   m 4   n 35   o 37   p  6   q 1   r 28   s 16   t 52   u 6   v

8 w  8   x 0   y  3   z  0

 

Sorting the letters according the criteria explained above yields the string:

 

etaonirhdsclgfvwpumbyqjkxz

 

Next, to generate the plaintext alphabet, we duplicate the most frequently occurring letter eight times, the second most frequently occurring letter seven times, …, and the eighth most frequently occurring letter once. (Note that 8+7+6+5+4+3+2+1 = 36 and that 26+36 = 62.) For our example, we obtain:

 

aaaaaaabcdeeeeeeeeefghhiiiijklmnnnnnoooooopqrrrsttttttttuvwxyz

 

Note that ‘e’ is repeated eight times, the ‘t’ is repeated seven times, the ‘a’ is repeated six times, etc. The ‘h’, which is the eighth most frequently occurring letter, is repeated only once. All other letters appear only once each. Note that the plaintext alphabet contains only lowercase letters. This means that any uppercase letters in the input message must be changed to lowercase during the encryption process.

 

Encryption Phase 3: Perform Substitutions to Generate the Ciphertext

 

Now we lay the plaintext alphabet on top of the ciphertext alphabet:

 

aaaaaaabcdeeeeeeeeefghhiiiijklmnnnnnoooooopqrrrsttttttttuvwxyz

WhatsSewolfImAOF20BUCVD19ZEdinbcgjkpqruvxyzGHJKLMNPQRTXY345678

 

We see that, in theory, ‘a’ can be replaced with any of the seven characters from the string “WhatsSe”; ‘b’ can be replaced only with ‘w’; ‘c’ can be replaced only with ‘o’; ‘d’ can be replaced only with ‘l’; ‘e’ can be replaced with any of the nine characters from “fImAOF20B”, and so on. To make this selection process deterministic (non-random), we will use the index of a character from the plaintext modulo ​     ​the number of instances of a character to choose the substituted character from the ciphertext alphabet. For instance, suppose there is a letter ‘e’ at index 12 of the plaintext. Note that there are nine instances of ‘e’ in the ciphertext alphabet. 12 mod 9 = 3, so we take the character at index 3 of the string

“fImAOF20B”, which is ‘A’. Note that in all computations we assume that indexes strings and substrings are 0-based. Namely, the leftmost character of the plaintext is 0; the characters of the plaintext alphabet and ciphertext alphabet are indexed 0 through 61 (inclusive); substrings drawn from the ciphertext alphabet are indexed starting from 0, etc. Finally, note that only lowercase letters from the plaintext are encrypted; all other characters (punctuation marks, spaces, etc.) are merely copied to the ciphertext unencrypted. We will assume for this assignment that the plaintext message will never contain digits.

 

Part 1: Compute the Length of a Null-terminated String

 

int strlen(string str)

 

This function takes a null-terminated string (possibly empty) and returns its length (i.e., the number of characters in the string). The null-terminator is guaranteed to be present and is not counted in the length.

 

The function takes one argument:

• str:​ the starting address of a null-terminated string

 

Returns in $v0:

• The number of characters in the string, not including the null-terminator.

 

Additional requirements:

• The function must not write any changes to main memory.

 

Examples:

 

Function Argument	Return Value
“Wolfie Seawolf!!! 2020??”	24
“MIPS”	4
“”      (​ empty string, containing only \0)	0

 

 

Part 2: Find the Index of a Character in a Null-terminated String

 

int index_of(string str, char ch, int start_index)

 

The function returns the index of the first instance of ​printable character​ ​ch​ in the null-terminated string str​, starting the search at index ​start_index​ and moving to the right (towards higher indexes). If the character is not present in the string or if ​start_index​ is not a valid index for ​str​, the function returns -1. It is possible that the string is empty.

 

The function takes the following arguments, in this order:

• str​: the starting address of a null-terminated string
• ch​: the printable character to search for
• start_index​: the index at which the search begins

 

Returns in $v0:

• The index of the leftmost occurrence of ​ch​ in ​str​ found at index ​start_index​ or to the right of ​start_index​; or -1 if ​ch​ is not found during the search or if ​start_index​ is not a valid index for ​str​.

 

Additional requirements:

• The function must not write any changes to main memory.
• The function must call ​strlen​.

 

Examples:

 

Function Arguments	Return Value
“CSE 220 COVID-19 Edition”, ‘V’, 3	10
“CSE 220 COVID-19 Edition”, ‘V’, 13	-1
“CSE 220 COVID-19 Edition”, ‘n’, 5	23
“CSE 220 COVID-19 Edition”, ‘n’, -5	-1
“”, ‘z’, 0	-1

 

 

Part 3: Convert a Null-terminated String to Lowercase

 

int to_lowercase(string str)

 

This function takes a null-terminated string (possibly empty) and changes all of its uppercase letters to lowercase. All other characters in the string remain unchanged.

 

The function takes one argument:

• str:​ the starting address of a null-terminated string

 

Returns in $v0:

• The number of letters changed from uppercase to lowercase.

 

Additional requirements:

• The function must not write any changes to main memory except for str​ .​

 

Examples:

 

Function Arguments	Return Value
“Stony Brook University”	3
“UNIVERSITY”	10
“2020-2021”	0
“”	0

 

 

Part 4: Generate the Ciphertext Alphabet from a Keyphrase

 

int generate_ciphertext_alphabet(string ciphertext_alphabet,                                   string keyphrase)

 

This function generates the ciphertext alphabet as described in Encryption Phase 1 in the Preliminaries section of the document above. The function must null-terminate ciphertext_alphabet​        by writing a​      null-terminator at ciphertext_alphabet[62]​            .​

 

The function takes the following arguments, in this order:

• ciphertext_alphabet:​ an uninitialized buffer of 63 contiguous bytes of main memory where the function writes the ciphertext alphabet.
• keyphrase:​ a non-empty, null-terminated string to serve as the keyphrase

 

Returns in $v0:

• The number of unique, case-sensitive alphanumerical characters drawn from keyphrase​ .​

 

Additional requirements:

• The function must not write any changes to main memory except for ciphertext_alphabet​ .​ For example, the string keyphrase​               must remain unchanged.​

 

Example #1:

 

keyphrase = “Stony Brook University” Resulting ciphertext_alphabet:​

“StonyBrkUivesabcdfghjlmpquwxzACDEFGHIJKLMNOPQRTVWXYZ0123456789

”

 

Returns in $v0: 13​

 

Example #2:

 

keyphrase = “Monday, September 21st, 2020 4:39 PM EDT” Resulting ciphertext_alphabet​    :​

“MondaySeptmbr21s0439PEDTcfghijklquvwxzABCFGHIJKLNOQRUVWXYZ5678

”

 

Returns in $v0: 24​

 

Example #3:

 

keyphrase = “suPeRcalIfrAgiListICexPiaLIdoCIOus” Resulting ciphertext_alphabet​   :​

“suPeRcalIfrAgiLtCxdoObhjkmnpqvwyzBDEFGHJKMNQSTUVWXYZ0123456789”

 

Returns in $v0: 21​

 

 

Part 5: Count the Occurrences of Each Lowercase Letter in a String

 

int count_lowercase_letters(int[] counts, string message)

 

This function counts the number of times each lowercase letter occurs in ​message​, storing those counts in ​counts​. Specifically, ​counts[0]​ stores the number of instances of ‘a’ in ​message​, counts[1]​ the number of instances of ‘b’ in ​message​, etc. Note that each element in ​counts​ is a 4-byte integer. ​counts​ is not initialized with zeros when the function is called.

 

The function takes the following arguments, in this order:

• counts​: an uninitialized buffer of 26 contiguous words of main memory where the function writes the counts of the lowercase letters.
• message​: a null-terminated string (possibly empty) that could consist of any characters with ASCII codes 32 through 126, inclusive

 

Returns in $v0:

• The total number of lowercase letters in ​message​.

 

Additional requirements:

• The function must not write any changes to main memory except for ​counts​. For example, the string ​message​ must remain unchanged.

 

Example #1:

 

message = “The specialization in artificial intelligence and data science emphasizes modern approaches for building intelligent systems using machine learning.”

 

Resulting ​counts​: ​12 1 7 4 16 2 5 4 18 0 0 8 4 14 4 4 0 5 9 7 2 0 0 0 1 2

 

which means:

 

a:12   b: 1   c: 7   d: 4   e:16   f: 2   g: 5   h: 4   i:18   j: 0   k: 0 l: 8   m: 4   n:14   o: 4   p: 4   q: 0   r: 5   s: 9   t: 7   u: 2   v: 0 w: 0   x: 0   y: 1   z: 2

 

Return value in $v0: ​129

 

Example #2:

 

message = “We can only see a short distance ahead, but we can see plenty there that needs to be done. -Alan Turing”

 

Resulting ​counts​: ​8 2 3 4 15 0 1 4 2 0 0 3 0 9 4 1 0 3 5 8 2 0 1 0 2 0

 

which means:

 

a: 8   b: 2   c: 3   d: 4   e:15   f: 0   g: 1   h: 4   i: 2   j: 0   k: 0 l: 3   m: 0   n: 9   o: 4   p: 1   q: 0   r: 3   s: 5   t: 8   u: 2   v: 0 w: 1   x: 0   y: 2   z: 0

 

Return value in $v0: ​77

 

 

Part 6: Sort the Letters of the Alphabet by Frequency

 

void sort_alphabet_by_count(string sorted_alphabet, int[] counts)

 

This function’s purpose is to sort the lowercase letters of the Latin alphabet using the numbers given in the ​counts​ array as the sorting key, storing that sorted alphabet in ​sorted_alphabet​.  The buffer sorted_alphabet​ is guaranteed to be at least 27 bytes in size. The 26-word ​counts ​array provides a non-negative integer count associated with each lowercase letter. Specifically, ​counts[0]​ is the count for ‘a’, ​counts[1]​ is the count for ‘b’, etc. The function sorts the contents of sorted_alphabet​ so that the letter with highest count is at index 0, the letter with second-highest count is at index 1, and so. When two or more letters have the same count, the letter with smallest ASCII value is placed before the others in ​sorted_alphabet​, the letter with second-smallest ASCII value immediately follows the letter with smallest ASCII value, etc. The function null-terminates sorted_alphabet​ by writing a null-terminator at ​sorted_alphabet[26]​.

 

The function takes the following arguments, in this order:

• sorted_alphabet​: an uninitialized buffer of 27 contiguous bytes of main memory.
• counts​: an array of 26 non-negative counts. Each integer is four bytes. Note that this array is not necessarily the output of the ​count_lowercase_letters​ function, so do not assume that when coding this function.

 

Additional requirements:

• The function must not write any changes to main memory except for ​sorted_alphabet​ and

counts​.

 

Example #1:

 

counts = 28 13 24 2 28 19 12 2 0 10 23 14 3 28 1 2 21 4 4 25 29 0 9 29 13 18

Resulting ​sorted_alphabet​: “​uxaentckqfzlbygjwrsmdhpoiv”

 

Example #2:

 

counts = 21 17 20 25 21 19 28 26 15 16 21 13 11 16 1 27 24 20 5 23 26 2 29 15 21 8

Resulting ​sorted_alphabet​: “wgphudqtaekycrfbjnixlmzsvo”​

 

Example #3:

 

counts = 23 26 29 1 20 9 15 30 24 20 23 7 17 15 5 4 17 14 12 24 14 1 0 4 14 6

Resulting ​sorted_alphabet​: “hcbitakejmqgnruysflzopxdvw”​

 

 

Part 7: Generate the Plaintext Alphabet from a Sorted Alphabet

 

void generate_plaintext_alphabet(string plaintext_alphabet,                                   string sorted_alphabet)

 

This function generates the 62-character plaintext alphabet from a sorted lowercase Latin alphabet using the algorithm described in Encryption Phase 2 under Preliminaries earlier in this document. The plaintext alphabet is written into the uninitialized ​plaintext_alphabet​ buffer, which is guaranteed to be at least 63 bytes in size. The function null-terminates ​plaintext_alphabet​ by writing a null-terminator at ​plaintext_alphabet[62]​. Briefly, the plaintext alphabet contains the lowercase letters of the Latin alphabet in alphabetical order, except that ​sorted_alphabet[0]​ is repeated 8 times in ​plaintext_alphabet​, ​sorted_alphabet[1]​ is repeated 7 times in plaintext_alphabet​, etc., all the way to ​sorted_alphabet[7]​, which is repeated once in plaintext_alphabet​. The remaining 18 letters of ​sorted_alphabet​ each appears once in plaintext_alphabet​.

 

The function takes the following arguments, in this order:

• plaintext_alphabet​: an uninitialized buffer of 63 contiguous bytes of main memory where the function writes the 62-character plaintext alphabet, ending with a null-terminator
• sorted_alphabet​: a null-terminated string containing the 26 lowercase letters of the Latin alphabet, in any order

 

Additional requirements:

• The function must not write any changes to main memory except for ​plaintext_alphabet and ​sorted_alphabet​.

 

Example #1:

 

sorted_alphabet = “egljhotupvfsxawqkrmzdyncib” Resulting ​plaintext_alphabet​:

“abcdeeeeeeeeefgggggggghhhhhijjjjjjklllllllmnoooopqrstttuuvwxyz

”

 

Example #2:

 

sorted_alphabet = “eznovrqbdatjghlwmskyipcxfu” Resulting ​plaintext_alphabet​:

“abbcdeeeeeeeeefghijklmnnnnnnnoooooopqqqrrrrstuvvvvvwxyzzzzzzzz

”

 

Example #3:

 

sorted_alphabet = “jmhoxqzgityudwsecvfalnkrbp”

Resulting plaintext_alphabet​  :​

“abcdefgghhhhhhhijjjjjjjjjklmmmmmmmmnoooooopqqqqrstuvwxxxxxyzzz

”

 

 

Part 8: Return the Ciphertext Character Substituted for a Letter from the Plaintext

 

int encrypt_letter(char plaintext_letter, int letter_index,

string plaintext_alphabet, string ciphertext_alphabet)

 

This function computes and returns the substitution of a plaintext letter for the ciphertext, given the plaintext letter itself, that letter’s index in the plaintext message, the plaintext alphabet as generated by generate_plaintext_alphabet and the ciphertext alphabet as generated by​  generate_ciphertext_alphabet. The substitution process is described in Encryption Phase 3 in​   the Preliminaries section of the document, above. Briefly, suppose the plaintext_letter​              (located​ at index letter_index​         of some plaintext) appears at indexes ​            i​ through ​ i+k​       of​          plaintext_alphabet. The function will return the character at location​               ciphertext_alphabet[i+(letter_index mod (k+1))]. Note that it is this function’s​ responsibility to determine the value of k​ for a given letter in ​ plaintext_alphabet​           .​

 

The function takes the following arguments, in this order:

• plaintext_letter:​ a lowercase letter
• letter_index:​ a non-negative integer
• plaintext_alphabet:​ the 62-character plaintext alphabet required to encrypt a plaintext message
• ciphertext_alphabet:​ the 62-character ciphertext alphabet required to encrypt a plaintext message

 

Returns in $v0:

• The encrypted letter or -1 if plaintext_letter​ is not a lowercase letter.​

 

Additional requirements:

• The function must not write any changes to main memory.

 

Example #1:

 

plaintext_letter = ‘u’ letter_index = 3 plaintext_alphabet =

“abbbbbbbbcdefffffffgggghiiijkklmnopqrstuuuuuvvvvvvwxxxxxxxxxyz

” ciphertext_alphabet =

“StonyBrkUivesNwYadfAmcbghjlpquxzCDEFGHIJKLMOPQRTVWXZ0123456789

”

 

Return value in $v0: 77​ (ASCII code for ​ ‘M’​ )​

 

Example #2:

 

plaintext_letter = ‘p’ letter_index = 46 plaintext_alphabet =

“abcdeeefghijkkkkkkkllllllmmnoppppppppqrstuvvvvvwxyyyyzzzzzzzzz

” ciphertext_alphabet =

“StonyBrkUivesNwYadfAmcbghjlpquxzCDEFGHIJKLMOPQRTVWXZ0123456789

”

 

Return value in $v0: 70​   (ASCII code for ​ ‘F’​ )​

 

Example #3:

 

plaintext_letter = ‘x’ letter_index = 37 plaintext_alphabet =

“abcccccdeeeeeeeeeffffffffgghijkkklmnoppppqrstuvwxxxxxxyzzzzzzz

” ciphertext_alphabet =

“StonyBrkUivesNwYadfAmcbghjlpquxzCDEFGHIJKLMOPQRTVWXZ0123456789

”

 

Return value in $v0: 87​ (ASCII code for ​ ‘W’​ )​

 

Example #4:

 

plaintext_letter = ‘n’ letter_index = 15 plaintext_alphabet =

“abccccccccdddddefghiiiiiijjjjjjjjjklmmnopqrstuvwwwwwwwxyyyyzzz

” ciphertext_alphabet =

“StonyBrkUivesNwYadfAmcbghjlpquxzCDEFGHIJKLMOPQRTVWXZ0123456789

”

 

Return value in $v0: 73​ (ASCII code for ​ ‘I’​ )​

 

 

Part 9: Encrypt a Plaintext Message using a Homophonic Substitution Cipher

 

int, int encrypt(string ciphertext, string plaintext, string keyphrase,                   string corpus)

 

This function encrypts the given ​non-empty​ plaintext message using the homophonic substitution cipher described earlier in the document, storing the resulting ciphertext in ​ciphertext​. Assume that the plaintext contains only letters, spaces and punctuation marks; no digits will be present in the plaintext. All arguments are assumed to be valid. The buffer for the ciphertext is guaranteed to be large enough to store the null-terminated ​ciphertext​. Note that the function returns two values.

 

The function takes the following arguments, in this order:

• ciphertext​: an uninitialized buffer to store the encrypted plaintext
• plaintext​: a ​non-empty​, null-terminated, string to be encrypted using the homophonic substitution cipher
• keyphrase​: a ​non-empty​, null-terminated keyphrase string used during the encryption process
• corpus​: a ​non-empty​, null-terminated corpus string used during the encryption process

 

The function implements the following algorithm:

1. Call ​to_lowercase​ on both ​plaintext​ and ​corpus​.
2. Allocate at least 26 words’ worth of memory on the stack to temporarily store the ​counts​ array needed in the following step. (How? Simply subtract however many bytes you want to allocate from $sp. Make sure the number of bytes you allocate is a multiple of 4.) Be sure to deallocate this memory later.
3. Call ​count_lowercase_letters(counts, corpus)​.
4. Allocate at least 27 bytes of memory on the stack to store the ​lowercase_letters​ string needed in the following step. Be sure to deallocate this memory later.
5. Call ​sort_alphabet_by_count(lowercase_letters, counts)​.
6. Allocate at least 63 bytes of memory on the stack to temporarily store the plaintext_alphabet​ string needed in the following step. Be sure to deallocate this memory later.
7. Call ​generate_plaintext_alphabet(plaintext_alphabet, lowercase_letters)​.
8. Allocate at least 63 bytes of memory on the stack to temporarily store the ciphertext_alphabet​ string needed in the following step. Be sure to deallocate this memory later.
9. Call ​generate_ciphertext_alphabet(ciphertext_alphabet, keyphrase)​.
10. In a loop, call ​encrypt_letter​ to encrypt each lowercase letter of ​plaintext​ and write the return value into ​ciphertext​. Each non-lowercase letter of ​plaintext​ should not be passed as an argument to ​encrypt_letter​, but should instead simply be copied to ​ciphertext​.
11. Null-terminate the ​ciphertext​

 

Returns in $v0:

• The number of lowercase letters that were encrypted during the encryption process.

 

Returns in $v1:

• The number of characters from the plaintext that were not encrypted and simply copied to ciphertext.​

 

Additional requirements:

• The function must not write any changes to main memory except as needed.
• The function must call the functions to_lowercase​ (twice), ​ count_lowercase_letters​ ,​ sort_alphabet_by_count, ​ generate_ciphertext_alphabet​ ,​ generate_plaintext_alphabet, and ​ encrypt_letter​ .​

 

Example #1:

 

plaintext = “Never trust a computer you can’t throw out a window. -Steve Wozniak”  keyphrase = “I’ll have you know that I stubbed my toe last week and only cried for 20 minutes.”

corpus = “When in the Course of human events, it becomes necessary for one people to dissolve the political bands which have connected them with another, and to assume among the powers of the earth, the separate and equal station to which the Laws of Nature and of Nature’s God entitle them, a decent respect to the opinions of mankind requires that they should declare the causes which impel them to the separation.”

 

Resulting ciphertext​     :​ “Dk5wQ 1Q4RW h yLCO4XnQ 8H4 yaE’3 VpQH6 L4V a 6qGoJ6.​

-R3n5t 6J9GqIA”

 

Return value in $v0: 53​

 

Return value in $v1: 14​

 

Example #2:

 

plaintext = “The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it. -Terry Pratchett”

keyphrase = “What’s the difference between ignorance and apathy? I don’t know and I don’t care.”

 

corpus = “Call me Ishmael. Some years ago – never mind how long precisely – having little or no money in my purse, and nothing particular to interest me on shore, I thought I would sail about a little and see the watery part of the world. It is a way I have of driving off the spleen and regulating the circulation.”

 

Resulting ciphertext​           :​ “Xjc 1UN4dDn 6xXj jW5vJk WJ ORcK GmKf, PI iO4TVn, mV​

0jW3 RwQREy 6mDE xKVlV1 NJ iMGqLk aDPJk aJf 2U8uHk 2Q R40 2jlJkV xK lZ.

-3rUT8 RThYijc23”

 

Return value in $v0: 111​

 

Return value in $v1: 29​

 

Example #3:

 

plaintext = “If debugging is the process of removing software bugs, then programming must be the process of putting them in. -Edsger Dijkstra”

keyphrase = “What is the sum of 12 and 37? The answer, CLEARLY, is 49!”

corpus = “It was the best of times, it was the worst of times, it was the age of wisdom, it was the age of foolishness, it was the epoch of belief, it was the epoch of incredulity, it was the season of Light, it was the season of Darkness, it was the spring of hope, it was the winter of despair, we had everything before us, we had nothing before us, we were all going direct to Heaven, we were all going direct the other way – in short, the period was so far like the present period, that some of its noisiest authorities insisted on its being received, for good or for evil, in the superlative degree of comparison only.”

 

Resulting ciphertext​            :​ “L7 e1iXTTAkT 9K MCu zFxsnGH x7 F2jxZEkT Gy7P0hDo iXTI,​

VCfk zFqTDhjj4kT jXKP in Mwm zFqsdKG q7 zXNOEkT VCnj Rk. -2eGTuD eAbcKSDt”

 

Return value in $v0: 105​

 

Return value in $v1: 23​

 

 

Part 10: Decrypt Ciphertext that was Encrypted using a Homophonic Substitution Cipher

 

int, int decrypt(string plaintext, string ciphertext, string keyphrase,                   string corpus)

 

This function decrypts a ciphertext message that was encrypted using the homophonic substitution cipher described earlier in the document. The decryption algorithm is very similar to the encryption algorithm. All arguments are assumed to be valid. The buffer for the ciphertext is guaranteed to be large enough to store the null-terminated plaintext​            . Note that the function returns two values. The​          generated plaintext letters will all be in lowercase.

The function takes the following arguments, in this order:

• plaintext​: an uninitialized buffer to store the decrypted ciphertext
• ciphertext​: a ​non-empty​, null-terminated string to be decrypted using the homophonic substitution cipher
• keyphrase​: a ​non-empty​, null-terminated keyphrase string used during the decryption process
• corpus​: a ​non-empty​, null-terminated corpus string used during the decryption process

 

The function implements the following algorithm:

1. Call ​to_lowercase​ on ​corpus​.
2. Allocate at least 26 words’ worth of memory on the stack to temporarily store the ​counts​ array needed in the following step. Be sure to deallocate this memory later.
3. Call ​count_lowercase_letters(counts, corpus)​.
4. Allocate at least 27 bytes of memory on the stack to store the ​lowercase_letters​ string needed in the following step. Be sure to deallocate this memory later.
5. Call ​sort_alphabet_by_count(lowercase_letters, counts)​.
6. Allocate at least 63 bytes of memory on the stack to temporarily store the plaintext_alphabet​ string needed in the following step. Be sure to deallocate this memory later.
7. Call ​generate_plaintext_alphabet(plaintext_alphabet, lowercase_letters)​.
8. Allocate at least 63 bytes of memory on the stack to temporarily store the ciphertext_alphabet​ string needed in the following step. Be sure to deallocate this memory later.
9. Call ​generate_ciphertext_alphabet(ciphertext_alphabet, keyphrase)​.
10. In a loop, decrypt each alphabetical character of ​ciphertext​ and write the decrypted character into ​plaintext​. Each ​non-alphanumerical​ character of ​ciphertext​ should simply be copied to ​plaintext​.
11. Null-terminate the ​plaintext​

 

Returns in $v0:

• The number of lowercase letters that were written into the ​plaintext​ buffer during the decryption process.

 

Returns in $v1:

• The number of non-letters that were written into the ​plaintext​ buffer during the decryption process.

 

Additional requirements:

• The function must not write any changes to main memory except as needed.
• The function must call the functions ​to_lowercase​, ​count_lowercase_letters​, sort_alphabet_by_count​, ​generate_ciphertext_alphabet​, generate_plaintext_alphabet​, and ​index_of​.

 

Example #1:

ciphertext = “Dk5wQ 1Q4RW h yLCO4XnQ 8H4 yaE’3 VpQH6 L4V a 6qGoJ6. -R3n5t 6J9GqIA”  keyphrase = “I’ll have you know that I stubbed my toe last week and only cried for 20 minutes.”

corpus = “When in the Course of human events, it becomes necessary for one people to dissolve the political bands which have connected them with another, and to assume among the powers of the earth, the separate and equal station to which the Laws of Nature and of Nature’s God entitle them, a decent respect to the opinions of mankind requires that they should declare the causes which impel them to the separation.”

 

Resulting plaintext​ :​ “never trust a computer you can’t throw out a window.​

-steve wozniak”

 

Return value in $v0: 53​

 

Return value in $v1: 14​

 

Example #2:

 

ciphertext = ​ “Xjc 1UN4dDn 6xXj jW5vJk WJ ORcK GmKf, PI iO4TVn, mV 0jW3​

RwQREy 6mDE xKVlV1 NJ iMGqLk aDPJk aJf 2U8uHk 2Q R40 2jlJkV xK lZ. -3rUT8

RThYijc23”

keyphrase = “What’s the difference between ignorance and apathy? I don’t know and I don’t care.”

 

corpus = “Call me Ishmael. Some years ago – never mind how long precisely – having little or no money in my purse, and nothing particular to interest me on shore, I thought I would sail about a little and see the watery part of the world. It is a way I have of driving off the spleen and regulating the circulation.”

 

Resulting plaintext​ :​ “the trouble with having an open mind, of course, is that​    people will insist on coming along and trying to put things in it. -terry pratchett”

 

Return value in $v0: 111​

 

Return value in $v1: 29​

 

Example #3:

ciphertext = “L7 e1iXTTAkT 9K MCu zFxsnGH x7 F2jxZEkT Gy7P0hDo iXTI, VCfk zFqTDhjj4kT jXKP in Mwm zFqsdKG q7 zXNOEkT VCnj Rk. -2eGTuD eAbcKSDt”

keyphrase = “What is the sum of 12 and 37? The answer, CLEARLY, is 49!” corpus = “It was the best of times, it was the worst of times, it was the age of wisdom, it was the age of foolishness, it was the epoch of belief, it was the epoch of incredulity, it was the season of Light, it was the season of Darkness, it was the spring of hope, it was the winter of despair, we had everything before us, we had nothing before us, we were all going direct to Heaven, we were all going direct the other way – in short, the period was so far like the present period, that some of its noisiest authorities insisted on its being received, for good or for evil, in the superlative degree of comparison only.”

 

Resulting plaintext​ :​ “if debugging is the process of removing software bugs,​       then programming must be the process of putting them in. -edsger dijkstra”

 

Return value in $v0: 105​

 

Return value in $v1: 23​