门限密码系统
1. 定义
门限密码系统由分布式密钥生成算法、加密算法、门限解密算法三部分构成，定义如下：
（1）分布式密钥生成：这是一个由参与者共同生成公钥
y
y
y的协议，协议运行结束后，每个参与者将获得一个关于私钥
x
x
x的碎片、对应于该碎片的公钥密钥
y
i
y_i
yi，以及与私钥
x
x
x相对应的公钥
y
y
y。
（2）加密算法：该算法的输入为公钥
y
y
y和待加密的消息
m
m
m，其输出为在公钥
y
y
y下明文
m
m
m对应的密文
c
c
c。
（3）门限解密: 这是一个由任意
t
t
t个参与者
P
i
1
′
,
P
i
2
′
,
…
,
P
i
t
P_{i_1^{\prime}}, P_{i_2^{\prime}}, \ldots, P_{i_{t}}
Pi1′,Pi2′,…,Pit 运行的协议, 对于给定输人密文
c
c
c 、
t
t
t个公开验证密钥
h
i
1
′
,
h
i
2
′
,
…
,
h
i
t
h_{i_1^{\prime}},h_{i_2^{\prime}}, \ldots, h_{i_{t}}
hi1′,hi2′,…,hit 以及
t
t
t 个碎片
x
i
1
′
x
i
2
′
,
…
,
x
i
t
x_{i_1^{\prime}} x_{i_2^{\prime}}, \ldots, x_{i_{t}}
xi1′xi2′,…,xit, 协议运行结束后将输出 密文
c
c
c 和对应的明文
m
m
m 。
2. 分布式ElGamal加密
系统参数:
p
、
q
p、q
p、q是大素数, 且
q
/
p
−
1
q / p-1
q/p−1, 满足
Z
p
Z_{p}
Zp中离散对数问题是难解的,
g
g
g 是
Z
p
∗
Z_{p}^{*}
Zp∗的本原元,
M
M
M 为明文消息。
n
n
n个参与者
P
1
,
P
2
,
…
,
P
n
P_{1}, P_{2}, \ldots, P_{n}
P1,P2,…,Pn分别选取一个随机数
x
i
∈
Z
p
,
i
=
1
,
2
,
…
,
n
x_{i} \in Z_{p},i=1,2, \ldots, n
xi∈Zp,i=1,2,…,n 计算
y
i
=
g
x
i
m
o
d
p
y_{i}= g^{x_{i}} \bmod p
yi=gximodp并公布。
私钥:
x
=
∑
i
=
1
n
x
i
m
o
d
p
x=\sum_{i=1}^{n} x_{i} \bmod p
x=i=1∑nximodp**公钥**:
y
=
∏
i
=
1
n
y
i
m
o
d
p
=
g
∑
i
=
1
n
x
i
m
o
d
p
=
g
x
m
o
d
p
y=\prod_{i=1}^{n} y_{i} \bmod p=g^{\sum_{i=1}^{n} x_{i}} \bmod p = g^x \bmod p
y=i=1∏nyimodp=g∑i=1nximodp=gxmodp
加密: 选取随机数
r
∈
Z
p
r \in Z_{p}
r∈Zp, 计算
E
(
M
)
=
(
α
,
β
)
=
(
g
r
m
o
d
p
,
y
r
M
m
o
d
p
)
E(M)=(\alpha, \beta) = (g^{r} \bmod p, y^{r} M \bmod p)
E(M)=(α,β)=(grmodp,yrMmodp)**解密**:
n
n
n个参与者首先分别计算
α
x
i
m
o
d
p
\alpha^{x_{i}}\bmod p
αximodp并公布, 然后共同计算出
∏
i
=
1
n
α
x
i
\prod_{i=1}^{n} \alpha^{x^{i}}
∏i=1nαxi, 从而解出
M
M
M:
M
=
β
∏
i
=
1
n
α
x
i
m
o
d
p
=
β
α
∑
i
=
1
n
x
i
m
o
d
p
=
β
α
x
m
o
d
p
M=\frac{\beta}{\prod_{i=1}^{n} \alpha^{x^{i}}} \bmod p =\frac{\beta}{\alpha^{\sum_{i=1}^{n} x^{i}}} \bmod p =\frac{\beta}{\alpha^x} \bmod p
M=∏i=1nαxiβmodp=α∑i=1nxiβmodp=αxβmodp
推广
令消息
M
=
M
1
M
2
⋯
M
n
M=M_{1} M_{2} \cdots M_{n}
M=M1M2⋯Mn,
n
n
n个参与者
P
1
,
P
2
,
…
,
P
n
P_{1}, P_{2}, \ldots, P_{n}
P1,P2,…,Pn分别对消息
M
1
,
M
2
,
…
,
M
n
M_{1}, M_{2}, \ldots, M_{n}
M1,M2,…,Mn 加密。
系统参数:
p
、
q
p、q
p、q是大素数, 且
q
/
p
−
1
q / p-1
q/p−1, 满足
Z
p
Z_{p}
Zp中离散对数问题是难解的,
g
g
g 是
Z
p
∗
Z_{p}^{*}
Zp∗的本原元,
M
M
M 为明文消息。
利用分布式 ElGamal 加密方式产生私钥/公钥对：
n
n
n个参与者分别选取一个随机数
x
i
∈
Z
p
,
i
=
1
,
2
,
…
,
n
x_{i}\in Z_{p},i=1,2, \ldots,n
xi∈Zp,i=1,2,…,n 计算
y
i
=
g
x
i
m
o
d
p
y_{i}=g^{x_{i}} \bmod p
yi=gximodp 并公布。
私钥:
x
=
∑
i
=
1
n
x
i
m
o
d
p
x=\sum_{i=1}^{n} x_{i} \bmod p
x=i=1∑nximodp**公钥**:
y
=
∏
i
=
1
n
y
i
m
o
d
p
=
g
∑
i
=
1
n
x
i
m
o
d
p
=
g
x
m
o
d
p
y=\prod_{i=1}^{n} y_{i} \bmod p=g^{\sum_{i=1}^{n} x_{i}} \bmod p = g^x \bmod p
y=i=1∏nyimodp=g∑i=1nximodp=gxmodp
加密:
n
n
n个参与者分别选取随机数
r
1
,
r
2
,
…
,
r
n
∈
Z
p
r_{1}, r_{2}, \ldots, r_{n} \in Z_{p}
r1,r2,…,rn∈Zp, 对消息
M
i
M_{i}
Mi 加密
E
(
M
i
)
=
(
α
i
,
β
i
)
=
(
g
r
i
m
o
d
p
,
y
r
i
M
i
m
o
d
p
)
E\left(M_{i}\right)= \left(\alpha_i ,\beta_i\right) =(g^{r_{i}} \bmod p, y^{r_{i}} M_{i} \bmod p)
E(Mi)=(αi,βi)=(grimodp,yriMimodp)
根据同态性计算
E
(
M
)
=
E
(
M
1
M
2
⋯
M
n
)
=
E
(
M
1
)
E
(
M
2
)
⋯
E
(
M
n
)
=
(
α
,
β
)
E(M)=E\left(M_{1} M_{2} \cdots M_{n}\right)= E(M_{1})E(M_{2}) \cdots E(M_{n})= (\alpha, \beta)
E(M)=E(M1M2⋯Mn)=E(M1)E(M2)⋯E(Mn)=(α,β)其中，
α
=
∏
i
=
1
n
α
i
=
g
∑
i
=
1
n
r
i
m
o
d
p
,
β
=
∏
i
=
1
n
β
i
=
y
∑
i
=
1
n
r
i
M
m
o
d
p
\alpha=\prod_{i=1}^{n} \alpha_{i}=g^{\sum_{i=1}^{n} r_{i}} \bmod p,\beta = \prod_{i=1}^{n} \beta_{i}=y^{\sum_{i=1}^{n} r_{i}} M \bmod p
α=i=1∏nαi=g∑i=1nrimodp,β=i=1∏nβi=y∑i=1nriMmodp
解密:
n
n
n 个参与者首先分别计算
α
x
i
m
o
d
p
\alpha^{x_{i}} \bmod p
αximodp 并公布, 来共同计算出
∏
i
=
1
n
α
x
i
\prod_{i=1}^{n} \alpha^{x_{i}}
∏i=1nαxi, 从而解出
M
M
M:
M
=
β
∏
i
=
1
n
α
x
i
m
o
d
p
β
α
∑
i
=
1
n
x
i
m
o
d
p
=
β
α
x
m
o
d
p
\quad M=\frac{\beta}{\prod_{i=1}^{n} \alpha^{x_{i}}} \bmod p \frac{\beta}{\alpha^{\sum_{i=1}^{n} x_{i}}} \bmod p=\frac{\beta}{\alpha^x} \bmod p
M=∏i=1nαxiβmodpα∑i=1nxiβmodp=αxβmodp
3.有可信中心的门限ElGamal密码
(1) 分布式密钥生成
可信中心产生一个密钥
x
x
x, 对应的公钥为
y
=
g
x
m
o
d
p
y=g^{x} \bmod p
y=gxmodp，使用
(
t
,
n
)
(t, n)
(t,n) 门限方案在协议参与者中分享私钥
x
x
x : 选择随机多项式
f
(
u
)
=
a
t
−
1
u
t
−
1
+
…
+
a
2
u
2
+
a
1
u
+
a
0
∈
G
F
(
q
)
[
u
]
f(u)=a_{t-1} u^{t-1}+\ldots+a_{2} u^{2}+ a_{1} u+a_{0} \in G F(q)[u]
f(u)=at−1ut−1+…+a2u2+a1u+a0∈GF(q)[u]
P
i
P_{i}
Pi 得到
x
i
=
f
(
u
i
)
,
i
=
1
,
2
,
…
,
n
x_{i}=f\left(u_{i}\right), i=1,2, \ldots, n
xi=f(ui),i=1,2,…,n 。
(2) 加密
选取随机数
k
∈
Z
p
k \in Z_{p}
k∈Zp计算：
E
(
M
)
=
(
α
,
β
)
=
(
g
k
m
o
d
p
,
y
k
M
m
o
d
p
)
E(M)=(\alpha, \beta)= (g^{k} \bmod p, y^{k} M \bmod p)
E(M)=(α,β)=(gkmodp,ykMmodp)
(3) 解密
P
i
P_{i}
Pi 计算
α
i
=
α
x
i
\alpha_{i}=\alpha^{x_{i}}
αi=αxi并公布, 同时公布一个零知识证明以证明其计算的正确性;
每个协议参与者从公布的计算结果中选择
t
t
t 个
α
i
1
,
α
i
2
,
…
,
α
i
t
\alpha_{i_1}, \alpha_{i_2}, \ldots, \alpha_{i_t}
αi1,αi2,…,αit, 则
M
=
β
α
x
=
β
∏
s
=
1
t
α
i
s
λ
i
s
M=\frac{\beta}{\alpha^{x}}=\frac{\beta}{\prod_{s=1}^{t} \alpha_{i_s}^{\lambda_{i_s}}}
M=αxβ=∏s=1tαisλisβ
λ
i
s
\lambda_{i_s}
λis 为 Lagrange 揷值系数, 满足
x
=
λ
i
1
x
i
1
+
⋯
+
λ
i
t
x
i
t
x=\lambda_{i_1} x_{i_1}+\cdots+\lambda_{i_t} x_{i_t}
x=λi1xi1+⋯+λitxit .
有可信中的门限ElGamal密码不能算严格意义上的门限密码，存在第三方可心中，参加密钥分享的用户必须完全信任分发者，相信其不会对加密数据执行解密操作。
4. 无可信中心的门限ElGamal密码
（1）分布式密钥生成
每个参与者
P
i
P_{i}
Pi 选择择随机数
x
i
x_{i}
xi 作为私钥, 计算
y
i
=
g
x
i
m
o
d
p
y_{i}=g^{x_{i}} \bmod p
yi=gximodp, 并公布;
每个参与者收到广播的值后, 计算公钥:
y
=
∏
i
=
1
n
y
i
m
o
d
p
=
g
∑
i
=
1
n
x
i
m
o
d
p
=
g
x
m
o
d
p
y=\prod_{i=1}^{n} y_{i} \bmod p=g^{\sum_{i=1}^{n} x_{i}} \bmod p = g^x \bmod p
y=i=1∏nyimodp=g∑i=1nximodp=gxmodp每个参与者
P
i
P_{i}
Pi以秘密分发者身份执行 Feldman 的 VSS 方案, 在
P
1
,
P
2
,
…
,
P
n
P_{1}, P_{2}, \ldots, P_{n}
P1,P2,…,Pn 之间分享秘密
x
i
x_{i}
xi : 选择
t
−
1
t-1
t−1 次随机多项式,
f
i
(
u
)
=
a
i
,
t
−
1
u
t
−
1
+
…
+
a
i
2
u
2
+
a
i
1
u
+
a
i
o
∈
G
F
(
q
)
[
u
]
f_{i}(u)=a_{i, t-1} u^{t-1}+\ldots+a_{i 2} u^{2}+a_{i 1} u+a_{i o} \in G F(q)[u]
fi(u)=ai,t−1ut−1+…+ai2u2+ai1u+aio∈GF(q)[u]其中
x
i
=
a
i
0
=
f
i
(
0
)
x_{i}=a_{i 0}=f_{i}(0)
xi=ai0=fi(0)
P
i
P_{i}
Pi 计算
x
i
j
=
f
i
(
u
j
)
x_{i j}=f_{i}\left(u_{j}\right)
xij=fi(uj) , 发送给
P
j
,
j
=
1
,
2
…
,
n
P_{j}, j=1,2 \ldots, n
Pj,j=1,2…,n ;
P
j
P_{j}
Pj 收到其他参与者的值
x
i
j
=
f
i
(
u
j
)
,
i
=
1
,
2
…
,
n
x_{i j}=f_{i}\left(u_{j}\right), i=1,2 \ldots, n
xij=fi(uj),i=1,2…,n, 计算
s
j
=
∑
i
=
1
n
x
i
j
=
∑
i
=
1
n
f
i
(
u
j
)
s_{j}=\sum_{i=1}^{n} x_{i j}=\sum_{i=1}^{n} f_{i}\left(u_{j}\right)
sj=∑i=1nxij=∑i=1nfi(uj) 作为自己最终分享得到的关于私钥
x
x
x的秘密碎片, 其验证公钥为
y
j
=
g
s
j
m
o
d
p
=
g
∑
i
=
1
n
x
i
j
m
o
d
p
y_{j}=g^{s_{j}} \bmod p=g^{\sum_{i=1}^{n} x_{i j}} \bmod p
yj=gsjmodp=g∑i=1nxijmodp**(2) 加密**
选取随机数
k
∈
Z
p
k \in Z_{p}
k∈Zp,计算
E
(
M
)
=
(
α
,
β
)
=
(
g
k
m
o
d
p
,
y
k
M
m
o
d
p
)
E(M)=(\alpha, \beta) =(g^{k} \bmod p, y^{k} M \bmod p)
E(M)=(α,β)=(gkmodp,ykMmodp)**(3) 门限解密**
每个参与者
P
i
P_{i}
Pi 计算
α
i
=
α
s
i
\alpha_{i}=\alpha^{s_{i}}
αi=αsi , 并公布. 同时公布一个零知识证明以证明其计算的正确性;
每个协议参与者从公布的计算结果中选择
t
t
t 个
α
i
1
,
α
i
2
,
…
,
α
i
t
\alpha_{i_1}, \alpha_{i_2}, \ldots, \alpha_{i_t}
αi1,αi2,…,αit, 则
M
=
β
α
x
=
β
∏
s
=
1
t
α
i
s
λ
i
s
M=\frac{\beta}{\alpha^{x}}=\frac{\beta}{\prod_{s=1}^{t} \alpha_{i_s}^{\lambda_{i_s}}}
M=αxβ=∏s=1tαisλisβ
λ
i
s
\lambda_{i_s}
λis 为 Lagrange 揷值系数, 满足
x
=
λ
i
1
s
i
1
+
⋯
+
λ
i
t
s
i
t
x=\lambda_{i_1} s_{i_1}+\cdots+\lambda_{i_t} s_{i_t}
x=λi1si1+⋯+λitsit .
本文转载自: https://blog.csdn.net/apr15/article/details/128943155
版权归原作者 机器学习Zero 所有， 如有侵权，请联系我们删除。
版权归原作者 机器学习Zero 所有， 如有侵权，请联系我们删除。