RSA-based Hash and Sign Signature

Our Project has the objective of applying the RSA-based construction of the Hash-and-Sign Signature presented in the paper Realizing Hash-and-Sign Signatures under Standard Assumptions. See Paper here

Project Overview

In our RSA Signature realization there are three main stages:

1. The Setup Stage

In this stage the algorithm chooses N, as the product of two large safe primes under the security assumptions of the paper. We note that N must be a Blum-Williams integer. It then chooses two random quadratic residues u, h. Next, it establishes a hash function H by choosing a random key K for the PRF function F, a random c and defining HK(x) = c ⊕ FK(x). It then publishes the parameters L of some Chameleon Hash scheme ChamHash.

• The public key consists of N, u, h, c, K, L.

• The setup algorithm sets its state counter s = 0 and keeps the factorization of N as the secret key SK.

2. The Sign Stage

The signer first increments its counter s by one as s = s + 1. The algorithm then chooses a random r. It then computes x = ChamHash(M, r). Next, it checks if HK(s) is a prime. If not it increments s = s + 1 and tries again until es = HK(s) is a prime.

Then the signer computes:

The signature is output as:

Note: Conceptually, s is an index, but we will skip over many s values where HK(s) is not a prime.

3. The Verification Stage

The verification algorithm first makes sure that 0 < i < 2^λ. If this is false, then it rejects. Second, the verifier checks that HK(i) is a prime. If not, it rejects.Next, it squares σ1 a total of lg(s) times yielding the value:

Finally, it computes x = ChamHash(M, r) and ei = HK(i), and rejects unless it verifies that:

Deployment

In order to run the Project one must have installed the following requirements:

• Python
• pycryptodome
• libnum

Commands:

* sudo apt install python3.8
* sudo apt install python3-pip
* pip install pycryptodome
* pip install libnum

(these commands were used for an ubuntu enviorment)

Run Command:

• python3 main.py