現代密碼學8.1--密碼學所涉及的數論和群論

• 數論
• • 素數和整除
  • 模運算
• 群論
• • 有限群
  • 群${\mathcal{Z}}_n^{?}$
  • 群同構和中國剩余定理
  • 使用中國剩余定理進行計算

博主正在學習INTRODUCTION TO MODERN CRYPTOGRAPHY (Second Edition) --Jonathan Katz, Yehuda Lindell，做一些筆記供自己回憶，如有錯誤請指正。整理成一個系列現代密碼學，方便檢索。

博主暫時跳過私鑰加密部分，直接進入公鑰加密，從第8章開始。

8.1節介紹了密碼學所涉及的數學知識：數論和群論。其中，數論在初等數論，群論在近世代數中有較為完整深入的介紹。所以此節只簡單概述數論和群論的定理，少數進行證明。

數論

素數和整除

• $a\in Z,b\in Z^{+}$，存在唯一的整數$q,r$使得$a=qb+r，0\le r\le b$。
• $?X,Y\in Z,s.t.Xa+Yb=gcd(a,b)$，$gcd(a,b)$是可以寫成$Xa+Yb$的最小正整數。
• 如果$c\mid ab$，且$gcd(a,c)=1$，那么$c\mid b$。可推出，如果$p$是素數，而且$p\mid ab$，那么$p\mid a$或$p\mid b$。(因為$p?a\to gcd(a,p)=1$)
• 如果$a\mid N,b\mid N,gcd(a,b)=1$，那么$ab\mid N$。

模運算

• 如果$a=qN+r$，那么$[a$ mod $N]=r$
• “規約后，加、減、乘”$?$“加、減、乘，再規約”；即如果$a=a^{\prime }$ mod $N,b=b^{\prime }$ mod $N$，則有$a+b=a^{\prime }+b^{\prime }$ mod $N,ab=a^{\prime }{b}^{\prime }$ mod $N$。
• 除法不一定能滿足，因為往往沒有定義。只有$b$在模$N$下是可逆的，即$?c\in \{1,2\dots \dots N?1\},s.t.bc=1$ mod $N$，才有$a/b=a^{\prime }/b^{\prime }=a^{\prime }c$ mod $N$。而且$b$在模$N$下是可逆的$?gcd(b,N)=1$。(根據擴展歐幾里得算法，$gcd(b,N)=1\to Xb+YN=1\to Xb=1$ mod $N\to X=b^{?1}$ mod $N$)
• 模$N$下的加、減、乘、逆、指數運算都可以在多項式時間內完成。

群論

有限群

• 密碼學中通常研究的是有限交換群
  • 封閉性、結合性、單位元、逆元、有限、交換性
• 有限群$G$的階$m=|G|$，則$?g\in G,g^m=1$。(根據循環群：$g$的階是$<g>$的階，根據拉格朗日定理：$<g>$的階是$|G|$的因子，則$g$的階是$|G|$的因子，即若$g$的階為$d$，則有$d\mid m$，即$g^m=g^{nd}=(g^d{)}^n=e^n=e$)
• 有限群$G$的階$m=|G|$，$?g\in G,?x\in Z$，有$g^x=g^{[xmodm]}$
• 有限群$G$的階$m=|G|$，$e\in Z$，函數$f_e:G\to G$定義為$f_e(g)=g^e$。如果$gcd(e,m)=1$，則$f$雙射；如果$d=e^{?1}$ mod $m$，那么$f_d$是$f_e$的逆。($f_d(f_e(g))=f_d(g^e)=(g^e{)}^d=g^{ed}=g^{[edmodm]}=g^1=g$，雙射通過函數的逆來證明)

群${\mathcal{Z}}_n^{?}$

對于$Z_n=\{0,1\dots \dots n?1\}$，"0"對于乘法運算沒有可逆元，把"0"除去，得到集合$\{1,2,\dots \dots n?1\}$，這個集合是否對于乘法運算滿足群的定義呢？需要判斷是否每個元素都有可逆元。

在“模運算”中闡述過：$b$在模$N$下是可逆的$?gcd(b,N)=1$，也就是只有$b$和$N$互素，在模$N$下$b$才有可逆元。那么我們取這么一個集合：$Z_N^{?}=\{b\in \{1,\dots N?1\}|gcd(b,N)=1\}$。

