Questions and Answers of Cryptography And Network Security

What is the difference between statistical randomness and unpredictability?
List important design considerations for a stream cipher.
Why is it not desirable to reuse a stream cipher key?
What primitive operations are used in RC4?
If we take the linear congruential algorithm with an additive component of 0,Then it can be shown that if m is prime and if a given value of produces the maximum period of m - 1, then ak will also
a. What is the maximum period obtainable from the following generator?b. What should be the value of ?c. What restrictions are required on the seed? Xn+1 = (aXn) mod 24
You may wonder why the modulus m = 231 - 1 was chosen for the linear congruential method instead of simply 231, because this latter number can be represented with no additional bits and the mod
With the linear congruential algorithm, a choice of parameters that provides a full period does not necessarily provide a good randomization. For example, consider the following two generators:Write
In any use of pseudorandom numbers, whether for encryption, simulation, or statistical design, it is dangerous to trust blindly the random number generator that happens to be available in your
Suppose you have a true random bit generator where each bit in the generated stream has the same probability of being a 0 or 1 as any other bit in the stream and that the bits are not correlated;
Another approach to deskewing is to consider the bit stream as a sequence of nonoverlapping groups of n bits each and output the parity of each group. That is, if a group contains an odd number of
What RC4 key value will leave S unchanged during initialization? That is, after the initial permutation of S, the entries of S will be equal to the values from 0 through 255 in ascending order.
RC4 has a secret internal state which is a permutation of all the possible values of the vector S and the two indices and .a. Using a straightforward scheme to store the internal state, how many
Alice and Bob agree to communicate privately via email using a scheme based on RC4, but they want to avoid using a new secret key for each transmission. Alice and Bob privately agree on a 128-bit key
What is the meaning of the expression divides ?
What is Euler’s totient function?
The Miller-Rabin test can determine if a number is not prime but cannot determine if a number is prime. How can such an algorithm be used to test for primality?
What is a primitive root of a number?
What is the difference between an index and a discrete logarithm?
The purpose of this problem is to determine how many prime numbers there are. Suppose there are a total of \(n\) prime numbers, and we list these in order: \(p_{1}=2
The purpose of this problem is to demonstrate that the probability that two random numbers are relatively prime is about 0.6. a. Let \(P=\operatorname{Pr}[\operatorname{gcd}(a, b)=1]\). Show that
Why is \(\operatorname{gcd}(n, n+1)=1\) for two consecutive integers \(n\) and \(n+1\) ?
Using Fermat's theorem, find \(3^{201} \bmod 11\).
Use Fermat's theorem to find a number \(a\) between 0 and 72 with \(a\) congruent to 9794 modulo 73.
Use Fermat's theorem to find a number \(x\) between 0 and 28 with \(x^{85}\) congruent to 6 modulo 29. (You should not need to use any brute-force searching.)
Use Euler's theorem to find a number \(a\) between 0 and 9 such that \(a\) is congruent to \(7^{1000}\) modulo 10. (Note: This is the same as the last digit of the decimal expansion of \(7^{1000}\).)
Use Euler's theorem to find a number \(x\) between 0 and 28 with \(x^{85}\) congruent to 6 modulo 35. (You should not need to use any brute-force searching.)
Notice in Table 8.2 that \(\phi(n)\) is even for \(n>2\). This is true for all \(n>2\). Give a concise argument why this is so.
Prove the following: If \(p\) is prime, then \(\phi\left(p^{i}ight)=p^{i}-p^{i-1}\). Hint: What numbers have a factor in common with \(p^{i}\) ?
It can be shown (see any book on number theory) that if \(\operatorname{gcd}(m, n)=1\) then \(\phi(m n)=\phi(m) \phi(n)\). Using this property, the property developed in the preceding problem, and
It can also be shown that for arbitrary positive integer \(a, \phi(a)\) is given by\[\phi(a)=\prod_{i=1}^{t}\left[p_{i}^{a_{i}-1}\left(p_{i}-1ight)ight]\]where \(a\) is given by Equation (8.1),
Consider the function: \(\mathrm{f}(n)=\) number of elements in the set \(\{a: 0 \leq a
Although ancient Chinese mathematicians did good work coming up with their remainder theorem, they did not always get it right. They had a test for primality. The test said that \(n\) is prime if and
Show that, if \(n\) is an odd composite integer, then the Miller-Rabin test will return inconclusive for \(a=1\) and \(a=(n-1)\).
If \(n\) is composite and passes the Miller-Rabin test for the base \(a\), then \(n\) is called a strong pseudoprime to the base a. Show that 2047 is a strong pseudoprime to the base 2.
A common formulation of the Chinese remainder theorem (CRT) is as follows: Let \(m_{1}, \ldots, m_{k}\) be integers that are pairwise relatively prime for \(1 \leq i, j \leq k\), and \(i eq j\).
The example used by Sun-Tsu to illustrate the CRT was\[x \equiv 2(\bmod 3) ; x \equiv 3(\bmod 5) ; x \equiv 2(\bmod 7)\]Solve for \(x\).
Six professors begin courses on Monday, Tuesday, Wednesday, Thursday, Friday, and Saturday, respectively, and announce their intentions of lecturing at intervals of 2,3,4, 1,6 , and 5 days,
Find all primitive roots of 25 .
Given 2 as a primitive root of 29 , construct a table of discrete logarithms, and use it to solve the following congruences.a. \(17 x^{2} \equiv 10(\bmod 29)\)b. \(x^{2}-4 x-16 \equiv 0(\bmod 29)\)c.
Write a computer program that implements fast exponentiation (successive squaring) modulo \(n\).
Write a computer program that implements the Miller-Rabin algorithm for a userspecified \(n\). The program should allow the user two choices: (1) specify a possible witness \(a\) to test using the
What are the principal elements of a public-key cryptosystem?
What are the roles of the public and private key?
What are three broad categories of applications of public-key cryptosystems?
What requirements must a public key cryptosystems fulfill to be a secure algorithm?
What is a one-way function?
What is a trap-door one-way function?
Describe in general terms an efficient procedure for picking a prime number.
Prior to the discovery of any specific public-key schemes, such as RSA, an existence proof was developed whose purpose was to demonstrate that public-key encryption is possible in theory. Consider
Perform encryption and decryption using the RSA algorithm, as in Figure 9.5, for the following:a. \(p=3 ; q=11, e=7 ; M=5\)b. \(p=5 ; q=11, e=3 ; M=9\)c. \(p=7 ; q=11, e=17 ; M=8\)d. \(p=11 ; q=13,
In a public-key system using RSA, you intercept the ciphertext \(C=10\) sent to a user whose public key is \(e=5, n=35\). What is the plaintext \(M\) ?
In an RSA system, the public key of a given user is \(e=31, n=3599\). What is the private key of this user? Hint: First use trial-and-error to determine \(p\) and \(q\); then use the extended
In using the RSA algorithm, if a small number of repeated encodings give back the plaintext, what is the likely cause?
Suppose we have a set of blocks encoded with the RSA algorithm and we don't have the private key. Assume \(n=p q, e\) is the public key. Suppose also someone tells us they know one of the plaintext
In the RSA public-key encryption scheme, each user has a public key, \(e\), and a private key, \(d\). Suppose Bob leaks his private key. Rather than generating a new modulus, he decides to generate a
Suppose Bob uses the RSA cryptosystem with a very large modulus \(n\) for which the factorization cannot be found in a reasonable amount of time. Suppose Alice sends a message to Bob by representing
Using a spreadsheet (such as Excel) or a calculator, perform the operations described below. Document results of all intermediate modular multiplications. Determine a number of modular
Assume that you generate an authenticated and encrypted message by first applying the RSA transformation determined by your private key, and then enciphering the message using recipient's public key
"I want to tell you, Holmes," Dr. Watson's voice was enthusiastic, "that your recent activities in network security have increased my interest in cryptography. And just yesterday I found a way to
Show how RSA can be represented by matrices M1, M2, and M3 of Problem 9.1.
Consider the following scheme:1. Pick an odd number, \(E\).2. Pick two prime numbers, \(P\) and \(Q\), where \((P-1)(Q-1)-1\) is evenly divisible by \(E\).3. Multiply \(P\) and \(Q\) to get \(N\).4.
Consider the following scheme by which B encrypts a message for A.1. A chooses two large primes \(P\) and \(Q\) that are also relatively prime to \((P-1)\) and \((Q-1)\).2. A publishes \(N=P Q\) as
"This is a very interesting case, Watson," Holmes said. "The young man loves a girl, and she loves him too. However, her father is a strange fellow who insists that his would-be son-in-law must
Use the fast exponentiation algorithm of Figure 9.8 to determine \(5^{596} \bmod 1234\). Show the steps involved in the computation. c 0; f 1 for ik downto 0 do c 2 X c f (f x f) mod n if b = 1 then
Here is another realization of the fast exponentiation algorithm. Demonstrate that it is equivalent to the one in Figure 9.8.1. \(\mathrm{f} \leftarrow 1 ; \mathrm{T} \leftarrow \mathrm{a} ;
The problem illustrates a simple application of the chosen ciphertext attack. Bob intercepts a ciphertext \(C\) intended for Alice and encrypted with Alice's public key \(e\). Bob wants to obtain the
Show the OAEP decoding operation used for decryption that corresponds to the encoding operation of Figure 9.10.
Improve on algorithm P1 in Appendix 9B.a. Develop an algorithm that requires \(2 n\) multiplications and \(n+1\) additions. Hint: \(x^{i+1}=x^{i} \times x\).b. Develop an algorithm that requires only
What items are in the knapsack in Figure F.1?
Perform encryption and decryption using the knapsack algorithm for the following:a. \(\mathbf{a}^{\prime}=(1,3,5,10) ; w=7 ; m=20 ; \mathbf{x}=1101\)b. \(\mathbf{a}^{\prime}=(1,3,5,11,23,46,136,263)
Why is it a requirement that \(m>\sum_{1=1}^{n} a^{\prime}{ }_{i}\) ?
Briefly explain Diffie-Hellman key exchange.
What is an elliptic curve?
What is the zero point of an elliptic curve?
What is the sum of three points on an elliptic curve that lie on a straight line?
Users A and B use the Diffie-Hellman key exchange technique with a common prime \(q=71\) and a primitive root \(\alpha=7\).a. If user A has private key \(X_{A}=5\), what is A's public key \(Y_{A}\)
Consider a Diffie-Hellman scheme with a common prime \(q=11\) and a primitive root \(\alpha=2\).a. Show that 2 is a primitive root of 11 .b. If user A has public key \(Y_{A}=9\), what is A's private
In the Diffie-Hellman protocol, each participant selects a secret number \(x\) and sends the other participant \(\alpha^{x} \bmod q\) for some public number \(\alpha\). What would happen if the
This problem illustrates the point that the Diffie-Hellman protocol is not secure without the step where you take the modulus; i.e. the "Indiscrete Log Problem" is not a hard problem! You are Eve and
Describes a man-in-the-middle attack on the Diffie-Hellman key exchange protocol in which the adversary generates two public-private key pairs for the attack. Could the same attack be accomplished
Consider an ElGamal scheme with a common prime \(q=71\) and a primitive root \(\alpha=7\).a. If \(\mathrm{B}\) has public key \(Y_{B}=3\) and \(\mathrm{A}\) chose the random integer \(k=2\), what is
Rule (5) for doing arithmetic in elliptic curves over real numbers states that to double a point \(Q_{2}\), draw the tangent line and find the other point of intersection \(S\). Then \(Q+Q=2 Q=-S\).
Demonstrate that the two elliptic curves of Figure 10.4 each satisfy the conditions for a group over the real numbers. 4 2 0 -21 -4 -2 P -1 1 (a) y = x3 . 2 - (P + Q) (P + Q) 3 4 5
Is \((4,7)\) a point on the elliptic curve \(y^{2}=x^{3}-5 x+5\) over real numbers?
On the elliptic curve over the real numbers \(y^{2}=x^{3}-36 x\), let \(P=(-3.5,9.5)\) and \(Q=(-2.5,8.5)\). Find \(P+Q\) and \(2 P\).
Does the elliptic curve equation \(y^{2}=x^{3}+10 x+5\) define a group over \(Z_{17}\) ?
Consider the elliptic curve \(\mathrm{E}_{11}(1,6)\); that is, the curve is defined by \(y^{2}=x^{3}+x+6\) with a modulus of \(p=11\). Determine all of the points in \(\mathrm{E}_{11}(1,6)\). Hint:
What are the negatives of the following elliptic curve points over \(Z_{17}\) ? \(P=(5,8) ; Q=\) \((3,0) ; \mathrm{R}=(0,6)\).
For \(\mathrm{E}_{11}(1,6)\), consider the point \(G=(2,7)\). Compute the multiples of \(G\) from \(2 G\) through \(13 G\).
This problem performs elliptic curve encryption/decryption using the scheme outlined in Section 10.4. The cryptosystem parameters are \(\mathrm{E}_{11}(1,6)\) and \(G=(2,7)\). B's secret key is
The following is a first attempt at an elliptic curve signature scheme. We have a global elliptic curve, prime \(p\), and "generator" \(G\). Alice picks a private signing key \(X_{A}\) and forms the
Here is an improved version of the scheme given in the previous problem. As before, we have a global elliptic curve, prime \(p\), and "generator" \(G\). Alice picks a private signing key \(X_{A}\)
What characteristics are needed in a secure hash function?
What is the difference between weak and strong collision resistance?
What is the role of a compression function in a hash function?
What is the difference between little-endian and big-endian format?
What basic arithmetical and logical functions are used in SHA?
The high-speed transport protocol XTP (Xpress Transfer Protocol) uses a 32-bit checksum function defined as the concatenation of two 16-bit functions: XOR and RXOR, defined in Section 11.4 as “two
a. Consider the Davies and Price hash code scheme described in Section 11.4 and assume that DES is used as the encryption algorithm:If Y = E(K, X), then Y′ = E(K′, X′) Use this property to show

Showing 1 - 100 of 498