学步园

Problem 1. Find (31)-1 mod38923,i.e., the multiplicative inverse of 31 modulo38923.
Please use the extended Euclidean algorithm, which is a slight modification of the
Euclidean algorithm. Give details of your computation.

Problem 2. Use the Affine cipher with key (k0 ,k1 ) =(3, 2) to encrypt the following
plaintext(message)(fordefinition, seePage12 ofLecture4):

TOMORROW AT THREE

Problem 3. The piece of ciphertext posted at the URL:

http://www.cs.ust.hk/faculty/cding/COMP581/PROJECTS/ciphert0.html

isobtained using asimple substitution cipher(some punctuation symbols and most
blank spaces are deleted) and the language is English. Decrypt it by using the
frequency distribution of English letters. You may also use the fact that certain
digrams(e.g., an, en, er, es,he) appear more frequently. This may help you. Please
also give some details about how you decrypt it.

Note that the beginning of every line in the ciphertext is the beginning of an English
word, and the end of every line is the end of an English word. You may use the
online software at:

http://cryptoclub.math.uic.edu/substitutioncipher/frequency_txt.htm

for the frequency analysis.

Problem 4. WiththeECBmode ofDES,ifthereis an errorin ablock ofthetransmitted
ciphertext,only thecorrespondingplaintextblockisaffected. However,intheCBC
mode(seepage8 ofLecture06),thiserrorpropagates. Forexample,anerrorin
transmitted block c1 obviously corrupts two plaintext blocks m1 and m2 .

(A) Are there any blocks beyond m2 affected?
(B) Suppose that there is a bit error in the source version of m1 . Through how
many ciphertext blocks is this error propagated? What is the effect at the
receiver end?

Problem 5. Suppose that Bob’s public key for the RSA public-key cipher is (23, 55)
and his private key is 7.

a Use Bob’s public key to encrypt the message 53.
b Use Bob’s private key to decrypt the ciphertect 33.  

1.

qi <- quotient(ri-2 /r i-1), ri <- ri-2 mod ri-1

xi <- xi-2 - qi · xi-1 ,    yi <- yi-2 - qi · yi-1

So the multiplicative inverse of 31 modulo 38923 is 15067

2.