# Homework 8 FCS

# 1

## a)

(A mod C * B mod C) mod C

$[(12358 mod 29101)(1854 mod 29101)(14303 mod 29101)] mod 29101 = 25,392$

## b)

$12358 * 1854 * 14303 = 327706502796$

$327706502796$ mod $29101 = 25,392$

# 2

Diffie-Hellman protocol.

def ex2():
	P = 23
	G = 9
	 
	  
	print('The Value of P is :%d'%(P))
	print('The Value of G is :%d'%(G))
	 
	# Alice will choose the private key a
	a = 4
	print('The Private Key a for Alice is :%d'%(a))
	 
	# gets the generated key
	x = int(pow(G,a,P)) 
	 
	# Bob will choose the private key b
	b = 3
	print('The Private Key b for Bob is :%d'%(b))
	
	# gets the generated key
	y = int(pow(G,b,P)) 
	 
	 
	# Secret key for Alice
	ka = int(pow(y,a,P))
	 
	# Secret key for Bob
	kb = int(pow(x,b,P))
	 
	print('Secret key for the Alice is : %d'%(ka))
	print('Secret Key for the Bob is : %d'%(kb))
    
'''
The Value of P is :23
The Value of G is :9
The Private Key a for Alice is :4
The Private Key b for Bob is :3
Secret key for the Alice is : 9
Secret Key for the Bob is : 9
'''

# 3

def ex3():
	p = 71
	q = 89

	n = p * q

	e = 3

	phi = (p - 1) * (q - 1)
	d = modInverse(e, phi) # private RSA key 


	m1 = 5416
	m1_signed = pow(m1, d, n)

	m2 = 2397
	m2_signed = pow(m2, d, n)

	m3 = (m1 * m2) % n
	m3_signed = pow(m3, d, n)

	forged_signature = (m1_signed * m2_signed) % n

	print(f"Signature on m1 ( {m1} ) =  {m1_signed}")
	print(f"Signature on m1 ( {m2} ) =  {m2_signed}")
	print(f"Signature on m1 ( {m3} ) =  {m3_signed}")
	print(f"Product of 1st two signatures = ( {m1_signed} *  {m2_signed}) mod {n} = {forged_signature}")

	if m3_signed == forged_signature:
		print("Shown to be the same.")
	else:
		print("Unable to show third signature equal to product of 1st two signatures.")
        
'''
Signature on m1 ( 5416 ) =  1876
Signature on m1 ( 2397 ) =  2206
Signature on m1 ( 2926 ) =  5830
Product of 1st two signatures = ( 1876 *  2206) mod 6319 = 5830
Shown to be the same.
'''

# 4

import random
def rabin_miller(n):
	if n == 2 or n == 3:
		return True

	if n % 2 == 0 or n < 2:
		return False

	s = n - 1
	t = 0

	while s % 2 == 0:
		s = s // 2
		t = t + 1

	for count in range (0, 10):
		a = random.randint(2, n-1)
		x = pow(a, s, n) # a^s mod n

		if x != 1:
			i = 0
			while x != (n - 1):
				if i == t - 1 :
					return False
				else:
					i = i + 1
					x = pow(x, 2, n) # x^2 mod n

	return True

def gcd(a, b):
	while a != b:
		if a > b:
			a = a - b
		else:
			b = b - a
	return a

def modInverse(a, b):	# Find modular inverse of a mod b
	# Wijaya, H. (2020). Google Colaboratory. 
	# Extended Euclidean Algorithm for Finding Modular Inverse.
	if gcd(a, b) != 1:
		return None

	m = b
	x0, x1 = 1, 0
	y0, y1 = 0, 1

	while b != 0:
		q = a // b
		x0, x1 = x1, (x0 - q * x1)
		y0, y1 = y1, (y0 - q * y1)
		a, b = b, (a - q * b)

	return x0 % m

def Gen(minPrime):
	while True:
		temp = random.randrange(minPrime, 100*minPrime)
		if rabin_miller(temp):
			q = temp
			
			# check if 2*q + 1 is prime or not
			if rabin_miller(2*q + 1):
				p = 2*q + 1	# p is a safe prime
				break
			else:
				q = None
	
	n = p * q
	phi = (p - 1) * (q - 1)

	# Generate public exponent, e
	while True:							# such that
		e = random.randrange(2, phi)	# 1 < e < phi &
		if gcd(e, phi) == 1:			# gcd(e, phi) = 1
			break

	# Compute private exponent, d = e^-1 mod phi
	d = modInverse(e, phi)

	return (n, e), (p, q, phi, d)

