公钥密码体制（RSA，椭圆曲线密码，ElGamal
目錄
概述
RSA
?密鑰的產(chǎn)生
加密：
?解密：
?ElGamal：
橢圓密碼曲線密碼ECC：
概述
密鑰是需要定期更換的。如果采用對稱密鑰體制（分組密碼和序列密碼）更換密鑰以及相應(yīng)的“密鑰分發(fā)”工作量相當(dāng)大。
由于對稱密碼在實際應(yīng)用中“密鑰分發(fā)”的問題，非對稱密碼在這方面相對安全。
1976年，Diffie,Hellman發(fā)表了非對稱密碼的奠基性論文《密碼學(xué)的新方向》，建立了公鑰密碼的概念。
序列密碼在加密和解密時，無論是種子密鑰還是生成密鑰流，都是一樣
分組密碼初始密鑰是一樣的，子密鑰使用順序相反或者可以互推。
而非對稱密碼不一樣，公鑰公開，私鑰藏好。
?只有持有私鑰的才能解密。
對稱密碼體制和非對稱密碼體制配合，對稱密碼加密速度快，但密鑰分發(fā)困難，公鑰密碼加密速度慢，基本不存在密鑰分發(fā)問題。可以用公鑰密碼傳遞對稱密碼的密鑰，完成密鑰的分發(fā)，之后運用對稱密碼進(jìn)行大規(guī)模傳輸。
分類：基于大整數(shù)難分解問題（RSA，Rabin。基于離散對數(shù)難題ElGamal。基于橢圓曲線離散對數(shù)的密碼體制。
基于的數(shù)學(xué)難題
RSA
大整數(shù)難分解問題：
已知大整數(shù)N是兩個大素數(shù)的乘積。求大素數(shù)p和q使得N=p*q。
?密鑰的產(chǎn)生
選擇兩個滿足需求的大素數(shù)p和q，n=p*q計算φ(N) = (P-1)(Q-1)??其中φ(N)是n的歐拉函數(shù)。
選一個整數(shù)e，滿足1<e<φ(N),且gcd（φ(N)，e）=1，e 與 φ(n) 互質(zhì)。gcd求最大公因數(shù)
取d，可以使得 ed 除以 φ(n) 的余數(shù)為 1
( 1<d<e，且ed mod φ(n) = 1 )?
以{e，n}為公開密鑰，{d，n}為私密密鑰。
加密：
c：密文
m：明文
加密：c = m^e mod N
?解密：
解密：m = c^d mod N
?RSA準(zhǔn)確性證明：
證明 m ?經(jīng)加解密后還是? m，
?
?在實現(xiàn)RSA算法時，在提高指數(shù)運算速度上，可以運用膜重復(fù)的算法
?RSA平方乘算法
將e表示為二進(jìn)制形式 bk bk-1 .。。。。。b0
?a為明文，b為e??
?ElGamal：
?基于離散對數(shù)難題的公鑰密碼體制：
離散對數(shù)問題：已知大素數(shù)p，y屬于{1，2，。。。。，p-1}。g是膜p的本原元（即ord p（g）=p-1(g能被p^p-1整除)），由y，g，p求x使得y=g^X(modp)
1、ElGamal密鑰生成
首先選擇一個大素數(shù)p，g是模p的本原元α，再選取一個隨機(jī)數(shù)x,1<x < p-1, 計算 y = g^x ( mod p )，則其公鑰為 y,g,p。私鑰是x,g,p。
本原元的概念：若模n下a的階d=φ (n)，a就是n的本原元（又稱為原根）。
先是階的概念：模19下7的階為3（7^1=7mod19,7^2=11mod19,7^3=1mod19,7^4=7mod19....）
本原元并不唯一
2、ElGamal加密
（1）對于明文M加密，隨機(jī)地選取一個整數(shù)k，2≤k≤p-2
（2）C1＝g^k mod p
（3）C2＝My^k mod p
（4）密文為（C1,C2）
3、ElGamal解密
由密文可得明文M，M=C2/(C1^d) mod p
缺點：密文長度是所對應(yīng)的明文長度的兩倍。
橢圓密碼曲線密碼ECC：
?安全性：基于橢圓曲線離散對數(shù)問題的困難性
已知橢圓曲線Ep（a，b），以及兩個點Q R屬于Ep（a，b），由R Q Ep（a，b）求K屬于Z 使得R=KQ。
K=kG ?[其中 K,G為Ep(a,b)上的點，k為小于n（n是點G的階）的整數(shù)]
不難發(fā)現(xiàn)，給定k和G，根據(jù)加法法則，計算K很容易；但給定K和G，求k就相對困難了。
這就是橢圓曲線加密算法采用的難題。
我們把點G稱為基點（base point），
k（k<n，n為基點g的階）稱為私有密鑰（privte key），
k稱為公開密鑰（public="" key)。<="" p="">
現(xiàn)在我們描述一個利用橢圓曲線進(jìn)行加密通信的過程：
1、用戶A選定一條橢圓曲線Ep(a,b)，并取橢圓曲線上一點，作為基點G。
2、用戶A選擇一個私有密鑰k，并生成公開密鑰K=kG。
3、用戶A將Ep(a,b)和點K，G傳給用戶B。
4、用戶B接到信息后 ，將待傳輸?shù)拿魑木幋a到Ep(a,b)上一點M（編碼方法很多，這里不作討論），并產(chǎn)生一個隨機(jī)整數(shù)r（r<n）。
5、用戶B計算點C1=M+rK；C2=rG。
6、用戶B將C1、C2傳給用戶A。
7、用戶A接到信息后，計算C1-kC2，結(jié)果就是點M。
因為C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M再對點M進(jìn)行解碼就可以得到明文。
在這個加密通信中，如果有一個偷窺者H ，他只能看到Ep(a,b)、K、G、C1、C2 而通過K、G 求k 或通過C2、G求r 都是相對困難的。因此，H無法得到A、B間傳送的明文信息。
設(shè)私鑰、公鑰分別為k、K，即K = kG，其中G為G點。
?
公鑰加密：
選擇隨機(jī)數(shù)r，將消息M生成密文C，該密文是一個點對，即：
C = {rG, M+rK}，其中K為公鑰
?
私鑰解密：
M + rK - k(rG) = M + r(kG) - k(rG) = M
其中k、K分別為私鑰、公鑰。
摘抄于橢圓曲線
?
總結(jié)
以上是生活随笔為你收集整理的公钥密码体制（RSA，椭圆曲线密码，ElGamal的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 序列密码体制（python随机数密码，R
- 下一篇： 认知理论与技术（hash函数，SHA，M