Don't assert out when 65537|phi

1 files changed, 15 insertions, 11 deletions

diff --git a/rsa.cpp b/rsa.cpp
index 34b47f9..4adfa2c 100644
--- a/rsa.cpp
+++ b/rsa.cpp
@@ -22,17 +22,21 @@ namespace RSA{
 	}
 
 	pair<Key,Key> genkeys(int nbits,Rng &rng){
-		pair<Bigint,Bigint> pq=genprimepair(rng,nbits);
-		Key pubkey,privkey;
-		pubkey.mod=privkey.mod=pq.first*pq.second;
-		pubkey.exp=65537;
-		Bigint x;
-		Bigint phi((pq.first-Bigint::one)*(pq.second-Bigint::one));
-		assert(egcd(phi,pubkey.exp,x,privkey.exp)==1);
-		privkey.exp=privkey.exp.divmod(phi).second;
-		// cerr<<"pubkey = {"<<pubkey.mod<<" , "<<pubkey.exp<<'}'<<endl;
-		// cerr<<"privkey = {"<<privkey.mod<<" , "<<privkey.exp<<'}'<<endl;
-		return make_pair(pubkey,privkey);
+		while(true){ //retry loop for if invalid primes were generated
+			pair<Bigint,Bigint> pq=genprimepair(rng,nbits);
+			Key pubkey,privkey;
+			pubkey.mod=privkey.mod=pq.first*pq.second;
+			pubkey.exp=65537;
+			Bigint x;
+			Bigint phi((pq.first-Bigint::one)*(pq.second-Bigint::one));
+			if(egcd(phi,pubkey.exp,x,privkey.exp)!=1){
+				continue; //p-1 or q-1 is divisible by pubkey.exp=65537
+			}
+			privkey.exp=privkey.exp.divmod(phi).second;
+			// cerr<<"pubkey = {"<<pubkey.mod<<" , "<<pubkey.exp<<'}'<<endl;
+			// cerr<<"privkey = {"<<privkey.mod<<" , "<<privkey.exp<<'}'<<endl;
+			return make_pair(pubkey,privkey);
+		}
 	}
 
 	pair<Key,Key> genkeys(int nbits){