Solution to CS691 S2005 Homework#2
Basic Cryptography

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. [cs691@sanluis hwS2003]$ bc
    bc 1.06
    Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
    This is free software with ABSOLUTELY NO WARRANTY.
    For details type `warranty'.
    (7^37 % 77)^53 % 77
    (4^37 % 77)^53 % 77
    (11^37 % 77)^53 % 77
    (3^37 % 77)^53 % 77

    We got exact the same enciphered block values.

  3. Compare these values with those in the textbook example, what conclusion you can derive?
    Ans: It does not matter which order the Alice's private key and Bob's public key is apply to the formula m^x mod n.

  4. 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.
    Ans: Alice's public key is 17. Bob's private key is 13.

    (7^17 % 77)^13 % 77
    (37^17 % 77)^13 % 77
    (44^17 % 77)^13 % 77
    (47^17 % 77)^13 % 77

    We got the same 7 4 11 3 plaintex back.

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

Ans: We can start by perform the frequency count of the characters appear in the ciphertext. The following table the letters and their frequency count. z appear 30 times, d appears 28 times.

z 30 a zhx and
d 28 e kfd the
f 23 h eubd eume
k 23 t eu co
m 21 s ham has
u 19 o ur of
t 16 i ttme time
h 15 n ahd and
i 15 r foi for
r 10 f or of
x 10 d saix said
o 8 u oot out
c 7 g thincs things
p 7 w phether whether
s 7 b soiling boiling
b 6 m ttbe time
e 6 c eume come
y 6 l tayk talk
a 5 y mana many
g 3 k thanged thanked
n 3 p carnenter carpenter
l 2 v hale have
q 1 x waq wax

We also know that

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

By looking the trigram and the most frequent appear standalone 3 letter word, kfd, we will try to map kfd to THE.
zhx is the next frequent appearing standalone 3 letter word. We try to map it to AND.
We then substitute the standalone z with a. (I is another possibility).

THE TtbE HAm eubE THE pAyiom mAtD Tu TAyg ur bANa THtNcm
ur mHtnm AND mHuEm AND mEAytNc pAq ur eAssAcEm AND gtNcm
AND pHa THE mEA tm sutytNc HuT AND pHETHEi ntcm HAlE ptNcm
soT pAtT A stT THE uamTEim eitED sEruiE pE HAlE uoi eHAT
rui mubE ur om AiE uoT ur siEATH AND Ayy ur om AiE rAT
Nu Hoiia mAtD THE eAinENTEi THEa THANgED Htb boeH rui THAT

By examing the unmapped characters in between mapped uppercase characters, we can guess

g should be K ---THANgED
m should be S --- HAm and it was further confirmed by mEA.

THE TtbE HAS eubE THE pAyioS SAtD Tu TAyK ur bANa THtNcS
ur SHtnS AND SHuES AND SEAytNc pAq ur eAssAcES AND KtNcS
AND pHa THE SEA tS sutytNc HuT AND pHETHEi ntcS HAlE ptNcS
soT pAtT A stT THE uaSTEiS eitED sEruiE pE HAlE uoi eHAT
rui SubE ur oS AiE uoT ur siEATH AND Ayy ur oS AiE rAT
Nu Hoiia SAtD THE eAinENTEi THEa THANKED Htb boeH rui THAT

t can be I --- from tS and THtNcS, KtNcS
u can be O --- from SHuES, Nu
r can be F --- ur (OF)
c can be G --- THINcS, KINcS
b can be M -- TIbe, HIb, SObE
e can be C -- eOME, eHAT
a can be Y -- MANa, THEa

y can be L -- Ayy, TAyK
p can be W --- pHY, pING

i can be R -- FOi
s can be B -- sEFORE
o can be U -- BoT, OoR

n should be P -- CARnENTER, SHInS

l should be V -- HAlE

q should be X -- WAq

The plaintext is


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?

Ans: Let n be the times the computing power doubles. We then have 10^15=2^n. Take log on both side.
We get 15log(10)=nlog(2). n= 15*log(10)/log(2)=49.83. It takes 18 months or 1.5 years to double the computing power. 1.5 year*49.83=74.74 years. It takes 74.74 years to even build the machine.

Problem D. The Birthday Attack on MD5 Example in the handout.

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.

Ans: Yes. She can by adding white space characters (space, tab, line feed, carriage return) to generate many versions of the first letter, and their corresponding hashes to match with those of the seconds letters.

Problem E. Repeat the steps in 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.

Problem F. Follow the procedure in 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.

Ans: For Hashing algorithms, outlook provides SHA1 and MD5. For encryption algorithms, provides 3DES, RC2(128bit, 64bit, 40bit), and DES.


Option Problem E. 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 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

# 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 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 -out <login>publickey.pem



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.