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