python network 代写

SUTD 51.505: Foundations of Cybersecurity (2018) Exercise Sheet 10

November 16, 2018

• List your names (max 3 members for each group) on the answer sheet, if you

  have actually worked on the exercises.

• Answerquestionsinthesameorderasintheexercisesheet.
• Typein12ptfont,with1.5linespacing.
• Therecanbemultipleacceptableanswers.Justifycarefullyyourreasoning.
• Gotothepoint,avoidcopyingverbatimdefinitionsfromtheslidesorthebook.
• Submityourclassworkandhomeworksolutions(inpdffile)toeDimensionby the deadlines below. Each group only needs one submission.
• Grading:total100pointsforeachclassworkandhomework,eachexercisehas equal points in the same classwork and homework.

  Homework due on Friday November 23, 6:59 PM

  Exercise 1

  Prove lcm(a,b) = ab/gcd(a,b), where a and b are integers, lcm = the Least Common Multiple, gcd = the Greatest Common Divisor.

  Let gcd (a,b)=m and a/m=a1 and b/m=b1
  i.e. a=a1×m and b=b1×m
  As m is gcd of a and b, a1 and b1 should not have any common factors other than 1. so lcm(a,b)=a1×b1×m
  then gcd(a,b)×lcm(a,b)=m×(a1×b1×m)=(a1×m)×(b1×m)=a×b

lcm(a,b) = ab/gcd(a,b) Q.E.D

Exercise 2

Compute the result of 12358 * 1854 * 14303 (mod 29101) in two ways and verify the equivalence: by reducing modulo 29101 after each multiplication and by computing the entire product first and then reducing modulo 29101.

Output:

25392 25392

Exercise 3

What are the subgroups generated by 3, 7, and 10 in the multiplicative group of integers modulo p = 11?

30 mod 11 = 1 31 mod 11 = 3 32 mod 11 = 9

33 mod 11 = 5
34 mod 11 = 4
35 mod 11 = 1
==> subgroup generated by 3 is [1, 3, 4, 5, 9] 70 mod 11 = 1

71 mod 11 = 7
72 mod 11 = 5
73 mod 11 = 3
74 mod 11 = 10
75 mod 11 = 4
76 mod 11 = 6
77 mod 11 = 9
78 mod 11 = 8
79 mod 11 = 1
==> subgroup generated by 7 is [1, 3, 4, 5, 6, 7, 8, 9, 10] 100 mod 11 = 1

101 mod 11 = 10
102 mod 11 = 1
==> subgroup generated by 10 is [1, 10]

Exercise 4

Let p = 71,q = 89,n = pq,e = 3. First find the corresponding private RSA key d. Then compute the signature on m1 = 5416, m2 = 2397, and m3 = m1m2 (mod n) using the basic RSA operation. Show that the third signature is equivalent to the product of the first two signatures.

Exercise 5

Try to conduct timing attacks against your implementation of the RSA encryption: measure time that is needed to encrypt messages with different sizes and contents. What can an adversary deduct about a message given only the execution time of encrypting it? Repeat the measurement for different key sizes.

from Crypto.Util import number
import matplotlib.pyplot as plt
from datetime import datetime
from timeit import default_timer as timer

class RSA(object):
def Gen(minPrime):

p = number.getPrime(minPrime) q = number.getPrime(minPrime)

while q == p:
q = number.getPrime(minPrime)

n=p*q
phi = (p-1)*(q-1)
bits = int(minPrime/2)
e = 2**(bits)-1
d = number.inverse(e,phi) return (n,e),(p,q,phi,d)

def Gen1(minPrime):
p = number.getPrime(minPrime) q = number.getPrime(minPrime)

while q == p:
q = number.getPrime(minPrime)

n=p*q
phi = (p-1)*(q-1)

e = 65537
d = number.inverse(e,phi) return (n,e),(p,q,phi,d)

def Enc(pk,plain): n,e = pk

cipher = (plain**e)%n # pow(cipher,d,n) return cipher

def Dec(pk, cipher): p,q,phi,d = pk
n = p*q
plain = (cipher**d)%n # pow(cipher,d,n) return plain

def showfig(bits,time,keylen): plt.xlabel(‘message bit-length’) plt.ylabel(‘time’)

plt.title(‘For keylength of bits: ‘+str(keylen)) plt.plot(bits,time)
plt.show()

