CSE497b - Project #2 - Implementing Cryptography

Due Date: February 22, 2007.

Note: You are to complete this on your own. Any sharing of code or help during the coding of this project is expressly forbidden.

This assignment demonstrates the use of existing library functions to implement cryptographic algorithms. In particular, you will be required to use the Gnu multiprecision library to implement a variant of Diffie-Hellman (called the Hughes variant --- see the notes on it below) and RSA.

For RSA, make your life easier by using an acceptable, small value for the public key. 3 is sometimes used, but some crypto folks think this is too small. The Perlman book has an alternative.

Follow these instructions

  1. Obtain the tarfile from here.

  2. Unpack the tarfile in some appropriate directory on a UNIX system (there are many available at CSE). We are not using the Playpen for this assignment.

  3. Implement the functions for Diffie-Hellman (Hughes) and RSA as defined in the cse497b-appcrypto.h file.

  4. Use the Makefile included with the files to make the example application.

  5. Use the command line parameters of the example program to test your implementations of DH(Hughes) and RSA. A successful execution of these programs will look like the following (your numbers may differ, however):

    lion.cse.psu.edu p2-appcrypto > ./cse497b-p2 -d                  
    Running DH (Hughes) Algorithm
    Diffie-Hellman Exchange
      Prime      : c61823378ca06de01c8b6fb148c9bc935e433efcd960a1bf841fd60599811941a122cb1a323a76367ee78d71870b7134881ca077518c809013ae8ec6baecd5bf
      Generator  : 42a04a989c5800528ef687c978355e9c4afd410a9dd4b08cca7669c747cce5446d5e85022ca2a2c383c28e85ad038c37ced2e18bd88529bd2480e20191958497
    Left player ..
      x (Alice's secret)      : a744bf2335112e9c30bee1615fd1b5cd29c7e2b3580fcd464f66f7c24df54498b91055366a97052cfe50a5fad23c982bbccef3f03266bbcef5a1b242f40e97e9
      X (Alice's public)      : bde7a7ac537dbbbc719bf8677efe6e68c13de3ff2fab3b7c6424594093287ac96dacd1d9037fc148f163dcf96d1d2944ae1ff359909464c2426e70510cb2e5d3
      kl (Alice's key)        : af6dc013559186e7dbd917018323f5a0ba32ed79c727375bf0d5aa07d88e75365bf45705bcc82cc813ece7905b04ed03392db3f51460b5ca44e5859e253f561f
    Right player ..
      y (Bob's secret)        : 4e3d91de0cc2b53cc04a36690a26473de21f699171bd62450181fc81e4e90441f6ef52180688c838174a4f18ff47692942baf24fc0a8135f3c5db17e228f8c2b
      Y (Bob's public)        : 2a6e40f4a97343e7bfbd98851e618d1011944476dc5b31e7aab1ac5c5fdcec0c5cabb69807286ed1a53aa1a8572799db708134dc7cc3705efc7c9b41ad28ce3f
      kr (Bob's key)          : af6dc013559186e7dbd917018323f5a0ba32ed79c727375bf0d5aa07d88e75365bf45705bcc82cc813ece7905b04ed03392db3f51460b5ca44e5859e253f561f
    *** SUCCESS, key negotiated ***
    lion.cse.psu.edu project-1-appcrypto > ./cse497b-p2 -r
    Running RSA Algorithm
    RSA Key
      Modulus           : 2bf2978bc6d37fbfccdb013f2c33cac70bf704103aa8e8c39872e53df3812096228af96585d7cd4c036e36112a5f7c52b0b18c984e595894edb507c74cc1f0e1242016858be4f31c094d7904cf24c784d1976ec8cb95fd7adf3f331cda949fe1c903224ffd7dcc538467296996abad0d63338652ca08650e1d1490ab5fc482277af187ab83e9ebcf8108e0216a2cc4aff41b0458545868d5c9d210a0a1337e6f221ed5dfbfab2547dc6a80f35f78969c07208325cc106d583c6869555ada27026d5fa118ab8c3ef34209906d6de2af61b955f3baf41059b5e0daf9d6b38dcaff5aeb6baddca656208435b9e78385305645ce2b440fd5eb3b9e70b890dd32f8d
      Public expoonent  : 132f6ca389a263b32cf4354714c61878840bb20b4951fe9b5e24900633be5f60139d738b9a55ef20ff4c4380f7e37e5fc323c0fe78fb22ebcb8c055fe747b29df041a324796fe2850a927460220ab6917d2080e8cf20f1616df41edeebee8089e2346d5be902f957e618e18b0a4904fa0eaf839485605dda9e05a80d000bc3278f557eb65a465961e2469436b5d7166a6f155fa7104626c309f297369af482735463e36d7e4715a874f8fa6d3aba95dbeabc5773546957e9797247c35533bca3cec62934b875cc8ac11b294dbe6a147602e18ff39a01bcfe1187c0095d49a3cfa52d500381eda217595b8c70cc8b2a46a477f2bec557703dc7441301a748e3
      Private expoonent : 1f7bcdec632aeb6c4aa0d6a34dbd622743376f8eb80a71b5c137729aa4a0c45f482acb2066e93079bf15bb399cf7968f1e9ce9cf079ba43a8d9a8a38665075ce762e0bd3ec55d37aeb5ece0b0ebdcde5b9f971471e76f2facd074dde8b7036a277195da2d6bb9d1e3c75d404c08d7bf90db6585f76688160c7efe9cd94c059771bbb7a1e548001370bd474bacd11aa97c92936e9b2f9875131ebdaa7c17868ffb50bfe745058f015b4ea15fc0285a04e3fb473468f4d1dab790737aa26e00a76a1f4df4f07c7fdf13d7f031082d9bf7688423a6f83502a8c076cab00002efe9d9ae252703cbed2bff3e7ad557e0743792cbea6be7ded30aef8e40d3c275422b
    Private key encryption/public key decryption ..
      plaintext         : 881ca077518c809013ae8ec6baecd515
      ciphertext        : 18b1b8f606d8f45fc1888dc828a84cc74b99c0e31af6e9ab686f58383736ba4b671037e2f2ebf202fde4740efaf0dd67feafb11443de7bfd4472ae5954fa6ea9e5d18669b1dd98304345edfcd4577265a369994ca9e160ec834d3bcb8702082064136d93d5ee355bc8b57f71f6299bb43136b73ab6b4085450d8962c9d79e79f76710cd668b0f100539b882146d8252d27361937259d8a3c69f4a79e6b526bf9e9e1d21c9ed5549b13dd38ebfd3481eb52a0fccef605c6a4ad4a6b48e7141e0ce853cd42b7b782b1cf639270e90e18d595a60eadc90d9c70a616ac7972eca77e1c74761bcf2bea9f0c33fb93fc168cacaa5821e1c632d6e892a74ce3f2e0de2
      plaintext         : 881ca077518c809013ae8ec6baecd515
    Public key encryption/private key decryption ..
      plaintext         : 881ca077518c809013ae8ec6baecd515
      ciphertext        : 1fbc8ab099c15496cea5c812deb31c5668a54bfefcaf3080d8135a2d022092dbf027c07da4d40ff6fcce0c58242dd4be267dc014812059c4d521c3f5962804e357a3e48177ada6b5e25b14a088f1acb703bfec087ec2913feeef09f466e157aded2de1aa82263546b02b7aed436e0fb962c61783b1f59777d11003d2acd7e3d199c3e82fa7f23c9e4fc41473e04df36c056ab3b8a6d6cafb1df73255adc5a0a72801b24a49be7526f0e994ec9af61b51577a9c7480514ec4ff334f34f5e914074d4186fb35ed2e8a5de53d1393b7dde201e052eb72b61a17e1d0f7ef67ad3fe48ce75b1e7e86450a786188ae5185e022baa0853e0be35afe2de831d06f7aac
      plaintext         : 881ca077518c809013ae8ec6baecd515
    *** SUCCESS, data encrypted/decrypted ***
    lion.cse.psu.edu p2-appcrypto >
  6. When you have completed the code, email it to the course professor by 5:00pm on the 22nd. Please attach a tar file containing all the original source, plus your additions. Failure to compile or execute properly will likely result in a failing grade for the assignment.

Gnu Multiprecision Library

As part of this assignment, you will be required learn and use the GNU multi-precision library. Details of this library are presented in the link below. Do not contact the professor or TA (or anyone else) for information about this library -- learning how to use it is part of the exercise.

URL: http://www.gnu.org/software/gmp/manual/html_mono/gmp.html
Note: look for the section called "GMP Basics".

Hughes Diffie-Hellman Variant

The Hughes variant on Diffie-Hellman enables Alices to generate a key in advance that she can still provide securely to Bob. The advantage of this approach over DH is that a key k can be computed before any interaction. Alice can use this key to encrypt a value in advance of communication with Bob or others who she want to release the value to later.

The Hughes variant consists of the following steps

  1. As is typical in DH g and p are publicly known.

  2. Alice chooses a random, large integer x (as in DH normally) and generates the key k:

    k = gx mod p

  3. When Bob wants to communicate with Alice, he will compute a random, large integer y. In order to complete step 5, y must be relatively-prime to phi(p), so your code must check for this. In the protocol, he sends the value Y computed below to Alice (we run all this in one program in this project).

    Y = gy mod p

  4. Alice then computes the following X value to send to Bob.

    X = Yx mod p

  5. Then for the big finale, Bob performs two steps. First, he compute the exponentiative inverse (see Perlman Chapter 6) for y which we will call z. Hughes leverages the RSA property that a(d mod phi(p) * e mod phi(p)) mod p = a if d and e are exponentiative inverses (like private and public keys). So first we compute

    z such that yz mod phi(p) = 1

    Then we use this z to recover k from the first step.

    k = Xz mod p

Distinct DH and Hughes functions are defined for each of these steps. Good luck.

Trent Jaeger
Last modified: Wed Feb 7 08:03:39 EST 2007