Order ID:89JHGSJE83839 | Style:APA/MLA/Harvard/Chicago | Pages:5-10 |
Instructions:
CPSC467 Cryptography and Computer Security Handout
CPSC467 Cryptography and Computer Security Handout #9 Xueyuan Su October 12, 2008
Solution to Problem Set 2 In this problem set, we consider a variant of the Caesar cipher which we call the “Happy” cipher (named after the venerable “Happy Hacker” of CPSC 223 fame). Happy (E, D) is defined as follows: Let X1 = {0, . . . , 12} and X2 = {13, . . . , 25}. Let M = C = K = X = X1 ∪ X2, and let n = |X| = 26. Define
Ek(m) =
(m + k) mod 13 if k ∈ X1 ∧ m ∈ X1 m if k ∈ X1 ∧ m ∈ X2 m if k ∈ X2 ∧ m ∈ X1 ((m + k) mod 13) + 13 if k ∈ X2 ∧ m ∈ X2
We also consider Double Happy (E2, D2). Here, K2 = K×K, and E2 (k1,k2)
= Ek2 (Ek1 (m)).
Problem 1: Happy Encryption (5 points)
Encrypt the plaintext “i am a secret message” using Happy with key k = 3. (As usual, we will ignore spaces.)
Solution: m = “i am a secret message”; k = 3; c = “l dc d shfrht chssdjh”.
Problem 2: Happy Decryption (5 points)
Describe the Happy decryption function Dk(c).
Solution:
Dk(c) =
(c − k) mod 13 if k ∈ X1 ∧ c ∈ X1 c if k ∈ X1 ∧ c ∈ X2 c if k ∈ X2 ∧ c ∈ X1
((c − k) mod 13) + 13 if k ∈ X2 ∧ c ∈ X2
(1)
Problem 3: Security (10 points)
Is Happy information-theoretically secure? Why or why not?
Is Double Happy information-theoretically secure? Why or why not?
Solution: (a) No. Before observing any cipher text, the probability of the plain text m being a specific
letter m0 is P rob[m = m0] = 126 . After observing the cipher text, say c = m0, the probability of the plain text m = m0 becomes P rob[m = m0 | c = m0] = 1426 . Assuming m0 = 23, Figure 1
2 Solution to Problem Set 2
0
0.2
0.4
0.6
0.8
1
0 5 10 15 20 25
P ro
b a b
il iy
D e n si
ty F
u n c ti
n
letter
prior probability
Prior probability
0
0.2
0.4
0.6
0.8
1
0 5 10 15 20 25
P ro
b a b
il iy
D e n si
ty F
u n c ti
n
letter
posterior probability
Posterior probability
Figure 1: Probability distributions.
illustrates the plain text prior probability distribution and posterior probability distribution after we learn the cipher text c = m0 = 23.
Similar to (a).
Problem 4: Equivalent Key Pairs (10 points)
Suppose m0 = c0 = 4.
Find all key pairs (k, k′) such that E2 (k,k′)(m0) = c0.
Do all such key pairs give rise to the same function E2 (k,k′)? That is, if E
2 (k̂,k̂′)
(m0) =
E2 (k,k′)(m0) = c0, does E
2 (k̂,k̂′)
(m) = E2 (k,k′)(m) for all m ∈M? Why or why not?
Solution: (a) Note that m0, k0 ∈ X1. There are four different cases:
1) {(k, k ′ ) | k, k
′ ∈ X2}
2) {(k, k ′ ) | k = 0, k
′ ∈ X2}
3) {(k, k ′ ) | k
′ = 0, k ∈ X2}
4) {(k, k ′ ) | k, k
′ ∈ X1, (k + k
′ ) mod13 = 0}
No. For example, if m = 13, then E213,14(13) = 14 (case 1), but E 2 1,12(13) = 13 (case 4).
Problem 5: Group Property (10 points)
Is Happy a group? Why or why not?
Solution: No. group property requires that for any key pairs k1, k2 ∈ X, there is always a single key
k ∈ X, such that Ek1,k2 (m) = Ek(m) for any m ∈ X. Taking k1 = 1, k2 = 14 for example, now we will show that ∀k, there ∃m such that Ek1,k2 (m) 6= Ek(m).
k ∈ X1: E1,14(13) = 14, but Ek(13) = 13
Handout #9—October 12, 2008 3
k ∈ X2: E1,14(0) = 1, but Ek(0) = 0
The following problems ask you to compute probabilities. You may do so either analytically (if you’re facile with combinatorial counting techniques) or experimentally by writing a program to simulate 1000 random trials and reporting the fraction of times that the desired result is obtained. Either way, you should show your work – analytic derivation, or program and simulation results.
Problem 6: Birthday Problem (20 points)
Suppose u1, . . . , u6 and v1, . . . , v6 are chosen uniformly and independently at random from X (so duplicates are possible. Find the probability that {u1, . . . , u6} ∩ {v1, . . . , v6} 6= ∅. (Note that 6 = d
√ ne.)
Solution: We first calculate the probability that sets {ui} and {vi} do not have intersection and analyze
this situation case by case as follows: 1) 6 members of set {ui} are identical, (i.e., the form 6), {vi} choose from the remaining 25
letters: p1 = [1 × (
1 26
)5] × [( 25 26
)6] (2)
2) 5 members of set {ui} are identical, (i.e., the form 5:1), {vi} choose from the remaining 24 letters:
p2 =
( 6 5
) × [1 × (
1 26
)4 × 25 26
] × [( 24 26
)6] (3)
3) 4 members of set {ui} are identical, the rest 2 members themselves are identical, (i.e., the form 4:2), {vi} choose from the remaining 24 letters:
p3 =
( 6 4
) × [1 × (
1 26
)3 × 25 26 ×
1 26
] × [( 24 26
)6] (4)
4) 4 members of set {ui} are identical, the rest 2 members themselves are different, (i.e., the form 4:1:1), {vi} choose from the remaining 23 letters:
p4 =
( 6 4
) × [1 × (
1 26
)3 × 25 26 ×
24 26
] × [( 23 26
)6] (5)
3 members of set {ui} are identical, the rest 3 members themselves are identical, (i.e., the form 3:3), {vi} choose from the remaining 24 letters:
p5 =
( 6 3
) ×
1 2! × [1 × (
1 26
)2 × 25 26 × (
1 26
)2] × [( 24 26
)6] (6)
3 members of set {ui} are identical, other 2 members themselves are identical, the last one is different (i.e., the form 3:2:1), {vi} choose from the remaining 23 letters:
p6 =
( 6 3
) × (
3 2
) × [1 × (
1 26
)2 × 25 26 ×
1 26 ×
24 26
] × [( 23 26
)6] (7)
4 Solution to Problem Set 2
3 members of set {ui} are identical, the rest 3 members themselves are all different, (i.e., the form 3:1:1:1), {vi} choose from the remaining 22 letters:
p7 =
( 6 3
) × [1 × (
1 26
)2 × 25 26 ×
24 26 ×
23 26
] × [( 22 26
)6] (8)
{ui} are in the form of 2:2:2, {vi} choose from the remaining 23 letters:
p8 =
( 6 2
) × (
4 2
) ×
1 3! × [1 ×
1 26 ×
25 26 ×
1 26 ×
24 26 ×
1 26
] × [( 23 26
)6] (9)
{ui} are in the form of 2:2:1:1, {vi} choose from the remaining 22 letters:
p9 =
( 6 2
) × (
4 2
) ×
1 2! × [1 ×
1 26 ×
25 26 ×
1 26 ×
24 26 ×
23 26
] × [( 22 26
)6] (10)
{ui} are in the form of 2:1:1: 1:1, {vi} choose from the remaining 21 letters:
p10 =
( 6 2
) × [1 ×
1 26 ×
25 26 ×
24 26 ×
23 26 ×
22 26
] × [( 21 26
)6] (11)
All members of {ui} are different, (i.e., the form of 1:1:1:1:1:1), {vi} choose from the remaining 20 letters:
p11 = [1 × 25 26 ×
24 26 ×
23 26 ×
22 26 ×
21 26
] × [( 20 26
)6] (12)
Then the probability of non-empty intersection between ui and vi is:
p = 1 − 11∑
j=1
pj ≈ 0.752486 (13)
The above calculation is pretty tedious, but it helps to understand the detailed analysis. We can also use Monte Carlo simulation to obtain the success probabilities.
We can make use of the randRange() function we constructed in PS1 to generate a 6 random numbers ui and another 6 random numbers vi. Then we check each pair of (ui, vi) one by one to see whether there is a match. If there is such match, the counter increases by 1. In each experiment we run 1, 000, 000 trials and calculates the non-empty intersection probability. Then we run the experiments for 100 times and calculate the probability. The result is shown in Figure 2. The average probability is about 75.25%.
Problem 7: Birthday Attack on Double Happy (40 points)
Assume Alice chooses a random key pair (k0, k′0) and a random message m and computes c = E2
(k0,k ′ 0 ) (m) using Double Happy. Eve learns the plaintext-ciphertext pair (m, c) and then carries
out the Birthday Attack for m ∈M and c ∈C as follows:
She chooses k1, . . . , k6 uniformly at random from K and computes ui = Eki (m) for i = 1, . . . , 6.
She chooses k′1, . . . , k ′ 6 uniformly at random from K and computes vj = Dk′j (c) for j =
1, . . . , 6.
Handout #9—October 12, 2008 5
0
0.2
0.4
0.6
0.8
1
0 10 20 30 40 50 60 70 80 90 100
P ro
b a b il
it y o
f su
c c e ss
Experiment #
Non-empty intersection
Figure 2: Probability of non-empty intersection.
If {u1, . . . , u6} ∩ {v1, . . . , v6} 6= ∅, we say the Birthday Attack succeeds in producing a candidate key pair. In that case, Eve obtains the candidate key pair (k, k′) = (ki, k′j ), where (i, j) is the lexicographically smallest pair such that ui = vj .
If a candidate key pair (k, k′) is produced and (k, k′) can be used to decrypt any message Alice might send using her key, that is, if D2
(k,k′)(E 2 (k0,k
′ 0 ) (m)) = m for all m ∈M, then we
say the Birthday Attack succeeds in breaking Double Happy.
Find the probability that the Birthday Attack succeeds in producing a candidate key pair, and compare your result with your answer to problem 6.
Find the probability that the Birthday Attack succeeds in breaking Double Happy.
Solution: (a) To successfully produce a candidate key pair, it means that the Birthday Attack succeeds in
finding a key pair that decrypts a known plaintext-ciphertext pair (m, c). We still make use of the randRange() function to generate a random plain letter m and a key
pair (k0, k ′ 0). We use this key pair to encrypt m and get c. Now we need to generate 6 random keys
ki and another 6 random keys k ′ i. Use ki to encrypt m we get the set of {ui} and use k
′ i to decrypt
c we get the set of {vi}. Then if there is a match between any pair of (ui, vi), the counter increases by 1. In each experiment we run 1, 000, 000 trials and calculates the probability of succeeding in producing a candidate key pair. Then we run the experiments for 100 times and calculate the probability. The result is shown in Figure 3. The average probability is about 75.29%.
To successfully break Double Happy, it means that the candidate key can decrypts all the cipertext produced from any m ∈ X with the key pair that Alice owns. Due to the special property of Double Happy, it is suffice to show that if the candidate key pair can decrypts one plaintext- ciphertext pair (m1, c1) ∈ X1 and another plaintext-ciphertext pair (m2, c2) ∈ X2, it can break the entire encryption system.
Therefore, we make use of the randRange() function to generate two random plain letter m1 ∈ X1 and m2 ∈ X2, and a key pair (k0, k
′ 0). We use this key pair to encrypt m1, m2 and get c1, c2.
Now we need to generate 6 random keys ki and another 6 random keys k ′ i. Use ki to encrypt m we
get the set of {ui} and use k ′ i to decrypt c we get the set of {vi}. By finding the match between
any pair of (ui, vi), we find the candidate key pair that can decrypts (m1, c1). If we also succeed in
6 Solution to Problem Set 2
decrypting (m2, c2) with the same candidate key pair, we have succeeded in producing a candidate key pair that breaks Double Happy. In each experiment we run 1, 000, 000 trials and calculates the probability of succeeding in breaking Double Happy. Then we run the experiments for 100 times and calculate the probability. The result is shown in Figure 3. The average probability is about 13.53%.
0
0.2
0.4
0.6
0.8
1
0 20 40 60 80 100
P ro
b a b
il it
y o
f su
c c e ss
Experiment #
Finding candidate key pair Breaking Double Happy
Figure 3: Birthday attack on Double Happy.
Happy Encryption (5 points)
Happy Decryption (5 points)
Security (10 points)
Equivalent Key Pairs (10 points)
Group Property (10 points)
Birthday Problem (20 points)
128
Environmental Policies for Hotel Essay Paper
Questions
Does the hotel have a clearly defined environmental policy?
Does the hotel enlighten its staff with regard to environmental policy, and provide the role of staff in the implementation of this policy?
Does the hotel allow public participation in its effort to operate according to the set environmental policy?
How does the hotel minimize waste production and water consumption?
Does the hotel make an effort to communicate about its dedication to sustainability with the public and stakeholders?
Does the hotel monitor and record environmental impacts regularly? Does it compare its performance with the set targets and policies?
Does the hotel comply with all relevant legislations?
Does the hotel use renewable energy? Does the hotel have any partnership with local producers of renewable energy?
What are the various methods of energy-efficiency the hotel use?
How does the hotel ensure efficient water usage, recycle and treatment?
Have measures been taken to reduce the use of disposable products to minimum such as cutlery?
Does the hotel provide separate containers for storing hazardous waste, and provide appropriate site for processing the hazardous waste?
Recommendations for Improvement
Questions
How can the hotel influence the public and its stakeholders to support its environmental policy?
What measures should the hotel undertake to influence the public to participate in activities related to improved environmental policy?
What method of training and communication is sufficient to help the hotel’s management and subordinate staff appreciate their roles in matters relating to environmental policies?
How regular should the hotel collect data regarding environmental control and relate it to its performance?
What are the best energy-efficient methods should the hotel use to improve its energy saving or utilization?
How should the hotel ensure better water consumption with minimal wastage?
What are the best principles and policies should the hotel adopt to minimize waste production?
How should the hotel ensure monthly or annual reports on its progress on set goals and targets with regard to environmental policy?
How should the hotel regulate gaseous waste emission and quality air supply?
Can the hotel use public and campaigns awareness to emphasize on importance of environmental policy to both the public and its staff?
RUBRIC |
||||||
Excellent Quality 95-100%
|
Introduction
45-41 points The background and significance of the problem and a clear statement of the research purpose is provided. The search history is mentioned. |
Literature Support 91-84 points The background and significance of the problem and a clear statement of the research purpose is provided. The search history is mentioned. |
Methodology 58-53 points Content is well-organized with headings for each slide and bulleted lists to group related material as needed. Use of font, color, graphics, effects, etc. to enhance readability and presentation content is excellent. Length requirements of 10 slides/pages or less is met. |
|||
Average Score 50-85% |
40-38 points More depth/detail for the background and significance is needed, or the research detail is not clear. No search history information is provided. |
83-76 points Review of relevant theoretical literature is evident, but there is little integration of studies into concepts related to problem. Review is partially focused and organized. Supporting and opposing research are included. Summary of information presented is included. Conclusion may not contain a biblical integration. |
52-49 points Content is somewhat organized, but no structure is apparent. The use of font, color, graphics, effects, etc. is occasionally detracting to the presentation content. Length requirements may not be met. |
|||
Poor Quality 0-45% |
37-1 points The background and/or significance are missing. No search history information is provided. |
75-1 points Review of relevant theoretical literature is evident, but there is no integration of studies into concepts related to problem. Review is partially focused and organized. Supporting and opposing research are not included in the summary of information presented. Conclusion does not contain a biblical integration. |
48-1 points There is no clear or logical organizational structure. No logical sequence is apparent. The use of font, color, graphics, effects etc. is often detracting to the presentation content. Length requirements may not be met |
|||
You Can Also Place the Order at www.collegepaper.us/orders/ordernow or www.crucialessay.com/orders/ordernow
CPSC467 Cryptography and Computer Security Handout |
CPSC467 Cryptography and Computer Security Handout