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.
[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
7
(4^37 % 77)^53 % 77
37
(11^37 % 77)^53 % 77
44
(3^37 % 77)^53 % 77
47
We got exact the same enciphered block values.
(7^17 % 77)^13 % 77
7
(37^17 % 77)^13 % 77
4
(44^17 % 77)^13 % 77
11
(47^17 % 77)^13 % 77
3
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
j
v
w
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
THE TIME HAS COME THE WALRUS SAID TO TALK OF MANY THINGS
OF SHIPS AND SHOES AND SEALING WAX OF CABBAGES AND KINGS
AND WHY THE SEA IS BOILING HOT AND WHETHER PIGS HAVE WINGS
BUT WAIT A BIT THE OYSTERS CRIED BEFORE WE HAVE OUR CHAT
FOR SOME OF US ARE OUT OF BREATH AND ALL OF US ARE FAT
NO HURRY SAID THE CARPENTER THEY THANKED HIM MUCH FOR THAT
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 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.
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.
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
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 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
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.