# Homework 12

# 1

Requirements:
- Speed of revocation
- The speed of revocation is defined as the concept of the PKI in terms of public key infrastructure and the one public key will serve as a cryptographic proof. In some times the certificates will be declared as invalid because the expiration date has been changed to the identity of the key. All public key infrastructure will cancel the issued certificate and the revocation mechanism is categorized into a certificate revocation list with trusted dictionaries and online mechanisms.
- Reliability of revocations
- The reliability of the revocation will manage the list of certificates and guarantee for the application reliability, if any failure occurs the CRL is inaccessible through the steps as follows:

1. To configure the reliability of the certificate revocation list will be valid for a long period and it allows the CA (certificate authority) recovery to find out if there any failure will occur in hardware or software failure.
2. The reasonable certificate revocation list has the tolerance period to include the new CRL to protect from the CRL publications and also replication failures.
3. To make secure the private key certificate authentication and to secure the offline location.
- Overheads
- The overheads of the certificate revocation are to provide the overheads through the existing methods and also proposed methods to analyze the network latency for both storage and bandwidth overheads. The output will show the CRL and OCSP) methods. The methods of the certificate revolution language are as follows:

1. Data collection
2. Bandwidth cost
3. Network latency
4. Storage cost
- Connectivity
- There are two types of connectivity methods as follows:

1. LDAP: The LDAP will allow the port to verify which is not possible to allow the LDAP port for accessing the external revocation process.
2. HTTP: The HTTP is used by all the clients and is configured without the internal namespace so therefore it needs to create the DNS records to publish the URL and also to develop the virtual directory to configure the server.

# 2

import os
import sys


import random, hashlib

# Rabin-Miller algorithm for primality testing
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
	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:                        
		e = random.randrange(2, phi)    
		if gcd(e, phi) == 1:            
			break


	d = modInverse(e, phi)

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


