- Main Page
- Namespaces
- Classes
- Files

# luc.cpp

    00001 // luc.cpp - written and placed in the public domain by Wei Dai
    00002
    00003 #include "pch.h"
    00004 #include "luc.h"
    00005 #include "asn.h"
    00006 #include "nbtheory.h"
    00007 #include "sha.h"
    00008 #include "algparam.h"
    00009
    00010 NAMESPACE_BEGIN(CryptoPP)
    00011
    00012 void LUC_TestInstantiations()
    00013 {
    00014         LUC_HMP<SHA>::Signer t1;
    00015         LUCFunction t2;
    00016         InvertibleLUCFunction t3;
    00017 }
    00018
    00019 void DL_Algorithm_LUC_HMP::Sign(const DL_GroupParameters<Integer> &params, const Integer &x, const Integer &k, const Integer &e, Integer &r, Integer &s) const
    00020 {
    00021         const Integer &q = params.GetSubgroupOrder();
    00022         r = params.ExponentiateBase(k);
    00023         s = (k + x*(r+e)) % q;
    00024 }
    00025
    00026 bool DL_Algorithm_LUC_HMP::Verify(const DL_GroupParameters<Integer> &params, const DL_PublicKey<Integer> &publicKey, const Integer &e, const Integer &r, const Integer &s) const
    00027 {
    00028         Integer p = params.GetGroupOrder()-1;
    00029         const Integer &q = params.GetSubgroupOrder();
    00030
    00031         Integer Vsg = params.ExponentiateBase(s);
    00032         Integer Vry = publicKey.ExponentiatePublicElement((r+e)%q);
    00033         return (Vsg*Vsg + Vry*Vry + r*r) % p == (Vsg * Vry * r + 4) % p;
    00034 }
    00035
    00036 Integer DL_BasePrecomputation_LUC::Exponentiate(const DL_GroupPrecomputation<Element> &group, const Integer &exponent) const
    00037 {
    00038         return Lucas(exponent, m_g, static_cast<const DL_GroupPrecomputation_LUC &>(group).GetModulus());
    00039 }
    00040
    00041 void DL_GroupParameters_LUC::SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
    00042 {
    00043         for (unsigned int i=0; i<exponentsCount; i++)
    00044                 results[i] = Lucas(exponents[i], base, GetModulus());
    00045 }
    00046
    00047 void LUCFunction::BERDecode(BufferedTransformation &bt)
    00048 {
    00049         BERSequenceDecoder seq(bt);
    00050         m_n.BERDecode(seq);
    00051         m_e.BERDecode(seq);
    00052         seq.MessageEnd();
    00053 }
    00054
    00055 void LUCFunction::DEREncode(BufferedTransformation &bt) const
    00056 {
    00057         DERSequenceEncoder seq(bt);
    00058         m_n.DEREncode(seq);
    00059         m_e.DEREncode(seq);
    00060         seq.MessageEnd();
    00061 }
    00062
    00063 Integer LUCFunction::ApplyFunction(const Integer &x) const
    00064 {
    00065         DoQuickSanityCheck();
    00066         return Lucas(m_e, x, m_n);
    00067 }
    00068
    00069 bool LUCFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
    00070 {
    00071         bool pass = true;
    00072         pass = pass && m_n > Integer::One() && m_n.IsOdd();
    00073         pass = pass && m_e > Integer::One() && m_e.IsOdd() && m_e < m_n;
    00074         return pass;
    00075 }
    00076
    00077 bool LUCFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
    00078 {
    00079         return GetValueHelper(this, name, valueType, pValue).Assignable()
    00080                 CRYPTOPP_GET_FUNCTION_ENTRY(Modulus)
    00081                 CRYPTOPP_GET_FUNCTION_ENTRY(PublicExponent)
    00082                 ;
    00083 }
    00084
    00085 void LUCFunction::AssignFrom(const NameValuePairs &source)
    00086 {
    00087         AssignFromHelper(this, source)
    00088                 CRYPTOPP_SET_FUNCTION_ENTRY(Modulus)
    00089                 CRYPTOPP_SET_FUNCTION_ENTRY(PublicExponent)
    00090                 ;
    00091 }
    00092
    00093 // *****************************************************************************
    00094 // private key operations:
    00095
    00096 class LUCPrimeSelector : public PrimeSelector
    00097 {
    00098 public:
    00099         LUCPrimeSelector(const Integer &e) : m_e(e) {}
    00100         bool IsAcceptable(const Integer &candidate) const
    00101         {
    00102                 return RelativelyPrime(m_e, candidate+1) && RelativelyPrime(m_e, candidate-1);
    00103         }
    00104         Integer m_e;
    00105 };
    00106
    00107 void InvertibleLUCFunction::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
    00108 {
    00109         int modulusSize = 2048;
    00110         alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize);
    00111
    00112         if (modulusSize < 16)
    00113                 throw InvalidArgument("InvertibleLUCFunction: specified modulus size is too small");
    00114
    00115         m_e = alg.GetValueWithDefault("PublicExponent", Integer(17));
    00116
    00117         if (m_e < 5 || m_e.IsEven())
    00118                 throw InvalidArgument("InvertibleLUCFunction: invalid public exponent");
    00119
    00120         LUCPrimeSelector selector(m_e);
    00121         AlgorithmParameters primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize)
    00122                 ("PointerToPrimeSelector", selector.GetSelectorPointer());
    00123         m_p.GenerateRandom(rng, primeParam);
    00124         m_q.GenerateRandom(rng, primeParam);
    00125
    00126         m_n = m_p * m_q;
    00127         m_u = m_q.InverseMod(m_p);
    00128 }
    00129
    00130 void InvertibleLUCFunction::Initialize(RandomNumberGenerator &rng, unsigned int keybits, const Integer &e)
    00131 {
    00132         GenerateRandom(rng, MakeParameters("ModulusSize", (int)keybits)("PublicExponent", e));
    00133 }
    00134
    00135 void InvertibleLUCFunction::BERDecode(BufferedTransformation &bt)
    00136 {
    00137         BERSequenceDecoder seq(bt);
    00138
    00139         Integer version(seq);
    00140         if (!!version)  // make sure version is 0
    00141                 BERDecodeError();
    00142
    00143         m_n.BERDecode(seq);
    00144         m_e.BERDecode(seq);
    00145         m_p.BERDecode(seq);
    00146         m_q.BERDecode(seq);
    00147         m_u.BERDecode(seq);
    00148         seq.MessageEnd();
    00149 }
    00150
    00151 void InvertibleLUCFunction::DEREncode(BufferedTransformation &bt) const
    00152 {
    00153         DERSequenceEncoder seq(bt);
    00154
    00155         const byte version[] = {INTEGER, 1, 0};
    00156         seq.Put(version, sizeof(version));
    00157         m_n.DEREncode(seq);
    00158         m_e.DEREncode(seq);
    00159         m_p.DEREncode(seq);
    00160         m_q.DEREncode(seq);
    00161         m_u.DEREncode(seq);
    00162         seq.MessageEnd();
    00163 }
    00164
    00165 Integer InvertibleLUCFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
    00166 {
    00167         // not clear how to do blinding with LUC
    00168         DoQuickSanityCheck();
    00169         return InverseLucas(m_e, x, m_q, m_p, m_u);
    00170 }
    00171
    00172 bool InvertibleLUCFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
    00173 {
    00174         bool pass = LUCFunction::Validate(rng, level);
    00175         pass = pass && m_p > Integer::One() && m_p.IsOdd() && m_p < m_n;
    00176         pass = pass && m_q > Integer::One() && m_q.IsOdd() && m_q < m_n;
    00177         pass = pass && m_u.IsPositive() && m_u < m_p;
    00178         if (level >= 1)
    00179         {
    00180                 pass = pass && m_p * m_q == m_n;
    00181                 pass = pass && RelativelyPrime(m_e, m_p+1);
    00182                 pass = pass && RelativelyPrime(m_e, m_p-1);
    00183                 pass = pass && RelativelyPrime(m_e, m_q+1);
    00184                 pass = pass && RelativelyPrime(m_e, m_q-1);
    00185                 pass = pass && m_u * m_q % m_p == 1;
    00186         }
    00187         if (level >= 2)
    00188                 pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2);
    00189         return pass;
    00190 }
    00191
    00192 bool InvertibleLUCFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
    00193 {
    00194         return GetValueHelper<LUCFunction>(this, name, valueType, pValue).Assignable()
    00195                 CRYPTOPP_GET_FUNCTION_ENTRY(Prime1)
    00196                 CRYPTOPP_GET_FUNCTION_ENTRY(Prime2)
    00197                 CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
    00198                 ;
    00199 }
    00200
    00201 void InvertibleLUCFunction::AssignFrom(const NameValuePairs &source)
    00202 {
    00203         AssignFromHelper<LUCFunction>(this, source)
    00204                 CRYPTOPP_SET_FUNCTION_ENTRY(Prime1)
    00205                 CRYPTOPP_SET_FUNCTION_ENTRY(Prime2)
    00206                 CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
    00207                 ;
    00208 }
    00209
    00210 NAMESPACE_END