COMP1511 17s1 Introduction to Programming

Objectives

In this Lab, you will practice:

Preparation

Before the lab you should re-read the relevant lecture slides and their accompanying examples. You should also have read the lab assessment guidelines.

Getting Started

One member of your programming pair should login and run the following commands inside a Linux terminal

Create a new directory for this lab called lab06 by typing:

mkdir lab06
Change to this directory by typing:
cd lab06

Introduction

WWII code-breaking at Bletchley Park was the genesis of modern computing. In this lab you too will perform computer-assisted code-breaking but don't worry the ciphers you must break are simpler than the Nazi's Lorenz and Enigma ciphers.

Exercise: Devowelling

Write a C program devowel.c which reads characters from its input and writes the same characters to its output, except it does not write lower case vowels ('a', 'e','i', 'o', 'u').

Your program should stop only at the end of input.

For example:

./devowel
Are you saying 'Boo' or 'Boo-Urns'?
Ar y syng 'B' r 'B-Urns'?
It was the best of times. It was the worst of times.
It ws th bst f tms. It ws th wrst f tms.

Hint: hint use getcharto read characters don't use scanf or fgets.

Hint: use putchar to output each character.

As usual autotest is available to help you test your program.

 ~cs1511/bin/autotest lab06 devowel.c

Exercise: Caesar Cipher

Write a C program caesar.c which reads characters from its input and writes the characters to its output encrypted with a Caesar cipher.

A Caesar cipher shifts each letter a certain number of positions in the alphabet.

The number of positions to shift will be given to your program as a command line argument.

Characters other than letters should not be encrypted.

Your program should stop only at the end of input.

Your program should contain at least one function other than main.

For example:

./caesar 1
This life well it's slipping right through my hands
Uijt mjgf xfmm ju't tmjqqjoh sjhiu uispvhi nz iboet
These days turned out nothing like I had planned
Uiftf ebzt uvsofe pvu opuijoh mjlf J ibe qmboofe

./caesar 10
abcdefghijklmnopqrstuvwxyz
klmnopqrstuvwxyzabcdefghij
ABCDEFGHIJKLMNOPQRSTUVWXYZ
KLMNOPQRSTUVWXYZABCDEFGHIJ

./caesar -42
Control well it's slipping right through my hands
Myxdbyv govv sd'c cvszzsxq bsqrd drbyeqr wi rkxnc
These days? 
Droco nkic?

Hint: handle upper and lower case letters separately

Hint: use %

Hint: use atoi to convert the command-line argument to an int.

As usual autotest is available to help you test your program.

 ~cs1511/bin/autotest lab06 caesar.c

Exercise: Manually Cracking a Caesar Cipher

Here is some (New Zealand) English text that has been encrypted with a Caesar cipher.
Naq jr'yy arire or eblnyf
Vg qba'g eha va bhe oybbq
Gung xvaq bs yhk whfg nva'g sbe hf
Jr penir n qvssrerag xvaq bs ohmm
What is the plain-text?

Hint:: try various shifts with caesar.c)

Exercise: Letter Frequency

Write a C program letter_frequency.c which reads characters from its input until end of input.

It should then print the occurance frequency for each of the 26 letters 'a'..'z'.

The frequency should be printed as a decimal value and an absolute number in exactly the format below.

Note upper and lower case letters are counted together.

For example:

./letter_frequency
Hello and goodbye.

'a' 0.066667 1
'b' 0.066667 1
'c' 0.000000 0
'd' 0.133333 2
'e' 0.133333 2
'f' 0.000000 0
'g' 0.066667 1
'h' 0.066667 1
'i' 0.000000 0
'j' 0.000000 0
'k' 0.000000 0
'l' 0.133333 2
'm' 0.000000 0
'n' 0.066667 1
'o' 0.200000 3
'p' 0.000000 0
'q' 0.000000 0
'r' 0.000000 0
's' 0.000000 0
't' 0.000000 0
'u' 0.000000 0
'v' 0.000000 0
'w' 0.000000 0
'x' 0.000000 0
'y' 0.066667 1
'z' 0.000000 0
./letter_frequency
Hey! Hey! Hey!
I don't like walking around this old and empty house
So hold my hand, I'll walk with you my dear

