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, discrete log and multiplicative inverse in Sage.
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 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:
FIT2093 Week 4 Lab Sheet
• 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𝑝
a=1305051748
b=3528645214
n1, n1 % p, r1*r2 % p
FIT2093 Week 4 Lab Sheet
returns the result:
(4605064604602534072, 75437, 75437)
2. For 𝑎 = 5, 𝑏 = 22401562154533299041783378656, 𝑝 = 43902608862042298666481977063, calculate 𝑎𝑏 mod 𝑝 by using power_mod(a,b,p).
power_mod(5,22401562154533299041783378656,43902608862042298666481977063)
returns result
42568949792454651564941152870
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?
discrete_log(42568949792454651564941152870,Mod(5,43902608862042298666481977063)) returns result
22401562154533299041783378656
Solving the discrete logarithm usually takes longer time.
4. For 𝑒 = 65537, 𝑝 = 43902608862042298666481977063, solve the multiplicative inverse of 𝑒 mod 𝑝 by using inverse_mod(e,p) and verify the answer by using mod()
p=43902608862042298666481977063
d=inverse_mod(e,p)
returns result
1260063891687162424152045392
To verify it:
p=43902608862042298666481977063
d=inverse_mod(e,p)
a=mod(e*d, p)
returns result
FIT2093 Week 4 Lab Sheet
4 Optional Extra Exercises
(a) 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)
Since𝑝divides𝑛,𝑝istheGCDof𝑛,so𝑟 =𝑝.
(b) 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 you think your results match the expected behaviour (polynomial time for modular exponentiation, subexponential time for discrete log- arithm)?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com