Security and Cryptography (CSS 322)

Answers and Results

Tasks 1 and 2

For those that could not get RC4 working correctly, in Task 3 you can use the code of other groups. Here is an example that you may use, courtesy of Thanapa Chimmi and Ekaphan Pattanavijit. Their group was the first to submit which had both Diffie-Hellman and RC4 working correctly.

Results and comments on Tasks 1 and 2 are here. I have given a score out of 10 for each task (Diffie Hellman and RC4). The tasks may not be equally weighted (that is, in the final assignment score, the RC4 task will be weighted higher than the Diffie Hellman task - the weights will be determined once all tasks are completed).

Although most people implemented Diffie Hellman ok, some groups used bcmod(bcpow(a,b),q) instead of the much more efficient bcpowmod(a,b,q). When using large numbers, calculating exponentials (power) is time consuming EXCEPT if using modular arithmetic because then the algorithm can take advantage of the multiplication expansion covered in lectures, i.e. (axaxa)mod n = [((axa) mod n)x(a mod n)]mod n.

Task 3

Results and comments on Task 3 are here. An explanation of scores and comments follows:

  1. PU Score (out of 5): 5 marks were given if you emailed me ciphertext that successfully decrypted using RC4 and our shared secret key K. If you did not send me the encrypted Public key, or it did not successfully decrypt, then you received 0. For some groups although the decryption was successful, their value of e was 1 - they received only 2 marks.
  2. E/D Score (out of 5): 5 marks were given if your implementation of RSA Encrypt and Decrypt were correct. If you did not implemented these functions or they were wrong, you received 0 marks. Some groups passed in both the public key and private key to the function. That is incorrect: only one key can be passed in (because in most cases only one key will be known when encrypt/decrypt are used). Those groups received 2 marks.
  3. Gen Score (out of 10): Score for the implementation of GenerateKeys. You lost marks for the following:

Assignment

This assignment requires you to implement some simple security algorithms, and apply them. Everything is to be implemented in PHP. Although at first it may seem very difficult, PHP has been chosen because eventually you will find you only need several lines of code to implement most the algorithms. The assignment is a group task (groups of 2 - see the group list). Any cheating between groups, or copying code from the Internet will be penalised.

PHP

This assignment involves developing and using ciphers using PHP. I have a brief overview of using PHP which should be sufficient to get users new to PHP started. In addition I provide template PHP source code (Note: after downloading the template source code, change the file extension from .txt to .php). You should use this template and make use of the functions provided.

Terminology and Formats

Task 1

Complete the following steps:

  1. Implement Diffie-Hellman Key Exchange. Use q = 128903289023 and a = 23489.
  2. Using Diffie-Hellman, initiate an exchange with the CA to establish a shared secret key with the CA. The CA may take up to 24 hours to respond.

Task 2

Once the secret has been shared with the CA, the CA will send a message encrypted using RC4 and the shared key.

  1. Convert the secret generated by Diffie Hellman (a decimal integer) into a key that can be used by RC4 using the function Crypto_SecretToRC4Key().
  2. Implement RC4.
  3. Decrypt the ciphertext published here.
  4. Submit the plaintext of the received ciphertext and source code for Diffie Hellman and RC4 via email to steve@siit.tu.ac.th by 9:00am Wednesday 20 January 2010. The email must contain the following (where you replace XX with your group number and YY with the value of the plaintext):

Task 3

  1. Implement RSA.
  2. Generate your groups RSA keys. Make sure you record the values of p and q for your keys.
  3. Ecnrypt your public key using RC4.
  4. Submit the encrypted public key and source code for RSA via email to steve@siit.tu.ac.th by 9:00am Tuesday 26 January 2010. The email must contain the following (where you replace XX with your group number and YY with the value of the encrypted public key):

Task 4

Your group certificates (as well as the ID of your destination partner group) are available here. Each certificate is a string of the form:

PublicKeyOfUser IDOfUser Signature

where:

Note that the items are separated by a single space. Therefore one method to extract the certificate into 3 variables in PHP is:

$n = sscanf($certificate,"%s %s %s",$publickey,$id,$signature);	

The certificate of the CA (which you can trust is correct - it is signed by the CA itself) is:

a:2:{i:0;s:2:"97";i:1;s:10:"2845014301";} CA 866909010

Using the above information, complete the following steps:

  1. Download and validate your groups certificate.
  2. Download and validate your destination partner groups certificate.
  3. Take the first 8 digits of your secret key from Task 1 and send it confidentially, as well as signed to your destination partner group. Use RSA and Hash_Simple for the signature and confidentiality.
  4. When you receive a signed, confidential message, decrypt and validate it. If the message is valid, send the plaintext to the CA css322-ca@ict.siit.tu.ac.th containing:
    1. Your group ID
    2. The plaintext
    3. Values of p and q for RSA key
    4. Value of d for RSA key
    (If the message you received is invalid, see below). The CA will respond within 24 hours to indicate any further instructions.

Importantly, if a certificate or message validation fails then you must send an email to the CA css322-ca@ict.siit.tu.ac.th indicating your group ID, the certificate or message that failed validation, and the PHP code you used to determine the failure (do not send as an attachment; simply copy the relevant PHP lines into the body of the email - no functions are necessary). The CA will respond within 24 hours with further instructions.

Bonus points will be given to the first X groups that send correct messages to the CA (either with the plaintext or indicating an invalid message). You will lose points if you send incorrect messages to the CA.

You must complete the first 3 steps (including sending to your partner group) by 12noon Friday 5 February. You must complete all steps by 12noon Monday 8 February.

Examples and Test Vectors

The following shows an example of applying Diffie-Hellman, RC4 and RSA.

/* Diffie-Hellman example */
echo "Diffie-Hellman Example\n";
$Xa = '123451';
$Xb = '2435243';
$q = '128903289023';
$a = '23489';
$Ya = DH_GeneratePublic($q,$a,$Xa);
$Yb = DH_GeneratePublic($q,$a,$Xb);
$Ka = DH_GenerateSecret($q,$Xa,$Yb);
$Kb = DH_GenerateSecret($q,$Xb,$Ya);
echo $Ka . " " . $Kb . "\n";

/* RC4 Example */
echo "RC4 Example\n";
$p = 'pedia';
$k = array(87,105,107,105);
$c = RC4_Encrypt($p,$k);
echo $p . " " . $c . "\n";
print_r($k);

/* RSA Example */
echo "RSA Example\n";
$RSAkeys = RSA_GenerateKeys();
print_r($RSAkeys);
echo RSA_Encrypt("1034",$RSAkeys['pu']) . "\n";

The output of the above code was (note that the example used small values of p and q for RSA - you need to use larger values as described in Task 3):

Diffie-Hellman Example
68772533355 68772533355
RC4 Example
pedia 1021bf0420
Array
(
    [0] => 87
    [1] => 105
    [2] => 107
    [3] => 105
)
RSA Example
Array
(
    [pu] => Array
        (
            [0] => 191
            [1] => 31937
        )

    [pr] => Array
        (
            [0] => 16511
            [1] => 31937
        )

    [p] => 293
    [q] => 109
)
27094

Return to: CSS322 Home | Course List | Steven Gordon's Home | SIIT