def Enc(pubKey, msg):
	n, e = pubKey
	ctxt = pow(msg, e, n)
	return ctxt

def Dec(privKey, ctxt):
	p, q, phi, d = privKey
	msg = pow(ctxt, d, p*q)
	return msg

# 5

An adversary can deduce the that a large minimum prime is used, given only the execution time of encrypting it. A longer encryption time is required when using a large key size. This means, for good security (e.g. 2048 bits or more), it will be very resource intensive to perform RSA encryption. Also, it takes a longer time to generate the keys when using a larger minPrime (resulting in larger n).

def ex5():

	min_prime_ls = [
	27271,
	199957836325857837831079889994460955264807,
	1372700919823709432465276597450786841849939150768666389468639836138410690084638911314691944127177813,
	64418860678769753220216145153813492780772705889433966153663723284601684280647782579593019845358246623345580817057679212052080123782339072897264205151162401096069968341352071573932206373344077504813413,
	]


	msgList = [
	37123,
	43690,
	65535,
	87758383,
	4294967295,
	9264398173,
	549755813887,
	]

	for minPrime in min_prime_ls:

		for msg in msgList:
			print("minPrime = ", minPrime)
			print("msg:", msg)

			# Generate public/private key pair
			# where p, q > minPrime
			start = timeit.default_timer()
			pubKey, privKey = Gen(minPrime)
			end = timeit.default_timer()
			print(end - start, "seconds to generate keys\n")

			# Encryption Timing Attack
			total_time = 0

			for i in range(3):
				start = timeit.default_timer()
				C = Enc(pubKey, msg)
				end = timeit.default_timer()
				total_time = total_time + ((end - start) * 1000)
				print(f"{i+1}. Took", '{0:.6f}'.format((end - start) * 1000), "ms to encrypt message.")
			print("Length:", pubKey[0].bit_length(), "bits. n:", pubKey[0])
			print("Average encryption time = ", '{0:.6f}'.format(total_time/3), "ms.")

			# Decryption
			M = Dec(privKey, C)
			print("Decrypted plaintext message = ", M)

# Results
minPrime =  27271
msg: 37123
0.0004988999999999966 seconds to generate keys

1. Took 0.011800 ms to encrypt message.
2. Took 0.012300 ms to encrypt message.
3. Took 0.011700 ms to encrypt message.
Length: 44 bits. n: 11688624587503
Average encryption time =  0.011933 ms.
Decrypted plaintext message =  37123
minPrime =  27271
msg: 43690
0.001720299999999994 seconds to generate keys

1. Took 0.011000 ms to encrypt message.
2. Took 0.009700 ms to encrypt message.
3. Took 0.009600 ms to encrypt message.
Length: 41 bits. n: 1822679832403
Average encryption time =  0.010100 ms.
Decrypted plaintext message =  43690
minPrime =  27271
msg: 65535
0.00027240000000000597 seconds to generate keys

1. Took 0.016900 ms to encrypt message.
2. Took 0.098400 ms to encrypt message.
3. Took 0.010500 ms to encrypt message.
Length: 43 bits. n: 5186964738511
Average encryption time =  0.041933 ms.
Decrypted plaintext message =  65535
minPrime =  27271
msg: 87758383
0.001753599999999994 seconds to generate keys

1. Took 0.012700 ms to encrypt message.
2. Took 0.012100 ms to encrypt message.
3. Took 0.012300 ms to encrypt message.
Length: 44 bits. n: 11660501809153
Average encryption time =  0.012367 ms.
Decrypted plaintext message =  87758383
minPrime =  27271
msg: 4294967295
0.0009258000000000044 seconds to generate keys

1. Took 0.011600 ms to encrypt message.
2. Took 0.012300 ms to encrypt message.
3. Took 0.040700 ms to encrypt message.
Length: 43 bits. n: 5174179376941
Average encryption time =  0.021533 ms.
Decrypted plaintext message =  4294967295
minPrime =  27271
msg: 9264398173
0.0002954000000000012 seconds to generate keys

1. Took 0.010300 ms to encrypt message.
2. Took 0.011300 ms to encrypt message.
3. Took 0.013000 ms to encrypt message.
Length: 42 bits. n: 2917181235403
Average encryption time =  0.011533 ms.
Decrypted plaintext message =  9264398173
minPrime =  27271
msg: 549755813887
0.0004906000000000077 seconds to generate keys

