Base64 and import/export keys

5 files changed, 208 insertions, 19 deletions

diff --git a/base64.cpp b/base64.cpp
new file mode 100644
index 0000000..80640f2
--- /dev/null
+++ b/base64.cpp
@@ -0,0 +1,91 @@
+#include "base64.h"
+
+using namespace std;
+
+namespace Base64{
+
+	char alphabet[65]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
+	uint8_t revbet[128]={
+#define XX (127)
+		XX,XX,XX,XX,XX,XX,XX,XX,XX,XX,XX,XX,XX,XX,XX,XX, //0-15
+		XX,XX,XX,XX,XX,XX,XX,XX,XX,XX,XX,XX,XX,XX,XX,XX, //16-31
+		XX,XX,XX,XX,XX,XX,XX,XX,XX,XX,XX,62,XX,XX,XX,63, //32-47
+		52,53,54,55,56,57,58,59,60,61,XX,XX,XX,XX,XX,XX, //48-63
+		XX, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14, //64-79
+		15,16,17,18,19,20,21,22,23,24,25,XX,XX,XX,XX,XX, //80-95
+		XX,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40, //96-111
+		41,42,43,44,45,46,47,48,49,50,51,XX,XX,XX,XX,XX, //112-127
+#undef XX
+	};
+
+	string encode(const string &data){
+		int sz=data.size();
+		if(sz==0)return {};
+		int blocks=sz/3;
+		string res(4*blocks+4*(sz%3!=0),'\0');
+		int x;
+		for(int i=0;i<blocks;i++){
+			x=((unsigned char)data[3*i]<<16)|((unsigned char)data[3*i+1]<<8)|(unsigned char)data[3*i+2];
+			res[4*i+3]=alphabet[x&0x3f]; x>>=6;
+			res[4*i+2]=alphabet[x&0x3f]; x>>=6;
+			res[4*i+1]=alphabet[x&0x3f]; x>>=6;
+			res[4*i+0]=alphabet[x];
+		}
+		switch(sz%3){
+			case 1:
+				res[4*blocks+0]=alphabet[(unsigned char)data[3*blocks]>>2];
+				res[4*blocks+1]=alphabet[((unsigned char)data[3*blocks]&0x3)<<4];
+				res[4*blocks+2]='=';
+				res[4*blocks+3]='=';
+				break;
+
+			case 2:
+				res[4*blocks+0]=alphabet[(unsigned char)data[3*blocks]>>2];
+				res[4*blocks+1]=alphabet[(((unsigned char)data[3*blocks]&0x3)<<4)|((unsigned char)data[3*blocks+1]>>4)];
+				res[4*blocks+2]=alphabet[(((unsigned char)data[3*blocks+1]&0xf)<<2)];
+				res[4*blocks+3]='=';
+				break;
+		}
+		return res;
+	}
+
+	string decode(const string &dataS){
+		int szS=dataS.size();
+		if(szS==0)return {};
+		uint8_t data[szS];
+		int sz=0;
+		for(char c : dataS){
+			if(revbet[c&0x7f]!=127)data[sz++]=revbet[c&0x7f];
+		}
+
+		int blocks=sz/4;
+		int endlen;
+		if(sz%4==0){
+			if(data[sz-1]=='='){
+				blocks--;
+				if(data[sz-2]=='=')endlen=1;
+				else endlen=2;
+			} else endlen=0;
+		} else endlen=sz%4-1;
+		string res(3*blocks+endlen,'\0');
+		int x;
+		for(int i=0;i<blocks;i++){
+			x=(data[4*i]<<18)|(data[4*i+1]<<12)|(data[4*i+2]<<6)|data[4*i+3];
+			res[3*i+2]=x&0xff; x>>=8;
+			res[3*i+1]=x&0xff; x>>=8;
+			res[3*i+0]=x;
+		}
+		switch(endlen){
+			case 1:
+				res[3*blocks+0]=(data[4*blocks]<<2)|(data[4*blocks+1]>>4);
+				break;
+
+			case 2:
+				res[3*blocks+0]=(data[4*blocks]<<2)|(data[4*blocks+1]>>4);
+				res[3*blocks+1]=(data[4*blocks+1]<<4)|(data[4*blocks+2]>>2);
+				break;
+		}
+		return res;
+	}
+
+}
diff --git a/base64.h b/base64.h
new file mode 100644
index 0000000..d18f819
--- /dev/null
+++ b/base64.h
@@ -0,0 +1,10 @@
+#pragma once
+
+#include <string>
+
+namespace Base64{
+
+	std::string encode(const std::string&);
+	std::string decode(const std::string&);
+
+}
diff --git a/main.cpp b/main.cpp
index 491e67b..f818c48 100644
--- a/main.cpp
+++ b/main.cpp
@@ -6,9 +6,11 @@
 #include <cctype>
 #include <ctime>
 #include <cassert>
