HVZK

from Crypto.PublicKey import RSA
from Crypto.Util.number import inverse, getRandomInteger, getStrongPrime, isPrime
from math import gcd

def prime_product_constant(max_const=65537):
	print("Calculating Prime Const")
	i = 5
	ret = 1*2*3
	while i < max_const:
		if isPrime(i):
			ret *= i
		i+=2
	return ret

def verifier_part1(size, num_challenges):
	#Randomly generate challenges
	return [getRandomInteger(size//2) for _ in range(num_challenges)]


def prover_part2(size, challenges):
	#Generate Key
	print("Generating Key")
	mykey = RSA.generate(size)
	private_p, private_q, public_n, private_phi = [mykey.p, mykey.q, mykey.n, (mykey.p - 1) * (mykey.q - 1)]

	#Calculate the inverse for the power
	m = inverse(public_n, private_phi)

	#Calculate Proofs
	# challenge ^ m % N
	return [public_n, [pow(chal, m, public_n) for chal in challenges]]

def verifier_part3(challenges, proofs, public_n, alpha_const=319567):
	#Check Varables
	assert public_n > 1

	#Check that N is not devisible by primes smaller than 65537, or 319567
	prime_product = prime_product_constant(alpha_const)
	assert gcd(prime_product, public_n) == 1

	#Check that proof is greater than 0
	for proof in proofs:
		assert (proof % public_n) > 0

	#Validate Challenges
	for idx in range(num_challenges):
		#Compute test
		tmp = pow(proofs[idx], public_n, public_n)

		#Check that chal^m = proof^N

		#print(f"Testing Proof {challenges[idx]}, {tmp}")
		assert tmp == challenges[idx]

	return True

if __name__ == '__main__':
	#Setup
	num_challenges = 5
	size = 1024

	#Get challenges from Verifier
	challenges = verifier_part1(size, num_challenges)

	#Generate Profs from the challenges 
	public_n, proofs = prover_part2(size, challenges)


	#From the proofs verify that they are correct
	valid = verifier_part3(challenges, proofs, public_n)

	print(f"Challenges have been confirmed: {valid}")

from Crypto.PublicKey import RSA
from Crypto.Util.number import inverse, getRandomInteger, getStrongPrime, isPrime
from math import gcd
import hashlib

def prime_product_constant(max_const=65537):
	print("Calculating Prime Const")
	i = 5
	ret = 1*2*3
	while i <= max_const:
		if isPrime(i):
			ret *= i
		i+=2
	return ret

def generate_challenges(size, public_n, num_challenges, salt="squarefreeproof", hash_obj=hashlib.shake_256):
	counter = 0

	outputs = []

	#print(f"size: {size}, public_n: {public_n}, num_challenges: {num_challenges}")

	while len(outputs) < num_challenges:
		#Generate Order of inputs
		hash_list = [str(public_n), str(num_challenges), salt, str(counter)]

		#Generate String to hash with sizes
		hash_list = [str(len(s)) + s for s in hash_list]

		#Join to gether with "|"
		str_input = "|" + "|".join(hash_list)
		hash_output = hash_obj(str_input.encode("utf8")).digest(size//8)
		#print(f"hash_in:{str_input.encode("utf8")}, hash_out:{hash_output}")
		hash_int = (int.from_bytes(hash_output, byteorder='little') % public_n)

		#Check that gcd(hash_int,N)=1
		if gcd(hash_int, public_n) == 1:
			outputs.append(hash_int)

		counter += 1
	
	return outputs


def prover_part1(size, num_challenges):
	#Generate Key
	print("Generating Key")
	mykey = RSA.generate(size)
	private_p, private_q, public_n, private_phi = [mykey.p, mykey.q, mykey.n, (mykey.p - 1) * (mykey.q - 1)]

	#Randomly generate challenges
	challenges = generate_challenges(size, public_n, num_challenges)
	#print(f"Challenges: {challenges}")

	#Calculate the inverse for the power
	m = inverse(public_n, private_phi)

	#Calculate Proofs
	# challenge ^ m % N
	proofs = [pow(chal, m, public_n) for chal in challenges]
	#print(f"Proofs: {proofs}")

	return [public_n, proofs]


def verifier_part2(size, public_n, proofs, alpha_const=319567):
	#Check Varables
	assert public_n > 1

	#Check that N is not divisible by primes smaller than 65537, or 319567
	prime_product = prime_product_constant(alpha_const)
	assert gcd(prime_product, public_n) == 1

	#Check that proof is greater than 0
	for proof in proofs:
		assert (proof % public_n) > 0

	#Generate Challenges
	challenges = generate_challenges(size, public_n, len(proofs))
	#print(f"Challenges: {challenges}")


	#Validate Challenges
	for idx in range(len(challenges)):
		#Compute test
		tmp = pow(proofs[idx], public_n, public_n)

		#Challenge = proof^n

		#print(f"Testing Proof {challenges[idx]}, {tmp}")
		assert tmp == challenges[idx]

	return True

	

if __name__ == '__main__':
	#Setup
	num_challenges = 5
	size = 1024

	#Get challenges from Verifier
	public_n, proofs = prover_part1(size, num_challenges)

	#Generate Profs from the challenges 
	valid = verifier_part2(size, public_n, proofs)

	print(f"Challenges have been confirmed: {valid}")

challenge = pow(fake_proof, public_n, public_n)