1、橢圓曲線加密算法（ECC）,Tsinghua Carelife,假如平行線在很遠(yuǎn)很遠(yuǎn)的地方相交了？即平行線相交于無窮遠(yuǎn)點P： 無窮遠(yuǎn)點與平常點 與無窮遠(yuǎn)點相區(qū)別把原來平面上的點叫做平常點 由此出現(xiàn)了射影坐標(biāo)系 ,從平行線談起,射影平面坐標(biāo)系是對普通平面直角坐標(biāo)系的擴(kuò)展： 增加無窮遠(yuǎn)點P 構(gòu)造方法： 對普通平面直角坐標(biāo)系上的點A的坐標(biāo)（x , y）做如下改造：令x=X/Z ，y=Y/Z（Z0）；則A點可以表示為（X:Y:Z）。變成了有三個參量的坐標(biāo)點，這就對平面上的點建立了一個射影平面坐標(biāo)體系。,射影平面坐標(biāo)系,一條橢圓曲線是在射影平面上滿足方程： 2 + 1 + 3 2 = 3 + 2 2 +

2、 4 2 + 6 3 Weierstrass方程 的所有點的集合，且曲線上的每個點都是非奇異的 橢圓曲線上有一個無窮遠(yuǎn)點O（0:1:0）（滿足Weierstrass方程） 橢圓曲線的形狀不是橢圓的：,橢圓曲線,設(shè)x=X/Z ，y=Y/Z代入Weierstrass方程得到： 2 + 1 + 3 = 3 + 2 2 + 4 + 6 上述方程加上無窮遠(yuǎn)點O構(gòu)成了平面上的橢圓曲線 橢圓曲線上的切線斜率 =(3 2 +2 2 + 4 1 ) /(2+ 1 + 3 ) 運算法則：任意取橢圓曲線上兩點P、Q （若P、Q兩點重合，則做P點的切線）做直線交于橢圓曲線的另一點，過做y軸的平行線交于R。規(guī)定: +=

3、,平面上的橢圓曲線,前面所述的橢圓曲線是連續(xù)的，并不適合用于加密；必須把橢圓曲線變成離散的點 有限域Fp上： 有限域Fp中只有p（p為素數(shù)）個元素0,1,2 p-2,p-1； 加法(a + b)法則： a + b c (mod p) 乘法(a b)法則是：a b c (mod p) 除法(a b)法則： a / b c (mod p) 單位元是1，零元是 0 將橢圓曲線定義到有限域Fp上就變成了離散的橢圓曲線,從連續(xù)到離散,將 2 = 3 + 2 + 這條曲線定義在Fp上： 選擇兩個滿足下列條件的小于p(p為素數(shù))的非負(fù)整數(shù)a、b4 3 +27 2 0 則滿足下列方程的所有點(x , y)，再

4、加上無窮遠(yuǎn)點O 構(gòu)成一條橢圓曲線: 2 = 3 + 2 + ( ) 其中 x, y屬于0到p-1間的整數(shù)，并將這條橢圓曲線記為Ep(a , b),從連續(xù)到離散-怎么做, 2 = 3 + 2 +1 23 的圖像：,對于橢圓曲線上的某個點P，存在一個最小的數(shù)n，使得=，那么n就是P點的階。,橢圓曲線的點的階,終于進(jìn)入正題了,加密/解密 簽名 & 生成軟件序列號,橢圓曲線能干什么？,公開密鑰算法總是要基于一個數(shù)學(xué)上的難題。 RSA ：給定兩個素數(shù)p、q 很容易相乘得到n，而對n進(jìn)行因式分解卻相對困難。 那橢圓曲線上有什么難題呢？ 考慮K=kG ，其中 K,G為Ep(a , b)上的點，k為小于n（n

5、是點G的階）的整數(shù)。 給定k和G，根據(jù)加法法則，計算K很容易；但給定K和G，求k就相對困難了。 點G：基點（base point） k（kn，n為基點G的階）：私有密鑰（private key） K：公有密鑰（public key),橢圓曲線上的加密/解密-算法難題,用戶A選定一條橢圓曲線Ep(a , b)，并取橢圓曲線上一點，作為基點G。 用戶A選擇一個私有密鑰k，并生成公開密鑰=。 用戶A將Ep(a , b)和點K，G傳給用戶B。 用戶B接到信息后 ，將待傳輸?shù)拿魑木幋a到Ep(a , b)上一點M（編碼方法很多，這里不作討論），并產(chǎn)生一個隨機(jī)整數(shù)r（rn）。 用戶B計算點1=+；2=。 用

