diff options
| -rw-r--r-- | aes.cpp | 33 | ||||
| -rw-r--r-- | aes.h | 2 | ||||
| -rw-r--r-- | base64.cpp | 13 | ||||
| -rw-r--r-- | bigint.cpp | 110 | ||||
| -rw-r--r-- | envelope.cpp | 31 | ||||
| -rw-r--r-- | gf28.cpp | 2 | ||||
| -rw-r--r-- | numalgo.cpp | 8 | ||||
| -rw-r--r-- | primes.cpp | 22 | ||||
| -rw-r--r-- | rng.cpp | 3 | ||||
| -rw-r--r-- | rsa.cpp | 2 |
10 files changed, 37 insertions, 189 deletions
@@ -145,13 +145,11 @@ namespace AES{ addRoundKey(state,keysched); for(int round=0;round<numrounds-1;round++){ - //cout<<"round["<<setw(2)<<setfill(' ')<<round+1<<"].start "; printstate(state); subBytes(state); shiftRows(state); mixColumns(state); addRoundKey(state,keysched+16*(round+1)); } - //cout<<"round["<<setw(2)<<setfill(' ')<<numrounds<<"].start "; printstate(state); subBytes(state); shiftRows(state); addRoundKey(state,keysched+16*numrounds); @@ -162,13 +160,11 @@ namespace AES{ addRoundKey(state,keysched+16*numrounds); for(int round=numrounds-2;round>=0;round--){ - //cout<<"round["<<setw(2)<<setfill(' ')<<round+1<<"].start "; printstate(state); invShiftRows(state); invSubBytes(state); addRoundKey(state,keysched+16*(round+1)); invMixColumns(state); } - //cout<<"round["<<setw(2)<<setfill(' ')<<numrounds<<"].start "; printstate(state); invShiftRows(state); invSubBytes(state); addRoundKey(state,keysched); @@ -256,33 +252,4 @@ namespace AES{ return decryptCBC(data,key,10+2*increment); } - void test(){ - #if 0 - // Test encryption - initTables(); - const int numrounds=10; - uint8_t keysched[16*(numrounds+1)]; - uint8_t plaintext[16]={0x32,0x43,0xf6,0xa8,0x88,0x5a,0x30,0x8d,0x31,0x31,0x98,0xa2,0xe0,0x37,0x07,0x34}; - const int keylen=4; - uint8_t key[4*keylen]={0x2b,0x7e,0x15,0x16,0x28,0xae,0xd2,0xa6,0xab,0xf7,0x15,0x88,0x09,0xcf,0x4f,0x3c}; - keyExpand(keysched,key,keylen,numrounds); - uint8_t dest[16]; - encryptBlock(dest,keysched,plaintext,numrounds); - printstate(dest); - #endif - #if 1 - // Test decryption - initTables(); - const int numrounds=14; - uint8_t keysched[16*(numrounds+1)]; - uint8_t plaintext[16]={0x8e,0xa2,0xb7,0xca,0x51,0x67,0x45,0xbf,0xea,0xfc,0x49,0x90,0x4b,0x49,0x60,0x89}; - const int keylen=8; - uint8_t key[4*keylen]={0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f,0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x18,0x19,0x1a,0x1b,0x1c,0x1d,0x1e,0x1f}; - keyExpand(keysched,key,keylen,numrounds); - uint8_t dest[16]; - decryptBlock(dest,keysched,plaintext,numrounds); - printstate(dest); - #endif - } - } @@ -15,6 +15,4 @@ namespace AES{ //throws invalid_argument for an invalid ciphertext (length not a multiple of block size, or padding malformed) std::string decrypt(const std::string &data,const std::string &key,Algorithm algo); - void test(); - } @@ -1,3 +1,4 @@ +#include <cstdint> #include "base64.h" using namespace std; @@ -25,7 +26,7 @@ namespace Base64{ 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]; + x=((uint8_t)data[3*i]<<16)|((uint8_t)data[3*i+1]<<8)|(uint8_t)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; @@ -33,16 +34,16 @@ namespace Base64{ } 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+0]=alphabet[(uint8_t)data[3*blocks]>>2]; + res[4*blocks+1]=alphabet[((uint8_t)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+0]=alphabet[(uint8_t)data[3*blocks]>>2]; + res[4*blocks+1]=alphabet[(((uint8_t)data[3*blocks]&0x3)<<4)|((uint8_t)data[3*blocks+1]>>4)]; + res[4*blocks+2]=alphabet[(((uint8_t)data[3*blocks+1]&0xf)<<2)]; res[4*blocks+3]='='; break; } @@ -63,7 +63,6 @@ void Bigint::add(Bigint &a,const Bigint &b){ longdigit_t bdig=i<(int)b.digits.size()?b.digits[i]:0; longdigit_t sum=a.digits[i]+bdig+carry; a.digits[i]=sum; - // carry=sum>=((longdigit_t)1<<digit_bits); carry=sum>>digit_bits; } if(carry)a.digits.push_back(1); @@ -88,12 +87,10 @@ void Bigint::subtract(Bigint &a,const Bigint &b){ digit_t adig=a.digits[i]; digit_t bdig=i<(int)b.digits.size()?b.digits[i]:0; digit_t res=adig-(bdig+carry); - // cerr<<"carry="<<carry<<" res="<<res<<" adig="<<adig<<" bdig="<<bdig<<endl; carry=(bdig||carry)&&res>=adig; a.digits[i]=res; } if(carry){ - // cerr<<"2s complement"<<endl; //we do a fake 2s complement, sort of carry=0; for(int i=0;i<sz;i++){ @@ -120,14 +117,12 @@ Bigint Bigint::product(const Bigint &a,const Bigint &b){ longdigit_t newd=pr+res.digits[i+j]; //this always fits, I checked res.digits[i+j]=(digit_t)newd; carry=newd>>digit_bits; - // cerr<<"carry="<<carry<<endl; } for(int j=bsz;carry;j++){ assert(i+j<(int)res.digits.size()); longdigit_t newd=res.digits[i+j]+carry; res.digits[i+j]=newd; carry=newd>>digit_bits; - // cerr<<"(2) carry="<<carry<<endl; } } res.sign=a.sign*b.sign; @@ -322,63 +317,24 @@ Bigint Bigint::operator>>(int sh) const { return Bigint(*this)>>=sh; } -int depthrecord; - pair<Bigint,Bigint> Bigint::divmod(const Bigint &div) const { // cerr<<"divmod("<<hex<<*this<<','<<div<<dec<<')'<<endl; int bitcdiff=bitcount()-div.bitcount(); if(bitcdiff<0)bitcdiff=0; - pair<Bigint,Bigint> res=divmod(div,1,bitcdiff/29+10); - //cerr<<hex<<*this<<' '<<div<<' '; - //cerr<<dec<<depthrecord<<endl; - //cerr<<" -> "<<hex<<res.first<<' '<<res.second<<dec<<endl; - return res; -} - -inline void record(int depth){ - depthrecord=depth; + return divmod(div,1,bitcdiff/29+10); } pair<Bigint,Bigint> Bigint::divmod(const Bigint &div,int depth,int maxdepth) const { if(depth>maxdepth)assert(false); // cerr<<"divmod("<<hex<<*this<<','<<div<<dec<<") depth="<<depth<<" maxdepth="<<maxdepth<<endl; if(div.digits.size()==0)throw domain_error("Bigint divide by zero"); - if(digits.size()==0){record(depth); return make_pair(Bigint::zero,Bigint::zero);} + if(digits.size()==0)return make_pair(Bigint::zero,Bigint::zero); int cmp=compareAbs(div); - if(cmp==0){record(depth); return make_pair(Bigint(sign*div.sign),Bigint::zero);} - if(cmp<0){record(depth); return make_pair(Bigint::zero,*this);} + if(cmp==0)return make_pair(Bigint(sign*div.sign),Bigint::zero); + if(cmp<0)return make_pair(Bigint::zero,*this); //now *this is greater in magnitude than the divisor -#if 0 - int twoexp=bitcount()-div.bitcount(); - if(twoexp<0)twoexp=0; - Bigint quotient(sign*div.sign); - quotient<<=twoexp; - Bigint guess(div); //guess == quotient * div - guess<<=twoexp; - //cerr<<"guess="<<hex<<guess<<endl; - //twoexp now becomes irrelevant -#else -#if 0 - Bigint guess,quotient; - if(digits.size()==div.digits.size()){ - quotient=digits.back()/div.digits.back(); - quotient.sign=sign*div.sign; - guess=quotient; - guess*=div; - } else { - assert(digits.size()>div.digits.size()); - assert(digits.size()>=2&&div.digits.size()>=1); - longdigit_t factor=((longdigit_t)1<<digit_bits)*digits.back()+digits[digits.size()-2]; - factor/=div.digits.back()+1; - quotient=factor; - quotient<<=(digits.size()-1-div.digits.size())*digit_bits; - quotient.sign=sign*div.sign; - guess=quotient*div; - } - cerr<<"guess="<<hex<<guess<<" quotient="<<quotient<<dec<<endl; -#else int thisbtc=bitcount(),divbtc=div.bitcount(); assert(divbtc<=thisbtc); Bigint quotient,guess; @@ -386,80 +342,47 @@ pair<Bigint,Bigint> Bigint::divmod(const Bigint &div,int depth,int maxdepth) con //simple integral division longdigit_t thisnum=(digits.size()==2?((longdigit_t)1<<digit_bits)*digits[1]:0)+digits[0]; longdigit_t divnum=(div.digits.size()==2?((longdigit_t)1<<digit_bits)*div.digits[1]:0)+div.digits[0]; - if(divnum==1){record(depth); return make_pair(*this,Bigint::zero);} - record(depth); return make_pair( + if(divnum==1)return make_pair(*this,Bigint::zero); + return make_pair( Bigint(sign*div.sign*(slongdigit_t)(thisnum/divnum)), Bigint(sign*div.sign*(slongdigit_t)(thisnum%divnum))); } else if(divbtc>=digit_bits){ //the large case //take 2 digits of *this and 1 digit of div; quotient gives a good guess int spill=__builtin_clz(digits.back()); - //cerr<<"spill="<<spill<<endl; longdigit_t thishead2=((longdigit_t)digits.back()<<(spill+digit_bits))|((longdigit_t)digits[digits.size()-2]<<spill); if(spill>0)thishead2|=digits[digits.size()-3]>>(digit_bits-spill); - //cerr<<"thishead2="<<hex<<thishead2<<dec<<endl; longdigit_t divhead=((longdigit_t)div.digits.back()<<digit_bits)|div.digits[div.digits.size()-2]; divhead>>=digit_bits-__builtin_clz(div.digits.back()); - //cerr<<"divhead="<<hex<<divhead<<dec<<endl; longdigit_t factor=thishead2/(divhead+1); //+1 to make sure the quotient guess is <= the actual quotient - // cerr<<"factor="<<factor<<" thishead2="<<thishead2<<" divhead="<<divhead<<endl; quotient=factor; quotient<<=thisbtc-digit_bits-divbtc; //shift amount may be negative if thisbtc and divbtc are less than digit_bits apart if(quotient==0)quotient=1; //prevents against (HUGE+1)/HUGE where HUGE==HUGE quotient.sign=sign*div.sign; guess=quotient*div; - // cerr<<"quotient = "<<hex<<quotient<<dec<<endl; - // cerr<<"guess = "<<hex<<guess<<dec<<endl; } else { //divbtc<digit_bits, but *this is large //take 2 digits of *this and all of div int spill=__builtin_clz(digits.back()); longdigit_t thishead2=((longdigit_t)digits.back()<<(spill+digit_bits))|((longdigit_t)digits[digits.size()-2]<<spill); if(spill>0)thishead2|=digits[digits.size()-3]>>(digit_bits-spill); longdigit_t factor=thishead2/div.digits[0]; - //cerr<<"factor="<<factor<<endl; quotient=factor; quotient<<=thisbtc-2*digit_bits; quotient.sign=sign*div.sign; - //cerr<<"quotient="<<hex<<quotient<<dec<<endl; guess=quotient*div; - //cerr<<"guess= "<<hex<<guess<<dec<<endl; } - //cerr<<"guess= "<<hex<<guess<<" quotient="<<quotient<<dec<<endl; -#endif -#endif + + //Now actually subtract out our guess cmp=guess.compareAbs(*this); + assert(cmp<=0); //we specifically made our guessed quotient to be <= the actual quotient if(cmp<0){ - /*Bigint guess2(guess); - while(true){ - guess2<<=1; - int cmp=guess2.compareAbs(*this); - if(cmp>0)break; - guess<<=1; - quotient<<=1; - if(cmp==0){record(depth); return make_pair(quotient,Bigint::zero);} - }*/ Bigint rest(*this); rest-=guess; //also correct for *this and guess negative pair<Bigint,Bigint> dm=rest.divmod(div,depth+1,maxdepth); dm.first+=quotient; return dm; + } else { //then cmp==0 + return make_pair(quotient,Bigint::zero); } - if(cmp==0){record(depth); return make_pair(quotient,Bigint::zero);} - //then cmp>0, so our guess is too large - do { - if(quotient.digits[0]&1){ - guess-=div; - // quotient-=Bigint::one; // not necessary, since we shift the bit out anyway - } - guess>>=1; - quotient>>=1; - cmp=guess.compareAbs(*this); - } while(cmp>0); - if(cmp==0){record(depth); return make_pair(quotient,Bigint::zero);} - Bigint rest(*this); - rest-=guess; - pair<Bigint,Bigint> dm=rest.divmod(div,depth+1,maxdepth); - dm.first+=quotient; - return dm; } bool Bigint::operator==(const Bigint &o) const {return compare(o)==0;} @@ -619,7 +542,6 @@ istream& operator>>(istream &is,Bigint &b){ if(!is)break; b*=ten; b+=c-'0'; - // cerr<<"b="<<b<<endl; } if(!acted)is.setstate(ios_base::failbit); b.normalise(); @@ -641,14 +563,7 @@ std::ostream& operator<<(std::ostream &os,Bigint b){ } return os; } -#if 0 - assert(b.digits.size()<=2); - if(b.sign==-1)os<<'-'; - if(b.digits.size()==2)os<<((uint64_t)b.digits[1]<<32)+b.digits[0]; - else if(b.digits.size()==1)os<<b.digits[0]; - else os<<'0'; - return os; -#else + if(b==0)return os<<'0'; Bigint div((int64_t)1000000000000000000LL); vector<Bigint::longdigit_t> outbuf; @@ -667,5 +582,4 @@ std::ostream& operator<<(std::ostream &os,Bigint b){ (i==(int)outbuf.size()-1?os:os<<setfill('0')<<setw(18))<<outbuf[i]; } return os; -#endif } diff --git a/envelope.cpp b/envelope.cpp index 9bb011e..4674121 100644 --- a/envelope.cpp +++ b/envelope.cpp @@ -24,28 +24,25 @@ namespace Envelope{ do { for(int i=0;i<keylen;i++)*(uint32_t*)&key[4*i]=crng.get(); } while(!safeKey(key)); - //cerr<<"WARNING: using predetermined envelope key"<<endl; - //key="kaasKAASkaasKAAShalloHALLOhallo!"; - - cerr<<"decrkey="<<Base64::encode(key)<<endl; + // cerr<<"decrkey="<<Base64::encode(key)<<endl; string payload(AES::encrypt(data,key,AES::AES_256_CBC)); - cerr<<"payload="<<Base64::encode(payload)<<endl; + // cerr<<"payload="<<Base64::encode(payload)<<endl; Bigint rsadata; for(int i=0;i<(int)key.size();i++){ if(i!=0)rsadata<<=8; rsadata+=(uint8_t)key[i]; } - cerr<<"rsadata="<<rsadata<<endl; - // cerr<<"We encrypt:"<<endl<<" "<<rsadata<<endl; + // cerr<<"rsadata="<<rsadata<<endl; Bigint res(RSA::encrypt(rsadata,pubkey)); - // cerr<<"to:"<<endl<<" "<<res<<endl; + vector<uint8_t> bytes; //bytes in little-endian order while(res!=0){ bytes.push_back(res.lowdigits()&0xff); res>>=8; } - cerr<<"encrkey="<<Base64::encode(string(bytes.rbegin(),bytes.rend()))<<endl; + // cerr<<"encrkey="<<Base64::encode(string(bytes.rbegin(),bytes.rend()))<<endl; + payload.reserve(payload.size()+bytes.size()+2); for(int i=bytes.size()-1;i>=0;i--)payload.push_back(bytes[i]); payload.push_back(bytes.size()>>8); @@ -55,24 +52,27 @@ namespace Envelope{ } string decrypt(const string &data,const RSA::PrivateKey &privkey){ - cerr<<"=== DECRYPT ==="<<endl; + // cerr<<"=== DECRYPT ==="<<endl; if(data.size()<2)throw invalid_argument("Envelope data length invalid"); int encrkeylen=((uint16_t)(uint8_t)data[data.size()-2]<<8)+(uint8_t)data.back(); assert(encrkeylen<(1<<16)); - cerr<<"encrkeylen="<<encrkeylen<<endl; + // cerr<<"encrkeylen="<<encrkeylen<<endl; if((int)data.size()<encrkeylen+2)throw invalid_argument("Envelope key format invalid"); + string encrkey(encrkeylen,'\0'); for(int i=0;i<encrkeylen;i++){ encrkey[i]=data[data.size()-2-encrkeylen+i]; } - cerr<<"encrkey="<<Base64::encode(encrkey)<<endl; + // cerr<<"encrkey="<<Base64::encode(encrkey)<<endl; + Bigint rsadata; for(int i=0;i<encrkeylen;i++){ if(i!=0)rsadata<<=8; rsadata+=(uint8_t)encrkey[i]; } Bigint res(RSA::decrypt(rsadata,privkey)); - cerr<<"rsadata="<<res<<endl; + // cerr<<"rsadata="<<res<<endl; + vector<uint8_t> bytes; //bytes in little-endian order while(res!=0){ bytes.push_back(res.lowdigits()&0xff); @@ -80,8 +80,9 @@ namespace Envelope{ } string decrkey(bytes.size(),'\0'); for(int i=0;i<(int)bytes.size();i++)decrkey[bytes.size()-1-i]=bytes[i]; - cerr<<"decrkey="<<Base64::encode(decrkey)<<endl; - cerr<<"payload="<<Base64::encode(data.substr(0,data.size()-2-encrkeylen))<<endl; + // cerr<<"decrkey="<<Base64::encode(decrkey)<<endl; + + // cerr<<"payload="<<Base64::encode(data.substr(0,data.size()-2-encrkeylen))<<endl; return AES::decrypt(data.substr(0,data.size()-2-encrkeylen),decrkey,AES::AES_256_CBC); } @@ -47,7 +47,7 @@ GF28& GF28::operator-=(GF28 o){ return *this; } -GF28& GF28::operator<<=(int n){ //multiplication by x^n +GF28& GF28::operator<<=(int n){ assert(n>=0); value<<=n; if(value&0x100)value^=modulus; diff --git a/numalgo.cpp b/numalgo.cpp index 38184b1..ee77afc 100644 --- a/numalgo.cpp +++ b/numalgo.cpp @@ -25,10 +25,8 @@ Bigint gcd(Bigint a,Bigint b){ Bigint egcd(const Bigint &a,const Bigint &b,Bigint &x,Bigint &y){ Bigint x2(0),y2(1),r(a),r2(b); x=1; y=0; - //cerr<<x<<"\t * "<<a<<"\t + "<<y<<"\t * "<<b<<"\t = "<<r<<endl; while(r2!=0){ pair<Bigint,Bigint> dm=r.divmod(r2); - //cerr<<x2<<"\t * "<<a<<"\t + "<<y2<<"\t * "<<b<<"\t = "<<r2<<" (q = "<<dm.first<<')'<<endl; Bigint xn=x-dm.first*x2; Bigint yn=y-dm.first*y2; x=x2; x2=xn; @@ -54,11 +52,9 @@ Bigint expmod(const Bigint &b,const Bigint &e,const Bigint &m){ int jacobiSymbol(Bigint a,Bigint n){ //https://en.wikipedia.org/wiki/Jacobi_symbol#Calculating_the_Jacobi_symbol - // cerr<<"jacobiSymbol("<<a<<','<<n<<')'<<endl; assert(n>0&&n.odd()); int res=1; while(true){ - // cerr<<" a="<<a<<" n="<<n<<endl; a=a.divmod(n).second; if(a<0)a+=n; int nmod8=n.divmod(Bigint(8)).second.lowdigits(); @@ -79,14 +75,10 @@ Bigint isqrt(const Bigint &n){ assert(n>=0); if(n<=1)return n; const int maxiter=20; //empirically, this should happen around 3.5 million bits in n. (niter ~= -1.87+1.45ln(bits)) - // __asm("int3\n\t"); - // cout<<"bitcount="<<n.bitcount()<<" maxiter="<<maxiter<<endl; Bigint x(n); x>>=n.bitcount()/2; - // cerr<<"isqrt("<<hex<<n<<"); x = "<<x<<dec<<endl; int iter; for(iter=0;iter<maxiter;iter++){ - // cerr<<"x="<<hex<<x<<dec<<endl; Bigint xnext(x*x); // xnext = x - (x*x-n)/(2*x) [Newton's method] xnext-=n; xnext>>=1; @@ -11,7 +11,6 @@ vector<int> smallprimes; bool smallprimes_inited=false; void fillsmallprimes(){ - // cerr<<"Filling small primes..."<<endl; smallprimes_inited=true; //TODO: reserve expected amount of space in smallprimes smallprimes.push_back(2); @@ -27,8 +26,6 @@ void fillsmallprimes(){ composite[j/2-1]=true; } } - //for(int p : smallprimes)cerr<<p<<' '; - //cerr<<endl; } pair<Bigint,Bigint> genprimepair(Rng &rng,int nbits){ @@ -56,15 +53,12 @@ Bigint randprime(Rng &rng,const Bigint &biglow,const Bigint &bighigh){ if(diff<=maxrangesize){ low=biglow; high=bighigh; - // cerr<<"low=biglow="<<low<<" high=bighigh="<<high<<endl; } else { high=low=bigrandom(rng,diff-maxrangesize); high+=maxrangesize; - // cerr<<"low="<<low<<" high="<<high<<endl; } if(low.even())low+=1; if(high.even())high-=1; - // cerr<<"low="<<low<<" high="<<high<<endl; Bigint sizeb(high-low+1); assert(sizeb>=0&&sizeb<=maxrangesize); int nnums=(sizeb.lowdigits()+1)/2; @@ -83,23 +77,18 @@ Bigint randprime(Rng &rng,const Bigint &biglow,const Bigint &bighigh){ if(lowoffset==0)startat=0; else if((pr-lowoffset)%2==0)startat=(pr-lowoffset)/2; else startat=(pr-lowoffset+pr)/2; - // cerr<<"pr="<<pr<<" lowoffset="<<lowoffset<<" startat="<<startat<<endl; for(int i=startat;i<nnums;i+=pr){ //skips ahead `2*pr` each time (so `pr` array elements) - // cerr<<"sieving composite["<<i<<"]: "<<low+2*i<<endl; nleft-=!composite[i]; composite[i]=true; } } vector<int> maybeprimes; maybeprimes.reserve(nleft); - // cerr<<"Left ("<<nleft<<"):"; for(int i=0;i<nnums;i++){ if(!composite[i]){ - // cerr<<' '<<low+2*i; maybeprimes.push_back(i); } } - // cerr<<endl; while(maybeprimes.size()){ int idx=rng.get_uniform(maybeprimes.size()); @@ -148,13 +137,10 @@ bool strongLucasPrime(const Bigint &n){ } } //now we have a D - // cerr<<"D="<<D<<endl; int P=1,iQ=(1-D)/4; if(gcd(n,Bigint(P)).compareAbs(1)!=0||gcd(n,Bigint(iQ)).compareAbs(1)!=0)return false; //would be too easy to ignore - // cerr<<"ok"<<endl; //now begin the actual sequence algorithm -#if 1 int s=0; Bigint d(n); d+=1; @@ -162,11 +148,7 @@ bool strongLucasPrime(const Bigint &n){ d>>=1; s++; } -#else - Bigint d(n); - d+=1; -#endif - // cerr<<"d="<<d<<endl; + vector<bool> dbits=d.bits(); assert(dbits.size()>0); assert(dbits[dbits.size()-1]==true); @@ -198,7 +180,6 @@ bool strongLucasPrime(const Bigint &n){ } } if(U==0)return true; -#if 1 if(V==0)return true; //r=0 check for(int r=1;r<s;r++){ V*=V; @@ -207,7 +188,6 @@ bool strongLucasPrime(const Bigint &n){ Qk=(Qk*Qk).divmod(n).second; if(V==0)return true; } -#endif return false; } @@ -1,5 +1,3 @@ -// #include <iostream> -// #include <bitset> #include <cstring> #include <cassert> #include "rng.h" @@ -61,7 +59,6 @@ uint32_t KeyRng::get(){ state^=rotr64(state,11); //tempering state^=rotl64(state,7)&0x9d2c5680; state^=rotr64(state,18); - // cerr<<bitset<64>(state)<<endl; return state>>32; } @@ -11,8 +11,6 @@ using namespace std; namespace RSA{ Bigint encrypt(Bigint msg,const PublicKey &pubkey){ - // cerr<<"msg="<<msg<<endl; - // cerr<<"mod="<<pubkey.mod<<endl; assert(msg>1&&msg<pubkey.mod); return expmod(msg,pubkey.exp,pubkey.mod); } |