1. Took 0.064000 ms to encrypt message.
2. Took 0.092000 ms to encrypt message.
3. Took 0.018600 ms to encrypt message.
Length: 43 bits. n: 6322377755431
Average encryption time =  0.058200 ms.
Decrypted plaintext message =  549755813887
minPrime =  199957836325857837831079889994460955264807
msg: 37123
0.6049641 seconds to generate keys

1. Took 0.182700 ms to encrypt message.
2. Took 0.179100 ms to encrypt message.
3. Took 0.178300 ms to encrypt message.
Length: 288 bits. n: 381430450895436613203665552181658378559328301036156641957590727764000362472937206244253
Average encryption time =  0.180033 ms.
Decrypted plaintext message =  37123
minPrime =  199957836325857837831079889994460955264807
msg: 43690
0.8159945 seconds to generate keys

1. Took 0.176300 ms to encrypt message.
2. Took 0.175100 ms to encrypt message.
3. Took 0.175700 ms to encrypt message.
Length: 281 bits. n: 2240825371063244318871566962468441072782473826390679585557244152418397492888596441651
Average encryption time =  0.175700 ms.
Decrypted plaintext message =  43690
minPrime =  199957836325857837831079889994460955264807
msg: 65535
0.30565089999999984 seconds to generate keys

1. Took 0.184700 ms to encrypt message.
2. Took 0.179700 ms to encrypt message.
3. Took 0.178700 ms to encrypt message.
Length: 288 bits. n: 407610227126057578729100084757205994198340113597896282444126762942984550429090997468031
Average encryption time =  0.181033 ms.
Decrypted plaintext message =  65535
minPrime =  199957836325857837831079889994460955264807
msg: 87758383
0.9811128999999998 seconds to generate keys

1. Took 0.185400 ms to encrypt message.
2. Took 0.176900 ms to encrypt message.
3. Took 0.181900 ms to encrypt message.
Length: 288 bits. n: 290592048704749728023513109016057171504182442200607886487652974250832274169091467777141
Average encryption time =  0.181400 ms.
Decrypted plaintext message =  87758383
minPrime =  199957836325857837831079889994460955264807
msg: 4294967295
0.5714883999999998 seconds to generate keys

1. Took 0.279500 ms to encrypt message.
2. Took 0.212600 ms to encrypt message.
3. Took 0.188000 ms to encrypt message.
Length: 289 bits. n: 517365450007968134382300543012493790059722965432885439763729533706281249218262313203601
Average encryption time =  0.226700 ms.
Decrypted plaintext message =  4294967295
minPrime =  199957836325857837831079889994460955264807
msg: 9264398173
0.006764800000000015 seconds to generate keys

1. Took 0.173500 ms to encrypt message.
2. Took 0.172700 ms to encrypt message.
3. Took 0.173600 ms to encrypt message.
Length: 281 bits. n: 3420802810107971515111050767125098998663968014261552080676091299922667445561409693801
Average encryption time =  0.173267 ms.
Decrypted plaintext message =  9264398173
minPrime =  199957836325857837831079889994460955264807
msg: 549755813887
0.20825960000000032 seconds to generate keys

1. Took 0.181700 ms to encrypt message.
2. Took 0.178300 ms to encrypt message.
3. Took 0.177200 ms to encrypt message.
Length: 289 bits. n: 773520209062281239410497717468499532506879896044163266473801269315035057732750220605131
Average encryption time =  0.179067 ms.
Decrypted plaintext message =  549755813887
minPrime =  1372700919823709432465276597450786841849939150768666389468639836138410690084638911314691944127177813
msg: 37123
2.1585642000000003 seconds to generate keys

1. Took 1.134100 ms to encrypt message.
2. Took 1.132800 ms to encrypt message.
3. Took 1.134500 ms to encrypt message.
Length: 671 bits. n: 8959349263523002576539706520041762608186249937124307849512504428857247907923540821575861118787426149698132043133301266938774694586010791901105489468035396506682239406775873635516152387232055108262273621
Average encryption time =  1.133800 ms.
Decrypted plaintext message =  37123
minPrime =  1372700919823709432465276597450786841849939150768666389468639836138410690084638911314691944127177813
msg: 43690
10.4691464 seconds to generate keys

1. Took 1.069400 ms to encrypt message.
2. Took 1.069400 ms to encrypt message.
3. Took 1.058500 ms to encrypt message.
Length: 661 bits. n: 5178924421649196438400019163945483744148268244327112262056906072001238401663727114012046657603495725007128383261279068432096028888797867929812994143926198013354211178285514929540359126873400306823131
Average encryption time =  1.065767 ms.
Decrypted plaintext message =  43690
minPrime =  1372700919823709432465276597450786841849939150768666389468639836138410690084638911314691944127177813
msg: 65535
6.843333600000001 seconds to generate keys

