2.8 Assignment 5c: extra implement a hashing function 500 points
For this assignment, implement a program to calculate a hash such as SHA1, SHA256, MD4, MD5, or any other hash you like, of the input given to the program. If you do not know what a hash function is, Google a bit first.
Exercise:
Choose a well known hashing algorithm, and write a program that calculates and prints the hash of the input given to the program. From standard input or from a file.
Optional help from our side for SHA1:
Read the Wikipedia page about SHA14 especially the pseudo code. As you will see, the al gorithm has to split up the data up in 512bit chunks, and then process each chunk separately. In this simplified exercise, you will only implement the function to process a chunk. The rest of the code is provided by us. After you finish this exercise, you can go for the full 750 points by implementing the rest of the code too.
Our part of the code can be downloaded from Canvas. You can combine this with your own code by adding .sha1 test64.so5 as another parameter to gcc. Our code does everything until and including the line break chunk into sixteen . . . in the pseudo code on Wikipedia. The command used to compile your code could like something like this:
gcc o test mysha1chunk.s .sha1test64.so nopie
Your part of the code should not have a main function, but instead have a sha1 chunk function, which will be called by our part of the code. This sha1 chunk function takes two parameters: First, the address of h0 h1, h2, etc. are stored directly after h0. See Wikipedias pseudo code for SHA1 for these names. Second, the address of the first 32bit word of an array of 80 32bit words. The first sixteen of this array are set to the sixteen 32bit words the chunk contains which are called w0 till w15 on Wikipedia. Your function should modify h0 till h4 as described in the pseudo code.
When you execute the combined program, our part of the code prints a lot of information on what is happening, and when your function is called. It displays the result of your function, and whether that is correct or not. You can of course print more debugging information from your own function using printf.
2.9 Assignment 6: extra using assembly to hide data in a bitmap 750 points
On April 2, 1990, Dilbert was sent to the tiny country of Elbonia on a secret mission6: to infiltrate the formerly communist, newly capitalist country and find targets who can become Western engineers. Secretly, Dilbert was also charged with becoming a liaison to the resistance movement from within Elbonias totalitarian neighbour, North Elbonia. It has been over two decades, and the mission is still on with a twist. The governments of Elbonia and North Elbonia have joined forces and together tightened their grip on information. Facebook, Twit ter, YouTube have been banned. Searches on google.com are often filtered out or redirected to NorthElboniaSearchAndTortureDept.com.
You are the new tech assistant of Dilbert. Your mission: using assembly, encrypt messages into the photos of Elbonian white noise that Dilbert provides for you. In detail:
4http:en.wikipedia.orgwikiSha1
5there is also a sha1 test32.so for 32 bit compilation available
6See http:www.dilbert.comfast19900402 and http:www.dilbert.comfast19900403.
17
1. Make sure you understand the message.
2. Compress the message using the RunLength Encoding RLE technique.
3. Prepare the white noise image.
4. Use XOR to encrypt the message into the white noise image.
5. Save the results as image bitmaps, in BMP format.
6. Test that you can decrypt the message, using again the XOR encryption technique.
More details follow. This message will not selfdestruct in 5 seconds.
Data: The Message
Complexity: Easy
To demonstrate that your assembly code works, encrypt and decrypt the message Reading Dilbert strips or encoding Elbonian messages are not good excuses for failing the TI1406 final exam., including the final dot .. Save the message as an assembly data chunk before you con tinue.
Each message, before encryption, must be preceded and followed by the pattern 8T, 4I, 2 1, 24, 40, 85, where numbercharacter means that character is repeated number times, e.g., 8T means T T T T T T T T. The added parts are called the lead and the trail of the message.
Data Compression: RunLength Encoding RLE
Complexity: Moderate
RunLength Encoding RLE is one of the simplest data encoding techniques. RLE is based on the notion of runs, which are sequences of specified length of the same item.
For this assignment, you will use RLE8, which encodes, in turn, the size of the sequence and each item on 8 bits each. For example, the RLE8encoded sequence of two bytes 8T means that the sequence length is 8 and the item isT, for the fully decrypted textTTTTTTTT.
You have to devise your own algorithms for RLE8encoding and RLE8decoding the message described in the previous paragraph.
Data: Repeating White Noise Patterns
Complexity: Easy
Since Dilberts photo camera has been confiscated, we cannot provide you with pictures of anything Elbonian. However, Elbonians are very proud of their national art, which is based on white noise rectangles, that is, rectangles filled with a seemingly random collection of white and black pixels. You are to implement a generator of Elbonian white noise.
Be warned, to show that in Elbonia even white noise is controlled, the Elbonian Ministry of Mud approves every year a single pattern as that years white noise. The pattern can be seen in the numerous works of poorly printed art on the streets. Dilbert believes this years pattern is:
WWWWWWWWBBBBBBBBWWWWBBBBWWBBBWW
31 pixels long, where W means white and B means black.
Create a sequence by repeating the Elbonian white noise pattern, followed by a red pixel, 32
times. This will form a 3232 image, where each pixel is either white, black, or red.
18
Input xy
Output XORx,y
00 01 10 11
0 1 1 0
Data Encryption: XOR
Complexity: Moderate
Table 2.1: XOR truth table.
One of the common logical operations is the eXclusive OR XOR, , equivalent to the Boolean logic concept of TRUE if only one of the two operands, but not both, is TRUE. Table 2.1 summarises the truth table of XOR.
Two properties of XOR are of interest:
x0x 2.1a xx0 2.1b
From Equations 2.1a and 2.1b nonidempotency, it is trivial to observe that:
xyyxyy
x0 2.2 x
Equation 2.2 means that we can use XOR to first encrypt xy and then decrypt xyy a onebit message x with the encryptiondecryption key y. It turns out that these two onebit operations can be extended to nbit operations, that is, for an nbit message M and an nbit key K:
MKKM 2.3
For example, if the message is TEST in ASCII M01010100 01000101 01010011 01010100 in binary and the key is TRY! in ASCII K01010100 01010010 01011001 00100001, the encrypted text is:
The decrypted text is:
MK01010100 01000101 01010011 0101010001010100 01010010 01011001 0010000100000000 00010111 00001010 01110101
2.4
2.5
MKK00000000 00010111 00001010 0111010101010100 01010010 01011001 0010000101010100 01000101 01010011 01010100
M
If the size of the message is m bits and the size of the key is kn bits, the key can be repeated. Eectively, using the full k bits of the key K, first the first k bits of the message M are encrypted, then the next k bits, etc.
Last, a good example of implementing the XOR encryption technique in C is the C TutorialXOR Encryption by Shaden Smith, June 20097.
7Online Available: http:forum.codecall.nettopic48889ctutorialxorencryption.
19
Data Representation: the BMP Format Simplified
Complexity: Dicult
Storing data as images requires complex data formats. One of the simplest is the bitmap BMP format, which you must use. BMP files encode raster images, that is, images whose unit of information is a pixel; raster images can be directly displayed on computer screens, as their pixel information can be mapped onetoone to the pixels displayed on the screen.
The BMP file format consists of a header, followed by a metadescription of the encoding used for pixel data, followed sometimes by more details about the colours used in the image lookup table, see also the paragraph on white noise. The BMP file format is versatile, that is, it can accommodate a large variety of colour encodings, image sizes, etc. It is beyond the purpose of this manual to provide a full description of the BMP format, which is provided elsewhere8.
Luckily for you, of the many flavors of encodings, Elbonian authorities only accept one type. Thus, you must use the following BMP format for this assignment:
1. File Header, encoded as signature two bytes, BM in ASCII; file size integer, four bytes; reserved field four bytes, 00 00 00 00 in hexadecimal encoding; oset of pixel data inside the image integer, four bytes. The file size is the sum between the file header size, the size of the bitmap info header, and the size of the pixel data. The file header size is 14 two bytes for signature and four bytes each for file size, reserved field, and oset of pixel data. The file size is the sum of 14 the file header size, 40 the size of the bitmap header, and the size of the pixel data.
2. Bitmap Header, encoded as9: header size integer, four bytes, must have a value of 40; width of image in pixels integer, four bytes, set to 32see see paragraph on white noise; height of image in pixels integer, four bytes, set to 32see paragraph on white noise; reserved field two bytes, integer, must be 1; the number of bits per pixel two bytes, integer, set here to 24; the compression method four bytes, integer, set here to 0no compression; size of pixel data four bytes, integer; horizontal resolution of the image, in pixels per meter four bytes, integer, set to 2835; vertical resolution of the image, in pixels per meter four bytes, integer, set to 2835; colour palette information four bytes, integer, set to 0; number of important colours four bytes, integer, set to 0.
3. Pixel Data, encoded as B G R triplets for each pixel, where B, G, and R are intensities of the blue, green, and red channels, respectively, with values stored as onebyte unsigned integers 0255. It is important that the number of bytes per row must be a multiple of 4; use 0 to 3 bytes of padding, that is, having a value of zero 0 to achieve this for each row of pixels. The total size of the pixel data is NrowsSrow3, where Nrows is the number of rows in the image 32see paragraph on white noise; Srow is the size of the row, equal to the smallest multiple of 4 that is larger than the number of pixels per row here, 32see paragraph on white noise; and the constant 3 is the number of bytes per pixel 24 bits per pixel, as specified in the field number of bits per pixel, see the Bitmap header description.
Last, but not least
You should go and have your code checked by a lab course assistant. You have now ocially proved mastery in the basics of assembly programming. Not bad!
8BMP file format, Wikipedia article. Online Available: http:en.wikipedia.orgwikiBMPfileformat. Note: Although Wikipedia is not a universally trustworthy source of information, many of its articles on technical aspects, such as the BMP file format have been checked by tens to hundreds of domain experts.
9This encoding is BITMAPINFOHEADER, which is a typical encoding for Windows and Linux machines. Older encodings, such as BITMAPCOREHEADER for OS2, are obsolete. Newer versions, such as BITMAPV5HEADER exist, but they are too complex for Elbonian engineers.
20
2.10 Assignment 7: extra implement an esoteric language interpreter 7001000 points
For this assignment, implement an interpreter for a very simple programming language. We rec ommend you to chose a very simple esoteric programming language such as Brainfuck or Whites pace. In Brainfuck, for example, every character of the source code is a command, and there are only eight very simple commands. The interesting thing about this language is that even though it might not seem like it, it is still Turing complete. This basically means that you can write every possible program in it, but not necessarily in an ecient way.
Exercise:
Choose some basic programming language we recommend Brainfuck; http:esolangs.org wikiMainPage is a great place to look for similar simple andor fun languages and write a program in assembly that can execute a program in that language. Your program should read the source code of the interpreted program from from a file, given as a command line argument to your interpreter.
You can find a tarball containing assembly code and instructions for reading a file specified as a command line argument on Canvas.
Example:
Suppose you have written a Brainfuck interpreter. You have a file called hello.b containing the following code:
..
.
Now, executing your program assuming it is called brainfuck as follows .brainfuck hello.b
should make it give
Hello World!
as output.
More complex programs to test your interpreter with can be found all over the internet. For
Brainfuck, see e.g. http:esoteric.sange.fibrainfuckutilsmandelbrotmandelbrot.b. Bonus points: up to 3100 points
Find another interpreter for the same language, and compare the speed of your interpreter against it. You will probably notice a big dierence in speed. What is causing that?
Find ways to significantly improve the speed or memory usage of your interpreter. Depending on the optimisations you make, you can get at most 300 points extra, making a grand total of 1,000 for this assignment.
2.11 Assignment 8: extra using assembly to implement a game 1,000 points
For this exercise you will use your basic assembler programming skills to develop a complete and useful program: a game. For the purpose of this assignment, a game is an interactive computer application in which at least one user player influences the outcome via keyboard or mouse input.
21
Reviews
There are no reviews yet.