• $Z_N^{?}$在運算${?}_{modN}$下，是交換群。
• 如果$N=p$是素數，則$Z_N^{?}=\{1,2,\dots \dots N?1\},?(N)=|Z_N^{?}|=N?1$；
• 如果$N=pq$，$p、q$是素數，則對于$a\in \{1,2,\dots \dots N?1\}$，如果$p\mid a$或者$q\mid a$，則$gcd(a,N)=1$，也就是說滿足$p\mid a$或者$q\mid a$的$a$不在$Z_N^{?}$中。這樣的$a$有$\{p,2p,\dots \dots (q?1)p\}，\{q,2q,\dots \dots (p?1)q\}$，共有$p?1+q?1$個，那么$?(N)=N?1?(p?1+q?1)=pq?1?p+1?q+1=pq?p?q+1=(p?1)(q?1)$。
• $N={\prod }_i{p}_i^{e_i}$，$p_i$是素數，$e_i\ge 1$，則$?(N)={\prod }_i{p}_i^{e_i?1}(p_i?1)$。
• $?a\in Z_N^{?},a^{?(N)}=1$ mod $N$。

群同構和中國剩余定理

• 群$G$的運算是${°}_G$，群$H$的運算是${°}_H$，如果滿足以下兩個條件：
  • $f$是雙射
  • $?g_1,g_2\in G$，有$f(g_1{°}_G{g}_2)=f(g_1){°}_{H}f(g_2)$

那么函數$f:G\to H$是$G$到$H$的同構/isomorphism，寫作$G?H$

• 如果存在$G$到$H$的同構$f$，也一定存在$H$到$G$的同構$f^{?1}$，但有可能地，$f$是可高效計算的，然而$f^{?1}$不能。
• $G$和$H$的直積：寫作$G\times H,?(g,h)\in G\times H,g\in G,h\in H,$ 運算$°$的定義是：$(g,h)°(g^{\prime },h^{\prime })=(g{°}_G{g}^{\prime },h{°}_H{h}^{\prime })$。
• 中國剩余定理：$N=pq$，$p、q$是素數，則$Z_N?Z_p\times Z_q,Z_N^{?}?Z_p^{?}\times Z_q^{?}$，其中同構函數$f$的定義域是$x\in \{0,\dots \dots N?1\}$，值域是$(x_p,x_q),x_p\in \{0,\dots \dots p?1\},x_q\in \{0,\dots \dots q?1\}$，$f(x)=([x$ mod $p],[x$ mod $q])$。
  證明：
  • $f$是雙射
    • $f$是單射
      如果$f(x)=(x_p,x_q)=f(x^{\prime })$，那么$x=x^{\prime }=x_p$ mod $p,x=x^{\prime }=x_q$ mod $q$，那么$p\mid x?x^{\prime },q\mid x?x^{\prime },$又因為$gcd(p,q)=1$，所以$pq\mid x?x^{\prime }$，即$N\mid x?x^{\prime },x=x^{\prime }$ mod $N$。
    • $f$是滿射
      因為函數的值域大小應該是$p?q$，$|Z_N|=N=p?q=|Z_p|?|Z_q|$，所以$f$是滿射。
  • 定義群$Z_N$中的運算是"${+}_N$"，直積$Z_p\times Z_q$的運算是"$°$"，$?x_1,x_2\in Z_N$，有$f(x_1{+}_N{x}_2)=f(x_1)°f(x_2)$
    $f(x_1{+}_N{x}_2)=([x_1{+}_N{x}_2$ mod $p],[x_1{+}_N{x}_2$ mod $q])$
    $=([x_1{+}_p{x}_2$ mod $p],[x_1{+}_q{x}_2$ mod $q])$
    $=([x_1+x_2$ mod $p],[x_1+x_2$ mod $q])$
    $=([x_1$ mod $p],[x_1$ mod $q])°([x_2$ mod $p],[x_2$ mod $q])$
    $=f(x_1)°f(x_2)$

使用中國剩余定理進行計算

• 函數$f$是群$G\to H$的同構，$G$的運算是${°}_G$，$H$的運算是${°}_H$。$?g_1,g_2\in G$，當計算$g=g_1{°}_G{g}_2$時，可以通過以下3步來計算(先分別求函數值，然后在同構群上計算，得到結果再映射到原群)：
  • $h_1=f(g_1),h_2=f(g_2)$
  • $h=h_1{°}_H{h}_2$
  • $g=f^{?1}(h)$
• 直積里的元素$(x_p,x_q)$可以被寫成$(x_p,x_q)=x_p?(1,0)+x_q?(0,1)$，$1_p?(1,0),1_q?(0,1)$，也就是：$(x_p,x_q)?[(x_p?1_p+x_q?1_q)$ mod $N]$

總結

以上是生活随笔為你收集整理的现代密码学8.1--密码学所涉及的数论和群论的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。