1密碼學中的數(shù)學知識
密碼學算法中很多地方都有提到群，域，有限域等概念，如RSA,ECC,AES中均有提到群操作，有限域等內(nèi)容，一直對這塊內(nèi)容比較迷糊，專門來梳理一下。
2群(Group)
群指的是元素集合G及G內(nèi)任意兩個元素的聯(lián)合操作。群的部分公理如下，
1）單位元：Identify Element，在群內(nèi)存在一個元素e，使得群中任意元素a滿足ae=ea=a成立。單位元與群內(nèi)其他元素結(jié)合，不會改變那些元素。
2.）逆元：對于每個屬于群G的元素a，都存在一個元素a^(-1)，使得a*a^(-1)=1。a^(-1)就是a的逆元，逆元也屬于群G。
3域(Field)
域是擁有特定元素集合。如實數(shù)集合R是一個域，每個實數(shù)a都有一個逆元。在密碼學中，提到最多的是有限域，有限域就是指有限個元素的集合，域內(nèi)所包含的元素稱為這個域的階。常用的2個域是素域GF(p)和擴展域GF(2^m)。
4素域(Prime Field)
假設p是一個素數(shù)(prime)，則素域表示為GF(p)。在素域GF(p)內(nèi)所有的非零元素都存在逆元，在GF(p)內(nèi)的加法和乘法都要做模p操作(mod p將計算結(jié)果限制在有限域內(nèi))，即，
加法定義：a+b=(a+b)mod p
乘法定義：a•b=(a•b)mod p
素域GF內(nèi)，加法單位元是0，乘法單位元是1。
素域內(nèi)的加法逆元定義為a+(-a)=0 mod p。素域內(nèi)的任何一個非零元素a的乘法逆元定義為a*a^(-1)=1 mod p。
例子1有限域GF(5)
如對于有限域GF(5)=,在此有限域內(nèi)的加法和乘法結(jié)果，以及域內(nèi)加法逆元和乘法逆元。如下圖，計算的理解參考圖中標注，其中取模的作用就是將計算結(jié)果限制在有限域GF(5)之內(nèi)。
例子2有限域GF(2)
GF(2)是一個最小的有限域，也是一個比較好玩的域，GF(2)=,在此域內(nèi)的運算都是通過mod 2實現(xiàn)的。
GF(2)的加法，即模2加法，域異或(XOR)門等價。GF(2)乘法與邏輯與(AND)門等價。GF(2)域?qū)ES而言至關重要。
5擴展域GF(2^m)
又叫二元擴域，m>1的域稱為擴展域。在擴展域GF(2^m)中，元素使用多項式表示，多項式的系數(shù)為GF(2)中的元素。
擴展域GF(2^m)內(nèi)，零元0用全零比特串表示，乘法單位元1用比特串(00...001)表示。
AES中使用域GF(2^8)，在域內(nèi)的數(shù)字表示為，A(x)=a7 x^7+...+a1 x+a0，其中系數(shù)a0~a7均屬于GF(2)=。在GF(2^8)中共256個元素，因此有256個對應的多項式。
擴展域中的加減法
《SM2橢圓曲線密碼學中的定義》擴展域內(nèi)兩個域元素加法定義為比特串按比特異或運算。如下圖就是將x冪次相同的系數(shù)進行加減法操作，
按照對應系數(shù)做異或運算，因此計算結(jié)果中消去了x^4和x^0項。
擴展域中的乘法
擴展域內(nèi)乘法定義為a•b=a(x)b(x)mod f(x)，其中f(x)稱為不可約多項式，擴展域乘法對不可約多項式取模。
什么是不可約多項式呢？
類似于素數(shù)p，不能夠進行因式的多項式稱為不可約多項式。如多項式x^4+x^3+x+1是可約的，因為x^4+x^3+x+1=(x^2+x+1)(x^2+1)，可以做因式分解。AES使用的不可約多項式為x^8+x^4+x^3+x+1。
乘法舉例：
計算GF(4)中A(x)=x^3+x1和B(x)=x^2+x相乘，不可約多項式P(x)=x^4+x+1。
首先計算A(x)x B(x)=x^5+x^3+x^2+x，然后對P(x)取模，可用豎式乘法計算，
余數(shù)x^3即為乘法結(jié)果。
擴展域內(nèi)的逆操作
給定有限域GF(2^m)和不可約簡的多項式P(x)，任何一個屬于GF(2^m)內(nèi)的元素A的逆元定義為:A^(-1)*A=1 mod P(x)。A^(-1)就是A的乘法逆元。計算乘法逆元一般使用擴展歐幾里得算法。
6 AES中的S-Box
AES加解密算法中SubBytes字節(jié)替換中使用的S-Box盒中包含了GF(8)模P(x)=x^8+x^4+x^3+x+1()的逆元。
由于計算逆元比較復雜，因此AES算法中直接給出了S-Box和逆S-Box(可參考FIPS 197)，加解密過程中通過查表法使用。
對S-Box具體計算感興趣的小伙伴可參考[4]的6.3.1小節(jié)，或者參考[5]的鏈接，此處不給出計算過程。
S-Box
Inverse S-Box
7參考
《SM2橢圓曲線公鑰密碼學》第一章.
Understanding Cryptography-A Textbook for Students and Practitioners，Christof paar.
FIPS PUB 197 Specification for the Advanced Encryption Standard(AES),NIST.
Cryptography and Network Security,Principle and Practice,7th Edition
https://blog.csdn.net/u011516178/article/details/81221646
