ICOM 5018 EXAM I - Spring 2007

March 1, 2007


Open books and notes. Only the text, slide printouts and your own notes may be used.

In the interests of originality and creativity please turn off all electronic communication devices including celulares, laptops, pocket computing devices and telepathic capability if you have it.

1.       The following relate to symmetric (private-key) cryptography.

a.       When in the cycle of cryptosystem development and use is differential cryptanalysis normally done?  This means initial development, or cryptoanalysis by an adversary, etc.?  Explain.

Since it is a known plaintext attack, it is usually applied under somewhat artificial circumstances, most commonly to test a system before release.  It can also be employed if a new system is discovered to be in use to test for possible weak keywords or suspected monotonous plaintext.

b.       S-boxes are used in DES and many other symmetric ciphers.  What is the purpose of using S-boxes in DES rather than some other substitution process,

The S-box is a relatively small (In DES it is 64 locations by 4 bits) and thus takes relatively little hardware or memory.


c.       What other feature of the cipher mitigates the effect of the small scope (6 or 8 bits input) of the small S-boxes?

In most algorithms the S-Box receives a highly permuted input, which diffuses the data through all the S-boxes.  If permutation (P-boxes) were not used, the S-box approach would cause the cipher to have undesirable correlations between bits of ciphertext, among other tragedies.

d.       Why is it possible to use S-boxes in a Feistel block ciphers, but difficult otherwise?

The S-box (unless square, for example 8x8) is a one-way device – Feistel is a configuration that permits using a one-way function as part of a two-way round function.


2.       The following apply to public-key cryptography.  Please answer the following, briefly, but avoiding the dreaded RADQ.

You are attempting to generate a key pair for use with the RSA algorithm.  Unfortunately you chose q=rs, which you mistakenly thought was a prime – it is instead the product of two primes.  You then generate a randomly chosen encryption key e, and then calculate d as usual.

a.       Do you discover the nonprimality of q during the process of finding d?  Explain.

No, you find e by solving de=1 mod (φ(n) assumed = (p-1)(q-1).
 The actual φ(n)=(p-1)(r-1)s-1), so you will publish an incorrect d.

b.       Now assume you have published n (the product of p and q), but don’t publish p or q and also e but not d.  People begin sending you messages encrypted in (n, e).  What happens that tells you something is wrong?

No messages decrypt into recognizable plaintext.  You know something is wrong with your key, but not what.


c.       You decide to keep using the key, after you discover the factorization of q.  Can you then decrypt messages encrypted using (n, e), and if so, how do you do it

You find d using the correct φ(n)=(p-1)(r-1)s-1), then with the new values of d you can decrypt the past messages as well as the future ones.

d.       Describe a possible weakness of the resulting cipher.

The smallest factor of n is now either r or s.  Both of these are smaller than the square root of q, or approximately the fourth root of n.  If anyone is testing they will factor to find r and s, and then struggle a bit to discover if p is prime.  Then they know φ(n) and can find d.

e.       Suppose you instead are using the key for authentication.  What is the indication that something is wrong?

Only when you hear that destinations are not believing your authentication.


3.      Please answer the following, briefly, but avoiding the dreaded RADQ.

a.       What is the difference between stream cipher and block ciphers?

Stream ciphers can operate on byte-by-byte text rather than an integral number of blocks.  Usually the needed cipher data can be generated before use.

b.      Why would a stream cipher be desirable for transmitting irregular but fast data such as images or high-bandwidth telemetry?

Irregular (in time)  data of arbitrary size can be sent and decrypted as it appears without waiting for complete block-sized input.  Also, with many stream ciphers OFB is used, so a cryptosequence can be precomputed and stored.

c.       Why is AES preferable to triple-DES

Primarily the larger block size (128) which makes suspected text cryptanalysis much more difficult.  Key length for triple-DES is actually larger than for AES

d.      What is the difference between a person-in-the middle attack and a meet-in-the middle attack?

The person-in-the-middle has control of the channel and can insert and delete.  Typical person-in-the-middle attacks involve replacement of one message with another, or even absorbing and replacing data. 

Meet-in-the-middle is a form of coincidence-discovery attack in which pairs of keys or messages are discovered to produce matching results.