理解"質數有限場域倍乘群的橢圓曲線加密運算"

質數(prime number)有限場域(finite field)倍乘群(multiplicative group),用集合符號表示該質數形成的場域: Zp* = {x | 0 < x < p} 其中 x 是整數, p 是質數
1. 用 mod p (以質數當除數取餘數)的整數經過四則(+-*÷)運算後將映射回質數場域裏面.
2. 場域的質數 p 及原點 0, 不包含在該場域裏面,但在運算中會出現,分別是場域的上限及下限.
3. 場域內的整數 x 與該質數 p 互質,也就除了 1 以外無其它公因數:  GCD(x, p) = 1
4. 假設φ(p)是該場域內與 p 互質的個數,根據 Euler 定理:
              x^φ(p) mod p = 1         其中  φ(p) = p-1  就是集合裏面{ x }與 p 互質的個數
場域內 Zp* 所有整數 x 共有 p-1 個,且都與 p 互質.當 x 倍乘 p-1 次,以 p 當除數再取餘數運算將等於 1
              x^p-1 mod p = 1     ---(1)
兩邊同時乘上 x 就可以得出:
              x^p mod p = x         --- (2)
也就是說場域內的整數 x 倍乘 p 次後,再用 mod p 取餘數就會映射成(還原回)整數本身.這就是為何 ECC 會使用質數的原因? 因為該整數群裡(x)的模倒數(y)可以很容易計算出來.
           x * y  mod p = 1       --- (3)
將第(1)式分解 x
           x^p-1 mod = x * x^p-2 mod p    ---(4)         
比較(3)(4)式得出 x 的模倒數
           y = x^p-2 mod p
也就是說整數的模倒數與質數的關係式是將 x 倍乘 p-2 次後,再以 p 當除數取餘數:
           x^-1  mod p = x modinv p  =   x^p-2 mod p
ECC 用大整數當私鑰,曲線上的點當基底,兩個乘起來形成公鑰後,仍還是曲線上的一點,再指定一個質數 p 去做運算,形成一個整數場域.所有座標內的數值也都被限制在該場域內(mod p).由於曲線上兩點加法產生曲線上另外一點的特性.因此複予了它可以用數學運算法則,當使用通訊協定來加密或解密鑰匙,雖然公開了公鑰及質數 p 還有所使用的橢圓曲線,卻不影響到私鑰的保密性,因為解密出私鑰須耗費相當大的時間或空間(成本).給定一個橢圓曲線的點(公鑰)及質數,破解私鑰,也就是所謂的 ECDLP (橢圓曲線離散對數求解),或許有人認為可以破解 ECDLP,當使用的密碼很小的時候,例如 15, 運算點連加15次就可以找到破解點了(但這只是一種暴力破解法),當密碼是2的 128 次方(也就說 128 個位元)呢?"只要"(暴力)嘗試最多 2^128-1 就一定可以找破解點.但是這個暴力的方法恐怕是好幾?年的事(時間),仔細想一下 2 的 128 次方是一個多大的整數呢?可以用 python 稍微感受一下,它支援大整數,大整數的次方用 ** 來加以運算:
a=2**128
340282366920938463463374607431768211456L
乍看之下好像沒什麼,如果超級電腦每秒運算1百萬個百萬個百萬個百萬指令  = 1e6*1e6*1e6*1e6 = 10²⁴(10的24次方)指令來算,一年共 365*24*60*60 秒,所以一年來運算了指令總共
b=365*24*60*60*1e24
3.1536e+31

將a(等於a¹²⁸)除以 b(等於花一整年的指令數)=花費數(年):

a/b

10790283.070806015

取整數看就好了,總共要花掉 10790283 年的時間啊!假如將密鑰位元數提升一倍,也就是256位元組變成:
c=2**256
c/b
3.671743063080803e+45
一個天文數字 10 的 45 次方,嚇死人!運算時間隨著密碼長度成指數性增加,一旦保密性不夠,再加大密碼的位元數就能因應了!又或者用多部超級電腦同時進行(空間)呢?那恐怕需要計算一下需用多少部電腦來運作,但這樣花的值得嗎?如果不用暴力破解,那就要想辦法解決 ECDLP, 但目前為止還無有效方法可用.反而用亂數的方式隨便猜,機率極低卻有可能猜中,想要破解 ECC 密碼,門都沒有.如果故意放了後門,那就另當別論了.