G(x,y) :: y2 = x3 + a*x + b 其中 4a3 + 27b2 != 0
P Q R 是在橢圓曲線的3個點, 並且都同在一個直線上:
P + Q + R = O (橢圓曲線零點)
上式並不是算術運算的加法, 只是一個術語.
因此 P + Q = - R
負數代表的是鏡像(mirror), 因為橢圓曲線對於 Y 軸而言是一個對稱曲線, 因此可以想像成 R 與 -R 是分別在 Y 正負軸上面等距離的點
已知 P=G(x1,y1), Q=G(x2,y2) 求解 R=G(x3,y3), 帶入上述橢圓曲線G(x,y)及直線方程式L(x,y), 經由係數比較就可得出 x3 = s2 - x2 - x1的關係式
曲線 G(x,y) :: y2 = x3 + a*x + b
直線 L(x, y) :: y = s*x + c
條件(一) 當 P != Q 時, 使用一般直線斜率 s 的加法運算求出 R:
s = ( y2 - y1 ) / (x2 - x1 )
x3 = s2 - x2 - x1
y3 = s*(x2-x3) - y2
條件(二) 當 P == Q 時, x1=x2, 且 y1=y2, 運算斜率 s 時, 導致除零的錯誤, 要改用雙倍切線斜率運算:
s = ( 3 *x12 +a )/ ( 2y1)
x3 = s2 - 2x1
y3 = s*(x1 -x3) - y1
條件(三) n(n>1)倍G運算, 使用雙倍運算及累加運算(DAA),演算法用2進位法:
(1) 找出 n 當中最高位元是 1 時, 並開始初始化 R
R = G ; // 初始化 R 等於 G(x,y)
k = 要處理的位元數
(2) while( k-- > 0 ) { // 累進運算
R= optDouble(R);// 先將點作兩倍運算, 用上述條件(二)的雙倍運算
if( n.testBit(k) ) R=optINC(R, G); //當n測試到位元 1 時執行上述條件(一)的加法運算
} // 重複步驟2直到 k = 0 為止
ECC 的對稱加密通信演算法:
當有兩端要通訊時, 兩邊各選擇一個整數(通常是大整數)當成私鑰, 將它乘上 G就形成 public key例如 pubA = a * G, pubB =b * G, 兩邊交換後, A 將收到的 pubB 乘上自己的私鑰,B收到pubA也乘上自己的私鑰, 結果 a*pubB = a*b*G = b *a * G = b * pubA 就是共用金鑰( a*b=b*a)所對應 ECC 上的一點, 把該點的資訊當作 AES 加解密之密碼, 傳輸的資料經 AES 加密過, 對外人來說是一串亂碼, 就算中間 pubA 或 pubB 被擷取, 也很難算出 a, b , a*b 來. 因為 a, b 對局外人來講是未知(大整)數, 只有通信方兩端知道自己的私鑰(a, b)及共同金鑰(ab)所對應的點ab *G(x,y), 實際上兩邊通信方也很難推算出共用金鑰 ab, 因此 ECC 可以讓通信保密
實際上觀念很簡單, 使用小整數來說:
1. Alice 與 Bob 共同約定使用相同ECC編碼,橢圓曲線(EC)上的點假設是 G(x,y)當作初始點.
2. Alice 使用 3 當作密鑰, Alice 將 3*G(x,y) 映設到新的橢圓曲線上一點假設它是 G(xp,yp), 實際上G(xp,yp)就是 Alice 的公開鑰匙, 將它傳給 Bob.
3. Bob 使用 5 當作密鑰, 並將 5*G(x,y) 映設到新的橢圓曲線上一點假設它是 G(xq,yq), 實際上G(xq,yq)就是 Bob 的公開鑰匙, 將它傳給 Alice.
4. Alice 和 Bob 分別用自己的私鑰乘上所收到點的資訊並重新映設到新的橢圓曲線上一點,例如 Alice收到G(xq,yq), 而 Bob收到G(xp,yp), 實際上乘上自己的鑰匙後得到:
Alice: 3*G(xq,yq) = 3*5*G(x,y) = 15*G(x,y)
Bob: 5*G(xp,yp) = 5*3*G(x,y) = 15*G(x,y)
因此 3*5 稱為可以稱之共同金鑰, 而15*G(x,y) 是 ECC 上的一個點, 雖然兩邊很難算出 15 這個數字, 但可以利用該點共同座標當作訊息替後續要傳送的資料加以編碼(例如用 SHA-256 轉成亂數當成 AES-256 的密碼將訊息編碼). 重頭到尾, 外人無法得知 3, 5, 15 這個數字, 外人只能察覺到兩人在交換 ECC 上點的資訊(公開鑰匙), 如果要反推 3,5,15, 便需要從頭 G(x,y)一一去嘗試, 一旦試到 15 才能找到答案.但密碼學裡很重要的觀念是'數'的量很龐大,當我們使用超級大整數時例如 256 bit來將私鑰編碼時就有 2的256次方個組合, 這根本是一個無法想像的數字.而 ECC 點的運算,必需從頭到尾一一加以運算, 就算知道起點和終點,仍然很難分解出該私鑰點所對應的之相對位置. 更遑論是大整數的運算了. 當駭客無法破解密碼時,唯一可以用的方法是暴力窮舉法一一測試, 但由於是大整數的關係, 要一直不斷嘗試, 真的非常困難. 這就是 ECC 相當安全的重要原因.
ECC 使用的 ElGamal 非對稱加解密通信演算法:
1. 兩人約定用 ECC 的點 G(x, y) 當作通訊協定
2. Alice 挑選一個私鑰 a, 算出 ECC 上的一點座標 PA 傳給 Bob, PA 就是 Alice 公鑰:
座標 PA:: a*G(x, y) = G(xa, ya)
3. Bob 收到後, 也隨機挑選一個密鑰 b, 算出 ECC 上的一點當自己的公鑰 PB, 同時把要加密的文件訊息 m 用 Alice 的公鑰編碼成 R, 為了能適用 ECC 的加法運算, m 必須映射到橢圓曲線上, 有一種方式是將 m 當成 x 帶入曲線公式解出 y 得出座標(xm,ym), 再計算編碼過的座標 R = m + b*PA, 連同 PB 一起回傳給 Alice, 讓她用私鑰將 m 解讀出來, 通信過程就算公開了 G(xa,ya) 與 G(xb,yb) 的座標點, 也很難猜到 G(xab,yab) 的座標點 , 因此外人解出 m 的機會很渺茫, 只有兩邊通信方知道共用金鑰 ab 座標點是G(xab, yab), 直接卸下(減掉)該因子就能快速還原文件訊息 m:
座標 PB:: b*G(x, y) = G(xb, yb)
座標 R:: m + b*PA(x, y) = m + G(xab, yab) = m + G(xba, yba)
4. Alice 收到 PB, R後, 就用自己的私鑰 a 去計算 R - a*PB 得出 m
座標 (R - a*PB) :: [m + G(xab,yab)] - G(xab,yab) = m + O = m
5. ECC 的鏡射點相加是為零點 O:
- G(xab, yab) + G(xab, yab) = O
6. 鏡射點, 實際上只要反轉 y 座標為負值:
- G(xab, yab) = G(xab, - yab)
m = R - G(xab, yab) = R + G(xab, - yab) 利用ECC 的加法運算就可算出座標值 (xm, ym), 其中的 xm 就是解出來的訊息
ECC 的對稱加密通信演算法:
當有兩端要通訊時, 兩邊各選擇一個整數(通常是大整數)當成私鑰, 將它乘上 G就形成 public key例如 pubA = a * G, pubB =b * G, 兩邊交換後, A 將收到的 pubB 乘上自己的私鑰,B收到pubA也乘上自己的私鑰, 結果 a*pubB = a*b*G = b *a * G = b * pubA 就是共用金鑰( a*b=b*a)所對應 ECC 上的一點, 把該點的資訊當作 AES 加解密之密碼, 傳輸的資料經 AES 加密過, 對外人來說是一串亂碼, 就算中間 pubA 或 pubB 被擷取, 也很難算出 a, b , a*b 來. 因為 a, b 對局外人來講是未知(大整)數, 只有通信方兩端知道自己的私鑰(a, b)及共同金鑰(ab)所對應的點ab *G(x,y), 實際上兩邊通信方也很難推算出共用金鑰 ab, 因此 ECC 可以讓通信保密
實際上觀念很簡單, 使用小整數來說:
1. Alice 與 Bob 共同約定使用相同ECC編碼,橢圓曲線(EC)上的點假設是 G(x,y)當作初始點.
2. Alice 使用 3 當作密鑰, Alice 將 3*G(x,y) 映設到新的橢圓曲線上一點假設它是 G(xp,yp), 實際上G(xp,yp)就是 Alice 的公開鑰匙, 將它傳給 Bob.
3. Bob 使用 5 當作密鑰, 並將 5*G(x,y) 映設到新的橢圓曲線上一點假設它是 G(xq,yq), 實際上G(xq,yq)就是 Bob 的公開鑰匙, 將它傳給 Alice.
4. Alice 和 Bob 分別用自己的私鑰乘上所收到點的資訊並重新映設到新的橢圓曲線上一點,例如 Alice收到G(xq,yq), 而 Bob收到G(xp,yp), 實際上乘上自己的鑰匙後得到:
Alice: 3*G(xq,yq) = 3*5*G(x,y) = 15*G(x,y)
Bob: 5*G(xp,yp) = 5*3*G(x,y) = 15*G(x,y)
因此 3*5 稱為可以稱之共同金鑰, 而15*G(x,y) 是 ECC 上的一個點, 雖然兩邊很難算出 15 這個數字, 但可以利用該點共同座標當作訊息替後續要傳送的資料加以編碼(例如用 SHA-256 轉成亂數當成 AES-256 的密碼將訊息編碼). 重頭到尾, 外人無法得知 3, 5, 15 這個數字, 外人只能察覺到兩人在交換 ECC 上點的資訊(公開鑰匙), 如果要反推 3,5,15, 便需要從頭 G(x,y)一一去嘗試, 一旦試到 15 才能找到答案.但密碼學裡很重要的觀念是'數'的量很龐大,當我們使用超級大整數時例如 256 bit來將私鑰編碼時就有 2的256次方個組合, 這根本是一個無法想像的數字.而 ECC 點的運算,必需從頭到尾一一加以運算, 就算知道起點和終點,仍然很難分解出該私鑰點所對應的之相對位置. 更遑論是大整數的運算了. 當駭客無法破解密碼時,唯一可以用的方法是暴力窮舉法一一測試, 但由於是大整數的關係, 要一直不斷嘗試, 真的非常困難. 這就是 ECC 相當安全的重要原因.
ECC 使用的 ElGamal 非對稱加解密通信演算法:
1. 兩人約定用 ECC 的點 G(x, y) 當作通訊協定
2. Alice 挑選一個私鑰 a, 算出 ECC 上的一點座標 PA 傳給 Bob, PA 就是 Alice 公鑰:
座標 PA:: a*G(x, y) = G(xa, ya)
3. Bob 收到後, 也隨機挑選一個密鑰 b, 算出 ECC 上的一點當自己的公鑰 PB, 同時把要加密的文件訊息 m 用 Alice 的公鑰編碼成 R, 為了能適用 ECC 的加法運算, m 必須映射到橢圓曲線上, 有一種方式是將 m 當成 x 帶入曲線公式解出 y 得出座標(xm,ym), 再計算編碼過的座標 R = m + b*PA, 連同 PB 一起回傳給 Alice, 讓她用私鑰將 m 解讀出來, 通信過程就算公開了 G(xa,ya) 與 G(xb,yb) 的座標點, 也很難猜到 G(xab,yab) 的座標點 , 因此外人解出 m 的機會很渺茫, 只有兩邊通信方知道共用金鑰 ab 座標點是G(xab, yab), 直接卸下(減掉)該因子就能快速還原文件訊息 m:
座標 PB:: b*G(x, y) = G(xb, yb)
座標 R:: m + b*PA(x, y) = m + G(xab, yab) = m + G(xba, yba)
4. Alice 收到 PB, R後, 就用自己的私鑰 a 去計算 R - a*PB 得出 m
座標 (R - a*PB) :: [m + G(xab,yab)] - G(xab,yab) = m + O = m
5. ECC 的鏡射點相加是為零點 O:
- G(xab, yab) + G(xab, yab) = O
6. 鏡射點, 實際上只要反轉 y 座標為負值:
- G(xab, yab) = G(xab, - yab)
m = R - G(xab, yab) = R + G(xab, - yab) 利用ECC 的加法運算就可算出座標值 (xm, ym), 其中的 xm 就是解出來的訊息
沒有留言:
張貼留言