签名算法
# 加密模块总览
# 体系与算法
非对称加密体系
- RSA 体系:基于大数分解的非对称加密体系
- ElGamal 体系:基于离散对数问题的非对称加密体系
- Rabin 体系:基于平方剩余难题的公钥加密体系(特征为多解)
- ECC 体系:通过椭圆曲线构造的公钥加密体系
体系并不等于算法,RSA 体系代指的是基于大数分解的非对称加密体系,为什么叫 RSA 体系只是因为 RSA 算法是第一个属于这种体系的算法,沿用了名称罢了
- 容易让人混淆的点在于,ElGamal 算法既可以在 ElGamal 体系下实现,也可以在 ECC 体系下实现,因为体系是数学特征,算法是具体方案
例如
- 密钥交换协议:Diffie-Hellman(D-H),用于安全协商密钥,是一种协议,其实现类似于算法,也可以在多个体系中实现
- 门限密码:Shamir 门限方案,用于将秘密拆分成多个部分,满足门限才能恢复
用表来看或许清晰一点,不同的算法有其适用的密码体系,在“适用”的前提下,可以在不同密码体系中具体应用
| 算法 | 主要数学难题 | 典型适用体系 |
|---|---|---|
| RSA | 大数分解(Factoring) | RSA 体系 |
| Rabin | 二次剩余(Quadratic Residue) | Rabin 体系 |
| ElGamal | 离散对数(DLP) | 传统 ElGamal、ECC |
但注意
- RSA 和 Rabin 是基于大数分解问题的,属于数论体系(通常不和 ECC 结合)
- ElGamal 和 D-H 是基于离散对数问题的,它们既可以在整数域也可以在椭圆曲线上实现
# 接口与抽象类
Auth 接口
public interface Auth {
default KeyPair keygen(){
throw new UnsupportedOperationException("Key Generation Is Not Supported");
}
default CryptoMap sign(String message, CryptoMap sk){
throw new UnsupportedOperationException("Sign Is Not Supported");
}
default CryptoMap sanitize(String message, CryptoMap sk, CryptoMap signature){
throw new UnsupportedOperationException("Sanitize Is Not Supported");
}
default Boolean verify(String message, CryptoMap pk, CryptoMap signature){
throw new UnsupportedOperationException("Verify Is Not Supported");
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
CipherSystem 抽象类,实现 Auth 接口,这里提供了 updateable 和 sanitizable 的选项,供之后密钥更新和签名净化扩展
@Getter
@Setter
@Data
public abstract class CipherSystem implements Auth {
Pairing BP;
Field G1, G2, GT, Zr;
Boolean sanitizable, updatable;
public CipherSystem(Pairing BP, Field G1, Field G2, Field GT, Field Zr, Boolean sanitizable, Boolean updatable){
this.BP = BP;
this.G1 = G1;
this.G2 = G2;
this.GT = GT;
this.Zr = Zr;
this.sanitizable = sanitizable;
this.updatable = updatable;
}
public Element randomZ(){
return Zr.newRandomElement().getImmutable();
}
public Element getI(String i){
BigInteger bi = new BigInteger(i);
return Zr.newElement(bi).getImmutable();
}
public Element randomG1(){
return G1.newRandomElement().getImmutable();
}
public Element randomG2(){
return G2.newRandomElement().getImmutable();
}
public Element randomGT(){
return GT.newRandomElement().getImmutable();
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# 配置类
CryptoConfig:注入 Bean
@Configuration
public class CryptoConfig {
@Bean
public Pairing pairing() {
return PairingFactory.getPairing("a.properties");
}
@Bean
public Field G1(Pairing pairing) {
return pairing.getG1();
}
@Bean
public Field G2(Pairing pairing) {
return pairing.getG2();
}
@Bean
public Field GT(Pairing pairing) {
return pairing.getGT();
}
@Bean
public Field Zr(Pairing pairing) {
return pairing.getZr();
}
@Bean
public SchnorrRFID schnorrRFID(Pairing pairing, Field G1, Field G2, Field GT, Field Zr) {
int length = 10; // 可替换为配置参数
boolean sanitizable = false; // 同上
boolean updatable = false;
return new SchnorrRFID(pairing, G1, G2, GT, Zr, sanitizable, updatable, length);
}
@Bean
public RSA rsa(Field Zr) {
boolean sanitizable = false;
boolean updatable = false;
return new RSA(Zr, sanitizable, updatable);
}
@Bean
public Schnorr schnorr(Pairing pairing, Field G1, Field G2, Field GT, Field Zr){
boolean sanitizable = false;
boolean updatable = false;
return new Schnorr(pairing, G1, G2, GT, Zr, sanitizable, updatable);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
# 数据结构
数据表设计设想是用一个表来存所有密钥、签名等信息,表设计如下
crypto_data
| 字段名 | 类型 | 描述 |
|---|---|---|
| id | BIGINT/UUID | 主键 |
| user_id | VARCHAR | 所属用户(如有) |
| algo | VARCHAR | 算法名,如 Schnorr |
| code_type | VARCHAR | "Base64" / "Hex",编码方式 |
| key_type | VARCHAR | "private" / "public" / "signature" |
| key_name | VARCHAR | 元素内部名字,如 "d"、"e" |
| key_value | TEXT | Base64 或十六进制存储的值 |
| created_at | TIMESTAMP | 创建时间 |
对应加密模块的相关处理,Go 传来对应的参数,Java 只需要关注加密和认证内容,即algo, key_name, key_value三个字段的信息就可以工作,抛开算法名 algo,我们可以用一个 Map 存放key_name: key_value,这是一个初步构想
然后,因为涉及到跨语言和 RPC 传输,我不可能在 value 部分直接传输一个 BigInteger 或是 Element,这是无法序列化的,那么想当然的就应该进行编码,将 value 转化为 Base64 或是 16 进制的字符串,然后传给 Go 模块进行 SQL 就行
那么,Java 模块应当具备 Base64 和 Element 以及 Hex 和 BigInteger 的相互转化的功能,即一个简单的自动编码
那么现在需求就很简单了,我们封装一个类,类里面有一个Map<String, String>,在存入时,根据 value 类型自动编码 put,在取出时,将 String 自动解码为 BigInteger/Element,参与加密计算
CryptoMap
@Data
public class CryptoMap {
Map<String, String> cryptoMap;
public CryptoMap(){
cryptoMap = new HashMap<>();
}
public void put(String key, Element val){
cryptoMap.put(key, EncodeUtil.parseElement2Base64Str(val));
}
public void put(String key, BigInteger val){
cryptoMap.put(key, EncodeUtil.parseBigInteger2HexStr(val));
}
public void put(String ... kv){
int n = kv.length;
if(n % 2 != 0){
return;
}
for(int i = 0; i < n; i+=2){
cryptoMap.put(kv[i], kv[i+1]);
}
}
public String get(String key){
return cryptoMap.get(key);
}
public Element getE(String id, Field field){
return EncodeUtil.parseBase64Str2Element(cryptoMap.get(id), field);
}
public BigInteger getI(String key){
return EncodeUtil.parseHexStr2BigInteger(cryptoMap.get(key));
}
public String toString(){
return cryptoMap.toString();
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
由于在密钥生成阶段将同时生成私公钥,为了方便后续处理(写数据库),封装一个 KeyPair 维护两个 CryptoMap 用以区分公私钥
@Data
public class KeyPair {
public CryptoMap sk;
public CryptoMap pk;
public KeyPair(){
sk = new CryptoMap();
pk = new CryptoMap();
}
}
2
3
4
5
6
7
8
9
10
# 工具类
主要是哈希,将字符串(明文)映射到对应的域/群上,通常是 Zr 群
public class HashUtil {
public static byte[] concat(byte[] ... arr) {
ByteArrayOutputStream outputStream = new ByteArrayOutputStream();
try{
for(byte[] bytes: arr){
outputStream.write(bytes);
}
} catch (IOException e){
System.out.println("IOException: concat bytes error");
}
return outputStream.toByteArray();
}
public static Element hashByte2group(Field group, byte[] bytes){
return group.newElementFromHash(bytes, 0, bytes.length).getImmutable();
}
public static Element hashStr2Group(Field group, String ... strings){
int n = strings.length;
byte[][] bytes = new byte[n][];
for(int i = 0; i < n; i++){
bytes[i] = strings[i].getBytes();
}
byte[] input = concat(bytes);
return hashByte2Group(group, input);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
对于多个字符串,采取的是 concat 的方式,即联结||,这里用到了(String ... strings)的传参写法
噢还有上面提到的编码类,用于 Base64 / Hex / BigInteger / Element 的编码解码
public class EncodeUtil {
public static String parseBigInteger2HexStr(BigInteger bi){
return bi.toString(16);
}
public static BigInteger parseHexStr2BigInteger(String str){
return new BigInteger(str, 16);
}
public static String parseElement2Base64Str(Element element){
byte[] bytes = element.toBytes(); // 转为 byte[]
return Base64.getEncoder().encodeToString(bytes);
}
public static Element parseBase64Str2Element(String base64, Field field){
byte[] bytes = Base64.getDecoder().decode(base64);
return field.newElementFromBytes(bytes).getImmutable();
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# RSA 签名
基于大数分解问题,在整数域上实现
- 注意:JPBC 的 Zr 群并不是一个模大素数整数域,而是一个循环群,其性质并不一样,所以不能采用 JPBC 编写,而是选择用 BigInteger 手动实现,这里用到 Zr 群的原因是为了借用哈希函数
hashStr2Zr(Field Zr, String ... strings)
构造方法(继承自 CipherSystem)
// JPBC 并不适用,用 BigInteger 手写的
public class RSA extends CipherSystem {
public RSA(Field Zr, Boolean sanitizable, Boolean updatable) {
super(null, null, null, null, Zr, sanitizable, updatable);
}
}
2
3
4
5
6
# 密钥生成
返回一个公私钥密钥对KeyPair key = keygen(),结构非常简单,就是一对大素数逆元d, e满足
d 作为私钥,而 e 作为公钥
@Override
public KeyPair keygen(){
BigInteger p = BigInteger.probablePrime(512, new SecureRandom());
BigInteger q = BigInteger.probablePrime(512, new SecureRandom());
BigInteger n = p.multiply(q);
// 欧拉函数
BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
BigInteger e = BigInteger.probablePrime(128, new SecureRandom());
BigInteger d = e.modInverse(phi);
KeyPair k = new KeyPair();
k.sk.put("d", d);
k.sk.put("phi", phi);
k.sk.put("n", n);
k.pk.put("e", e);
k.pk.put("n", n);
return k;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 签名验签
签名:返回一个签名CryptoMap signature = sign(String message, CryptoMap sk),实际上只有一个元素s
// s = H(m)^d
@Override
public CryptoMap sign(String message, CryptoMap sk){
// 明文哈希
BigInteger m = HashUtil.hashStr2Group(getZr(), message).toBigInteger();
BigInteger d = sk.getI("d");
BigInteger n = sk.getI("n");
BigInteger s = m.modPow(d, n);
CryptoMap signature = new CryptoMap();
signature.put("m", m);
signature.put("s", s); // s = m^d % n
return signature;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
验签:返回布尔值Boolean flag = verify(String message, CryptoMap pk, CryptoMap signature),验签过程如下
// H(m) ?= s^e
@Override
public Boolean verify(CryptoMap pk, CryptoMap signature){
BigInteger s = signature.getI("s");
BigInteger e = pk.getI("e");
BigInteger n = pk.getI("n");
BigInteger m = signature.getI("m");
BigInteger recovered = s.modPow(e, n);
return m.equals(recovered);
}
2
3
4
5
6
7
8
9
10
11
# Schnorr 签名
和上面类似,都是继承 CipherSystem 然后一个个实现接口 Auth 的功能,只不过上面 RSA 是用的 BigInteger,而 Schnorr 在 ECC 上实现,自然用到 JPBC
构造函数
public class Schnorr extends CipherSystem {
public Schnorr(Pairing BP, Field G1, Field G2, Field GT, Field Zr, Boolean sanitizable, Boolean updatable) {
super(BP, G1, G2, GT, Zr, sanitizable, updatable);
}
}
2
3
4
5
# 密钥生成
randomG1 / randomZ等函数是封装在抽象类 CipherSystem 中的语法糖
@Override
public KeyPair keygen(){
Element g = randomG1();
Element x = randomZ();
Element y = g.mulZn(x).getImmutable();
KeyPair keyPair = new KeyPair();
keyPair.sk.put("g", g);
keyPair.sk.put("x", x);
keyPair.pk.put("g", g);
keyPair.pk.put("y", y);
return keyPair;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
# 签名验签
签名:根据私钥g, x计算签名z, c,c是一个哈希值,z是后续参与计算的 tip,R才是认证的关键
// R = rG, c = H(msg, R), z = r+cx
@Override
public CryptoMap sign(String message, CryptoMap sk){
Element g = sk.getE("g", getG1());
Element x = sk.getE("x", getZr());
Element r = randomZ();
Element R = g.mulZn(r).getImmutable();
Element c = HashUtil.hashStr2Group(getZr(), message, R.toString());
Element z = r.add(x.mulZn(c)).getImmutable();
CryptoMap signature = new CryptoMap();
signature.put("z", z);
signature.put("c", c);
signature.put("m", message);
return signature;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
验签:利用公钥g, y从签名z, c中还原出 R'
然后利用明文信息 Message 和 R' 进行哈希,看是否等于签名信息中的c,从而实现验签
// R1 = zG-xGc = (r+cx)G-cxG = rG = R
// H(msg, R1) = H(msg, R) = c
@Override
public Boolean verify(CryptoMap pk, CryptoMap signature){
Element y = pk.getE("y", getG1());
Element g = pk.getE("g", getG1());
Element z = signature.getE("z", getZr());
Element c = signature.getE("c", getZr());
String m = signature.get("m");
Element R1 = g.mulZn(z).sub(y.mulZn(c)).getImmutable();
return c.isEqual(HashUtil.hashStr2Group(getZr(), m, R1.toString()));
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# ElGamal 签名
基于离散对数问题,它可以在不同的数学结构上实现,这里实现在整数域
经典 ElGamal(整数模运算):适用于传统 DLP(模素数)
构造函数
public class Elgamal extends CipherSystem {
public Elgamal(Field Zr, Boolean sanitizable, Boolean updatable) {
super(null, null, null, null, Zr, sanitizable, updatable);
}
}
2
3
4
5
6
# 密钥生成
公私钥
@Override
public KeyPair keygen(){
BigInteger p = BigInteger.probablePrime(1024, new SecureRandom());
BigInteger g = randomZ().toBigInteger();
BigInteger x = randomZ().toBigInteger();
BigInteger y = g.modPow(x, p);
KeyPair key = new KeyPair();
key.sk.put("x", x);
key.sk.put("g", g);
key.sk.put("p", p);
key.pk.put("g", g);
key.pk.put("y", y);
key.pk.put("p", p);
return key;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 签名验签
签名:根据私钥 x 对 m 签名
@Override
public CryptoMap sign(String message, CryptoMap sk){
BigInteger g = sk.getI("g");
BigInteger p = sk.getI("p");
BigInteger x = sk.getI("x");
BigInteger m = HashUtil.hashStr2Group(getZr(), message).toBigInteger();
// k 必须是可逆的
BigInteger k = BigInteger.probablePrime(128, new SecureRandom());
BigInteger k1 = k.modInverse(p.subtract(BigInteger.ONE)); // k的逆
BigInteger r = g.modPow(k, p);
BigInteger s = m.subtract(x.multiply(r)).multiply(k1).mod(p.subtract(BigInteger.ONE));
CryptoMap signature = new CryptoMap();
signature.put("m", m);
signature.put("r", r);
signature.put("s", s);
return signature;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
验签:根据公钥 (y, g) 验证消息 m' 的签名 (r, s)
注意手动取模
@Override
public Boolean verify(CryptoMap pk, CryptoMap signature){
BigInteger g = pk.getI("g");
BigInteger y = pk.getI("y");
BigInteger p = pk.getI("p");
BigInteger r = signature.getI("r");
BigInteger s = signature.getI("s");
BigInteger m = signature.getI("m");
BigInteger left = y.modPow(r, p).multiply(r.modPow(s, p)).mod(p);
BigInteger right = g.modPow(m, p);
return left.equals(right);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 可擦除盲签名
SBS 的复现,理论部分可见基于可擦除签名的权限切换协议 | Arkrypto (opens new window)
与上述的经典的签名方案不同,可擦除签名依靠变色龙哈希,给签名添加了一个“擦除”过程,即,擦除者可以在不需要经过原始签名者的情况下,对签名进行适度的修改并且不改变签名的合法性
# 密钥生成
密钥生成
根据生成元 g 初始化,这里选择在外层调用两次 keygen 来生成实验所需的两套密钥,即每次仅生成一个私钥和一个公钥
public class SBS extends CipherSystem {
Element g;
public SBS(Pairing BP, Field G1, Field GT, Field Zr) {
super(BP, G1, null, GT, Zr, true, true);
g = randomG1(); // 生成元
}
/* ========= KeyGen ========= */
@Override
public KeyPair keygen() {
Element sk = randomZ(); // Z_q 元素
Element pk = g.powZn(sk).getImmutable();
KeyPair kp = new KeyPair();
kp.sk.put("sk", sk);
kp.pk.put("pk", pk);
return kp;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
这是合理的,因为实际签名时,真实情况就是有两名参与者,这也更符合数据库存储逻辑
一个简单的哈希函数,将字符串映射到 Zr 群上
public Element h(String message){
return HashUtil.hashStr2Group(this.getZr(), message);
}
2
3
# 签名验签
签名者对消息 message 进行签名,需要同时用到自身的签名私钥和擦除者的擦除公钥
/* ========= Sign ========= */
// 使用签名者的私钥和擦除者的公钥进行签名
@Override
public CryptoMap sign(String message, CryptoMap key) {
Element sk_sig = key.getE("sk_sig", this.getZr()); // 签名私钥
Element pk_san = key.getE("pk_san", this.getG1()); // 擦除公钥
Element m = h(message); // 明文哈希 H(m)∈G1
Element X = pk_san.powZn(m).getImmutable();
// 构造 mu 和 eta
Element r = randomZ();
Element R = g.powZn(r).getImmutable();
Element mu = X.powZn(sk_sig.add(r)).getImmutable();
CryptoMap signature = new CryptoMap();
signature.put("m", m);
signature.put("X", X);
signature.put("R", R);
signature.put("mu", mu);
return signature;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
验签时使用明文消息、签名、签名公钥和擦除公钥进行验证
1️⃣ 首先判断 X 是否匹配明文:验签者通过公钥和明文 m 计算 X'
2️⃣ 再利用签名者的公钥通过配对验证 μ 的合法性
/* ========= Verify ========= */
// 使用签名者的公钥和擦除者的公钥进行验签
@Override
public Boolean verify(CryptoMap key, CryptoMap signature) {
Element pk_sig = key.getE("pk_sig", this.getG1());
Element pk_san = key.getE("pk_san", this.getG1());
Element X = signature.getE("X", this.getG1());
Element R = signature.getE("R", this.getG1());
Element mu = signature.getE("mu", this.getG1());
Element m = signature.getE("m", this.getZr());
Element X1 = pk_san.powZn(m).getImmutable();
boolean flag1 = X.isEqual(X1);
System.out.println("f1: " + flag1);
Element left1 = pairing(mu, g).getImmutable();
Element right1 = pairing(X1, pk_sig).mul(pairing(R, X1)).getImmutable();
boolean flag2 = left1.isEqual(right1);
System.out.println("f2: " + flag2);
return flag1 && flag2;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 擦除和二次验签
在擦除时,擦除者首先用到自身的私钥验证权限,而后使用新的明文对原有签名进行更新
1️⃣ 权限认证
2️⃣ 签名擦除
注意 R 是保持不变的
/* ========= Sanitize ========= */
@Override
public CryptoMap sanitize(String message, CryptoMap key, CryptoMap signature) {
Element sk_san = key.getE("sk_san", this.getZr());
// sk_san = sk_san.add(this.getI("1"));
Element X = signature.getE("X", this.getG1());
Element m = signature.getE("m", this.getZr());
if(!X.powZn(sk_san.invert()).isEqual(g.powZn(m))){
System.out.println("不具备擦除权力,签名照旧");
return signature;
}
Element s = h(message); // 根据新的消息更新明文 m
m = m.mul(s).getImmutable();
Element mu = signature.getE("mu", this.getG1());
// 重签 eta
Element X1 = X.powZn(s).getImmutable();
Element mu1 = mu.powZn(s).getImmutable();
signature.put("m", m);
signature.put("X", X1);
signature.put("mu", mu1);
return signature;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
二次验签:对擦除后的明文和签名进行验签,和上述的验签代码一致,由于同时加入了指数变量 s,匹配式将保持一致
# 测试代码
测试密钥生成、签名以及验签的耗时
public class CryptoTest {
private static final Pairing BP = PairingFactory.getPairing("a.properties");
private static final Field G1 = BP.getG1();
private static final Field G2 = BP.getG2();
private static final Field GT = BP.getGT();
private static final Field Zr = BP.getZr();
public static void main(String[] args) {
CipherSystem rsa = new RSA(Zr);
CipherSystem schnorr = new cia.arkrypto.auth.crypto.impl.Schnorr(G1, Zr);
CipherSystem elgamal = new Elgamal(Zr);
CipherSystem sbs = new SBS(BP, G1, GT, Zr);
System.out.println(test(rsa));
System.out.println(test(schnorr));
System.out.println(test(elgamal));
System.out.println(test(sbs));
}
public static Map<String, Long> test(CipherSystem cipherSystem){
Map<String, Long> timeCost = new HashMap<>();
long s1 = System.currentTimeMillis();
KeyPair key = cipherSystem.keygen();
long e1 = System.currentTimeMillis();
long s2 = System.currentTimeMillis();
CryptoMap signature = cipherSystem.sign("test", key.sk);
long e2 = System.currentTimeMillis();
long s3 = System.currentTimeMillis();
System.out.println(cipherSystem.verify("test", key.pk, signature));
long e3 = System.currentTimeMillis();
timeCost.put("keygen", e1-s1);
timeCost.put("sign", e2-s2);
timeCost.put("verify", e3-s3);
return timeCost;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45