1. Took 1.123500 ms to encrypt message.
2. Took 1.117800 ms to encrypt message.
3. Took 1.306500 ms to encrypt message.
Length: 666 bits. n: 186496274938888298618530619691919805824863785130294485890317470589649412639248422645832263610703568953414934372066814157012096085269524950379903314976287092330263472943785220414972576659078255437569253
Average encryption time =  1.182600 ms.
Decrypted plaintext message =  65535
minPrime =  1372700919823709432465276597450786841849939150768666389468639836138410690084638911314691944127177813
msg: 87758383
7.555866399999999 seconds to generate keys

1. Took 1.208600 ms to encrypt message.
2. Took 1.205000 ms to encrypt message.
3. Took 1.265500 ms to encrypt message.
Length: 673 bits. n: 27964274140506405603575904733705336548076055069807881502503945703502597194109186238750484059755301840045404706951931027965640432915367843430730678484467973633582956241939771065116871998230551987021925841
Average encryption time =  1.226367 ms.
Decrypted plaintext message =  87758383
minPrime =  1372700919823709432465276597450786841849939150768666389468639836138410690084638911314691944127177813
msg: 4294967295
1.0700301000000003 seconds to generate keys

1. Took 1.236100 ms to encrypt message.
2. Took 1.338100 ms to encrypt message.
3. Took 1.153700 ms to encrypt message.
Length: 673 bits. n: 31958958347821357323790130654812555023237293831094132987950090910570307262704228897516343224914183164876807530414177726975733119401708023636704639870085829670719022235441618901420494682187282153704293821
Average encryption time =  1.242633 ms.
Decrypted plaintext message =  4294967295
minPrime =  1372700919823709432465276597450786841849939150768666389468639836138410690084638911314691944127177813
msg: 9264398173
4.024938699999996 seconds to generate keys

1. Took 1.198400 ms to encrypt message.
2. Took 1.201000 ms to encrypt message.
3. Took 1.439800 ms to encrypt message.
Length: 669 bits. n: 2215661467291700308605777173661297383205802352014282197500165546277563094492714967239233847483863058071625782186032613484673470893381543909293820705744144162083533430976332282961324875610441211596046253
Average encryption time =  1.279733 ms.
Decrypted plaintext message =  9264398173
minPrime =  1372700919823709432465276597450786841849939150768666389468639836138410690084638911314691944127177813
msg: 549755813887
0.35646280000000274 seconds to generate keys

1. Took 1.224700 ms to encrypt message.
2. Took 1.218600 ms to encrypt message.
3. Took 1.379400 ms to encrypt message.
Length: 665 bits. n: 104012710032730832433939384326584034624990823080306950109763465163019653497242928876831297138628267205525167620232051740984829699230002873564273208537468614884800515644433504050450920560270307874961881
Average encryption time =  1.274233 ms.
Decrypted plaintext message =  549755813887
minPrime =  64418860678769753220216145153813492780772705889433966153663723284601684280647782579593019845358246623345580817057679212052080123782339072897264205151162401096069968341352071573932206373344077504813413
msg: 37123
47.1715848 seconds to generate keys

1. Took 6.508000 ms to encrypt message.
2. Took 6.650100 ms to encrypt message.
3. Took 6.331800 ms to encrypt message.
Length: 1340 bits. n: 18727027181215934419039674230892951941399334726439758842011148095231164627799352794607370002518383697052098020163142985185395087884522183874627844463533727975695631646840010859007301182229435157329075827283130118976688862406213264278284141751735292486086422660678453025402246111149419709521645960022403437050279943541113256000971191408999298092321301555640888681382555946551833395339684045567124991568661
Average encryption time =  6.496633 ms.
Decrypted plaintext message =  37123
minPrime =  64418860678769753220216145153813492780772705889433966153663723284601684280647782579593019845358246623345580817057679212052080123782339072897264205151162401096069968341352071573932206373344077504813413
msg: 43690
155.78270609999998 seconds to generate keys

