Problem Set 2 : Crypto

Hello, world! Congratulations, you’ve completed problem set 1! Now, we’re getting started into Problem Set 2. What was the problem? In this problem set, you’ll study about Cryptography , which was very challenging and exciting at the same . You will be among the “more comfortable” if you can complete this pset. Anyway, you have to complete 2 parts in it :

  1. Caesar Cipher
  2. Vigenere Cipher

Then we’re gonna talk about “What is Cryptography?“ (http://en.wikipedia.org/wiki/Cryptography).

“Why did we do this?” Well, it’s very useful. Say, if you want to send a message to your crush but you don’t want others see what exactly you said. So we can keep secret from each other what the message actually says by using Cryptography. Since, the actual string will be covered by the key which can make the primary text hiding. For example : “Can I have your number ? “ you can use 11 as the secret key, and it will say “Nly T slgp jzfc yfxmpc ?” instead of above. Who knows what you said then? But, how’s work ? That’s simple. Ok, I used 11 for the key, the letter “C” inside of the word “Can” was changed by “N” which was 11 letters away from “C”. Can you figure out the next letters? It’s really fun!

The parts of Cryptography are :

  1. Key (secret position a non- negative integers) see : http://en.wikipedia.org/wiki/Key_%28cryptography%29
  2. Ciphertext (Encrypted message) see : http://en.wikipedia.org/wiki/Ciphertext
  3. Plaintext (Unencrypted message) see : http://en.wikipedia.org/wiki/Plaintext

By the way, an ASCII characters are very useful in order to do this pset.

ascii

(image : http://commons.wikimedia.org/wiki/File:ASCII-Table.svg)


Alright, here we go!

Open up the terminal inside of the appliance then execute :

update50

To make sure that your appliance is up-to date.

Next, execute :

mkdir ~/Dropbox/pset2

This was a command for make new directory called “pset2” inside of “Dropbox”.

Then, execute :

cd ~/Dropbox/pset2

To make sure that you move yourself into that directory. Your prompt now should be like :

jharvard@appliance (~/Dropbox/pset2) : 

  1. Caesar cipher.

Have you watched short videos ? If haven’t , be sure to watch it first (https://www.youtube.com/watch?v=36xNpbosfTY) it will be helpful. Recall from the video’s short that Caesar’s cipher encrypts (i.e scrambles in a reversible way) messages by rotating each letter by “k” positions, wrapping around “z” to “A” as needed (http://en.wikipedia.org/wiki/Caesar_cipher) in other words, if “p” is some plaintext (i.e unencrypted message), “pi” is the i-th character in “p”, and “k” is the secret key (i.e non negative integer), then each letter “ci” in the ciphertext “c” is computed as :

ci = (pi + k) % 26

ci = i-th letter of ciphertext.

pi = i-th letter of plaintext.

k = the key.

%26 = remainder after dividing by 26.

This formula perhaps makes the cipher seem more complicated than it is, but it’s really nice way of expressing the algorithm precisely and concisely.

Anyhow, your goal is to write caesar.c, a program that encrypts message by using Caesar Cipher.

Where to begin?

  • This program needs to accept a command-line argument, “k” so this time you’ll want to declare main with :
int main(int argc, string argv[])

The “argv” is an array of strings. Keep in mind that arrays are zero-indexed. To access the next letter, you use syntax like argv[1]. With that you can access for each letter with the code like :

string k = argv[1];
  • Your program must a single command line-argument. If your program is executed without any command line argument, your program should yell at the user and return value of 1 :
return 1;
  • The users must type an integer at the prompt, that doesn’t mean their input will be stored as an int. It will stored as a string. You’ll need to convert that string to an actual int. As luck, we would have a function atoi http://www.cs50.net/resources/cppreference.com/stdstring/ exists for exactly that purposes. Here’s how you might use :
int k = atoi(argv[1]);

But don’t forget to add the library #include <stdlib.h> because atoi is declared there.

  • OK, so once you’ve got “k” stored as an int. You’ll need to ask the user for some plaintext. GetString() can help you with that.
  • You can iterate over the characters in a string, printing each one at the time, with code like below :
for (int i = 0, n = strlen(p); i < n ; i++)
{
     printf("%c", p[i]);
}

Incidentally, you’ll want to add another header file #include in order to use strlen http://www.cs50.net/resources/cppreference.com/stdstring/.

Here you go with the pseudocode !

Pseudocode :

  1. Get the key
  2. Get the plaintext
  3. Encipher
  4. Print Ciphertext

If you’re done with that. So we can automate some tests of your code, your program must behave per the below. Assumed that the underline text is what some user has typed.

jharvard@appliance (~/Dropbox/pset2) : ./caesar 13
Be sure to drink your Ovaltine!
Or fher gb qevax lbhe Binygvar!

If you’d like to check the correctness of your program with check50, you may execute the below:

check50 2014/x/pset2/caesar caesar.c

Congrats! You’ve completed Caesar!

  1. Vigenere cipher.

This last cipher of this problem set was hardly secure. Be sure to watch Vigenere’s short http://cs50.tv/2012/fall/shorts/vigenere_cipher/vigenere_cipher-720p.mp4 there was more sophisticated algorithm out there. It’s French  http://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher.

Vigenere’s cipher improves upon Caesar’s by encrypting messages using a sequence of keys, in other word, if “p” is a plaintext and “k” is a keyword, then each letter “ci” in the ciphertext “c” is computed as :

ci = (pi + kj) % 26

ci = i-th letter of ciphertext.

pi = i-th letter of plaintext.

kj = j-th letter of the key.

%26 = remainder after dividing by 26.

Note this cipher’s use of “kj” as opposed to just “k”. And recall that. If “k” is shorther than “p”, then the letter in “k” must reused cyclically as many times as it takes to encrypt “p”.

Your next challenge is to write in vigenere.c, a program that encrypts messages using Vigenere’s cipher.

Pseudocode :

Get the key

  • 2nd command line argument : argv[1]
  • Must be alphabetical : isalpha

Get plaintext

  • GetString()

Encipher

  • Advance the next letter in keyword only if the character is a plaintext letter
  • isalpha
  • Preserve case
  • isupper, islower
  • Keep track of :
  • Position in plaintext
  • Position in keyword

In two separate variables.

Print ciphertext

With that, you’ll complete Vigenere cipher. So we can automate some tests of your code, your program must behave per the below :

jharvard@appliance (~/Dropbox/pset2): ./vigenere bacon 
Meet me at the park at eleven am 
Negh zf av huf pcfx bt gzrwep oz

If you’d like to check the correctness of your program with check50, you may execute the below:

check50 2014/x/pset2/vigenere vigenere.c

And, viola! You’ve completed Caesar and Vigenere cipher! Congratulations!

This was Problem Set 2.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s