Homework #2: Basic Cryptography, Secure Web/Email with Digital Certificates


Assignment Date: 3/1/2005
Due Day: 3/8/2005

Problem A:

Repeat the RSA encipherment example for both Confidentiality and Authentication in Page 236 but apply Bob 's public key first followed by Alice private key. For example, the encipherment of 'H' will be (07^37 mod 77)^53 mod 77.

  1. Show the enciphered values for H, E, L and D. Hint. You can use the bc program on CS Unix machines to compute the enciphered values as follows. First login to CS Unix machine. type "bc". The bc program then identifies itself (bc 1.06) and wait for your input of the expression. For the above encipherment equation. We enter (7^37 % 77)^53 % 77
    the hit enter. The result will show in the next line. ^ represent "to the power" operation; % is the modulo operator.
  2. Compare these values with those in the textbook example, what conclusion you can derive?
  3. Repeat that for decipherment process by first applying Alice's public key then Bob's private key. Show the deciphered values for H, E, L and D.

Problem B.

Break the following monoalphabetic cipher. The plaintext, consisting of letters only, is a well-known excerpt from a poem by Lewis Carroll.

kfd ktbd fzm eubd kfd pzyiom mztx ku kzyg ur bzha kfthcm
ur mftnm zhx mfudm zhx mdzythc pzq ur ezsszcdm zhx gthcm
zhx pfa kfd mdz tm sutythc fuk zhx pfdkfdi ntcm fzld pthcm
sok pztk z stk kfd uamkdim eitdx sdruid pd fzld uoi efzk
rui mubd ur om zid uok ur sidzkf zhx zyy ur om zid rzk
hu foiia mztx kfd ezindhkdi kfda kfzhgdx ftb boef rui kfzk

Problem C.

A cipher-breaking machine with a billion processors that could analyze a key in 1 picosecond would take only 10^10 years to break the 128-bit version of AES. However, current machines might have 1024 processors and take I msec to analyze a key, so we need a factor of 10^15 improvement in performance just to obtain the AES-breaking machine. If Moore's law (computing power doubles every 18 months) continues to hold, how many years will it take to even build the machine?

Problem D. The Birthday Attack on MD5 Example in the handout, http://cs.uccs.edu/~cs691/crypto/basicCrypto.ppt#49.

After Ellen confessed to Marilyn about tricking her in the matter of Tom's tenure, Marilyn resolved to avoid this problem by dictating the contents of future messages into a dictating machine and having her new secretary just type them in. Marilyn then planned to examine the messages on her terminal after they had been typed in to make sure they contained her exact words. Can the new secretary still use the birthday attack to falsify a message, and if so, how? Hint: She can.

Problem E. Repeat the steps in http://cs.uccs.edu/%7Ecs526/secureWebAccess/secureWebAccess.htm for CA certificate signing and client/sever certificate request generation and signing. Generate snapshots of server certificated and client certificate-based access as shown in the secure web access web page. Save the snapshots in CS Unix server and email me just their urls.

For Problem E, we will use the MS-VPC2004 based virtual machine fc3cSis in c:\VirtualMachines\lab138\fc3cSis of any PC in EAS138. Each of these PCs has a label on the top cover with name similar to EN138-11. The last two digits indicate the unique machine in the lab. The following is your designated machine. Let's try to use the machine with mod(LastThreeDigits of Your SID, 27) so that we all use different machines. But there are exceptions (those with X mark). Note that you can save the machine status until next Saturady, where a new copy virtual machineswill be distributed and overwrited the existing copy. If you find the machines are being used by other students. You can use EN138-14, 19, 20, 25, and 26. Please do not use the podium machine EN138-27.

Last3digits of SID Machine Assigned Exception
092 EN138-11
099 EN138-18
124 EN138-16
174 EN138-12
229 EN138-13
238 EN138-22
310 EN138-02 X
434 EN138-05 X
480 EN138-21
555 EN138-15
576 EN138-09
611 EN138-03 X
714 EN138-01 X
752 EN138-23
753 EN138-24
779 EN138-06 X
807 EN138-07 X
841 EN138-04
854 EN138-17
915 EN138-08 X
928 EN138-10

Problem F. Follow the procedure in http://cs.uccs.edu/~cs691/crypto/verisign/SecureEmail.html to setup your outlook for secure email. Send me a signed email. I will return a signed encrypted email with questions. You need to signed and encrypted your reply.


Problem a:

z should be a
and is a frequent trigram
use frequency of unigram to match letters.
use vowel and ending characters as clues.

kfd ktbd fzm eubd kfd pzyiom mztx ku kzyg ur bzha kfthcm
ur mftnm zhx mfudm zhx mdzythc pzq ur ezsszcdm zhx gthcm
zhx pfa kfd mdz tm sutythc fuk zhx pfdkfdi ntcm fzld pthcm
sok pztk z stk kfd uamkdim eitdx sdruid pd fzld uoi efzk
rui mubd ur om zid uok ur sidzkf zhx zyy ur om zid rzk
hu foiia mztx kfd ezindhkdi kfda kfzhgdx ftb boef rui kfzk

