aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--base64.cpp91
-rw-r--r--base64.h10
-rw-r--r--main.cpp31
-rw-r--r--rsa.cpp65
-rw-r--r--rsa.h30
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);
+
+}