From df0418098fd5a9f34148e1cb353e1b6e42db9708 Mon Sep 17 00:00:00 2001 From: MITSUNARI Shigeo Date: Wed, 10 Aug 2016 09:33:54 +0900 Subject: first commit --- Makefile | 58 ++++++++ include/bls.hpp | 101 ++++++++++++++ readme.md | 31 +++++ src/bls.cpp | 395 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ test/bls_test.cpp | 154 +++++++++++++++++++++ 5 files changed, 739 insertions(+) create mode 100644 Makefile create mode 100644 include/bls.hpp create mode 100644 readme.md create mode 100644 src/bls.cpp create mode 100644 test/bls_test.cpp diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..3e023e0 --- /dev/null +++ b/Makefile @@ -0,0 +1,58 @@ +include ../mcl/common.mk +LIB_DIR=lib +OBJ_DIR=obj +EXE_DIR=bin + +SRC_SRC=bls.cpp +TEST_SRC=bls_test.cpp +#SAMPLE_SRC= + +CFLAGS+=-I../mcl/include +################################################################## +BLS_LIB=$(LIB_DIR)/libbls.a +all: $(BLS_LIB) + +LIB_OBJ=$(OBJ_DIR)/bls.o + +$(BLS_LIB): $(LIB_OBJ) + -$(MKDIR) $(@D) + $(AR) $@ $(LIB_OBJ) + +MCL_LIB=../mcl/lib/libmcl.a + +$(MCL_LIB): + $(MAKE) -C ../mcl + +################################################################## + +VPATH=test sample src + +.SUFFIXES: .cpp .d .exe + +$(OBJ_DIR)/%.o: %.cpp + -$(MKDIR) $(@D) + $(PRE)$(CXX) $(CFLAGS) -c $< -o $@ -MMD -MP -MF $(@:.o=.d) + +$(EXE_DIR)/%.exe: $(OBJ_DIR)/%.o $(BLS_LIB) $(MCL_LIB) + -$(MKDIR) $(@D) + $(PRE)$(CXX) $< -o $@ $(BLS_LIB) $(LDFLAGS) -lmcl -L../mcl/lib + +SAMPLE_EXE=$(addprefix $(EXE_DIR)/,$(SAMPLE_SRC:.cpp=.exe)) +sample: $(SAMPLE_EXE) $(BLS_LIB) + +TEST_EXE=$(addprefix $(EXE_DIR)/,$(TEST_SRC:.cpp=.exe)) +test: $(TEST_EXE) + @echo test $(TEST_EXE) + @sh -ec 'for i in $(TEST_EXE); do $$i|grep "ctest:name"; done' > result.txt + @grep -v "ng=0, exception=0" result.txt || echo "all unit tests are ok" + +clean: + $(RM) $(BLS_LIB) $(OBJ_DIR)/* $(EXE_DIR)/*.exe $(GEN_EXE) $(ASM_SRC) $(ASM_OBJ) $(LIB_OBJ) $(LLVM_SRC) + +ALL_SRC=$(SRC_SRC) $(TEST_SRC) $(SAMPLE_SRC) +DEPEND_FILE=$(addprefix $(OBJ_DIR)/, $(ALL_SRC:.cpp=.d)) +-include $(DEPEND_FILE) + +# don't remove these files automatically +.SECONDARY: $(addprefix $(OBJ_DIR)/, $(ALL_SRC:.cpp=.o)) + diff --git a/include/bls.hpp b/include/bls.hpp new file mode 100644 index 0000000..5288da0 --- /dev/null +++ b/include/bls.hpp @@ -0,0 +1,101 @@ +#pragma once +/** + @file + @brief BLS threshold signature on BN curve + @author MITSUNARI Shigeo(@herumi) + @license modified new BSD license + http://opensource.org/licenses/BSD-3-Clause +*/ +#include +#include +#include + +namespace bls { + +namespace impl { + +struct PublicKey; +struct PrivateKey; +struct Sign; + +} // bls::impl + +void init(); + +class Sign { +public: + impl::Sign *self_; + int id_; + friend class PublicKey; + friend class PrivateKey; + template + friend void LagrangeIntepolation(G& r, const T& vec); +public: + Sign(); + ~Sign(); + Sign(const Sign& rhs); + Sign& operator=(const Sign& rhs); + void setStr(const std::string& str); + void getStr(std::string& str) const; + bool operator==(const Sign& rhs) const; + bool operator!=(const Sign& rhs) const { return !(*this == rhs); } + int getId() const { return id_; } + friend std::ostream& operator<<(std::ostream& os, const Sign& s); + friend std::istream& operator>>(std::istream& is, Sign& s); + + /* + recover sign from k signVec + */ + void recover(const std::vector& signVec); +}; + +class PublicKey { + impl::PublicKey *self_; + int id_; + friend class PrivateKey; +public: + PublicKey(); + ~PublicKey(); + PublicKey(const PublicKey& rhs); + PublicKey& operator=(const PublicKey& rhs); + void setStr(const std::string& str); + void getStr(std::string& str) const; + bool operator==(const PublicKey& rhs) const; + bool operator!=(const PublicKey& rhs) const { return !(*this == rhs); } + int getId() const { return id_; } + friend std::ostream& operator<<(std::ostream& os, const PublicKey& pub); + friend std::istream& operator>>(std::istream& is, PublicKey& pub); + bool verify(const Sign& sign, const std::string& m) const; +}; + +class PrivateKey { + impl::PrivateKey *self_; + int id_; // master if id_ = 0, shared if id_ > 0 + template + friend void LagrangeIntepolation(G& r, const T& vec); +public: + PrivateKey(); + ~PrivateKey(); + PrivateKey(const PrivateKey& rhs); + PrivateKey& operator=(const PrivateKey& rhs); + void setStr(const std::string& str); + void getStr(std::string& str) const; + bool operator==(const PrivateKey& rhs) const; + bool operator!=(const PrivateKey& rhs) const { return !(*this == rhs); } + int getId() const { return id_; } + friend std::ostream& operator<<(std::ostream& os, const PrivateKey& prv); + friend std::istream& operator>>(std::istream& is, PrivateKey& prv); + void init(); + void getPublicKey(PublicKey& pub) const; + void sign(Sign& sign, const std::string& m) const; + /* + k-out-of-n secret sharing of privateKey + */ + void share(std::vector& prvVec, int n, int k); + /* + recover privateKey from k prvVec + */ + void recover(const std::vector& prvVec); +}; + +} // bls diff --git a/readme.md b/readme.md new file mode 100644 index 0000000..59ec541 --- /dev/null +++ b/readme.md @@ -0,0 +1,31 @@ +# BLS threshold signature + +An implementation of BLS threshold signature + +# Installation Requirements + +Create a working directory (e.g., work) and clone the following repositories. +``` +mkdir work +cd work +git clone git://github.com/herumi/xbyak.git +git clone git://github.com/herumi/cybozulib.git +git clone git://github.com/herumi/mcl.git +git clone git://github.com/herumi/bls.git +``` + +# Build and test +To make lib/libbls.a and test, run +``` +cd bls +make test +``` + +# License + +modified new BSD License +http://opensource.org/licenses/BSD-3-Clause + +# Author + +MITSUNARI Shigeo(herumi@nifty.com) diff --git a/src/bls.cpp b/src/bls.cpp new file mode 100644 index 0000000..2d6598d --- /dev/null +++ b/src/bls.cpp @@ -0,0 +1,395 @@ +/** + @file + @author MITSUNARI Shigeo(@herumi) + @license modified new BSD license + http://opensource.org/licenses/BSD-3-Clause +*/ +#include +#include +#include +#include +#include +#include + +typedef mcl::FpT Fp; +typedef mcl::bn::BNT BN; +typedef BN::Fp2 Fp2; +typedef BN::Fp6 Fp6; +typedef BN::Fp12 Fp12; +typedef BN::G1 G1; +typedef BN::G2 G2; +typedef std::vector IntVec; + +struct FrTag; +typedef mcl::FpT Fr; +typedef std::vector FrVec; + + +#define PUT(x) std::cout << #x << "=" << x << std::endl; + +static cybozu::RandomGenerator& getRG() +{ + static cybozu::RandomGenerator rg; + return rg; +} + +namespace bls { + +void init() +{ + BN::init(mcl::bn::CurveFp254BNb); + G1::setCompressedExpression(); +// G2::setCompressedExpression(); + Fr::init(BN::param.r.get_str()); +} + +static const G2& getQ() +{ + static const G2 Q( + Fp2("12723517038133731887338407189719511622662176727675373276651903807414909099441", "4168783608814932154536427934509895782246573715297911553964171371032945126671"), + Fp2("13891744915211034074451795021214165905772212241412891944830863846330766296736", "7937318970632701341203597196594272556916396164729705624521405069090520231616") + ); + return Q; +} + +static void hash(Fp& t, const std::string& m) +{ + std::string digest = cybozu::crypto::Hash::digest(cybozu::crypto::Hash::N_SHA256, m); + t.setArrayMask(digest.c_str(), digest.size()); +} + +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) +{ + Fp t; + hash(t, m); + mapToG1(P, t); +} + +struct Polynomial { + FrVec c; // f[x] = sum_{i=0}^{k-1} c[i] x^i + void init(const Fr& s, int k) + { + if (k < 2) throw cybozu::Exception("Polynomial:init:bad k") << k; + c.resize(k); + c[0] = s; + for (size_t i = 1; i < c.size(); i++) { + c[i].setRand(getRG()); + } + } + // y = f(id) + void eval(Fr& y, int id) const + { + if (id == 0) throw cybozu::Exception("Polynomial:calc_f:i is zero"); + if (c.size() < 2) throw cybozu::Exception("Polynomial:calc_f:bad size") << c.size(); + const Fr x(id); + y = c[c.size() - 1]; + for (int i = (int)c.size() - 2; i >= 0; i--) { + y *= x; + y += c[i]; + } + } +}; + +/* + 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 IntVec& 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) { + int v = S[j] - S[i]; + if (v == 0) throw cybozu::Exception("bls:calcDelta:S has same id") << i << j; + b *= v; + } + } + delta[i] = a / b; + } +} + +template +void LagrangeIntepolation(G& r, const T& vec) +{ + IntVec S(vec.size()); + for (size_t i = 0; i < vec.size(); i++) { + S[i] = vec[i].getId(); + } + FrVec delta; + calcDelta(delta, S); + + r.clear(); + G t; + for (size_t i = 0; i < delta.size(); i++) { + G::mul(t, vec[i].self_->get(), delta[i]); + r += t; + } +} + +namespace impl { + +struct Sign { + G1 sHm; // s Hash(m) + const G1& get() const { return sHm; } +}; + +struct PublicKey { + G2 sQ; + void init(const Fr& s) + { + G2::mul(sQ, getQ(), s); + } + bool verify(const Sign& sign, const std::string& m) const + { + G1 Hm; + HashAndMapToG1(Hm, m); // Hm = Hash(m) + Fp12 e1, e2; + BN::pairing(e1, getQ(), sign.sHm); // e(Q, s Hm) + BN::pairing(e2, sQ, Hm); // e(sQ, Hm) + return e1 == e2; + } +}; + +struct PrivateKey { + Fr s; + const Fr& get() const { return s; } + 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); + } +}; + +} // mcl::bls::impl + +Sign::Sign() + : self_(new impl::Sign()) + , id_(0) +{ +} + +Sign::~Sign() +{ + delete self_; +} + +Sign::Sign(const Sign& rhs) + : self_(new impl::Sign(*rhs.self_)) + , id_(rhs.id_) +{ +} + +Sign& Sign::operator=(const Sign& rhs) +{ + *self_ = *rhs.self_; + id_ = rhs.id_; + return *this; +} + +void Sign::setStr(const std::string& str) +{ + std::istringstream iss(str); + iss >> *this; +} + +void Sign::getStr(std::string& str) const +{ + std::ostringstream oss(str); + oss << *this; + str = oss.str(); +} + +bool Sign::operator==(const Sign& rhs) const +{ + return id_ == rhs.id_ && self_->sHm == rhs.self_->sHm; +} + +std::ostream& operator<<(std::ostream& os, const Sign& s) +{ + return os << s.id_ << ' ' << s.self_->sHm; +} + +std::istream& operator>>(std::istream& os, Sign& s) +{ + return os >> s.id_ >> s.self_->sHm; +} + +void Sign::recover(const std::vector& signVec) +{ + G1 sHm; + LagrangeIntepolation(sHm, signVec); + self_->sHm = sHm; + id_ = 0; +} + +PublicKey::PublicKey() + : self_(new impl::PublicKey()) + , id_(0) +{ +} + +PublicKey::~PublicKey() +{ + delete self_; +} + +PublicKey::PublicKey(const PublicKey& rhs) + : self_(new impl::PublicKey(*rhs.self_)) + , id_(rhs.id_) +{ +} + +PublicKey& PublicKey::operator=(const PublicKey& rhs) +{ + *self_ = *rhs.self_; + id_ = rhs.id_; + return *this; +} + +void PublicKey::setStr(const std::string& str) +{ + std::istringstream iss(str); + iss >> *this; +} + +void PublicKey::getStr(std::string& str) const +{ + std::ostringstream oss(str); + oss << *this; + str = oss.str(); +} + +bool PublicKey::operator==(const PublicKey& rhs) const +{ + return id_ == rhs.id_ && self_->sQ == rhs.self_->sQ; +} + +std::ostream& operator<<(std::ostream& os, const PublicKey& pub) +{ + return os << pub.id_ << ' ' << pub.self_->sQ; +} + +std::istream& operator>>(std::istream& is, PublicKey& pub) +{ + return is >> pub.id_ >> pub.self_->sQ; +} + +bool PublicKey::verify(const Sign& sign, const std::string& m) const +{ + return self_->verify(*sign.self_, m); +} + +PrivateKey::PrivateKey() + : self_(new impl::PrivateKey()) + , id_(0) +{ +} + +PrivateKey::~PrivateKey() +{ + delete self_; +} + +PrivateKey::PrivateKey(const PrivateKey& rhs) + : self_(new impl::PrivateKey(*rhs.self_)) + , id_(rhs.id_) +{ +} + +PrivateKey& PrivateKey::operator=(const PrivateKey& rhs) +{ + *self_ = *rhs.self_; + id_ = rhs.id_; + return *this; +} + +void PrivateKey::setStr(const std::string& str) +{ + std::istringstream iss(str); + iss >> *this; +} + +void PrivateKey::getStr(std::string& str) const +{ + std::ostringstream oss(str); + oss << *this; + str = oss.str(); +} + +bool PrivateKey::operator==(const PrivateKey& rhs) const +{ + return id_ == rhs.id_ && self_->s == rhs.self_->s; +} + +void PrivateKey::init() +{ + self_->init(); +} + +void PrivateKey::getPublicKey(PublicKey& pub) const +{ + self_->getPublicKey(*pub.self_); + pub.id_ = id_; +} + +std::ostream& operator<<(std::ostream& os, const PrivateKey& prv) +{ + return os << prv.id_ << ' ' << prv.self_->s; +} + +std::istream& operator>>(std::istream& is, PrivateKey& prv) +{ + return is >> prv.id_ >> prv.self_->s; +} + +void PrivateKey::sign(Sign& sign, const std::string& m) const +{ + self_->sign(*sign.self_, m); + sign.id_ = id_; +} + +void PrivateKey::share(std::vector& prvVec, int n, int k) +{ + if (id_ != 0) throw cybozu::Exception("bls:PrivateKey:share:already shared") << id_; + Polynomial poly; + poly.init(self_->s, k); + prvVec.resize(n); + for (int i = 0; i < n; i++) { + int id = i + 1; + poly.eval(prvVec[i].self_->s, id); + prvVec[i].id_ = id; + } +} + +void PrivateKey::recover(const std::vector& prvVec) +{ + Fr s; + LagrangeIntepolation(s, prvVec); + self_->s = s; + id_ = 0; +} + +} // bls diff --git a/test/bls_test.cpp b/test/bls_test.cpp new file mode 100644 index 0000000..1dd3b65 --- /dev/null +++ b/test/bls_test.cpp @@ -0,0 +1,154 @@ +#include +#include +#include + +CYBOZU_TEST_AUTO(bls) +{ + bls::init(); + bls::PrivateKey prv; + prv.init(); + { + std::string str; + prv.getStr(str); + bls::PrivateKey prv2; + prv2.setStr(str); + CYBOZU_TEST_EQUAL(prv, prv2); + } + bls::PublicKey pub; + prv.getPublicKey(pub); + { + std::string str; + pub.getStr(str); + bls::PublicKey pub2; + pub2.setStr(str); + CYBOZU_TEST_EQUAL(pub, pub2); + } + for (int i = 0; i < 5; i++) { + std::string m = "hello"; + m += char('0' + i); + bls::Sign s; + prv.sign(s, m); + CYBOZU_TEST_ASSERT(pub.verify(s, m)); + CYBOZU_TEST_ASSERT(!pub.verify(s, m + "a")); + { + std::string str; + s.getStr(str); + bls::Sign s2; + s2.setStr(str); + CYBOZU_TEST_EQUAL(s, s2); + } + } +} + +CYBOZU_TEST_AUTO(k_of_n) +{ + bls::init(); + const std::string m = "abc"; + const int n = 5; + const int k = 3; + bls::PrivateKey prv0; + prv0.init(); + bls::Sign s0; + prv0.sign(s0, m); + bls::PublicKey pub0; + prv0.getPublicKey(pub0); + CYBOZU_TEST_ASSERT(pub0.verify(s0, m)); + + std::vector allPrvVec; + prv0.share(allPrvVec, n, k); + CYBOZU_TEST_EQUAL(allPrvVec.size(), n); + for (int i = 0; i < n; i++) { + CYBOZU_TEST_EQUAL(allPrvVec[i].getId(), i + 1); + } + + std::vector allSignVec(n); + for (int i = 0; i < n; i++) { + CYBOZU_TEST_ASSERT(allPrvVec[i] != prv0); + allPrvVec[i].sign(allSignVec[i], m); + bls::PublicKey pub; + allPrvVec[i].getPublicKey(pub); + CYBOZU_TEST_ASSERT(pub != pub0); + CYBOZU_TEST_ASSERT(pub.verify(allSignVec[i], m)); + } + + /* + 3-out-of-n + can recover + */ + std::vector prvVec(3); + for (int a = 0; a < n; a++) { + prvVec[0] = allPrvVec[a]; + for (int b = a + 1; b < n; b++) { + prvVec[1] = allPrvVec[b]; + for (int c = b + 1; c < n; c++) { + prvVec[2] = allPrvVec[c]; + bls::PrivateKey prv; + prv.recover(prvVec); + CYBOZU_TEST_EQUAL(prv, prv0); + } + } + } + { + /* + n-out-of-n + can recover + */ + bls::PrivateKey prv; + prv.recover(allPrvVec); + CYBOZU_TEST_EQUAL(prv, prv0); + } + /* + 2-out-of-n + can't recover + */ + prvVec.resize(2); + for (int a = 0; a < n; a++) { + prvVec[0] = allPrvVec[a]; + for (int b = a + 1; b < n; b++) { + prvVec[1] = allPrvVec[b]; + bls::PrivateKey prv; + prv.recover(prvVec); + CYBOZU_TEST_ASSERT(prv != prv0); + } + } + /* + 3-out-of-n + can recover + */ + std::vector signVec(3); + for (int a = 0; a < n; a++) { + signVec[0] = allSignVec[a]; + for (int b = a + 1; b < n; b++) { + signVec[1] = allSignVec[b]; + for (int c = b + 1; c < n; c++) { + signVec[2] = allSignVec[c]; + bls::Sign s; + s.recover(signVec); + CYBOZU_TEST_EQUAL(s, s0); + } + } + } + { + /* + n-out-of-n + can recover + */ + bls::Sign s; + s.recover(allSignVec); + CYBOZU_TEST_EQUAL(s, s0); + } + /* + 2-out-of-n + can't recover + */ + signVec.resize(2); + for (int a = 0; a < n; a++) { + signVec[0] = allSignVec[a]; + for (int b = a + 1; b < n; b++) { + signVec[1] = allSignVec[b]; + bls::Sign s; + s.recover(signVec); + CYBOZU_TEST_ASSERT(s != s0); + } + } +} -- cgit v1.2.3