注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

宁辉博客

 
 
 

日志

 
 

ElGamal 加密法  

2015-10-17 03:02:06|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
如果通讯的一方(A方)定义了函数 F, 另一方(B方)定义了函数G,它们都是把整数投射到到整数的函数,而且   G(F(x ))= F(G(x )) = x,那么通讯的一方就可以用 F 来加密, 另一方可以用G用来解密。

现在我们来考虑
 F( x ) =  mod( ax, p)
 G( x ) = mod( bx, p), 这里 a, b, p 都是整数的常数,
那么很容易证明 G(F(x ))= F(G(x )), 也就是
mod(b mod(ax,p), p) = mod(a mod(bx,p),p)= mod(abx, p)   ** (注1)

如果 G(F(x )) = x, 那样 G 就是 F 的逆函数, F 也是 G 的逆函数了。
不过 p,  a 和 b有甚么关系才能使 G(F(x )) = x 呢?

引理1: 对整数的常数 a, b, p而言, 如果 mod(ab,p)=1  那时对小于 p 的 x  G(F(x )) = x。
证明: G(F(x)) = mod(b mod(ax,p), p) = mod(bax, p)   ** (注1)
                          = mod(x mod(ab,p), p)                        ** (注1)
                          = mod(x, p) = x  因为 x < p.   QED.

这样的a 和 b是不难找的。但这只能是全由通讯一方找出来,他一定要把p告诉给对方。但不可能直接把 a 或 b不加密的传送过去。所以我们得找曲节一点的方法间接去传送。

Taher Elgamal 就在 1985年找到这样的方法:

通讯的A方找来一个质数 (也叫素数) p, 和两个小于p的整数 c,g。A 先算出来c1 = mod(g^c, p), 再把 p, g  和 c1 传送给通讯的B方。

B方找来一个小于p的整数 d,再算出 d1 = mod(g^d, p), 然后把 d1 传送给通讯给A方。

到此两方算是打完招呼了, B方就算出 a = c1^d , 他的加密函数就是
F(x) = mod(ax,p) = mod((c1^d)x,p)

A方也算出 b = d1^(-c) , 他的解密函数就是
G(x) = mod(bx,p) = mod( (d1^(-c))x,p)

根据引理1,要证明G是F的逆函数只需证明 mod(ab,p) = 1.

这里 mod(ab, p) = mod(c1^d  d1^(-c), p)
                          = mod( mod(g^c, p)^d  mod(g^d, p)^(-c),   p)
                          = mod( mod(g^cd, p)  mod(g^(-cd), p),   p)   ** (注3)
                          =  mod(g^cd  g^(-cd), p)    ** (注2)
                          = mod(1, p) = 1.  Q.E.D.

这里的 g 最好是选质数 p 的原根(请参考“密码学浅释”)。

在我举一个具体例子之前我想讨论一下这个加密法的可靠性。要知道 p, g  和 c1 都是加密以前所传送的,而 c1 = mod(g^c, p)。黑客要找到 c 就得解 c1 = mod(g^x, p) 这个方程,也就是算 log(g, c1) mod p  这个离散对数。所以破解这个加密法的难度是和破解 Diffie Hellman 加密钥交递法相同的,对大数值的 p 而言这是难度很高的。

这里c就是通讯的A方的私钥, p, g  和 c1 这组数据算是A交给 B的公钥。
而 B 的私钥是d, d1 却是 B 交给 A 的公钥。
以上的函数 F 是 B方用来加密送往 A 方的, 也可以解读 A 方的密件。
反之函数 G 就是 A方用来加密送往 B 方, 也可以解读 B 方来的密件。

上面 b = d1^(-c) 应该会招来质疑, 怎样去算 mod( (d1^(-c))x,p) 呢? 希望下面的例子可以解答:

例子:
A 方选 p = 23,  g = 7 (原根),  c = 4 (私钥),  c1 = mod(7^4, 23) = 9.
A 把  p = 23,  g = 7, c1 = 9  送往 B 方。
B 选  d = 7 (私钥), 算出  d1 = mod(g^d, p) = mod(7^7, 23) = 5.
假设 B 传送的数据是 x = 10 , 他先要算
 y = mod(x c1^d, p) = mod(10 *  9 ^7, 23) = 17
然后他把 d1= 5 (交给 A 的公钥), 和加密后的数据 17 传送给A。

当 A 收到  y 和 d1  后他是这样解读的:
 mod(y  d1^(-c), p) = mod(17 * 5^(-4), 23).
你可能会问怎样去算   x  = mod(17 * 5^(-4), 23) = mod(17 /  625, 23) 这个数目呢?
这相当于去解
 mod(625 x, 23)  =  mod(625 mod(17 / 625, 23), 23)   
                             = mod(17, 23)    (注1)
                            = 17   这个方程。
又因为 mod(625, 23) = 4,  这方程又可以简化为
mod(625 x, 23) = mod(mod(625,23) x, 23)    (注1)
                           =  mod( 4x, 23) =  17
走到这一步我们只好去求  4x = 23k + 17 这个不定方程的整数解。
 当 k = 1,  23 + 17 = 40, 所以 x = 10。

这不是一个可以用在电脑程式的方法,我相信实际应用上的电脑编程会有更好的方法。不过求  mod( 4x, 23) =  17 的解比起破解这加密法所要解的方程  c1 = mod(g^x, p), 也就是 mod(7^x,23) = 9   来讲,是容易很多倍了。就算用穷举法把0,1,2,,,,, 22 这些数目代进这两个方程,一方是做乘数,另一方是做乘方运算, 难度很不同的。

***********************************************************************************
(注1)   对任何整数 e,f,p   mod(e mod(f,p), p) = mod(ef, p)   
   让     n = mod(f, p)
          我们会有整数  s   使     f = sp + n
          那么 ef = e(sp + n)  =  en  +  p(es)
         所以   mod(ef,p) = mod(en,p) =  mod(e mod(f,p), p)

(注2)   对任何整数 e,f,p  mod(mod(e,p) mod(f,p), p)  =  mod(ef, p)  
       其际这是注1的翻版:
      mod(ef, p)   =  mod(e mod(f,p), p) = mod(mod(e,p) mod(f,p), p)

 (注3)   对任何整数 e,f,p   mod(mod(e,p) ^ f, p) = mod(e ^ f, p)
这在 “密码学浅释” 已经证明, 当时用 x,y,p 这些符号:
          mod(mod(x,p) ^ y, p) = mod(x ^ y, p)
  评论这张
 
阅读(183)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018