In RSA for our private key, we pick two large prime numbers (\(p\) and \(q\))). We then calculate a modulus (\(N=pq\)) and \(\phi(N)=(p-1)(q-1)\). We then make sure that \(gcd(pq,\phi(N))=1\). In this case we will use a HVZK (Honest Verifier Zero Knowledge) method for Peggy to prove the Victor that she has generated a modulus which is secure, and that Peggy hasn't cheated in creating the modulus (\(N\)) and in the usage of the \(e\) value.
HVZK (Honest Verifier Zero Knowledge) for RSA and using Kryptology |
Background
And so to understand how we can prove that a secure RSA key pair has been generated? Overall we can use the methods in the Kryptography library to implement the privacy-preserving methods in [1]:
The focus of the paper is to proven that a suitable private key has been created, so that the public key has all the possible values within the given field, and without leaking anything about the private key. In RSA, we pick two large prime numbers (\(p\) and \(q\)). We then calculate a modulus (\(N=pq\)) and \(\phi(N)=(p−1)(q−1)\). We then make sure that \(gcd(pq,\phi(N))=1\).
One of the key properties is to prove that the value of N is square free (that is, it does not have a factor that is a square). Overall, Victor - the verifier - will not be able to factorize the modulus (\(N\)), so will have to trust Peggy in the creation of a secure modulus. For example, Peggy could cheat, and rather than creating \(N=p.q\), she could create \(N=p.p\), and which is p squared (\(N=p^2\)). This will produce a weak key. The method is defined here:
In RSA, Peggy picks two large prime numbers (\(p\) and \(q\)). She then calculates a modulus (\(N=pq\)) and \(\phi(N)=(p-1)(q-1)\). Now Victor wants Peggy to prove that the modulus is safe. For the proof Peggy computes:
\(Inv_e=e^{-1} \pmod {\phi(N)}\)
and where \(e\) is typically a value of 65,537. In an interactive proof, Victor (the verifier) then generates a number of random values as challenges (\(x_i\)), and passes these to Peggy. She then computes:
\(y_i = x_i^{Inv_e} \pmod N \)
Peggy passes these back to Victor and Victor then checks that:
\(x_i=y_i^{e} \pmod N \)
for all values of \(i\). If these are all true, Peggy has proven that the modulus is safe, as she should not be able to generate the proofs if she has cheated. Overall, we can make this non-interactive (NI), by allowing Peggy the chance to create her own challenges, and then present these with the proofs. This works because:
\( x_i=y_i^{e} \pmod N = {(x_i^{Inv_e})}^{e} \pmod N = x_i^{1} \pmod N \)
Coding
The outline coding using the library from the Krytology library:
package main import ( "crypto/rand" "fmt" "math" "math/big" crypto "github.com/coinbase/kryptology/pkg/core" ) func main() { p, _ := rand.Prime(rand.Reader, 128) q, _ := rand.Prime(rand.Reader, 128) N := new(big.Int).Mul(p, q) PHI := new(big.Int).Mul(new(big.Int).Sub(p, big.NewInt(1)), new(big.Int).Sub(q, big.NewInt(1))) PsfProofLength := 5 // 1. M = N^{-1} mod \phi(N) e := big.NewInt(65537) inv_e, _ := crypto.Inv(e, PHI) // 2. Generate challenges x := make([]*big.Int, PsfProofLength) for i := 0; i < PsfProofLength; i++ { x[i], _ = rand.Int(rand.Reader, new(big.Int).SetUint64(uint64(math.Pow(2, 64)))) } proof := make([]*big.Int, PsfProofLength) // 3. Create proofs y_i = x_i^M mod N for i, xj := range x { yi, _ := crypto.Exp(xj, inv_e, N) proof[i] = yi } fmt.Printf("p=%s\n", p) fmt.Printf("q=%s\n", q) fmt.Printf("N=%s\n", N) fmt.Printf("\nChallenges:\t%v\n", x) fmt.Printf("Proof:\t%v\n", proof) proven := true for j, xj := range x { // 4. Proof: yj^N == x mod N return false lhs, _ := crypto.Exp(proof[j], e, N) if lhs.Cmp(xj) != 0 { fmt.Printf("Failed at %d\n", j) proven = false } } if proven == true { fmt.Printf("\nZero knowledge proof of safe RSA\n") } else { fmt.Printf("\nNo Zero knowledge proof of safe RSA\n") } fmt.Printf("\n\n== Now trying with an incorrect value of N ==\n") N = new(big.Int).Mul(p, p) PHI = new(big.Int).Mul(new(big.Int).Sub(p, big.NewInt(1)), new(big.Int).Sub(p, big.NewInt(1))) proof = make([]*big.Int, PsfProofLength) // 3. Create proofs y_i = x_i^M mod N for i, xj := range x { yi, _ := crypto.Exp(xj, inv_e, N) proof[i] = yi } fmt.Printf("p=%s\n", p) fmt.Printf("N=%s\n", N) fmt.Printf("Challenges:\t%v\n", x) fmt.Printf("Proof:\t%v\n", proof) proven = true for j, xj := range x { // 4. Proof: yj^N == x mod N return false lhs, _ := crypto.Exp(proof[j], e, N) if lhs.Cmp(xj) != 0 { fmt.Printf("[Failed at %d]", j) proven = false } } if proven == true { fmt.Printf("\nZero knowledge proof of safe RSA\n") } else { fmt.Printf("\nNo Zero knowledge proof of safe RSA\n") } }
A sample run is:
p=258581595203391469340795312176642376317 q=288059447212716774487770527913879609557 N=74486871373671442056394740584261231089944893163767166408521271742800623661569 PHI=74486871373671442056394740584261231089398252121351058164692705902710101675696 Challenges: [6264047865840045870 8189542868859990793 1775843552211811404 7285635826578212280 7070225850536804176] Proof: [22794428293333295557939999443580253735923766660684255687079228991163005823559 1226999095559081471355045698452979976300800950373409577381662352383226579101 36931638445215778995016059394695148648253499281085796679830736713313903737179 37065756098273751278629883525158287091378520480631186339899168316845070187908 70225506565630773121212772159373588401797067220940337464868716100064046366690] Zero knowledge proof of safe RSA == Now trying with an incorrect value of N == p=258581595203391469340795312176642376317 N=66864441377930606144440990582925894285263376845106010875949380918916642484489 PHI=66864441377930606144440990582925894284746213654699227937267790294563357731856 Challenges: [6264047865840045870 8189542868859990793 1775843552211811404 7285635826578212280 7070225850536804176] Proof: [63965010444339329424618525339322598136389622732162978383416070984210811127276 27825318786601364804534040180371169627610424675613990092643393187956457169688 4186488301738325906098061170695792937436247412704794321751337738972266252851 36131837897386215216243184146665108255632232585645705092597282901570091580991 9952610881106943920449008230199904092605335031790156848353147718199851241612] [Failed at 0][Failed at 1][Failed at 2][Failed at 3][Failed at 4] No Zero knowledge proof of safe RSA
Coding
[1] Goldberg, S., Reyzin, L., Sagga, O., & Baldimtsi, F. (2019, December). Efficient noninteractive certification of RSA moduli and beyond. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 700-727). Springer, Cham.