Bitwise operators

| is Bitwise OR which will give you the result of "or"ing each bit of two ints, chars etc & is Bitwise AND and will give you the result of "and"ing each bit of two ints, chars etc

Upper case letter | 32 = lower case letter (i.e. 0s in every column except 32) Lower case letter & ~32 = upper case letter (i.e. 1s in every column except 32 - where ~32 = 256 - 32)

Command line arguments

Main can be initialised with 2 parameters, argc and char* argv[].

argc contains the number of arguments in including the command itself e.g. for mv here there, argc will be 3. char* arg[] will contain these arguments: mv, here, there and finally NULL or \0.

Arrays

There are two different ways to declare arrays:

// VERSION 1 (bracket-type array)
int x[N];

// VERSION 2 (pointer-type array)
int *x = malloc(sizeof(int) * N);
  • The first creates the array on the stack, the second on the heap, with a variable x on the stack which holds the address of the assigned area on the heap.
  • The first since its on the stack be automatically deallocated. The second won't be and free must be explicitly called.
  • The bracket array isn't actually a variable, its just a symbol - a kind of constant which the compiler chooses for you. So you can't increment the bracket array, but you can call e.g. x++ on the pointer array.
  • sizeof the bracket array will return the size of the big block of memory on the stack, but sizeof the pointer array will return the size of the variable x itself (e.g. 4 bytes)
  • The bracket array can be initialised using shortcut notation int x[] = {1,2,3,4};

Redirecting and Pipes

./hello > file.txt              # redirects stdout to the file and overwrite previous contents
./hello >> file.txt             # appends to previous contents
./hello > /dev/null             # discards the data
./hello < file.txt              # redirects stdin and provides input to the program from the contents of file.txt
./hello < file.txt > file2.txt  # redirect both stdin and stdout
./hello | ./redirect            # the output of hello is piped as the input to redirect
cat students.txt                # cat reads a file and outputs the contents to stdout

Encryption Algorithms

Caesar Cipher

This encrypts data by transposing each character by a set number of places e.g. with a key of 1: A becomes B, B becomes C, hello becomes ifmmp etc. There are only 25 possible keys which need to be tried in order to crack the cipher.

Vigenere Cipher

This cipher is a polyalphabetic cipher which uses two or more cipher alphabets to encrypt the data which means that the letters are shifted by different amounts, dependent on a word or phrase as the encryption key.

http://www.counton.org/explorer/codebreaking/vigenere-cipher.php

RSA

Both ciphers above use the same key to both encrypt and decrypt the data. These are know as symmetric key algorithms. This means that the sender and receiver need to have agreed on the key upfront. But then how do they establish this key in the first place. The secret key would also need to be encrypted and decrypted.

RSA uses a pair of keys, the public key and the private key. The public key is used to encrypt a message and the private key to decrypt a message. For two parties wanting to communicate, they both need their own set of keys. This is assymetric key cryptography.

To generate the two keys, we first start with 2 large prime numbers. The public key uses the product of these primes, but not the primes themselves. Since it is computationally difficult to factor numbers, it is difficult for an attacker to work out the two primes which make up the product and thereby decipher the message.

Two prime numbers

Generate two prime numbers by generating large numbers over and over again and then testing if they are probably prime. It is recommended that these numbers are at least 10^24 bits i.e. over 300 decimal digits.

p = 23, q = 43

Private and public keys

First calculate n and m thus:

n = p * q = 23 * 43 = 989 m = (p - 1) * (q - 1) = 22 * 42 = 924

We now need another number e which is relatively prime to m and less than m. Two numbers are relatively prime (or co-prime) if their only common factor is 1. In practice e is commonly the prime number 65537, as long as this isn't a factor of m.

e = 5

Finally we need a number d such that de = 1(mod m). 1(mod 924) = 925 = 1849 etc. 925 / 5 = 185. So d = 185.

Public key is the pair (e, n) which is (5, 989). Private key is the pair (d, n) which is (185, 989).

Notice that the original two primes do not feature in either the private or public keys.

Encrypting

To encrypt a message we need to break it into parts less than n in size and then encrypt each part.

chunk = message ^ e (mod n)

So if we want to encrypt CS50 we can take the ascii values of C, S, 5, 0 i.e. 67, 83, 53, 48. Encrypting them gives e.g. for C: 67 ^ 5 (mod 989) = 1,350,125,107 mod 989 = 658

Decrypting

message = (chunk ^ d) (mod n)

So e.g. (658 ^ 185) (mod 989) = 67 [how do we calculate this ??]

Critique

Since the message first needs to be broken down into chunks, this can be quite expensive. If we need to encrypt a large message it is common to use a mixture of symmetric key cryptography and assymetric key cryptography to make it secure but performant.

AES using symmetric key cryptography and uses RSA to send the key between the two systems