6、戶B將C1、C2傳給用戶A。 用戶A接到信息后，計算1 2，結(jié)果就是點M。12=+()=+()= 再對點M進(jìn)行解碼就可以得到明文。,橢圓曲線上的加密/解密-過程,上圖是ECC加密/解密的圖示，從中可以看到如果有一個偷窺者H ，他只能看到Ep(a , b)、K、G、C1、C2 而通過K、G 求k 或通過C2、G求r 都是相對困難的。因此，H無法得到A、B間傳送的明文信息。,橢圓曲線上的加密/解密-過程,描述一條Fp上的橢圓曲線，常用到六個參量： T=(p , a , b , G , n , h) p 、a 、b 用來確定一條橢圓曲線，G為基點，n為點G的階，h 是橢圓曲線上所有點的個數(shù)m與n相除

7、的整數(shù)部分 參量值一般要求滿足以下幾個條件： p 越大越安全，但越大，計算速度會變慢，200位左右可以滿足一般安全要求 1 ( )，120 4 3 + 27 2 0 ( ) 為素數(shù) 4,橢圓曲線上的加密/解密-參數(shù)選擇,簽名過程： 選擇一條橢圓曲線Ep(a , b)，和基點G； 選擇私有密鑰k（kn，n為G的階），利用基點G計算公開密鑰 =； 產(chǎn)生一個隨機(jī)整數(shù)r（rn），計算點=； 計算SHA值，即=( , , )； 計算 ( )； 將sn和Hash作為用戶名username的序列號,橢圓曲線上的簽名-軟件注冊保護(hù),驗證過程（軟件中存有橢圓曲線Ep(a , b)，和基點G，公開密鑰K）： 從用

8、戶輸入的序列號中，提取sn以及Hash； 計算點+ ( )，如果sn、Hash正確，其值等于軟件作者簽名過程中點R(x , y)的坐標(biāo)，因為( )所以+=()+=+=+= = 計算=( , , )； 如果H=Hash 則注冊成功。如果H Hash ，則注冊失敗。,橢圓曲線上的簽名-軟件注冊保護(hù),簡單對比一下兩個過程： 作者簽名用到了：橢圓曲線Ep(a , b)，基點G，私有密鑰k，及隨機(jī)數(shù)r。 軟件驗證用到了：橢圓曲線Ep(a , b)，基點G，公開密鑰K。,橢圓曲線上的簽名-軟件注冊保護(hù),Microsoft的產(chǎn)品安裝Key為25位字符，這25位字符是如何得出來的呢？下面將一一敘述,ECC簽名

9、應(yīng)用-Microsoft軟件序列號,Base24： 這25個字符實際是114bits的數(shù)據(jù)用Base24進(jìn)行UUCode后的結(jié)果，做為安裝Key，這個Base必須絕對避免誤認(rèn)，所以Microsoft選擇了以下這24個字符做為UUCode的Base： BCDFGHJKMPQRTVWXY2346789,Microsoft軟件序列號-BASE,上頁所述的114位數(shù)據(jù)按Intel高位在后的格式表示如下： Flag： 不明標(biāo)志，目前所見的各類Key中這一位總是為0。 Serial：用戶序列號，轉(zhuǎn)成十進(jìn)制表示為AAAABBBBBB，對應(yīng)顯示為： 零售版： xxxxx-AAA-BBBBBBx-xxxxx O

10、EM版： xxxxx-OEM-0AAAABx-BBBBB 以上31bits總稱為Data，是CDKey中的基本部分。 Hash：Data經(jīng)特定處理得到的結(jié)果,既ECC中的hash Sign：Hash值的橢圓曲線簽名，既ECC中的sn,Microsoft軟件序列號-114BITS,Microsoft用了如下形式的橢圓曲線： 2 = 3 + 2 + 然后按照上述的簽名過程生成Sign, Hash： 任選整數(shù)rq，求點(,)=； 對Data, rx, ry共100個字節(jié)求SHA-1，取結(jié)果中的28位得Hash； 求 = ( )； 把Flag, Data, Hash, Sign四個數(shù)組合后UUCode

11、得25位CDKey。 驗證CDKey時： 把25位CDKey先UUDecode再拆分后得到Data、Hash、Sign； 求點(, ) = + ( )； 將Data, rx, ry共100個字節(jié)求SHA-1，取結(jié)果中的28位得Hash*； 如果 = ，則該CDKey為有效Key。,Microsoft軟件序列號-橢圓曲線,微軟的序列號能不能被輕易破解呢？ 答案是肯定的 注冊機(jī)！ 要破解CDKey的生成算法，只要求出k即可。微軟公鑰中，p是一個384 bits的質(zhì)數(shù)，求k的計算量為( 2 192 ) ，但是 回顧 = ( )，這里盡管p是個很大的數(shù)，但是Sign被限制死了在55bits，也就是q最大不超過56bits，而，所以計算k的計算量只要( 2 28 )( 10 8.5 )！,ECC加密破譯 傳說中的注冊機(jī),優(yōu)點 安全性能更高 160位ECC與1024