1. Took 6.432500 ms to encrypt message.
2. Took 6.096300 ms to encrypt message.
3. Took 6.235500 ms to encrypt message.
Length: 1334 bits. n: 231861856994605752916764226229417795156586540174524695629542908432435741702755712320611964741207288526945955470268060961129102981995185342378826325345782880845871265198302244530282596293772782512930155183986704317790256756550597020196471338113039421661360065023117608369875077420536352133877140861798275259355742700084612081624924798869020978764775904571110644169078624332621354282231810742035040898153
Average encryption time =  6.254767 ms.
Decrypted plaintext message =  43690
minPrime =  64418860678769753220216145153813492780772705889433966153663723284601684280647782579593019845358246623345580817057679212052080123782339072897264205151162401096069968341352071573932206373344077504813413
msg: 65535
70.3420634 seconds to generate keys

1. Took 6.271900 ms to encrypt message.
2. Took 6.388200 ms to encrypt message.
3. Took 6.541000 ms to encrypt message.
Length: 1336 bits. n: 1497068550700900094845127482053156841088435267133257996413165610230063198459296243040760702181878582190885408767646583992244133477684468176734886632418112515938244011800896400546386445359869202418140986683356860357854109153844802052053088694880557727201741365465495968909548073037606915576102082761454923989219533078223977799100949395025895867791759453192726980085343821161680232177043550352361857069201
Average encryption time =  6.400367 ms.
Decrypted plaintext message =  65535
minPrime =  64418860678769753220216145153813492780772705889433966153663723284601684280647782579593019845358246623345580817057679212052080123782339072897264205151162401096069968341352071573932206373344077504813413
msg: 87758383
20.921105899999986 seconds to generate keys

1. Took 7.001100 ms to encrypt message.
2. Took 6.695400 ms to encrypt message.
3. Took 6.385000 ms to encrypt message.
Length: 1341 bits. n: 44312720110212854575934777588322169743461636296561312973831501568603252555790783527025707912525518651500056285685763270347329275743863384351231414342773958726135337764141723758314436813829004767171547907271513838404255894041971000370574188149752392103304811049985461026425615953443237481179766333379694986118331986574616055154115482765054187885065591664761796521338816755555414391305059390162809880436153
Average encryption time =  6.693833 ms.
Decrypted plaintext message =  87758383
minPrime =  64418860678769753220216145153813492780772705889433966153663723284601684280647782579593019845358246623345580817057679212052080123782339072897264205151162401096069968341352071573932206373344077504813413
msg: 4294967295
188.77195700000004 seconds to generate keys

1. Took 7.121400 ms to encrypt message.
2. Took 7.171500 ms to encrypt message.
3. Took 6.735100 ms to encrypt message.
Length: 1342 bits. n: 61476116702165620691742146064613285457128062187246703450383729802461778477991330236193501991531268407565735387304503285087791366636705334181943209257492073367667563010076485625182419862306944874341376303726383535158866926233965288470953611546300758710150975971720540609986267808504064170811749462027536182696671665388145053866744342264881504151556869595988534656485916588803020738935587550191407638241801
Average encryption time =  7.009333 ms.
Decrypted plaintext message =  4294967295
minPrime =  64418860678769753220216145153813492780772705889433966153663723284601684280647782579593019845358246623345580817057679212052080123782339072897264205151162401096069968341352071573932206373344077504813413
msg: 9264398173
12.333438499999943 seconds to generate keys

1. Took 6.790100 ms to encrypt message.
2. Took 6.708100 ms to encrypt message.
3. Took 6.472000 ms to encrypt message.
Length: 1334 bits. n: 367115147541241650259393315381218248103245638243219524373794841112426069284286534330146439335680889576732114418202333056113669745399225889247345221976477353855845000918086673353674479560678594474797388862618939139876121839056974101805855791683898589549636916998214111251098445443993335044876105434176776652134779765485828882073269686076080898751149166070871007943274544182599501299071275001715922522561
Average encryption time =  6.656733 ms.
Decrypted plaintext message =  9264398173
minPrime =  64418860678769753220216145153813492780772705889433966153663723284601684280647782579593019845358246623345580817057679212052080123782339072897264205151162401096069968341352071573932206373344077504813413
msg: 549755813887
97.26959879999993 seconds to generate keys

1. Took 6.857700 ms to encrypt message.
2. Took 6.846800 ms to encrypt message.
3. Took 6.683500 ms to encrypt message.
Length: 1342 bits. n: 67977196209067126466228789947290623939707729717547194213678557206894737362168754413824532899135459264967415876894654154513403772926731973150637276940075725659248943981458919431459834363978345267305479367664437385781752675412734964599131746916562711095650358892975926143508570013724214009332202554811000004814210243006186023628460377289072924061675703266655749703300193017103199595758960986858410607485811
Average encryption time =  6.796000 ms.
Decrypted plaintext message =  549755813887