Reference no: EM133684146
Mathematical Sciences
Assignment 1: For any finite alphabet A (finite set of symbols), A∗ denotes the set of finite strings (or finite words) on A. Note that A∗ includes the empty string, denoted ε.
Question 1. A hash function is used to transform a text, binary string or number into a fixed-length hash value (for instance a fixed-length binary string). Hash functions are typically not injective functions. We then call hash collision a pair of entries with the same hash value. This represents a security threat. Suppose for instance that we store a data base of users identified using a 5 digits user number and a 4 digit code. Any legal entry to a service, say for instance a related website, will be granted based on a 9 digits number (user number and code). Instead of storing the user numbers and related codes in the database, we decide to store only a hash value of these 9-digit numbers coded on 16 binary digits. Then, the access to the website is granted if the hash value of the 9-digit input corresponds to a valid hash value. In addition, the system allows only to try one combination (user number + code) from a single IP address every 10 seconds to prevent a malicious agent from using a brute force approach. We denote by C the set of all 9-digit numbers and by H = {0, 1}16 the set of all possible 16 digit binary strings.
a) [(K,M,P,E)=(1,0,1,1)]
Give a brief justification that |C| = 109 and |H| = 216.
b) [(K,M,P,E)=(1,1,1,1)]
When choosing the possible user numbers and corresponding codes, we ensure that two different entries in the database correspond to different hash values (no collision) to be able to identify the user based on the hash value only. Justify that, if there are 65537 users or more, then it is not possible to uniquely identify them based on the hash value.
c) One of the most naive hash function will transform a 9 digit number into the sum of digits coded as a 16 binary digit string.
i) [(K,M,P,E)=(0,1,0,1)]
How many possible values do we have for the related hash values? Does it sound reasonable?
ii)[(K,M,P,E)=(0,1,0,1)]
Justify that, for this hash function, it is easy to enumerate a list of possible entries with different hash values, and consequently, to find a pre-image for each possible hash value.
d) [(K,M,P,E)=(1,1,1,0)]
Another hash value we can consider maps a 9-digit number a1 . . . a9 ∑i=19 iai first digit is multiplied by 1, the second by two, the third by 3 . . . and then all results are summed.What is the maximum hash value H for this hash function? Briefly comment about the suitability of this hash function for our problem.
e) [(K,M,P,E)=(1,2,1,1)]Suppose now that we are able to find a surjective hash function f from C to H as well as a process to enumerate one pre-image for each possible hash value. If the database includes 104 users, what time at most will it take to a malicious agent to find a collision with a valid hash value?
Question 2. A message written in English that possibly includes numbers is seen as a string with char- acters in the alphabet {σ, 0, 1, . . . , 9, a, b, c, . . . z}, where σ represents the space. A usual way to encrypt such a messages is to define a bijection ? from {0, 1, . . . , 9, a, b, c, . . . z} onto {0, 1, . . . , 9, a, b, c, . . . z} and then, encrypt a word a1 . . . ap with ?(a1) . . . ?(ap) (spaces are kept in the encrypted message).
a) [(K,M,P,E)=(1,0,2,1)]
Justify that, if ? is a bijection, then this encryption defines a bijection from {0, 1, . . . , 9, a, b, c, . . . z}∗ onto {0, 1, . . . , 9, a, b, c, . . . z}∗ and as a consequence, that it can encrypt without ambiguity any message formed by letters, numbers and/or spaces.
A usual way to define ? is to number digits 0, . . . 9 from 0 to 9 and then letters a, . . . , z from 10 to 35 (10 for a, 35 for z) and use a bijection φ : {0, . . . , 35} -→ {0, . . . , 35} so that we can use operations between numbers. Then, the image of the ith character in
{0, 1, . . . , 9, a, b, c, . . . z} is the character numbered with φ(i).
We remind that, for two integers, a, b, b > 0, a mod b is the reminder of the division of
a by b defined by the two following conditions:
c = a mod b <=> 0 ≤ c ≤ b - 1
a ≡ c(mod b)
b) [(K,M,P,E)=(2,2,3,0)]
We define φ : {0, . . . , 35} -→ {0, . . . , 35}
x → 25x + 7 mod 36
Let x, y ∈ {0, . . . , 35} such that φ(x) = φ(y). Show, using Gauss' Theorem (See exercice 2, practical Week 2) that 36 is a factor of |x - y| and conclude that φ is injective.
c) [(K,M,P,E)=(1,0,3,0)]
Deduce from the previous question that φ is bijective.
d) This question aims at determining the inverse of φ, which will give us the a method for decoding a message.
i) [(K,M,P,E)=(2,2,0,0)]
Determine gcd(25, 36) using the Euclidean algorithm and determine two integers (λ, µ) such that λ × 25 + µ × 36 = gcd(25, 36) and deduce that
25 × λ ≡ 1(mod 36) Show all steps of your working on your answer sheet.
Here, you may find worth to use the second version of the algorithm (see Exercise 3, slide 32, Week 2).
[(K,M,P,E)=(2,2,3,0)]
Show that
ψ : {0, . . . , 35} -→ {0, . . . , 35}
y '→ λ × (y - 7) mod 36 is the inverse of φ
We recall that you need to show φ?ψ = ψ?φ = Id, where Id denotes the identity on
{0, . . . , 35} -→ {0, . . . , 35}. We recommend using the result of Exercise 5, practical Week 2.
ii) [(K,M,P,E)=(1,3,0,1)]
Use ψ to decode the message "hxxcp6b 2kh 5c kvp6c 4la".
You can use a computer program, Excel or by hand calculation. In all cases, please explain your method, show your working and upload the related file if you use a computer bases tool.