GM(Goldwasser-Micali)加密算法

我会带着你远行 2022-05-09 11:44 198阅读 0赞

# GM（Goldwasser \- Micali）概率公钥加密算法，其基于二次剩余难以复合困难性问题 #

--------------------

![Goldwasser][]   ![micali][]

--------------------

具体过程：

密钥产生：

1.  大素数p，q，求出N=p\*q
2.  任取R，满足![J\\left(\\frac\{R\}\{p\} \\right )=J\\left(\\frac\{R\}\{q\} \\right )=-1][J_left_frac_R_p_ _right _J_left_frac_R_q_ _right _-1]  （J（）雅可比符号）
3.  PK（R ,N）,SK （p，q）

加密：

1. B将明文转化为二进制数字M=(m1,m2,m3… mk) ∈\{0,1\}

2. 对于每一个mi，都对应选取一个xi ∈\{1，N-1\}

若mi=1 ci= ![R\\times xi^\{2\} mod N][R_times xi_2_ mod N]

若mi=0 ci=![xi^\{2\} mod N][xi_2_ mod N]

3.  C =\{c1,c2,c3…ck\} 将这个C发给A

解密：

对于每一个ci 都求![J\\left ( \\frac\{ci\}\{p\} \\right )][J_left _ _frac_ci_p_ _right]与![J\\left ( \\frac\{ci\}\{q\} \\right )][J_left _ _frac_ci_q_ _right]

![J\\left ( \\frac\{ci\}\{p\} \\right )][J_left _ _frac_ci_p_ _right] 与![J\\left ( \\frac\{ci\}\{q\} \\right )][J_left _ _frac_ci_q_ _right]，若都=1,mi=0 ，若都=-1,mi=1

最终得到M

--------------------

具体演示（点击进入全屏）：

注：演示中任选R满足的是![J\\left(\\frac\{R\}\{p\} \\right )=J\\left(\\frac\{R\}\{q\} \\right )=-1][J_left_frac_R_p_ _right _J_left_frac_R_q_ _right _-1] 是负1

![Goldwasser-micali][]

--------------------

[Goldwasser]: https://img-blog.csdn.net/20181007130409323?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODE2NTkx/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[micali]: /images/20220509/93dd14b29ac4494ca7432e2e14b0b486.png
[J_left_frac_R_p_ _right _J_left_frac_R_q_ _right _-1]: https://private.codecogs.com/gif.latex?J%5Cleft%28%5Cfrac%7BR%7D%7Bp%7D%20%5Cright%20%29%3DJ%5Cleft%28%5Cfrac%7BR%7D%7Bq%7D%20%5Cright%20%29%3D-1
[R_times xi_2_ mod N]: https://private.codecogs.com/gif.latex?R%5Ctimes%20xi%5E%7B2%7D%20mod%20N
[xi_2_ mod N]: https://private.codecogs.com/gif.latex?xi%5E%7B2%7D%20mod%20N
[J_left _ _frac_ci_p_ _right]: https://private.codecogs.com/gif.latex?J%5Cleft%20%28%20%5Cfrac%7Bci%7D%7Bp%7D%20%5Cright%20%29
[J_left _ _frac_ci_q_ _right]: https://private.codecogs.com/gif.latex?J%5Cleft%20%28%20%5Cfrac%7Bci%7D%7Bq%7D%20%5Cright%20%29
[Goldwasser-micali]: /images/20220509/99753b4405584ae8bf31b81448d6be69.png