From 5f324fd631bd33214cc52f3469dd40f9b099469b Mon Sep 17 00:00:00 2001 From: MITSUNARI Shigeo Date: Wed, 31 Aug 2016 10:33:19 +0900 Subject: refactor bls.cpp --- include/bls.hpp | 10 ++-- src/bls.cpp | 156 ++++++++++++++++++++---------------------------------- test/bls_test.cpp | 8 +-- 3 files changed, 67 insertions(+), 107 deletions(-) diff --git a/include/bls.hpp b/include/bls.hpp index 78c2c9c..aa287c1 100644 --- a/include/bls.hpp +++ b/include/bls.hpp @@ -44,10 +44,11 @@ class Sign; class Id; /* - value of secretKey and Id must be less than -r = 16798108731015832284940804142231733909759579603404752749028378864165570215949 + the value of secretKey and Id must be less than + r = 0x2523648240000001ba344d8000000007ff9f800000000010a10000000000000d + sizeof(uint64_t) * keySize = 32-byte */ -const size_t keySize = 4; // 256-bit size +const size_t keySize = 4; typedef std::vector SecretKeyVec; typedef std::vector PublicKeyVec; @@ -114,7 +115,7 @@ public: /* make [s_0, ..., s_{k-1}] to prepare k-out-of-n secret sharing */ - void getMasterSecretKey(SecretKeyVec& msk, int k) const; + void getMasterSecretKey(SecretKeyVec& msk, size_t k) const; /* set a secret key for id > 0 from msk */ @@ -149,7 +150,6 @@ public: bool operator!=(const PublicKey& rhs) const { return !(*this == rhs); } friend std::ostream& operator<<(std::ostream& os, const PublicKey& pub); friend std::istream& operator>>(std::istream& is, PublicKey& pub); - void getStr(std::string& str) const; /* set public for id from mpk */ diff --git a/src/bls.cpp b/src/bls.cpp index c0add0b..096fe36 100644 --- a/src/bls.cpp +++ b/src/bls.cpp @@ -23,7 +23,6 @@ struct FrTag; typedef mcl::FpT Fr; typedef std::vector FrVec; - #define PUT(x) std::cout << #x << "=" << x << std::endl; static cybozu::RandomGenerator& getRG() @@ -57,6 +56,7 @@ static void mapToG1(G1& P, const Fp& t) static mcl::bn::MapTo mapTo; mapTo.calcG1(P, t); } + static void HashAndMapToG1(G1& P, const std::string& m) { std::string digest = cybozu::crypto::Hash::digest(cybozu::crypto::Hash::N_SHA256, m); @@ -106,98 +106,66 @@ struct Polynomial { } }; -/* - delta_{i,S}(0) = prod_{j != i} S[j] / (S[j] - S[i]) = a / b - where a = prod S[j], b = S[i] * prod_{j != i} (S[j] - S[i]) -*/ -static void calcDelta(FrVec& delta, const FrVec& S) -{ - const size_t k = S.size(); - if (k < 2) throw cybozu::Exception("bls:calcDelta:bad size") << k; - delta.resize(k); - Fr a = S[0]; - for (size_t i = 1; i < k; i++) { - a *= S[i]; - } - for (size_t i = 0; i < k; i++) { - Fr b = S[i]; - for (size_t j = 0; j < k; j++) { - if (j != i) { - Fr v = S[j] - S[i]; - if (v.isZero()) throw cybozu::Exception("bls:calcDelta:S has same id") << i << j; - b *= v; - } - } - delta[i] = a / b; - } -} - namespace impl { struct Id { Fr v; }; +struct SecretKey { + Fr s; + const Fr& get() const { return s; } +}; + struct Sign { G1 sHm; // s Hash(m) const G1& get() const { return sHm; } - bool verify(const PublicKey& pub, const std::string& m) const; }; struct PublicKey { G2 sQ; - void init(const Fr& s) - { - G2::mul(sQ, getQ(), s); - } const G2& get() const { return sQ; } -}; - -inline bool Sign::verify(const PublicKey& pub, const std::string& m) const -{ - G1 Hm; - HashAndMapToG1(Hm, m); // Hm = Hash(m) - Fp12 e1, e2; - BN::pairing(e1, getQ(), sHm); // e(Q, s Hm) - BN::pairing(e2, pub.sQ, Hm); // e(sQ, Hm) - return e1 == e2; -} - -struct SecretKey { - Fr s; - const Fr& get() const { return s; } - void set(const uint64_t *p) + void getStr(std::string& str) const { - s.setArray(p, keySize); - } - void init() - { - s.setRand(getRG()); - } - void getPublicKey(PublicKey& pub) const - { - pub.init(s); - } - void sign(Sign& sign, const std::string& m) const - { - G1 Hm; - HashAndMapToG1(Hm, m); - G1::mul(sign.sHm, Hm, s); + sQ.getStr(str, mcl::IoArrayRaw); } }; } // mcl::bls::impl +/* + recover f(0) by { (x, y) | x = S[i], y = f(x) = vec[i] } +*/ template -void LagrangeInterpolation(G& r, const T& vec, const IdVec& idVec) +void LagrangeInterpolation(G& r, const T& vec, const IdVec& S) { - FrVec S(idVec.size()); - for (size_t i = 0; i < vec.size(); i++) { - S[i] = idVec[i].self_->v; + /* + delta_{i,S}(0) = prod_{j != i} S[j] / (S[j] - S[i]) = a / b + where a = prod S[j], b = S[i] * prod_{j != i} (S[j] - S[i]) + */ + const size_t k = S.size(); + if (vec.size() != k) throw cybozu::Exception("bls:LagrangeInterpolation:bad size") << vec.size() << k; + if (k < 2) throw cybozu::Exception("bls:LagrangeInterpolation:too small size") << k; + FrVec delta(k); + Fr a = S[0].self_->v; + for (size_t i = 1; i < k; i++) { + a *= S[i].self_->v; + } + for (size_t i = 0; i < k; i++) { + Fr b = S[i].self_->v; + for (size_t j = 0; j < k; j++) { + if (j != i) { + Fr v = S[j].self_->v - S[i].self_->v; + if (v.isZero()) throw cybozu::Exception("bls:LagrangeInterpolation:S has same id") << i << j; + b *= v; + } + } + delta[i] = a / b; } - FrVec delta; - calcDelta(delta, S); + /* + f(0) = sum_i f(S[i]) delta_{i,S}(0) + */ r.clear(); G t; for (size_t i = 0; i < delta.size(); i++) { @@ -206,7 +174,6 @@ void LagrangeInterpolation(G& r, const T& vec, const IdVec& idVec) } } - Id::Id(unsigned int id) : self_(new impl::Id()) { @@ -292,20 +259,24 @@ std::istream& operator>>(std::istream& os, Sign& s) bool Sign::verify(const PublicKey& pub, const std::string& m) const { - return self_->verify(*pub.self_, m); + G1 Hm; + HashAndMapToG1(Hm, m); // Hm = Hash(m) + Fp12 e1, e2; + BN::pairing(e1, getQ(), self_->sHm); // e(Q, s Hm) + BN::pairing(e2, pub.self_->sQ, Hm); // e(sQ, Hm) + return e1 == e2; } + bool Sign::verify(const PublicKey& pub) const { std::string str; - pub.getStr(str); + pub.self_->getStr(str); return verify(pub, str); } + void Sign::recover(const SignVec& signVec, const IdVec& idVec) { - if (signVec.size() != idVec.size()) throw cybozu::Exception("Sign:recover:bad size") << signVec.size() << idVec.size(); - G1 sHm; - LagrangeInterpolation(sHm, signVec, idVec); - self_->sHm = sHm; + LagrangeInterpolation(self_->sHm, signVec, idVec); } void Sign::add(const Sign& rhs) @@ -349,13 +320,6 @@ std::istream& operator>>(std::istream& is, PublicKey& pub) return is >> pub.self_->sQ; } -void PublicKey::getStr(std::string& str) const -{ - std::ostringstream os; - os << *this; - str = os.str(); -} - void PublicKey::set(const PublicKeyVec& mpk, const Id& id) { Wrap w(mpk); @@ -364,10 +328,7 @@ void PublicKey::set(const PublicKeyVec& mpk, const Id& id) void PublicKey::recover(const PublicKeyVec& pubVec, const IdVec& idVec) { - G2 sQ; - if (pubVec.size() != idVec.size()) throw cybozu::Exception("PublicKey:recover:bad size") << pubVec.size() << idVec.size(); - LagrangeInterpolation(sQ, pubVec, idVec); - self_->sQ = sQ; + LagrangeInterpolation(self_->sQ, pubVec, idVec); } void PublicKey::add(const PublicKey& rhs) @@ -413,22 +374,24 @@ std::istream& operator>>(std::istream& is, SecretKey& sec) void SecretKey::init() { - self_->init(); + self_->s.setRand(getRG()); } void SecretKey::set(const uint64_t *p) { - self_->set(p); + self_->s.setArray(p, keySize); } void SecretKey::getPublicKey(PublicKey& pub) const { - self_->getPublicKey(*pub.self_); + G2::mul(pub.self_->sQ, getQ(), self_->s); } void SecretKey::sign(Sign& sign, const std::string& m) const { - self_->sign(*sign.self_, m); + G1 Hm; + HashAndMapToG1(Hm, m); + G1::mul(sign.self_->sHm, Hm, self_->s); } void SecretKey::getPop(Sign& pop) const @@ -436,16 +399,16 @@ void SecretKey::getPop(Sign& pop) const PublicKey pub; getPublicKey(pub); std::string m; - pub.getStr(m); + pub.self_->getStr(m); sign(pop, m); } -void SecretKey::getMasterSecretKey(SecretKeyVec& msk, int k) const +void SecretKey::getMasterSecretKey(SecretKeyVec& msk, size_t k) const { if (k <= 1) throw cybozu::Exception("bls:SecretKey:getMasterSecretKey:bad k") << k; msk.resize(k); msk[0] = *this; - for (int i = 1; i < k; i++) { + for (size_t i = 1; i < k; i++) { msk[i].init(); } } @@ -458,10 +421,7 @@ void SecretKey::set(const SecretKeyVec& msk, const Id& id) void SecretKey::recover(const SecretKeyVec& secVec, const IdVec& idVec) { - Fr s; - if (secVec.size() != idVec.size()) throw cybozu::Exception("SecretKey:recover:bad size") << secVec.size() << idVec.size(); - LagrangeInterpolation(s, secVec, idVec); - self_->s = s; + LagrangeInterpolation(self_->s, secVec, idVec); } void SecretKey::add(const SecretKey& rhs) diff --git a/test/bls_test.cpp b/test/bls_test.cpp index 59cad31..ed63f96 100644 --- a/test/bls_test.cpp +++ b/test/bls_test.cpp @@ -211,8 +211,8 @@ CYBOZU_TEST_AUTO(k_of_n) CYBOZU_TEST_AUTO(pop) { - const int k = 3; - const int n = 6; + const size_t k = 3; + const size_t n = 6; const std::string m = "pop test"; bls::SecretKey sec0; sec0.init(); @@ -240,7 +240,7 @@ CYBOZU_TEST_AUTO(pop) bls::SecretKeyVec secVec(n); bls::PublicKeyVec pubVec(n); bls::SignVec sVec(n); - for (int i = 0; i < n; i++) { + for (size_t i = 0; i < n; i++) { int id = idTbl[i]; secVec[i].set(msk, id); secVec[i].getPublicKey(pubVec[i]); @@ -258,7 +258,7 @@ CYBOZU_TEST_AUTO(pop) secVec.resize(k); sVec.resize(k); bls::IdVec idVec(k); - for (int i = 0; i < k; i++) { + for (size_t i = 0; i < k; i++) { idVec[i] = idTbl[i]; } bls::SecretKey sec; -- cgit v1.2.3