Remember the RSA public-key cryptosystem.
Encryption:𝑐 = 𝑚
Decryption:𝑚 = 𝑐ௗ 𝑚𝑜𝑑 𝑛
where 𝑒 is the public key, 𝑑 the private key and 𝑛 = 𝑝 ∗ 𝑞 is the public parameter.
● The public key 𝑒 is chosen such that 1 < 𝑒 < 𝜙(𝑛), and 𝑒is coprime to
𝜙(𝑛). i.e., 𝑒and 𝜙(𝑛)share no factors other than 1.
● The private key 𝑑is chosen to satisfy 𝑑𝑒 ≡ 1 𝑚𝑜𝑑 𝜙(𝑛).
Note: 𝜙(𝑛) = (𝑝−1)(𝑞−1)
A. Explain in words (no proof needed) if 𝑝 = 33 and 𝑞 = 12 are suitable values
to generate 𝑛. Why or why not? (4pts)
B. Let’s assume you are eavesdropping on a communication. You know the
public parameters, in this case, 𝑛 = 33 and 𝑒 = 3. You also acquired a
ciphertext that you now want to decrypt. It is 𝑐 = 2. Factoring large numbers
is known to be a hard problem (is in NP). However, assume that you happen
to know a secret polynomial-time algorithm to factorize 𝑛. As a result, you
assume 𝑝 = 3, 𝑞 = 11. How can you use 𝑝 and 𝑞 to compute 𝑚 (i.e., decrypt
C. Let us assume that the attacker’s secret factoring algorithm is of complexity
𝑂(𝑠7), where 𝑠 is the number of bits in 𝑛.
Which measures can mitigate the presence of such a factoring algorithm
without changing the RSA algorithm? (4pts)
In PHP, hash tables are based on DJBX33A algorithm. DJBX33A (Daniel J.
Bernstein times 33 with Addition) is a recursive hash algorithm. For any given
input string it performs the following computation:
hash = 5381; // Initialization
for (int i = 0; i < input.length(); i++)
hash = hash * 33 +input[i];
Therefore, the input string abc will be hashed to:
(((5381 * 33 + a) * 33 + b) * 33 + c
Find a way to calculate hash collisions and find two strings that result in the same
hash value. (16pts)
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: firstname.lastname@example.org 微信号:vipnxx