def Sign(privKey, data):
	# simple MD5 hashing before applying signature
	m = hashlib.md5()
	for item in data:
		if type(item) == int:
			m.update(item.to_bytes((item.bit_length() + 7) // 8, byteorder='big'))
		elif type(item) == str:
			m.update(bytes(item,'utf-8'))
	hashed = int(m.hexdigest(), 16)
	return pow(hashed, privKey[3], privKey[0] * privKey[1])     # p, q, phi, d = privKey

def verify(pubKey, data, sig):
	# simple MD5 hashing before verifying with signature
	m = hashlib.md5()
	for item in data:
		if type(item) == int:
			m.update(item.to_bytes((item.bit_length() + 7) // 8, byteorder='big'))
		elif type(item) == str:
			m.update(bytes(item,'utf-8'))
	hashed = int(m.hexdigest(), 16)
	return hashed == pow(sig, pubKey[1], pubKey[0])

def submitRequest(subject, issuer, SubPubKey):
	if subject == subject: #To simulate CA verification of subject's identity
		print(f"{subject} identity verified by CA ({issuer}) and proceeds to signs certificate:")
		return (subject, issuer, SubPubKey)
	else:
		print('Identity verification failed.')

def createCert(request, IssuerPrivKey):
	newCert = {}
	newCert["Subject"] = request[0]
	newCert["Issuer"] = request[1]
	newCert["Modulo"] = request[2][0]
	newCert["Public Exponent"] = request[2][1]
	newCert["Signature"] = Sign(IssuerPrivKey, (request[0], request[1],request[2][0],request[2][1]))
	return newCert
	
def printCert(cert):
	for x in cert:
		print (f'{x} : {cert[x]}\n')





def main():
	minPrime = 20000000000000000000000000000000000  # minimum for a large prime number

	print("Root Certificate:")

	ca_name = "Walter White Certificate Authority"
	ca_pubKey, ca_privKey = Gen(minPrime)
	ca_cert = {	"Subject": ca_name, 
				"Issuer": ca_name,
				"Modulo": ca_pubKey[0], 
				"Public Exponent": ca_pubKey[1]}
	ca_cert["Signature"] = Sign(ca_privKey,ca_cert.values())
	printCert(ca_cert)

	sub1_name = "Dragoons"
	sub1_pubKey, sub1_privKey = Gen(minPrime)
	sub1_request = submitRequest(sub1_name, ca_name, sub1_pubKey)
	sub1_cert = createCert(sub1_request, ca_privKey)
	printCert(sub1_cert)


	sub2_name = "DeadBeats"
	sub2_pubKey, sub2_privKey = Gen(minPrime)
	sub2_request = submitRequest(sub2_name, sub1_name, sub2_pubKey)
	sub2_cert = createCert(sub2_request, sub1_privKey)
	printCert(sub2_cert)

	sub3_name = "KFP"
	sub3_pubKey, sub3_privKey = Gen(minPrime)
	sub3_request = submitRequest(sub3_name, sub2_name, sub3_pubKey)
	sub3_cert = createCert(sub3_request, sub2_privKey)
	printCert(sub3_cert)


	# To-Be-Signed (TBS) Certificate = Certificate without the Signature
	ca_TBSCertificate = ca_cert["Subject"],ca_cert["Issuer"],ca_cert["Modulo"],ca_cert["Public Exponent"]
	print("CA's Certificate Verified: ", end = "")
	print(verify(ca_pubKey, ca_TBSCertificate, ca_cert["Signature"]))

	sub1_TBSCertificate = sub1_cert["Subject"],sub1_cert["Issuer"],sub1_cert["Modulo"],sub1_cert["Public Exponent"]
	print("Subject 1's Certificate Verified: ", end = "")
	print(verify(ca_pubKey, sub1_TBSCertificate, sub1_cert["Signature"]))

	sub2_TBSCertificate = sub2_cert["Subject"],sub2_cert["Issuer"],sub2_cert["Modulo"],sub2_cert["Public Exponent"]
	print("Subject 2's Certificate Verified: ", end = "")
	print(verify(sub1_pubKey, (sub2_cert["Subject"],sub2_cert["Issuer"],sub2_cert["Modulo"],sub2_cert["Public Exponent"]), sub2_cert["Signature"]))

	sub3_TBSCertificate = sub3_cert["Subject"],sub3_cert["Issuer"],sub3_cert["Modulo"],sub3_cert["Public Exponent"]
	print("Subject 3's Certificate Verified: ", end = "")
	print(verify(sub2_pubKey, sub3_TBSCertificate, sub3_cert["Signature"]))

Results

>>>>>>>>>>>>>>>>>>
Root Certificate:
Subject : Walter White Certificate Authority

Issuer : Walter White Certificate Authority

Modulo : 6299296136437535806400441341542741557309396763763005843580119452882943451

Public Exponent : 4665375878038070311143499330090855437358728626863063826498842311625399571

Signature : 215045302673116056957214080963583995900209072664461271072246295139273012

Dragoons identity verified by CA (Walter White Certificate Authority) and proceeds to signs certificate:
Subject : Dragoons

Issuer : Walter White Certificate Authority

Modulo : 3043602269699686103513777878634870371840972934960319172564705392581375653

Public Exponent : 1513564612126971161736795424456044931757046905303086043795336952412807259

Signature : 1270365785229746560540409370549132360528814573478164180086863982090153831

DeadBeats identity verified by CA (Dragoons) and proceeds to signs certificate:
Subject : DeadBeats

Issuer : Dragoons

Modulo : 196370230589027262469738779596636767640386917531762632480834558075898211

Public Exponent : 139695531167027825911502085826370713085827672670370226172823850257810007

Signature : 2707509966208755607441500296539018057219136327095632090126635787470039189

KFP identity verified by CA (DeadBeats) and proceeds to signs certificate:
Subject : KFP

Issuer : DeadBeats

Modulo : 2062897203336190809952461380947015017890089020265993897953602114597040511

Public Exponent : 205789305311202015814480601293874191062335311171982019678943528468967507

Signature : 162687765257758784757889595739535802525456758384804474030541717345903347

CA's Certificate Verified: True
Subject 1's Certificate Verified: True
Subject 2's Certificate Verified: True
Subject 3's Certificate Verified: True
>>>>>>>>>>>>>>>>>>