+#include "base64.h"
 #include "bigint.h"
 #include "numalgo.h"
 #include "primes.h"
+#include "rng.h"
 #include "rsa.h"
 
 using namespace std;
@@ -128,7 +130,7 @@ void testisqrt(int argc,char **argv){
 }
 
 void performrsa(){
-	PrivateKey privkey;
+	RSA::PrivateKey privkey;
 	Bigint p(1000000007),q(3000000019U);
 	privkey.pub.mod=3000000040000000133LL;
 	privkey.pub.exp=65537;
@@ -139,9 +141,9 @@ void performrsa(){
 	cout<<"d = "<<privkey.pexp<<endl;
 	Bigint msg(123456789);
 	cout<<"msg = "<<msg<<endl;
-	Bigint encr=encrypt(privkey.pub,msg);
+	Bigint encr=RSA::encrypt(privkey.pub,msg);
 	cout<<"encr = "<<encr<<endl;
-	Bigint msg2=decrypt(privkey,encr);
+	Bigint msg2=RSA::decrypt(privkey,encr);
 	cout<<"msg = "<<msg2<<endl;
 }
 
@@ -195,5 +197,26 @@ int main(int argc,char **argv){
 	// cout<<strongLucasPrime(Bigint(5777))<<endl;
 	// pseudolist(strongPseudoPrime2);
 	// pseudolist(strongLucasPrime);
-	listprimes();
+	// listprimes();
+
+	// Rng rng("wachtwoord");
+	// for(int i=0;i<100000;i++)cout<<rng.get()<<endl;
+
+	// for(int i=0;i<10000;i++)cout<<arc4random()<<endl;
+
+	/*KeyRng rng("wachtwoord"); //for DieHarder
+	char data[4];
+	for(int i=0;i<10000000;i++){
+		*(uint32_t*)data=rng.get();
+		fwrite(data,1,4,stdout);
+	}*/
+
+	string s;
+	while(true){
+		char c=cin.get();
+		if(!cin)break;
+		s.push_back(c);
+	}
+	cout<<Base64::encode(s)<<endl;
+	// cout<<Base64::decode(s)<<flush;
 }
diff --git a/rsa.cpp b/rsa.cpp
index 11bf0eb..ec79e72 100644
--- a/rsa.cpp
+++ b/rsa.cpp
@@ -1,12 +1,65 @@
+#include <cstdint>
 #include <cassert>
+#include "base64.h"
 #include "numalgo.h"
+#include "primes.h"
+#include "rng.h"
 #include "rsa.h"
 
-Bigint encrypt(const PublicKey &pubkey,Bigint msg){
-	assert(msg>1&&msg<pubkey.mod);
-	return expmod(msg,pubkey.exp,pubkey.mod);
-}
+using namespace std;
+
+namespace RSA{
+
+	Bigint encrypt(const PublicKey &pubkey,Bigint msg){
+		assert(msg>1&&msg<pubkey.mod);
+		return expmod(msg,pubkey.exp,pubkey.mod);
+	}
+
+	Bigint decrypt(const PrivateKey &privkey,Bigint encr){
+		return expmod(encr,privkey.pexp,privkey.pub.mod);
+	}
+
+	PrivateKey genkey(int nbits,Rng &rng){
+		pair<Bigint,Bigint> pq=genprimepair(rng,nbits);
+		PrivateKey key;
+		key.pub.mod=pq.first*pq.second;
+		key.pub.exp=65537;
+		Bigint x;
+		egcd((pq.first-Bigint::one)*(pq.second-Bigint::one),key.pub.exp,x,key.pexp);
+		return key;
+	}
+
+	PrivateKey genkey(int nbits){
+		Arc4Rng rng;
+		return genkey(nbits,rng);
+	}
+
+	PrivateKey genkey(int nbits,const string &password){
+		KeyRng rng(password);
+		return genkey(nbits,rng);
+	}
+
+	pair<string,string> exportkey(const PrivateKey &key){
+		string modser=key.pub.mod.serialiseMantissa();
+		int32_t modlen=modser.size();
+		string modlenstr{(char)(modlen&0xff),(char)((modlen>>8)&0xff),(char)((modlen>>16)&0xff),(char)((modlen>>24)&0xff)};
+		return make_pair(
+			Base64::encode(modlenstr + modser + key.pub.exp.serialiseMantissa()),
+			Base64::encode(modlenstr + modser + key.pexp.serialiseMantissa()));
+	}
+
+	PrivateKey importkey(const string &pub,const string &priv){
+		string pubdeser=Base64::decode(pub);
+		assert(pubdeser.size()>4);
+		int modlen=(unsigned char)(pubdeser[0])+(unsigned char)(pubdeser[1]<<8)+
+		           (unsigned char)(pubdeser[2]<<16)+(unsigned char)(pubdeser[3]<<24);
+		assert((int)pubdeser.size()-4>modlen);
+		PrivateKey key;
+		key.pub.mod.deserialiseMantissa(string(pubdeser.begin()+4,pubdeser.begin()+(4+modlen)));
+		key.pub.exp.deserialiseMantissa(string(pubdeser.begin()+(4+modlen),pubdeser.end()));
+		string privdeser=Base64::decode(priv);
+		key.pexp.deserialiseMantissa(string(privdeser.begin()+(4+modlen),privdeser.end()));
+		return key;
+	}
 
-Bigint decrypt(const PrivateKey &privkey,Bigint encr){
-	return expmod(encr,privkey.pexp,privkey.pub.mod);
 }
diff --git a/rsa.h b/rsa.h
index ec3c349..abedf84 100644
--- a/rsa.h
+++ b/rsa.h
@@ -1,15 +1,27 @@
 #pragma once
 
+#include <string>
+#include <utility>
 #include "bigint.h"
 
-struct PublicKey{
-	Bigint mod,exp;
-};
+namespace RSA{
 
-struct PrivateKey{
-	PublicKey pub;
-	Bigint pexp;
-};
+	struct PublicKey{
+		Bigint mod,exp;
+	};
 
-Bigint encrypt(const PublicKey&,Bigint);
-Bigint decrypt(const PrivateKey&,Bigint);
+	struct PrivateKey{
+		PublicKey pub;
+		Bigint pexp;
+	};
+
+	Bigint encrypt(const PublicKey &key,Bigint msg);
+	Bigint decrypt(const PrivateKey &key,Bigint msg);
+
+	PrivateKey genkey(int nbits); //nbits is target number of bits of modulus
+	PrivateKey genkey(int nbits,const std::string &password); //generates key seeded by password
+
+	std::pair<std::string,std::string> exportkey(const PrivateKey&); //returns {pub,priv}
+	PrivateKey importkey(const std::string &pub,const std::string &priv);
+
+}