def showfigdiffcont(bits,time,keylen):
plt.xlabel(‘No. of 1s’)
plt.ylabel(‘time’)
plt.title(‘For messagelength 1024bit keylength of bits: ‘+str(keylen)) plt.plot(bits,time)

plt.show()

#showing that longer messages will take longer to encrypt pubkey,prikey = RSA.Gen1(512)
print(pubkey)
print(prikey)

msgtime = []
msgbits = []
for i in range(16,512*10+16,16):

msg = 2**i-1
start_time = timer()
s1 = RSA.Enc(pubkey,i) time_elapsed = timer() – start_time msgtime.append(time_elapsed) msgbits.append(i)

showfig(msgbits,msgtime,512)
#showing that longer messages will take longer to encrypt

#showing that different content will take longer to encrypt pubkey,prikey = RSA.Gen1(512)
print(pubkey)
print(prikey)

msgtime = []
msgbits = []
msg1 = 2*1024-1 print(bin(msg1))
for i in range(16,512,1):

msg = msg1^(2**i-1)
start_time = timer()
s1 = RSA.Enc(pubkey,i)
time_elapsed = timer() – start_time msgtime.append(time_elapsed) msgbits.append(bin(msg).count(“1”))

showfigdiffcont(msgbits,msgtime,512)
#showing that different content will take longer to encrypt

#showing that longer key will take longer to encrypt keybits = [16,24,32]
keys = []

for key in keybits: keys.append([RSA.Gen(key),key])

print(keys)

for key in keys: bits = []

time = []
for i in range(16,8192,16):

msg = 2**i-1
start_time = timer()
s1 = RSA.Enc(key[0][0],i) time_elapsed = timer() – start_time time.append(time_elapsed) bits.append(i)

showfig(bits,time,key[1])
#showing that longer key will take longer to encrypt

Using the below RSA public and private key, we encrypt different message length (ranging from 16bits to 5120bits) and plot the timings for them.
We observed it is possible to deduce the message length as there is a general upward trend in encryption timing for longer messages. Hence attacker can infer the message length from the encryption times.

pubkey = (N,e) = (1269804564453385881286164141386567155419349135155890064404386 83587974127946645964437220137054264511945181177323143913749583 02996013117557311119282207713893283108885701278075644102572667 77723812712460735415159667391567077844362448712527446821984715 18300605431749967633397329711830754938604118288361699958730193, 65537)
privkey = (p,q,phi,d) = (9680142538605985857162026913773357269843689109143659689880402 95617153569707266270865727081851438226150681648251051450340174 2342429453185581651436302058943, 13117622590671556324048039856424530547415432165406142798927107 79531417970469201252194687490113117088345006260532549175146603 6474708464154848326053742448751, 12698045644533858812861641413865671554193491351558900644043868 35879741279466459644372201370542645119451811773231439137495830 29960131175573111192822077138910033323727735238575230958956479 88456401212479899171347793164595629872084310657751407805275187 2747460474870879797391074844051937800686777858384209914222500,

22715700617439760856003461241155550803571187665849299044931918 25053647063561770125367302267153206796230074801923400895372249 94011410028292286132207155099650766847335698603392893748997630 37164174102432875762528270604653732184920954293220242780268595 695427416686546450777621213538381658837782986888268871543473)

For the same message of length 1024bit, we change the content with different number of 1-bits, as shown above content of more ‘1’s will generally take longer to encrypt. Hence attacker can infer the ‘1’s information from the encryption times.

Using different lengths of RSAkey = ((N,e),(p,q,phi,d)),bitlength =
a. [((2360984861, 255), (63857, 36973, 2360884032, 2323850557)), 16] b. [((109979374802753, 4095), (8490563, 12953131, 109979353359060, 2309700705465)), 24]
c. [((5683836443255167711, 65535), (2410117607, 2358323273, 5683836438486726832, 3467196601836940239)), 32]

We plotted the encryption timing of messages of length ranging from 16bits to 8192bits:

We can observe the encryption timing for longer keylength will generally takes longer as shown from above, maximum

time taken increases from 16bits:~0.000025s to 24bits:~0.0006s and finally to 32bits:0.05s. Hence attacker can infer the key length from the encryption times.

As like previous experiment, longer message length generally will take longer time for encryption even for different key sizes.

2