2 * Based on code parts from pegwit program written by George Barwood.
3 * This code is in the public domain; do with it what you wish.
15 static vlong modexp( const vlong & x, const vlong & e, const vlong & m ); // m must be odd
16 static vlong gcd( const vlong &X, const vlong &Y ); // greatest common denominator
17 static vlong modinv( const vlong &a, const vlong &m ); // modular inverse
19 // VLONG.CPP -----------------------------------
21 class flex_unit // Provides storage allocation and index checking
25 unsigned * a; // array of units
26 unsigned z; // units allocated
28 unsigned n; // used units (read-only)
31 void clear(); // set n to zero
32 unsigned get( unsigned i ) const; // get ith unsigned
33 void set( unsigned i, unsigned x ); // set ith unsigned
34 void reserve( unsigned x ); // storage hint
36 // Time critical routine
37 void fast_mul( flex_unit &x, flex_unit &y, unsigned n );
40 class vlong_value : public flex_unit
43 unsigned share; // share count, used by vlong to delay physical copying
45 int test( unsigned i ) const;
46 unsigned bits() const;
47 int cf( vlong_value& x ) const;
50 void shr( unsigned n );
51 void add( vlong_value& x );
52 void subtract( vlong_value& x );
53 void init( unsigned x );
54 void copy( vlong_value& x );
55 operator unsigned(); // Unsafe conversion to unsigned
57 void mul( vlong_value& x, vlong_value& y );
58 void divide( vlong_value& x, vlong_value& y, vlong_value& rem );
61 unsigned flex_unit::get( unsigned i ) const
63 if ( i >= n ) return 0;
67 void flex_unit::clear()
72 flex_unit::flex_unit()
79 flex_unit::~flex_unit()
82 while (i) { i-=1; a[i] = 0; } // burn
86 void flex_unit::reserve( unsigned x )
90 unsigned * na = new unsigned[x];
91 for (unsigned i=0;i<n;i+=1) na[i] = a[i];
98 void flex_unit::set( unsigned i, unsigned x )
103 if (x==0) while (n && a[n-1]==0) n-=1; // normalise
108 for (unsigned j=n;j<i;j+=1) a[j] = 0;
114 // Macros for doing double precision multiply
115 #define BPU ( 8*sizeof(unsigned) ) // Number of bits in an unsigned
116 #define lo(x) ( (x) & ((1<<(BPU/2))-1) ) // lower half of unsigned
117 #define hi(x) ( (x) >> (BPU/2) ) // upper half
118 #define lh(x) ( (x) << (BPU/2) ) // make upper half
120 void flex_unit::fast_mul( flex_unit &x, flex_unit &y, unsigned keep )
122 // *this = (x*y) % (2**keep)
123 unsigned i,j,limit = (keep+BPU-1)/BPU; // size of result in words
124 reserve(limit); for (i=0; i<limit; i+=1) a[i] = 0;
125 unsigned min = x.n; if (min>limit) min = limit;
126 for (i=0; i<min; i+=1)
129 unsigned c = 0; // carry
130 unsigned min = i+y.n; if (min>limit) min = limit;
131 for ( j=i; j<min; j+=1 )
133 // This is the critical loop
134 // Machine dependent code could help here
135 // c:a[j] = a[j] + c + m*y.a[j-i];
136 unsigned w, v = a[j], p = y.a[j-i];
137 v += c; c = ( v < c );
138 w = lo(p)*lo(m); v += w; c += ( v < w );
139 w = lo(p)*hi(m); c += hi(w); w = lh(w); v += w; c += ( v < w );
140 w = hi(p)*lo(m); c += hi(w); w = lh(w); v += w; c += ( v < w );
144 while ( c && j<limit )
152 // eliminate unwanted bits
153 keep %= BPU; if (keep) a[limit-1] &= (1<<keep)-1;
156 while (limit && a[limit-1]==0) limit-=1;
160 vlong_value::operator unsigned()
165 int vlong_value::is_zero() const
170 int vlong_value::test( unsigned i ) const
171 { return ( get(i/BPU) & (1<<(i%BPU)) ) != 0; }
173 unsigned vlong_value::bits() const
176 while (x && test(x-1)==0) x -= 1;
180 int vlong_value::cf( vlong_value& x ) const
182 if ( n > x.n ) return +1;
183 if ( n < x.n ) return -1;
188 if ( get(i) > x.get(i) ) return +1;
189 if ( get(i) < x.get(i) ) return -1;
194 void vlong_value::shl()
197 unsigned N = n; // necessary, since n can change
198 for (unsigned i=0;i<=N;i+=1)
206 void vlong_value::shr()
219 void vlong_value::shr( unsigned x )
221 unsigned delta = x/BPU; x %= BPU;
222 for (unsigned i=0;i<n;i+=1)
224 unsigned u = get(i+delta);
228 u += get(i+delta+1) << (BPU-x);
234 void vlong_value::add( vlong_value & x )
237 unsigned max = n; if (max<x.n) max = x.n;
239 for (unsigned i=0;i<max+1;i+=1)
242 u = u + carry; carry = ( u < carry );
243 unsigned ux = x.get(i);
244 u = u + ux; carry += ( u < ux );
249 void vlong_value::subtract( vlong_value & x )
253 for (unsigned i=0;i<N;i+=1)
255 unsigned ux = x.get(i);
260 unsigned nu = u - ux;
267 void vlong_value::init( unsigned x )
273 void vlong_value::copy( vlong_value& x )
277 while (i) { i -= 1; set( i, x.get(i) ); }
280 vlong_value::vlong_value()
285 void vlong_value::mul( vlong_value& x, vlong_value& y )
287 fast_mul( x, y, x.bits()+y.bits() );
290 void vlong_value::divide( vlong_value& x, vlong_value& y, vlong_value& rem )
297 while ( rem.cf(m) > 0 )
302 while ( rem.cf(y) >= 0 )
304 while ( rem.cf(m) < 0 )
314 // Implementation of vlong
316 void vlong::load( unsigned * a, unsigned n )
320 for (unsigned i=0;i<n;i+=1)
324 void vlong::store( unsigned * a, unsigned n ) const
326 for (unsigned i=0;i<n;i+=1)
327 a[i] = value->get(i);
330 unsigned vlong::get_nunits() const
335 unsigned vlong::bits() const
337 return value->bits();
345 vlong_value * nv = new vlong_value;
351 int vlong::cf( const vlong x ) const
353 int neg = negative && !value->is_zero();
354 //int neg2 = x.negative && !x.value->is_zero();
356 if ( neg == (x.negative && !x.value->is_zero()) )
358 return value->cf( *x.value );
360 else if ( neg ) return -1;
364 vlong::vlong (unsigned x)
366 value = new vlong_value;
371 vlong::vlong ( const vlong& x ) // copy constructor
373 negative = x.negative;
378 vlong& vlong::operator =(const vlong& x)
380 if ( value->share ) value->share -=1; else delete value;
383 negative = x.negative;
389 if ( value->share ) value->share -=1; else delete value;
392 vlong::operator unsigned () // conversion to unsigned
397 vlong& vlong::operator +=(const vlong& x)
399 if ( negative == x.negative )
402 value->add( *x.value );
404 else if ( value->cf( *x.value ) >= 0 )
407 value->subtract( *x.value );
418 vlong& vlong::operator -=(const vlong& x)
420 if ( negative != x.negative )
423 value->add( *x.value );
425 else if ( value->cf( *x.value ) >= 0 )
428 value->subtract( *x.value );
435 negative = 1 - negative;
440 vlong operator +( const vlong& x, const vlong& y )
447 vlong operator -( const vlong& x, const vlong& y )
454 vlong operator *( const vlong& x, const vlong& y )
457 result.value->mul( *x.value, *y.value );
458 result.negative = x.negative ^ y.negative;
462 vlong operator /( const vlong& x, const vlong& y )
466 result.value->divide( *x.value, *y.value, rem );
467 result.negative = x.negative ^ y.negative;
471 #if defined(__DEBUG__)
472 void print_vlong( const vlong_value & v, const char *name )
474 printf("%s value(%d): ", name, v.n * sizeof(unsigned int));
475 for(int i = 0; i < v.n; ++i)
477 printf("%08X", v.a[i]);
483 vlong operator %( const vlong& x, const vlong& y )
487 divide.divide( *x.value, *y.value, *result.value );
488 result.negative = x.negative; // not sure about this?
492 static vlong gcd( const vlong &X, const vlong &Y )
497 if ( y == (vlong)0 ) return x;
499 if ( x == (vlong)0 ) return y;
504 static vlong modinv( const vlong &a, const vlong &m ) // modular inverse
505 // returns i in range 1..m-1 such that i*a = 1 mod m
506 // a must be in range 1..m-1
508 vlong j=1,i=0,b=m,c=a,x,y;
509 while ( c != (vlong)0 )
524 class monty // class for montgomery modular exponentiation
527 vlong T,k; // work registers
528 unsigned N; // bits for R
529 void mul( vlong &x, const vlong &y );
531 vlong exp( const vlong &x, const vlong &e );
532 monty( const vlong &M );
535 monty::monty( const vlong &M )
538 N = 0; R = 1; while ( R < M ) { R += R; N += 1; }
539 R1 = modinv( R-m, m );
540 n1 = R - modinv( m, R );
543 void monty::mul( vlong &x, const vlong &y )
546 T.value->fast_mul( *x.value, *y.value, N*2 );
548 // k = ( T * n1 ) % R;
549 k.value->fast_mul( *T.value, *n1.value, N );
551 // x = ( T + k*m ) / R;
552 x.value->fast_mul( *k.value, *m.value, N*2 );
559 vlong monty::exp( const vlong &x, const vlong &e )
561 vlong result = R-m, t = ( x * R ) % m;
562 unsigned bits = e.value->bits();
566 if ( e.value->test(i) )
571 if ( i == bits ) break;
574 return ( result * R1 ) % m;
577 static vlong modexp( const vlong & x, const vlong & e, const vlong & m )
580 return me.exp( x,e );
583 // RSA.CPP -----------------------------------
585 vlong public_key::encrypt( const vlong& plain )
587 #if defined(__DEBUG__)
589 printf("ERROR: plain too big for this key\n");
592 return modexp( plain, e, m );
595 vlong private_key::decrypt( const vlong& cipher )
597 // Calculate values for performing decryption
598 // These could be cached, but the calculation is quite fast
599 vlong d = modinv( e, (p-(vlong)1)*(q-(vlong)1) );
600 vlong u = modinv( p, q );
601 vlong dp = d % (p-(vlong)1);
602 vlong dq = d % (q-(vlong)1);
604 // Apply chinese remainder theorem
605 vlong a = modexp( cipher % p, dp, p );
606 vlong b = modexp( cipher % q, dq, q );
608 return a + p * ( ((b-a)*u) % q );
611 void vlong_pair_2_str (char *me_str,vlong &m,vlong &e)
613 const char *hex_str = "0123456789ABCDEF";
615 char tmp_str[MAX_CRYPT_BITS/2+1];
618 unsigned int me_len = 0;
629 m1 = m1 / (vlong) 16;
630 tmp_str[i++] = hex_str[x];
633 for (j=0; j < i; j++)
634 me_str[me_len++] = tmp_str[i-1-j];
636 me_str[me_len++] = '#';
643 tmp_str[i++] = hex_str[x];
646 for (j=0; j < i; j++)
647 me_str[me_len++] = tmp_str[i-1-j];
651 void str_2_vlong_pair (const char *me_str,vlong &m,vlong &e)
658 int me_len = (int)strlen (me_str);
660 for (i = me_len-1; i>0; i--)
661 if (me_str[i] == '#')
671 for (i = 0; i<dash_pos; i++)
675 m = m + (vlong) (me_str[i]-'A'+10);
677 m = m + (vlong) (me_str[i]-'0');
680 for (i = dash_pos+1; i<me_len; i++)
684 e = e + (vlong) (me_str[i]-'A'+10);
686 e = e + (vlong) (me_str[i]-'0');
694 void private_key::MakeMeStr(char * me_str)
696 vlong_pair_2_str (me_str,m,e);
699 void private_key::MakePqStr(char * me_str)
701 vlong_pair_2_str (me_str,p,q);
704 void private_key::MakePq (const char *me_str)
706 str_2_vlong_pair (me_str,p,q);
709 e = 50001; // must be odd since p-1 and q-1 are even
710 while ( gcd(p-(vlong)1,e) != (vlong)1 || gcd(q-(vlong)1,e) != (vlong)1 ) e += 2;
716 void public_key::MakeMe(const char *me_str)
718 str_2_vlong_pair (me_str,m,e);
721 CCryptoProviderRSA::CCryptoProviderRSA()
725 CCryptoProviderRSA::~CCryptoProviderRSA()
729 void inline _rmemcpy (char *dst,const char *src,size_t size)
736 void CCryptoProviderRSA::GetBlockSize(int &enbs, int &debs)
742 void CCryptoProviderRSA::EncryptPortion(const char *pt, size_t pt_size, char *ct, size_t &ct_size)
746 const size_t bytes_per_unit = BPU / 8;
748 size_t padding = (pt_size & 3) ? (4 - (pt_size & 3)) : 0;
749 char tmp[MAX_CRYPT_BITS/4];
751 // ensure big-endianness
752 _rmemcpy(tmp, pt, pt_size);
753 memset(tmp + pt_size, 0, padding);
754 plain.load((unsigned int*)tmp, (int)(pt_size+padding) / bytes_per_unit);
756 cipher = prkface.encrypt(plain);
757 ct_size = cipher.get_nunits() * bytes_per_unit;
759 // ensure big-endianness
760 cipher.store((unsigned int*)tmp, (int)ct_size / bytes_per_unit);
761 _rmemcpy(ct, tmp, ct_size);
764 void CCryptoProviderRSA::DecryptPortion(const char *ct, size_t ct_size, char *pt, size_t &pt_size)
768 const size_t bytes_per_unit = BPU / 8;
770 char tmp[MAX_CRYPT_BITS/4];
772 // ensure big-endianness
773 _rmemcpy(tmp, ct, ct_size);
775 cipher.load((unsigned int*)tmp, (int)ct_size / bytes_per_unit);
776 plain = prkface.decrypt(cipher);
778 // ensure big-endianness
779 plain.store((unsigned int*)tmp, plain.get_nunits());
780 _rmemcpy(pt, tmp, pt_size);
783 void CCryptoProviderRSA::ImportPublicKey(const char *pk)
787 void CCryptoProviderRSA::ImportPrivateKey(const char *pk)
792 void CCryptoProviderRSA::ExportPublicKey(char *pk)
794 prkface.MakeMeStr(pk);
797 void CCryptoProviderRSA::ExportPrivateKey(char *pk)
799 prkface.MakePqStr(pk);
802 #if defined(__DEBUG__)
803 void printbuf(const char * buf, int size)
805 for(const char * p = buf; p < buf + size; ++p)
807 printf("%02X", *p & 0x000000ff);
813 void CCryptoProviderRSA::Encrypt(const char *inbuf, size_t in_size,char *outbuf, size_t &out_size)
817 char portbuf[MAX_CRYPT_BITS/8];
818 char cpbuf[MAX_CRYPT_BITS/4];
819 const char *inp = inbuf;
823 // must ensure that any data block would be < key's modulus
825 int portion_len = (prkface.m.bits() - 1) / 8;
826 char prev_crypted[portion_len];
827 memset(&prev_crypted, 0, portion_len);
832 size_t cur_size = in_size > portion_len ? portion_len : in_size;
834 for (i=0; i<cur_size; i++)
835 portbuf[i] = inp[i] ^ prev_crypted[i];
837 EncryptPortion(portbuf, cur_size, cpbuf, cp_size);
839 for (i=0; i<portion_len; i++)
840 prev_crypted[i] = i < cp_size ? cpbuf[i] : 0;
843 memcpy (outbuf+out_size,&lm, sizeof(unsigned short)); out_size+=sizeof (unsigned short);
844 lm=(unsigned short)cp_size;
845 memcpy (outbuf+out_size,&lm, sizeof(unsigned short)); out_size+=sizeof (unsigned short);
846 memcpy (outbuf+out_size,cpbuf, cp_size); out_size+=cp_size;
854 void CCryptoProviderRSA::Decrypt(const char *inbuf, size_t in_size,char *outbuf, size_t &out_size)
856 size_t i, cp_size,pt_size;
858 char portbuf[MAX_CRYPT_BITS/8];
859 char cpbuf[MAX_CRYPT_BITS/4];
861 unsigned short lmi, lmo;
863 // must ensure that any data block would be < key's modulus
865 int portion_len = (prkface.m.bits() - 1) / 8;
866 char prev_crypted[portion_len];
867 memset(&prev_crypted, 0, portion_len);
869 const char *inp=inbuf;
874 memcpy (&lmi,inp,sizeof (unsigned short)); inp += sizeof(unsigned short); in_size -= sizeof(unsigned short);
875 memcpy (&lmo,inp,sizeof (unsigned short)); inp += sizeof(unsigned short); in_size -= sizeof(unsigned short);
880 memcpy (cpbuf,inp,lmo);
884 DecryptPortion(cpbuf, cp_size, portbuf, pt_size);
887 lmi=(unsigned short)pt_size;
889 for (i=0; i<lmi; i++)
890 portbuf[i] ^= prev_crypted[i];
892 for (i=0; i<portion_len; i++)
893 prev_crypted[i] = i < cp_size ? cpbuf[i] : 0;
895 memcpy (outbuf+out_size,portbuf,lmi);