Part1背景

BLS签名中需要对群元素进行操作，但在现实中我们要签名的消息一般都是比特流，于是我们需要一种将任意比特串映射为群元素的方法。一般需要分两步进行：

1. 利用密码学哈希函数（比如blake2b）将消息缩减为固定长度（比如256比特）的消息摘要。
2. 使用hash-to-curve技术将该消息摘要映射到一个群元素（通常是椭圆曲线群中的元素即一个椭圆曲线点）。

1Pedersen哈希

Pedersen哈希是其中一种hash-to-curve技术。

输入消息摘要，Pedersen哈希输出为。

其中是个群元素。假设给定其中任意一个群元素，都不能找到该群元素以另外任意一个群元素为底的离散对数。即对任意 ，找不到使得。

Part2分析

2挑战内容

见该Github仓库：https://github.com/kobigurk/zkhack-bls-pedersen

题目给出公钥pk，256个消息 ，以及这些消息在pk对应的未知私钥下的BLS签名。要求基于上述输入，给出任意新消息的合法签名。也就说明该BLS签名的具体实现不满足签名的存在不可伪造安全定义。

其中是任意选择的群元素，见如下代码：

let rng_pedersen = &mut ChaCha20Rng::from_seed([

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

]);
let parameters = CRH::<G1Projective, ZkHackPedersenWindow>::setup(rng_pedersen).unwrap();

3记号

记消息的blake2s输出为，其中的第比特为。

于是的Pedersen哈希为

也可以写为列向量。

对于两个消息，我们有：

定义标量乘法：

4解法

生成伪造BLS签名

对于想要伪造签名的消息，计算其消息摘要为，如果能找到常数满足：

即对于所有：

则我们可以通过如下计算得到所需伪造签名：

原理

• 首先，BLS签名（对群元素）是线性的，即签名两个群元素的和等于对两个群元素分别签名后签名求和。

• 其次，Pedersen哈希也是线性的，对于两个消息摘要应用Pedersen哈希再求和等于对两个消息摘要求和的Pederson哈希：

于是有：

计算

向量方程可以用矩阵向量乘法写成线性方程组的形式：

其中：

于是解为：

Part3代码

5输入预处理

首先使用下列函数得到现有消息的blake2s哈希：

fn bytes_to_bits_string(bytes: &[u8]) -> String {
      let bits = bytes_to_bits(bytes);
      let mut s = String::with_capacity(bits.len());
      for bit in bits {
          if bit {
              s.push('1');
          } else {
              s.push('0');
          }
      }
      return s;
  }

fn write_msgs_to_file(msgs: Vec) {
      let mut file = File::create(format!(
          "bits_vecs-{}",
          (SystemTime::now().duration_since(UNIX_EPOCH))
              .unwrap()
              .as_millis()
      ))
      .unwrap();
      for msg in msgs {
          let blake = hash_to_curve(&msg).0;
          let string = bytes_to_bits_string(&blake);
          file.write_all(string.as_ref()).unwrap();
          file.write_all(b"\n").unwrap();
      }
  }

6使用Sage进行代数处理

A = list()
with open("bits_vecs-1635288647752", 'r') as f:
 for line_index, line in enumerate(f):
  A.append(list())
  for bit_index in range(0, 256):
   A[line_index].append(int(line[bit_index]))

# 定义`BLS12-381`椭圆曲线群的阶
P = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
F = FiniteField(P)

GA = Matrix(F, A)
GAT = GA.transpose()
GAinv = GAT.inverse()

# blake2s of your msg
bitstring = '0111011010010000...'
bits = [int(el) for el in bitstring]
gbits = vector(F, bits)
gsolution = GAinv * gbits
# Print the generator multipliers.
",".join(['Fq::from_str("'+str(el)+'").unwrap()' for el in gsolution])

7输出伪造签名

每个:

let selectors = [
      Fr::from_str(
          "27645015623588109382996024038763530282647599513403648261518408122004451823795",
      )
      .unwrap(),
      Fr::from_str(
          "23018579491472099737921523253639007115479688088731410213980168199642094036630",
      )
  ....
  ....
  ....
      .unwrap(),
      Fr::from_str(
        "6769691326408305518047502379958157439957827386631887324632648911856770263560",
      )
      .unwrap(),
  ];

let mut sum = G1Projective::zero();
for (i, num) in selectors.iter().enumerate() {
 let additive = sigs[i].into_projective().mul(num);
      sum += additive;
}
let affine = G1Affine::from(sum);  

验证伪造成功：

verify(pk, msg, affine.clone());