Week 4 Lab Sheet
IMPORTANT NOTES:
Public Key Encryption: Part 1
1. Study lecture materials at least 1 hour and prepare Question 1-2 under Lab Tasks section prior to the lab session. Prepared questions will be discussed in the lab session.
Copyright By PowCoder代写 加微信 powcoder
1 Overview
The objectives of this lab are to learn concepts of number theory on how to compute modular arithmetic operations, discrete log and multiplicative inverse using the SageMath package. Please attempt question 1 in Section 3 before the lab.
2 Lab Environment
SageMath: Inthislab,weneedtousetheSageMathlibrarytoperformcertainmathematicalcalculations.
Use the SageMath web interface at https://sagecell.sagemath.org/.
Figure 1: Sage Interface
3 Lab Tasks: Modular Arithmetic
All the numbers in this section are represented in base 10.
For the following task you can use the sage library variables similar to programming languages such
as python. For instance writing x=7 will create an integer variable x with value 7 that can be used in other 1
FIT2093 Week 4 Lab Sheet expressions. To print the value of a variable simply type its name and press enter. Note that mod can be
performed with % in sage as illustrated in the last example below that computes 73 mod 11 = 2. Examples:
• The sage code
returns (after pressing Evaluate):
• The sage code
returns (after pressing Evaluate):
(7, 9, 63)
• The sage code
x=7 y=9 x**3
returns (after pressing Evaluate):
• The sage code
returns (after pressing Evaluate):
1. For 𝑎 = 1305051748, 𝑏 = 3528645214, 𝑝 = 146347, in the first step calculate 𝑛1 = 𝑎 × 𝑏 and then 𝑛1 mod𝑝,forthesecondstepcalculate𝑟1 =𝑎mod𝑝,𝑟2 =𝑏mod𝑝andthen𝑟1×𝑟2 mod𝑝
2. For 𝑎 = 5, 𝑏 = 22401562154533299041783378656, 𝑝 = 43902608862042298666481977063, calculate 𝑎𝑏 mod 𝑝 by using power_mod(a,b,p).
FIT2093 Week 4 Lab Sheet
3. For 𝑎 = 5, 𝑏 = 42568949792454651564941152870, 𝑝 = 43902608862042298666481977063, solve the discrete logarithm 𝑎𝑥 mod 𝑝 = 𝑏 by using discrete_log(b,Mod(a,p)). Do you notice the time dif- ference between solving the discrete logarithm and computing the multiplication modulo reductions in 3.1.2?
4. For 𝑒 = 65537, 𝑝 = 43902608862042298666481977063, solve the multiplicative inverse of 𝑒 mod 𝑝 by using inverse_mod(e,p) and verify the answer by using mod().
4 Optional Extra Exercises
1. The following sage code generates two random 512-bit primes 𝑝, 𝑞, multiplies them to get 𝑛 = 𝑝 × 𝑞 and computes 𝑟 = gcd(𝑛, 𝑝). What do you think should be the value of 𝑟 in terms of 𝑝 and 𝑞? Try to run the code and find out.
p=random_prime(2^511,2^512-1)
q=random_prime(2^511,2^512-1)
r=gcd(n,p)
2. Experiment to see how the running time of sage code to compute a modular exponentiation (Given 𝑎, 𝑏, 𝑝, compute 𝑦 = 𝑎𝑏 mod 𝑝 for a prime 𝑝) depends on the bit-length of the numbers 𝑎, 𝑏, 𝑝 by doing the computation with numbers of increasing bit length and making a graph of run-time versus bit length. Do the same experiment for the discrete-logarithm computation (given 𝑦 , 𝑎, 𝑝, find 𝑏 such that 𝑦 = 𝑎𝑏 mod 𝑝). Do your results match the expected behaviour (polynomial time for modular exponentiation, subexponential time for discrete logarithm)?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com