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.

Hint:

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
j
v
w

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