dsa.cpp Source File

00001 // dsa.cpp - written and placed in the public domain by Wei Dai
00002 
00003 #include "pch.h"
00004 #include "dsa.h"
00005 #include "asn.h"
00006 #include "oids.h"
00007 #include "nbtheory.h"
00008 #include "sha.h"
00009 
00010 NAMESPACE_BEGIN(CryptoPP)
00011 
00012 unsigned int DSAConvertSignatureFormat(byte *buffer, unsigned int bufferSize, DSASignatureFormat toFormat, const byte *signature, unsigned int signatureLen, DSASignatureFormat fromFormat)
00013 {
00014         Integer r, s;
00015         StringStore store(signature, signatureLen);
00016         ArraySink sink(buffer, bufferSize);
00017 
00018         switch (fromFormat)
00019         {
00020         case DSA_P1363:
00021                 r.Decode(store, signatureLen/2);
00022                 s.Decode(store, signatureLen/2);
00023                 break;
00024         case DSA_DER:
00025         {
00026                 BERSequenceDecoder seq(store);
00027                 r.BERDecode(seq);
00028                 s.BERDecode(seq);
00029                 seq.MessageEnd();
00030                 break;
00031         }
00032         case DSA_OPENPGP:
00033                 r.OpenPGPDecode(store);
00034                 s.OpenPGPDecode(store);
00035                 break;
00036         }
00037 
00038         switch (toFormat)
00039         {
00040         case DSA_P1363:
00041                 r.Encode(sink, bufferSize/2);
00042                 s.Encode(sink, bufferSize/2);
00043                 break;
00044         case DSA_DER:
00045         {
00046                 DERSequenceEncoder seq(sink);
00047                 r.DEREncode(seq);
00048                 s.DEREncode(seq);
00049                 seq.MessageEnd();
00050                 break;
00051         }
00052         case DSA_OPENPGP:
00053                 r.OpenPGPEncode(sink);
00054                 s.OpenPGPEncode(sink);
00055                 break;
00056         }
00057 
00058         return sink.TotalPutLength();
00059 }
00060 
00061 Integer DSA_EncodeDigest(unsigned int modulusBits, const byte *digest, unsigned int digestLen)
00062 {
00063         Integer h;
00064         if (digestLen*8 <= modulusBits)
00065                 h.Decode(digest, digestLen);
00066         else
00067         {
00068                 h.Decode(digest, bitsToBytes(modulusBits));
00069                 h >>= bitsToBytes(modulusBits)*8 - modulusBits;
00070         }
00071         return h;
00072 }
00073 
00074 GDSADigestVerifier::GDSADigestVerifier(const Integer &p, const Integer &q,
00075                            const Integer &g, const Integer &y)
00076         : m_p(p), m_q(q), m_g(g), m_y(y),
00077           m_gpc(p, g), m_ypc(p, y)
00078 {
00079 }
00080 
00081 void GDSADigestVerifier::Precompute(unsigned int precomputationStorage)
00082 {
00083         m_gpc.Precompute(ExponentBitLength(), precomputationStorage);
00084         m_ypc.Precompute(ExponentBitLength(), precomputationStorage);
00085 }
00086 
00087 void GDSADigestVerifier::LoadPrecomputation(BufferedTransformation &bt)
00088 {
00089         m_gpc.Load(bt);
00090         m_ypc.Load(bt);
00091 }
00092 
00093 void GDSADigestVerifier::SavePrecomputation(BufferedTransformation &bt) const
00094 {
00095         m_gpc.Save(bt);
00096         m_ypc.Save(bt);
00097 }
00098 
00099 Integer GDSADigestVerifier::EncodeDigest(const byte *digest, unsigned int digestLen) const
00100 {
00101         return DSA_EncodeDigest(m_q.BitCount(), digest, digestLen);
00102 }
00103 
00104 unsigned int GDSADigestVerifier::ExponentBitLength() const
00105 {
00106         return m_q.BitCount();
00107 }
00108 
00109 GDSADigestVerifier::GDSADigestVerifier(BufferedTransformation &bt)
00110 {
00111         BERSequenceDecoder subjectPublicKeyInfo(bt);
00112         if (subjectPublicKeyInfo.PeekByte() == INTEGER)
00113         {
00114                 // for backwards compatibility
00115                 m_p.BERDecode(subjectPublicKeyInfo);
00116                 m_q.BERDecode(subjectPublicKeyInfo);
00117                 m_g.BERDecode(subjectPublicKeyInfo);
00118                 m_y.BERDecode(subjectPublicKeyInfo);
00119         }
00120         else
00121         {
00122                 BERSequenceDecoder algorithm(subjectPublicKeyInfo);
00123                         ASN1::id_dsa().BERDecodeAndCheck(algorithm);
00124                         BERSequenceDecoder parameters(algorithm);
00125                                 m_p.BERDecode(parameters);
00126                                 m_q.BERDecode(parameters);
00127                                 m_g.BERDecode(parameters);
00128                         parameters.MessageEnd();
00129                 algorithm.MessageEnd();
00130 
00131                 BERSequenceDecoder subjectPublicKey(subjectPublicKeyInfo, BIT_STRING);
00132                         subjectPublicKey.CheckByte(0);  // unused bits
00133                         m_y.BERDecode(subjectPublicKey);
00134                 subjectPublicKey.MessageEnd();
00135         }
00136         subjectPublicKeyInfo.MessageEnd();
00137 
00138         m_gpc.SetModulusAndBase(m_p, m_g);
00139         m_ypc.SetModulusAndBase(m_p, m_y);
00140 }
00141 
00142 void GDSADigestVerifier::DEREncode(BufferedTransformation &bt) const
00143 {
00144         DERSequenceEncoder subjectPublicKeyInfo(bt);
00145 
00146                 DERSequenceEncoder algorithm(subjectPublicKeyInfo);
00147                         ASN1::id_dsa().DEREncode(algorithm);
00148                         DERSequenceEncoder parameters(algorithm);
00149                                 m_p.DEREncode(parameters);
00150                                 m_q.DEREncode(parameters);
00151                                 m_g.DEREncode(parameters);
00152                         parameters.MessageEnd();
00153                 algorithm.MessageEnd();
00154 
00155                 DERGeneralEncoder subjectPublicKey(subjectPublicKeyInfo, BIT_STRING);
00156                         subjectPublicKey.Put(0);        // unused bits
00157                         m_y.DEREncode(subjectPublicKey);
00158                 subjectPublicKey.MessageEnd();
00159 
00160         subjectPublicKeyInfo.MessageEnd();
00161 }
00162 
00163 bool GDSADigestVerifier::VerifyDigest(const byte *digest, unsigned int digestLen, const byte *signature) const
00164 {
00165         assert(digestLen <= MaxDigestLength());
00166 
00167         Integer h = EncodeDigest(digest, digestLen);
00168         unsigned int qLen = m_q.ByteCount();
00169         Integer r(signature, qLen);
00170         Integer s(signature+qLen, qLen);
00171         return RawVerify(h, r, s);
00172 }
00173 
00174 bool GDSADigestVerifier::RawVerify(const Integer &h, const Integer &r, const Integer &s) const
00175 {
00176         if (r>=m_q || r<1 || s>=m_q || s<1)
00177                 return false;
00178 
00179         Integer w = EuclideanMultiplicativeInverse(s, m_q);
00180         Integer u1 = (h * w) % m_q;
00181         Integer u2 = (r * w) % m_q;
00182         // verify r == (g^u1 * y^u2 mod p) mod q
00183         return r == m_gpc.CascadeExponentiate(u1, m_ypc, u2) % m_q;
00184 }
00185 
00186 // ******************************************************************
00187 
00188 GDSADigestSigner::GDSADigestSigner(const Integer &p, const Integer &q, const Integer &g, const Integer &y, const Integer &x)
00189         : GDSADigestVerifier(p, q, g, y), m_x(x)
00190 {
00191 }
00192 
00193 GDSADigestSigner::GDSADigestSigner(RandomNumberGenerator &rng, unsigned int pbits)
00194 {
00195         PrimeAndGenerator pg(1, rng, pbits, 2*DiscreteLogWorkFactor(pbits));
00196         m_p = pg.Prime();
00197         m_q = pg.SubPrime();
00198         m_g = pg.Generator();
00199         m_x.Randomize(rng, 1, m_q-1, Integer::ANY);
00200         m_gpc.SetModulusAndBase(m_p, m_g);
00201         m_y = m_gpc.Exponentiate(m_x);
00202         m_ypc.SetModulusAndBase(m_p, m_y);
00203 }
00204 
00205 GDSADigestSigner::GDSADigestSigner(RandomNumberGenerator &rng, const Integer &pIn, const Integer &qIn, const Integer &gIn)
00206 {
00207         m_p = pIn;
00208         m_q = qIn;
00209         m_g = gIn;
00210         m_x.Randomize(rng, 1, m_q-1, Integer::ANY);
00211         m_gpc.SetModulusAndBase(m_p, m_g);
00212         m_y = m_gpc.Exponentiate(m_x);
00213         m_ypc.SetModulusAndBase(m_p, m_y);
00214 }
00215 
00216 GDSADigestSigner::GDSADigestSigner(BufferedTransformation &bt)
00217 {
00218         BERSequenceDecoder privateKeyInfo(bt);
00219                 m_p.BERDecode(privateKeyInfo);
00220                 if (m_p != Integer::Zero())
00221                 {
00222                         // for backwards compatibility
00223                         m_q.BERDecode(privateKeyInfo);
00224                         m_g.BERDecode(privateKeyInfo);
00225                         m_y.BERDecode(privateKeyInfo);
00226                         m_x.BERDecode(privateKeyInfo);
00227                 }
00228                 else
00229                 {
00230                         BERSequenceDecoder algorithm(privateKeyInfo);
00231                                 ASN1::id_dsa().BERDecodeAndCheck(algorithm);
00232                                 BERSequenceDecoder parameters(algorithm);
00233                                         m_p.BERDecode(parameters);
00234                                         m_q.BERDecode(parameters);
00235                                         m_g.BERDecode(parameters);
00236                                 parameters.MessageEnd();
00237                         algorithm.MessageEnd();
00238 
00239                         BERGeneralDecoder octetString(privateKeyInfo, OCTET_STRING);
00240                                 m_x.BERDecode(octetString);
00241                         octetString.MessageEnd();
00242                 }
00243         privateKeyInfo.MessageEnd();
00244 
00245         m_gpc.SetModulusAndBase(m_p, m_g);
00246         m_y = m_gpc.Exponentiate(m_x);
00247         m_ypc.SetModulusAndBase(m_p, m_y);
00248 }
00249 
00250 void GDSADigestSigner::DEREncode(BufferedTransformation &bt) const
00251 {
00252         DERSequenceEncoder privateKeyInfo(bt);
00253 
00254                 DEREncodeUnsigned<word32>(privateKeyInfo, 0);   // version
00255 
00256                 DERSequenceEncoder algorithm(privateKeyInfo);
00257                         ASN1::id_dsa().DEREncode(algorithm);
00258                         DERSequenceEncoder parameters(algorithm);
00259                                 m_p.DEREncode(parameters);
00260                                 m_q.DEREncode(parameters);
00261                                 m_g.DEREncode(parameters);
00262                         parameters.MessageEnd();
00263                 algorithm.MessageEnd();
00264 
00265                 DERGeneralEncoder octetString(privateKeyInfo, OCTET_STRING);
00266                         m_x.DEREncode(octetString);
00267                 octetString.MessageEnd();
00268 
00269         privateKeyInfo.MessageEnd();
00270 }
00271 
00272 void GDSADigestSigner::SignDigest(RandomNumberGenerator &rng, const byte *digest, unsigned int digestLen, byte *signature) const
00273 {
00274         assert(digestLen <= MaxDigestLength());
00275 
00276         Integer h = EncodeDigest(digest, digestLen);
00277         Integer k(rng, 1, m_q-1);
00278         Integer r, s;
00279 
00280         RawSign(k, h, r, s);
00281         r.Encode(signature, m_q.ByteCount());
00282         s.Encode(signature+m_q.ByteCount(), m_q.ByteCount());
00283 }
00284 
00285 void GDSADigestSigner::RawSign(const Integer &k, const Integer &h, Integer &r, Integer &s) const
00286 {
00287         do
00288         {
00289                 r = m_gpc.Exponentiate(k) % m_q;
00290                 Integer kInv = EuclideanMultiplicativeInverse(k, m_q);
00291                 s = (kInv * (m_x*r + h)) % m_q;
00292         } while (!r || !s);
00293 }
00294 
00295 bool GenerateDSAPrimes(byte *seed, unsigned int g, int &counter,
00296                                                   Integer &p, unsigned int L, Integer &q)
00297 {
00298         assert(L >= MIN_DSA_PRIME_LENGTH && L <= MAX_DSA_PRIME_LENGTH);
00299         assert(L % 64 == 0);
00300 
00301         SHA sha;
00302         SecByteBlock U(SHA::DIGESTSIZE);
00303         SecByteBlock temp(SHA::DIGESTSIZE);
00304         SecByteBlock W(((L-1)/160+1) * SHA::DIGESTSIZE);
00305         const int n = (L-1) / 160;
00306         const int b = (L-1) % 160;
00307         Integer X;
00308 
00309         sha.CalculateDigest(U, seed, g/8);
00310 
00311         for (int i=g/8-1, carry=true; i>=0 && carry; i--)
00312                 carry=!++seed[i];
00313 
00314         sha.CalculateDigest(temp, seed, g/8);
00315         xorbuf(U, temp, SHA::DIGESTSIZE);
00316 
00317         U[0] |= 0x80;
00318         U[SHA::DIGESTSIZE-1] |= 1;
00319         q.Decode(U, SHA::DIGESTSIZE);
00320 
00321         if (!IsPrime(q))
00322                 return false;
00323 
00324         for (counter = 0; counter < 4096; counter++)
00325         {
00326                 for (int k=0; k<=n; k++)
00327                 {
00328                         for (int i=g/8-1, carry=true; i>=0 && carry; i--)
00329                                 carry=!++seed[i];
00330                         sha.CalculateDigest(W+(n-k)*SHA::DIGESTSIZE, seed, g/8);
00331                 }
00332                 W[SHA::DIGESTSIZE - 1 - b/8] |= 0x80;
00333                 X.Decode(W + SHA::DIGESTSIZE - 1 - b/8, L/8);
00334                 p = X-((X % (2*q))-1);
00335 
00336                 if (p.GetBit(L-1) && IsPrime(p))
00337                         return true;
00338         }
00339         return false;
00340 }
00341 
00342 DSAPrivateKey::DSAPrivateKey(RandomNumberGenerator &rng, unsigned int keybits)
00343 {
00344         SecByteBlock seed(SHA::DIGESTSIZE);
00345         Integer h;
00346         int c;
00347 
00348         do
00349         {
00350                 rng.GetBlock(seed, SHA::DIGESTSIZE);
00351         } while (!GenerateDSAPrimes(seed, SHA::DIGESTSIZE*8, c, m_p, keybits, m_q));
00352 
00353         do
00354         {
00355                 h.Randomize(rng, 2, m_p-2);
00356                 m_g = a_exp_b_mod_c(h, (m_p-1)/m_q, m_p);
00357         } while (m_g <= 1);
00358 
00359         m_x.Randomize(rng, 1, m_q-1);
00360         m_gpc.SetModulusAndBase(m_p, m_g);
00361         m_y = m_gpc.Exponentiate(m_x);
00362         m_ypc.SetModulusAndBase(m_p, m_y);
00363 }
00364 
00365 NAMESPACE_END