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:
Overall Pallier can be used to create partial homomorphic encryption.
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.
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) 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=340069946197445247909665765929092506899 q=274014759234517226259192085046073289181 N=93184184430188186537999864864689604831461577510979057793735630626257864559719 Challenges: [920921161664649996 3298508731111621460 121630938926004548 5996473199326725515 7504591963242030003] Proof: [67465781721267213874565205194897628338466242464013920689624277493718932266301 1428891490032698168978692182343916885240651025678518291879909669723777909845 90600543461354452824264819189116751314232607395147496419244374359632822351424 74869381299039993247789914632942639914478080488784725325378301504863575669610 35590467988261665224361685518299605146944134162310940836290192687428885198349] Zero knowledge proof of safe RSA == Now trying with an incorrect value of N == p=340069946197445247909665765929092506899 N=115647568306733305628177925717219630810414629632407036057306111845868362596201 Challenges: [920921161664649996 3298508731111621460 121630938926004548 5996473199326725515 7504591963242030003] Proof: [50673886683060777586112644928400905913750569946032444383268293716218833684219 57432128946750069024383493790275946154074932615007319560164728150458223308103 24631546728085063322787854549890238268248395111823439110472820897680586483657 111102425468617674560057847222368561808371869163887120808342954674492469403565 33421903583053851334545862601778895489261031678557369007359984657966039950917] [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.