'a' 0.072289 6
'b' 0.000000 0
'c' 0.000000 0
'd' 0.084337 7
'e' 0.084337 7
'f' 0.000000 0
'g' 0.012048 1
'h' 0.096386 8
'i' 0.072289 6
'j' 0.000000 0
'k' 0.036145 3
'l' 0.084337 7
'm' 0.036145 3
'n' 0.060241 5
'o' 0.084337 7
'p' 0.012048 1
'q' 0.000000 0
'r' 0.024096 2
's' 0.036145 3
't' 0.048193 4
'u' 0.036145 3
'v' 0.000000 0
'w' 0.036145 3
'x' 0.000000 0
'y' 0.084337 7
'z' 0.000000 0
Hint: use an array of counts.

As usual autotest is available to help you help test your program.

 ~cs1511/bin/autotest lab06 letter_frequency.c

Exercise: Substitution Cipher Encoding

Write a C program substitution.c which reads characters from its input and writes the characters to its output encrypted with a Substitution cipher.

A Substitution cipher maps each letter to another letter.

The mapping will be given to your program as a single command line argument. This command line argument will contain 26 characters: an ordering of the letters 'a'..'z'.

Characters other than letters should not be encrypted.

Your program should stop only at the end of input.

Your program should contain at least one function other than main.

For example:

./substitution qwertyuiopasdfghjklzxcvbnm
I was scared of dentists and the dark
O vql leqktr gy rtfzolzl qfr zit rqka
I was scared of pretty girls and starting conversations
O vql leqktr gy hktzzn uoksl qfr lzqkzofu egfctklqzogfl

./substitution abcdefghijklmnopqrstuvwxyz
The identity cipher!!!
The identity cipher!!!
./substitution bcdefghijklmnopqrstuvwxyza
The Caesar cipher is a subset of the substitution cipher!
Uif Dbftbs djqifs jt b tvctfu pg uif tvctujuvujpo djqifs!

As usual autotest is available to help you test your program.
 ~cs1511/bin/autotest lab06 substitution.c

Exercise: Substitution Cipher Decoding

Write a C program decode.c which decrypts text encrypted by substitution.c

For example:

./decode qwertyuiopasdfghjklzxcvbnm
O vql leqktr gy rtfzolzl qfr zit rqka
I was scared of dentists and the dark
O vql leqktr gy hktzzn uoksl qfr lzqkzofu egfctklqzogfl
I was scared of pretty girls and starting conversations

./decode abcdefghijklmnopqrstuvwxyz
The identity cipher!!!
The identity cipher!!!
./decode bcdefghijklmnopqrstuvwxyza
Uif Dbftbs djqifs jt b tvctfu pg uif tvctujuvujpo djqifs!
The Caesar cipher is a subset of the substitution cipher!

As usual autotest is available to help you test your program.
 ~cs1511/bin/autotest lab06 decode.c

Exercise: Manually Cracking a Substitution Cipher

This English text was encrypted with a Substitution cipher.
Ndwu fdw sojfauw xafwl dvsq
Vuq vcxafaoul vsw yon
Vuq fdw swlwufcwuf saqwl datd
Xjf wcofaoul nouf tson
Vuq nwsw kdvutaut ojs nvrl,
Fviaut qappwswuf sovql
Fdwu yomw, yomw nayy fwvs jl vbvsf vtvau
What was the original text?

Hint: use letter_frequency.c on the encrypted text and compare the frequencies to English letter frequencies and then try your guesses with decode.c

Challenge Exercise: Automatically Cracking Caesar Ciphers

Write a C program crack_caesar.c which decrypts text encrypted by an unknown Caesar cipher.

Your program should make no assumptions about the language of the original text - don't assume its English.

Your program will be given as a command-line argument the name of a file containing a large amount of unencrypted text in the same language as the encrypted text.

Your program will be given the encrypted text on standard input. You may read it all before printing the decryption.

You may assume the encrypted text contains at most 10000 characters. For example: /import/adams/A/cs1511/public_html/17s1/tlb/06/unsw.txt contains 42000 characters of English text (UNSW students on facebook)

For example, here is some English text encrypted with a Caesar cipher with an unknown shift:

