Is username and password needed to register and authenticate user in zero knowledge guillou quisquater?

Question

I want to make guillou quisquater authentication for a website with Laravel (PHP). The authentication is between server and client(user). In the references i've read (here and here) the registration scheme is:

1. The server selects 2 primes p and q large enough that factoring their product n = pq is infeasible.
2. Then the server select another large prime b (0 < b < n). The values b and n are published. p and q are kept secret from all provers and verifiers.
3. When generating new certificates, the server rolls new random private key u (0 < u < n) and public key its inverse u^-1 obscured by the group key v = u^{-1 b}. These values replace the private and public keys normally generated by the RSA scheme.

For the authentication scheme:

1. Alice rolls random r (0 < r < n) and sends to Bob.
2. Bob rolls random k (1 < k < n) and computes y = k u^r mod n and x = k^b mod n, then sends (y, hash(x)) to Alice.
3. Alice computes z = v^r y^b mod n and verifies hash(z) equals hash(x).

My questions are:

1. When user register to my website, the user has to choose username and password. But the scheme not mentioning what the username and password for. Please explain to me what is the purpose of username and password in registering and the authentication scheme.
2. When the user register, the scheme said that the server select 2 primes p and q. Should I generate the 2 primes on each user registration? or should I generate the 2 prime numbers once and use those primes for every user?
3. Is there any PHP library that can compute z = v^r y^b mod n fast? because it takes up to 3 minutes when computing this equation (I tested with p=337 and q=357)
4. In the registration scheme (the bold sentence), should I save the p and q value in the server database?

Answer 1

Username and password is an authentication system where you would transmit the pair trough (encrypted) channel and use it to prove to the server that client is who it claims to be (knowledge of the password is the proof). In contrast, Zero Knowledge authentication protocols never transmit a password over the channel. They work on challenge-response scheme.

Since you are designing a zero knowledge solution based on Guillou Quisquater authentication protocol, having username and password will defeat the purpose. This would in turn answer your first question: no, you will not have username and password on the registration. The purpose of registration is to introduce the client to the server as a registered client. During registration, a user will provide some means for the server to verify the client in the future (authentication). In username and password authentication scheme, this would be the password. It would be later used to prove to the server that the client is the one who registered and the knowledge of the password is the proof of this. Registration in a zero knowledge authentication protocol would be a bit different.

On purely theoretical level, without going into details on any specific point, here are the steps needed to design such a scheme:

Registration

1. Client will generate public and private key pair
2. Client will present it's public key to the server (who also assumes trusted authority role)
3. Server will make the public key into a certificate and send it to client
4. Client is responsible for storing the certificate and private key corresponding to this certificate securely. Certificate is in turn the username and the private key would be the password even though it would never be transmitted over the wire.

Authentication

1. Client will present it's certificate to the server
2. Server will check the certificate and reject it if it is not valid (not issued by the server). Taken directly from article you linked:

1. Prover chooses random k ∈ Z_n^∗
2. Prover sends verifier Cert(prover), γ = k^b mod n
3. Verifier checks certificate, rejecting if ver_TA(ID(prover) || v, s)≠true.

4. If check is successful, server will continue with the authentication scheme as you described in your question.

Answers to your questions

When the user register, the scheme said that the server select 2 primes p and q. Should I generate the 2 primes on each user registration? or should I generate the 2 prime numbers once and use those primes for every user?

These two numbers are not generated on user registration but on initial set up. You would generate them once and use them on every user registration.

Is there any PHP library that can compute z = vr yb mod n fast? because it takes up to 3 minutes when computing this equation (I tested with p=337 and q=357)

You will need to ask this specific question on another SE, probably on stackoverflow.SE. You will also need to do mathematical (RSA) calculations on the client side and will need similar toolkit there. Even though all this is purely theoretical, please bear in mind doing cryptography in the browser is tricky at best. Also, you will need to solve the storage of the client credentials (certificate and private key) on the client side too. This is not trivial!

In the registration scheme (the bold sentence), should I save the p and q value in the server database?

Since all of this is for your thesis, you need to decide the scope. If safe storage of these two numbers is out of scope, you can declare a database as a safe enough storage and save them there. The other extreme is to use HSM.