门限密码系统

  • 1. 定义
  • 2. 分布式ElGamal加密
    • 推广
  • 3.有可信中心的门限ElGamal密码
  • 4. 无可信中心的门限ElGamal密码

1. 定义

门限密码系统由分布式密钥生成算法、加密算法、门限解密算法三部分构成,定义如下:

(1)分布式密钥生成:这是一个由参与者共同生成公钥 yyy的协议,协议运行结束后,每个参与者将获得一个关于私钥 xxx的碎片、对应于该碎片的公钥密钥 yi y_iyi,以及与私钥 xxx相对应的公钥 yyy

(2)加密算法:该算法的输入为公钥 yyy和待加密的消息 mmm,其输出为在公钥 yyy下明文 mmm对应的密文 ccc

(3)门限解密: 这是一个由任意 ttt个参与者 P i 1 ′, P i 2 ′, … , P i t P_{i_1^{\prime}}, P_{i_2^{\prime}}, \ldots, P_{i_{t}}Pi1,Pi2,,Pit 运行的协议, 对于给定输人密文 ccc ttt个公开验证密钥 h i 1 ′, h i 2 ′, … , h i t h_{i_1^{\prime}},h_{i_2^{\prime}}, \ldots, h_{i_{t}}hi1,hi2,,hit 以及 ttt 个碎片 x i 1 ′x i 2 ′, … , x i t x_{i_1^{\prime}} x_{i_2^{\prime}}, \ldots, x_{i_{t}}xi1xi2,,xit, 协议运行结束后将输出 密文 ccc 和对应的明文 mmm

2. 分布式ElGamal加密

系统参数: p 、 qp、qpq是大素数, 且 q / p − 1q / p-1q/p1, 满足 Zp Z_{p}Zp中离散对数问题是难解的, ggg Zp∗ Z_{p}^{*}Zp的本原元, MMM 为明文消息。

nnn个参与者 P1, P2, … , Pn P_{1}, P_{2}, \ldots, P_{n}P1,P2,,Pn分别选取一个随机数 xi∈ Zp, i = 1 , 2 , … , nx_{i} \in Z_{p},i=1,2, \ldots, nxiZp,i=1,2,,n 计算 yi= g x i  m o d   py_{i}= g^{x_{i}} \bmod pyi=gximodp并公布。

私钥: x= ∑ i=1n x i  mod  px=\sum_{i=1}^{n} x_{i} \bmod p x=i=1nximodp公钥: y= ∏ i=1n y i  mod  p= g∑ i=1n x i mod  p= g x  mod  py=\prod_{i=1}^{n} y_{i} \bmod p=g^{\sum_{i=1}^{n} x_{i}} \bmod p = g^x \bmod p y=i=1nyimodp=gi=1nximodp=gxmodp

加密: 选取随机数 r ∈ Zp r \in Z_{p}rZp, 计算E(M)=(α,β)=( g r  mod  p, y rM  mod  p)E(M)=(\alpha, \beta) = (g^{r} \bmod p, y^{r} M \bmod p) E(M)=(α,β)=(grmodp,yrMmodp)解密: nnn个参与者首先分别计算 α x i  m o d   p\alpha^{x_{i}}\bmod pαximodp并公布, 然后共同计算出 ∏ i = 1nα x i \prod_{i=1}^{n} \alpha^{x^{i}}i=1nαxi, 从而解出 MMM:M= β∏ i=1n α xi  mod  p= β α ∑ i = 1nxi  mod  p= β αx mod  pM=\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 = M1M2⋯ Mn M=M_{1} M_{2} \cdots M_{n}M=M1M2Mn, nnn个参与者 P1, P2, … , Pn P_{1}, P_{2}, \ldots, P_{n}P1,P2,,Pn分别对消息 M1, M2, … , Mn M_{1}, M_{2}, \ldots, M_{n}M1,M2,,Mn 加密。

系统参数: p 、 qp、qpq是大素数, 且 q / p − 1q / p-1q/p1, 满足 Zp Z_{p}Zp中离散对数问题是难解的, ggg Zp∗ Z_{p}^{*}Zp的本原元, MMM 为明文消息。

利用分布式 ElGamal 加密方式产生私钥/公钥对: nnn个参与者分别选取一个随机数 xi∈ Zp, i = 1 , 2 , … , nx_{i}\in Z_{p},i=1,2, \ldots,nxiZp,i=1,2,,n 计算 yi= g x i  m o d   py_{i}=g^{x_{i}} \bmod pyi=gximodp 并公布。

私钥: x= ∑ i=1n x i  mod  px=\sum_{i=1}^{n} x_{i} \bmod p x=i=1nximodp公钥: y= ∏ i=1n y i  mod  p= g∑ i=1n x i mod  p= g x  mod  py=\prod_{i=1}^{n} y_{i} \bmod p=g^{\sum_{i=1}^{n} x_{i}} \bmod p = g^x \bmod p y=i=1nyimodp=gi=1nximodp=gxmodp

加密: nnn个参与者分别选取随机数 r1, r2, … , rn∈ Zp r_{1}, r_{2}, \ldots, r_{n} \in Z_{p}r1,r2,,rnZp, 对消息 Mi M_{i}Mi 加密 E ( Mi)= ( αi, βi)=( g ri mod  p, y riM i  mod  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 ( M1M2⋯ Mn)=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(M1M2Mn)=E(M1)E(M2)E(Mn)=(α,β)其中,α= ∏ i=1n α i= g∑ i=1n r i mod  p,β= ∏ i=1n β i= y∑ i=1n r i M  mod  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=1nαi=gi=1nrimodp,β=i=1nβi=yi=1nriMmodp

解密: nnn 个参与者首先分别计算 α x i  m o d   p\alpha^{x_{i}} \bmod pαximodp 并公布, 来共同计算出 ∏ i = 1nα x i \prod_{i=1}^{n} \alpha^{x_{i}}i=1nαxi, 从而解出 MMM: M= β∏ i=1n α xi  mod  p β α ∑ i = 1nxi  mod  p= β αx mod  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) 分布式密钥生成

