Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members

# rw.cpp

    00001 // rw.cpp - written and placed in the public domain by Wei Dai
    00002
    00003 #include "pch.h"
    00004 #include "rw.h"
    00005 #include "nbtheory.h"
    00006 #include "asn.h"
    00007
    00008 NAMESPACE_BEGIN(CryptoPP)
    00009
    00010 void EMSA2Pad::ComputeMessageRepresentative(RandomNumberGenerator &rng,
    00011         const byte *recoverableMessage, unsigned int recoverableMessageLength,
    00012         HashTransformation &hash, HashIdentifier hashIdentifier, bool messageEmpty,
    00013         byte *representative, unsigned int representativeBitLength) const
    00014 {
    00015         if (representativeBitLength % 8 != 7)
    00016                 throw PK_SignatureScheme::InvalidKeyLength("EMSA2: EMSA2 requires a key length that is a multiple of 8");
    00017
    00018         unsigned int digestSize = hash.DigestSize();
    00019         if (representativeBitLength < 8*digestSize + 31)
    00020                 throw PK_SignatureScheme::KeyTooShort();
    00021
    00022         unsigned int representativeByteLength = BitsToBytes(representativeBitLength);
    00023
    00024         representative[0] = messageEmpty ? 0x4b : 0x6b;
    00025         memset(representative+1, 0xbb, representativeByteLength-digestSize-4);  // pad with 0xbb
    00026         byte *afterP2 = representative+representativeByteLength-digestSize-3;
    00027         afterP2[0] = 0xba;
    00028         hash.Final(afterP2+1);
    00029         representative[representativeByteLength-2] = *hashIdentifier.first;
    00030         representative[representativeByteLength-1] = 0xcc;
    00031 }
    00032
    00033 // *****************************************************************************
    00034
    00035 void RWFunction::BERDecode(BufferedTransformation &bt)
    00036 {
    00037         BERSequenceDecoder seq(bt);
    00038         m_n.BERDecode(seq);
    00039         seq.MessageEnd();
    00040 }
    00041
    00042 void RWFunction::DEREncode(BufferedTransformation &bt) const
    00043 {
    00044         DERSequenceEncoder seq(bt);
    00045         m_n.DEREncode(seq);
    00046         seq.MessageEnd();
    00047 }
    00048
    00049 Integer RWFunction::ApplyFunction(const Integer &in) const
    00050 {
    00051         DoQuickSanityCheck();
    00052
    00053         Integer out = in.Squared()%m_n;
    00054         const word r = 12;
    00055         // this code was written to handle both r = 6 and r = 12,
    00056         // but now only r = 12 is used in P1363
    00057         const word r2 = r/2;
    00058         const word r3a = (16 + 5 - r) % 16;     // n%16 could be 5 or 13
    00059         const word r3b = (16 + 13 - r) % 16;
    00060         const word r4 = (8 + 5 - r/2) % 8;      // n%8 == 5
    00061         switch (out % 16)
    00062         {
    00063         case r:
    00064                 break;
    00065         case r2:
    00066         case r2+8:
    00067                 out <<= 1;
    00068                 break;
    00069         case r3a:
    00070         case r3b:
    00071                 out.Negate();
    00072                 out += m_n;
    00073                 break;
    00074         case r4:
    00075         case r4+8:
    00076                 out.Negate();
    00077                 out += m_n;
    00078                 out <<= 1;
    00079                 break;
    00080         default:
    00081                 out = Integer::Zero();
    00082         }
    00083         return out;
    00084 }
    00085
    00086 bool RWFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
    00087 {
    00088         bool pass = true;
    00089         pass = pass && m_n > Integer::One() && m_n%8 == 5;
    00090         return pass;
    00091 }
    00092
    00093 bool RWFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
    00094 {
    00095         return GetValueHelper(this, name, valueType, pValue).Assignable()
    00096                 CRYPTOPP_GET_FUNCTION_ENTRY(Modulus)
    00097                 ;
    00098 }
    00099
    00100 void RWFunction::AssignFrom(const NameValuePairs &source)
    00101 {
    00102         AssignFromHelper(this, source)
    00103                 CRYPTOPP_SET_FUNCTION_ENTRY(Modulus)
    00104                 ;
    00105 }
    00106
    00107 // *****************************************************************************
    00108 // private key operations:
    00109
    00110 // generate a random private key
    00111 void InvertibleRWFunction::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
    00112 {
    00113         int modulusSize = 2048;
    00114         alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize);
    00115
    00116         if (modulusSize < 16)
    00117                 throw InvalidArgument("InvertibleRWFunction: specified modulus length is too small");
    00118
    00119         const NameValuePairs &primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize);
    00120         m_p.GenerateRandom(rng, CombinedNameValuePairs(primeParam, MakeParameters("EquivalentTo", 3)("Mod", 8)));
    00121         m_q.GenerateRandom(rng, CombinedNameValuePairs(primeParam, MakeParameters("EquivalentTo", 7)("Mod", 8)));
    00122
    00123         m_n = m_p * m_q;
    00124         m_u = m_q.InverseMod(m_p);
    00125 }
    00126
    00127 void InvertibleRWFunction::BERDecode(BufferedTransformation &bt)
    00128 {
    00129         BERSequenceDecoder seq(bt);
    00130         m_n.BERDecode(seq);
    00131         m_p.BERDecode(seq);
    00132         m_q.BERDecode(seq);
    00133         m_u.BERDecode(seq);
    00134         seq.MessageEnd();
    00135 }
    00136
    00137 void InvertibleRWFunction::DEREncode(BufferedTransformation &bt) const
    00138 {
    00139         DERSequenceEncoder seq(bt);
    00140         m_n.DEREncode(seq);
    00141         m_p.DEREncode(seq);
    00142         m_q.DEREncode(seq);
    00143         m_u.DEREncode(seq);
    00144         seq.MessageEnd();
    00145 }
    00146
    00147 Integer InvertibleRWFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &in) const
    00148 {
    00149         // no need to do blinding because RW is only used for signatures
    00150
    00151         DoQuickSanityCheck();
    00152
    00153         Integer cp=in%m_p, cq=in%m_q;
    00154
    00155         if (Jacobi(cp, m_p) * Jacobi(cq, m_q) != 1)
    00156         {
    00157                 cp = cp%2 ? (cp+m_p) >> 1 : cp >> 1;
    00158                 cq = cq%2 ? (cq+m_q) >> 1 : cq >> 1;
    00159         }
    00160
    00161         cp = ModularSquareRoot(cp, m_p);
    00162         cq = ModularSquareRoot(cq, m_q);
    00163
    00164         Integer out = CRT(cq, m_q, cp, m_p, m_u);
    00165
    00166         return STDMIN(out, m_n-out);
    00167 }
    00168
    00169 bool InvertibleRWFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
    00170 {
    00171         bool pass = RWFunction::Validate(rng, level);
    00172         pass = pass && m_p > Integer::One() && m_p%8 == 3 && m_p < m_n;
    00173         pass = pass && m_q > Integer::One() && m_q%8 == 7 && m_q < m_n;
    00174         pass = pass && m_u.IsPositive() && m_u < m_p;
    00175         if (level >= 1)
    00176         {
    00177                 pass = pass && m_p * m_q == m_n;
    00178                 pass = pass && m_u * m_q % m_p == 1;
    00179         }
    00180         if (level >= 2)
    00181                 pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2);
    00182         return pass;
    00183 }
    00184
    00185 bool InvertibleRWFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
    00186 {
    00187         return GetValueHelper<RWFunction>(this, name, valueType, pValue).Assignable()
    00188                 CRYPTOPP_GET_FUNCTION_ENTRY(Prime1)
    00189                 CRYPTOPP_GET_FUNCTION_ENTRY(Prime2)
    00190                 CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
    00191                 ;
    00192 }
    00193
    00194 void InvertibleRWFunction::AssignFrom(const NameValuePairs &source)
    00195 {
    00196         AssignFromHelper<RWFunction>(this, source)
    00197                 CRYPTOPP_SET_FUNCTION_ENTRY(Prime1)
    00198                 CRYPTOPP_SET_FUNCTION_ENTRY(Prime2)
    00199                 CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
    00200                 ;
    00201 }
    00202
    00203 NAMESPACE_END