Kyzj zj fli crjk xffuspv
Z yrkv kf wvvc kyv cfmv svknvve lj uzv
Slk zk'j fmvi
Aljk yvri kyzj reu kyve Z'cc xf
Pfl xrmv dv dfiv kf czmv wfi
Dfiv kyre pfl'cc vmvi befn
So for example:
./crack_caesar /import/adams/A/cs1511/public_html/17s1/tlb/06/unsw.txt
Kyzj zj fli crjk xffuspv
Z yrkv kf wvvc kyv cfmv svknvve lj uzv
Slk zk'j fmvi
Aljk yvri kyzj reu kyve Z'cc xf
Pfl xrmv dv dfiv kf czmv wfi
Dfiv kyre pfl'cc vmvi befn

This is our last goodbye
I hate to feel the love between us die
But it's over
Just hear this and then I'll go
You gave me more to live for
More than you'll ever know
Hint: extract the letter frequencies from the file of unencrypted text. Use these frequencies as estimate of the probability each letter will be used. Test all possible shifts using these probabilities to see which is the most likely..

As usual autotest is available to help you test your program.

 ~cs1511/bin/autotest lab06 crack_caesar.c

Challenge Exercise: Automatically Cracking Substitution Ciphers

Write a C program crack_substitution.c which decrypts text encrypted by an unknown s cipher.

Your program should make no assumptions about the language of the original text - don't assume its English. In other words don't hard code English properties into your program, extract the statistical properties from the sample plain text.

Your program will be given as a command-line argument the name of a file containing a large amount of unencrypted text in the same language as the encrypted text.

Your program will be given the encrypted text on standard input. You may read it all before printing the decryption.

You may assume the encrypted text contains at most 10000 characters.

For example:

./crack_substitution /import/adams/A/cs1511/public_html/17s1/tlb/06/unsw.txt
M'ka paat dra qegbu, ueta md xbb
Rxu vw fxya teq
Umxvetup, ogmbbmxtd, mt Oab-Xmg teq
Red psvvag tmlrdp, vmu Jsbw
Qrat wes xtu M qaga negakag qmbu
Dra fgxzw uxwp, fmdw bmlrdp
Dra qxw wes'u cbxw qmdr va bmya x frmbu
Qmbb wes pdmbb beka va
Qrat M'v te betlag westl xtu oaxsdmnsb?
Qmbb wes pdmbb beka va
Qrat M'ka led tedrmtl osd vw xfrmtl pesb?
M yteq wes qmbb, M yteq wes qmbb
M yteq drxd wes qmbb
Qmbb wes pdmbb beka va qrat M'v te betlag oaxsdmnsb?
M'ka paat dra qegbu, bmd md sc
Xp vw pdxla teq
Frxbbatlmtl xtlabp mt x taq xla teq
Red psvvag uxwp, gefy t gebb
Dra qxw wes cbxw neg va xd wesg preq
Xtu xbb dra qxwp, M led de yteq
Wesg cgaddw nxfa xtu abafdgmf pesb

I've seen the world, done it all
Had my cake now
Diamonds, brilliant, in Bel-Air now
Hot summer nights, mid July
When you and I were forever wild
The crazy days, city lights
The way you'd play with me like a child
Will you still love me
When I'm no longer young and beautiful?
Will you still love me
When I've got nothing but my aching soul?
I know you will, I know you will
I know that you will
Will you still love me when I'm no longer beautiful?
I've seen the world, lit it up
As my stage now
Challenging angels in a new age now
Hot summer days, rock n roll
The way you play for me at your show
And all the ways, I got to know
Your pretty face and electric soul
Hint: you will need to look at the probabilities of sequences of 2 or perhaps 3 letters occurring or perhepas the probabilities of words.

An autotest is available to help you test your program but because this is a difficult problem it is possible very good attempts at the problem won't pass the autotests.

 ~cs1511/bin/autotest lab06 crack_substitution.c

Submission/Assessment

When you are satisfied with your work, ask your tutor to assess it. You also need to submit your work electronically by typing (run this command in the lab06 directory):
give cs1511 lab06 devowel.c caesar.c letter_frequency.c substitution.c decode.c crack_caesar.c crack_substitution.c
Submit the challenge exercises only if you attempt them.

If you are working at home, you may find it more convenient to upload your work via give's web interface.

Remember the lab assessment guidelines - if you don't finish the exercises you can finish them in your own time, submit them by Monday 11:00am using give and ask your tutor to assess them at the start of the following lab.

Either or both members of a programming pair can submit the work (make sure each program lists both of you as authors in the header comment).