可信中心产生一个密钥 xxx, 对应的公钥为 y = gx  m o d   py=g^{x} \bmod py=gxmodp,使用 ( t , n )(t, n)(t,n) 门限方案在协议参与者中分享私钥 xxx : 选择随机多项式f(u)= a t−1u t−1 +…+ a 2 u 2+ a 1u+ a 0∈GF(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)=at1ut1++a2u2+a1u+a0GF(q)[u] Pi P_{i}Pi 得到 xi= f ( u i), i = 1 , 2 , … , nx_{i}=f\left(u_{i}\right), i=1,2, \ldots, nxi=f(ui),i=1,2,,n

(2) 加密

选取随机数 k ∈ Zp k \in Z_{p}kZp计算:E(M)=(α,β)=( g k  mod  p, y kM  mod  p)E(M)=(\alpha, \beta)= (g^{k} \bmod p, y^{k} M \bmod p) E(M)=(α,β)=(gkmodp,ykMmodp)

(3) 解密

Pi P_{i}Pi 计算 αi= α x i \alpha_{i}=\alpha^{x_{i}}αi=αxi并公布, 同时公布一个零知识证明以证明其计算的正确性;
每个协议参与者从公布的计算结果中选择 ttt α i 1, α i 2, … , α i t \alpha_{i_1}, \alpha_{i_2}, \ldots, \alpha_{i_t}αi1,αi2,,αit, 则M= β αx = β∏ s=1t α isλ i sM=\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 1x i 1+ ⋯ + λ i tx i t x=\lambda_{i_1} x_{i_1}+\cdots+\lambda_{i_t} x_{i_t}x=λi1xi1++λitxit .

有可信中的门限ElGamal密码不能算严格意义上的门限密码,存在第三方可心中,参加密钥分享的用户必须完全信任分发者,相信其不会对加密数据执行解密操作。

4. 无可信中心的门限ElGamal密码

(1)分布式密钥生成

每个参与者 Pi P_{i}Pi 选择择随机数 xi x_{i}xi 作为私钥, 计算 yi= g x i  m o d   py_{i}=g^{x_{i}} \bmod pyi=gximodp, 并公布;
每个参与者收到广播的值后, 计算公钥:y= ∏ i=1n y i  mod  p= g∑ i=1n x i mod  p= g x  mod  py=\prod_{i=1}^{n} y_{i} \bmod p=g^{\sum_{i=1}^{n} x_{i}} \bmod p = g^x \bmod p y=i=1nyimodp=gi=1nximodp=gxmodp每个参与者 Pi P_{i}Pi以秘密分发者身份执行 Feldman 的 VSS 方案, 在 P1, P2, … , Pn P_{1}, P_{2}, \ldots, P_{n}P1,P2,,Pn 之间分享秘密 xi x_{i}xi : 选择 t − 1t-1t1 次随机多项式, f i(u)= a i,t−1u t−1 +…+ a i2u 2+ a i1 u+ a io ∈GF(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,t1ut1++ai2u2+ai1u+aioGF(q)[u]其中 xi= a i 0= fi( 0 )x_{i}=a_{i 0}=f_{i}(0)xi=ai0=fi(0)

Pi P_{i}Pi 计算 x i j= fi( u j) x_{i j}=f_{i}\left(u_{j}\right)xij=fi(uj) , 发送给 Pj, j = 1 , 2 … , nP_{j}, j=1,2 \ldots, nPj,j=1,2,n ; Pj P_{j}Pj 收到其他参与者的值 x i j= fi( u j), i = 1 , 2 … , nx_{i j}=f_{i}\left(u_{j}\right), i=1,2 \ldots, nxij=fi(uj),i=1,2,n, 计算 sj= ∑ i = 1nx i j= ∑ i = 1nfi( 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) 作为自己最终分享得到的关于私钥 xxx的秘密碎片, 其验证公钥为 y j= g sj mod  p= g∑ i=1n x ij  mod  py_{j}=g^{s_{j}} \bmod p=g^{\sum_{i=1}^{n} x_{i j}} \bmod p yj=gsjmodp=gi=1nxijmodp(2) 加密

选取随机数 k ∈ Zp k \in Z_{p}kZp,计算E(M)=(α,β)=( g k  mod  p, y kM  mod  p)E(M)=(\alpha, \beta) =(g^{k} \bmod p, y^{k} M \bmod p) E(M)=(α,β)=(gkmodp,ykMmodp)(3) 门限解密

每个参与者 Pi P_{i}Pi 计算 αi= α s i \alpha_{i}=\alpha^{s_{i}}αi=αsi , 并公布. 同时公布一个零知识证明以证明其计算的正确性;
每个协议参与者从公布的计算结果中选择 ttt α i 1, α i 2, … , α i t \alpha_{i_1}, \alpha_{i_2}, \ldots, \alpha_{i_t}αi1,αi2,,αit, 则M= β αx = β∏ s=1t α isλ i sM=\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 1s i 1+ ⋯ + λ i ts i t x=\lambda_{i_1} s_{i_1}+\cdots+\lambda_{i_t} s_{i_t}x=λi1si1++λitsit .