z 30
d 28 E
f 23 H
k 23 T
m 21
u 19
t 16
h 15
i 15
r 10
x 10
o 8
c 7
p 7
s 7
b 6
e 6
y 6
a 5
g 3
n 3
l 2
q 1

leadig unigram: e, t, o, a, n, i
leading bigram: th, in, er, re, an
leading trigram: the, ing, and , ion

You can use the MS Word replace menuitem to replace cipher character(lower case) to a plaintext character (make it a upper case for easy recongition). Make sure you choose the "Match Case" option; otherwise the committed choice will be rewritten.

Problem c: Hint

10^15 factor improvement required. computer performance improve by 2^n where n is expressed in terms 1 and 1/2 years as time unit.

Problem d: Hinit

You can still change the first letter with characters that will not raise the suspicion of Marilyn.


If you have time, you may want to try the following exercise, to gain more experience with OpenSSL. It is optional.

Exercise e of S2003. Use OpenSSL to create RSA private, pubilc key, and certificate request. Have the certificate request signed by a self-signed CA. Encrypt text using RSA public key and decrypt it with the private key. Geneate the signed sha1 digest.

First, copy the ~cs691/public_html/crypto/hw2 directory to your own public_html directory. It contains the openssl.cnf configuration file for this exercise. Execute the following commands before you proceed with openssl commands listed below. Note that you need to replace <login> with your own login on CS Unix Machines. You can try telnet to any of blanca, sanluis, shavano, wetterhorn, redcloud for this exercise.

Telnet to a CS Uix machine.

chmod 755 ../<login>
cp -r ~cs691/public_html/crypto/hw2 ~<login>/public_html
cd ~<login>/public_html/hw2
mkdir <login>
mkdir <login>/public <login>/private

http://www.openssl.org/docs/apps/openssl.html provides high level descriptions of the available OpenSSL commands. For detailed description and options of each command, see the man pages in our CS Unix machines using "man openssl" or "man <openssl command>".

The following OpenSSL commands illustrate how to perform the above tasks.
See a more detailed description and explanation at http://cs.uccs.edu/~cs691/crypto/openssl/example.htm

# create CA private key and self signed certificate
# then retrieve the public key from private key

openssl req -new -x509 -keyout private/cakey.pem -out cacert.pem -days 365 -config openssl.cnf
cp private/cakey.pem private/cakey.pem.enc
openssl rsa -in private/cakey.pem.enc -out private/cakey.pem

# the following shows how a server keys and x509 certificate request
# can be created and how CA can use openssl to sign the certificate for server
# to use
openssl req -nodes -new -x509 -keyout cs691privatekey.pem -out cs691req.pem -days 365 -config openssl.cnf
openssl x509 -x509toreq -in cs691req.pem -signkey cs691privatekey.pem -out cs691certrequest.pem
openssl ca -config openssl.cnf -policy policy_anything -out cs691signedcert.pem -infiles cs691certrequest.pem

# create rsa private/public keys and certifcate and perform encryption using
# public key an decryption using private key
cp cs691privatekey.pem cs691/private/cs691privatekey.pem
openssl rsa -in cs691/private/cs691privatekey.pem -passin pass:cs03se -pubout -out cs691/public/cs691publickey.pem
openssl rsautl -encrypt -pubin -inkey cs691/public/cs691publickey.pem -in plain.txt -out cipher.txt
openssl rsautl -decrypt -inkey cs691/private/cs691privatekey.pem -in cipher.txt -out plainRcv.txt

# create, sign, and verify message digest
openssl sha1 -out digest.txt plain.txt
openssl sha1 -sign cs691/private/cs691privatekey.pem -out rsasign.bin plain.txt
openssl sha1 -verify cs691/public/ cs691publickey.pem -signature rsasign.bin plain.txt


Telnet to one of the CS Unix machines, sanluis, blanca, shavano, wetterhorn, or recloud.

chmod 755 ../<login>

So that your directory can be accessed by apache web server and by me.

Create public_html directory if you have not done so.

Copy the ~cs691/public_html/crypto/hw2 directory to your public_html using

cp -r ~cs691/public_html/crypto/hw2 ~<login>/public_html

where <login> is your login name.

cd ~<login>/public_html/hw2

mkdir <login>

mkdir <login>/public <login>/private

Repeat the above openssl commands to create your own RSA private, pubic key, and certificate request. Have the certificate signed by the CA.

Create a file called hw2part1 that included your answers to hw2 problems a-d. Geneate and sign hw2part1 with your private key. Email me the hw2part1 file, the signed sha1 hash, and your signed certificate to me.

To protect your hw2part1 file, private key, public key, and certificate, you should change the access right of hw2 to 700.

For verifying your signed sha1 hash, I need to extract the public key from your signed certificate. It can be done by the following command:

openssl x509 -in <login>signedcert.pem -pubkey -noout > <login>publickey.pem