RSA非對稱加密演算法 (二) 數學理論

這篇紀錄一些RSA運算時要用到的數學定理和我比較能夠理解的證明

同餘理論

定義
對於整數 a,b，若正整數 m 能整除 a-b ，以符號表示就是 m | (a-b) ，則稱為 a,b 對於模 m 同餘，可以寫成
`a-=b(mod m)`

由此定義可以推導出
`a-=b (mod m) <=> a mod m = b mod m`

證明1：`a ≡ b (mod m) ⇒ a mod m = b mod m`
`a-=b (mod m) => a mod m = b mod m`
令 `a=mp+r , b=mq+s` (r,s為餘數)
`a -= b (mod m)`
`a-=b(mod m)`
`=> m |(a-b)`
`=> m | m(p-q)+(r-s)`
`=> m |(r-s)`

r,s是除以m的餘數，`0 <= r,s < m` `=>0 <= |r-s| < m ` `=>r-s =0`
`=>r=s 得證`

證明2：`a mod m = b mod m ⇒ a -= b (mod m)`
a,b 除以 m 餘數相同
令 `a=mp+r,b=mq+r`
`=>a-b = m(p-q)`
`=> m | m(p-q)`
`=> m | a-b`
`=> a -= b (mod m) 得證`

由證明1,2得知`a-=b (mod m) <=> a mod m = b mod m`

(*) 也有看過將 a ≡ b (mod m)定義成 a,b 除以m餘數相同，再由此定義去推導出
`a -= b (mod m) <=> m |(a-b)`

同餘的性質

1.反身性(reflexive) `a -= a (mod m)`
2.對稱姓(symmetric) `a -= b (mod m) => b -= a (mod m)`
3.遞移性(transitive) `a -= b (mod m), b -= c (mod m) => a -= c (mod m)`
4.加姓 `a -= b (mod m), c -= d (mod m) => a+c -= b+d (mod m)`
5.乘性 `a -= b (mod m), c -= d (mod m) => ac -= bd (mod m)`
6.冪性 `a -= b (mod m),k>=0 => a^k -= b^k (mod m)`
7.
\(
\left. \begin{matrix} a \equiv b \pmod{m} \\
n|m
\end{matrix} \right\}
\Rightarrow a \equiv b \pmod n
\)
8.
\(
\left.
\begin{matrix}
a \equiv b \pmod{m_1} \\
a \equiv b \pmod{m_2} \\
\vdots \\
a \equiv b \pmod{m_n} \\
(n \ge 2)
\end{matrix} \right\}
\Rightarrow a \equiv b \pmod{lcm(m_1,m_2,\cdots,m_n)}
\)

證明
1.反身性
`m|(a-a)`
`=>a -= a (mod m)`

2.對稱姓
`m|(a-b)`
`令a-b=mk`
`=>b-a=-mk`
`=>m|-mk`
`=>m|(b-a)`
`=>b -= a (mod m)`

3.遞移性
`a -= b (mod m)`
`=>m|(a-b),令a-b=p m`
同理，令`b-c=qm`
`(a-b)+(b-c)=pm+qm`
`a-c=(p+q)m`
`=>m|(a-c)`
`=> a -= c (mod m)`

4.加性
`a -= b (mod m)`
`=>m|(a-b),令a-b=p m`
同理，令`c-d=qm`
`=>(a+c)-(b+d)=(p+q)m`
`=>m|(a+c)-(b+d)`
`=>a+c -= b+d (mod m)`

5.乘性
同上
`a=b+p m,c=d+qm`
`=>ac=bd+m(bq+dp+pqm)`
`=>ac-bd=m(bq+dp+pqm)`
`=>m|ac-bd`
`=>ac -= bd (mod m)`

6.冪性
利用乘性即可推倒
`a-=b (mod m),a-=b (mod m)`
`=>aa-=bb (mod m)`
`=>a^2=>b^2 (mod m)`
再用歸納法就能推出`=>a^k=>b^k (mod m)`

7.
`a-=b (mod m)`
`令a-b=km`
`n|m`
`令m=ln`
`=>a-b=lkn`
`=>a-=b (mod n)`

8.
`(a-b)同時被m_1,m_2,...,m_n整除`
`=>lcm(m_1,m_2,...,m_n)|(a-b)`
`=>a-=b (mod lcm(m_1,m_2,...,m_n))`

模反元素(Modular multiplicative inverse)

整數a的模反元素為整數x，x滿足 `ax-=1(mod m)，x可寫成a^-1`
`模反元素存在的充分必要條件為a與m互質`

歐拉函式(Euler's totient function)

定義：`\phi(n)`為小於等於`n`的正整數中與`n`互質的個數

若`p`為質數
`因為<=p的正整數都和p互質` `=>phi(p)=p-1`

若`n=p^a`，則小於等於`n`的正整數中，
和`n`有公因數的為 `p,2p,...,p^(a-1)p`
`=>\phi(n)=p^a-p^(a-1)`
`=p^a-p^(a-1)`

若`n=pxxq,p,q 為兩相異質數，求\phi(n)`

第一步：扣除含有`p`這個因數的數`p,2p,...,n/p p,共n/p個`
`n-n/p=n(1-1/p)`
第二步：再扣除含有`q`這個因數的數
n(1-1/p)-n/q
第三步：含有`pq`這個因數的數倍多扣了一次，再加回來
`\phi(n)=n(1-1/p)-n/q+n/(pq)`
`=n(1-1/p)(1-1/q)`
`=(p-1)(q-1)`

通式寫成
`\phi(n)=n\prod_(p|n)(1-1/p)`

這個證明還沒看懂

在RSA演算法中會用到的只會有2個因數

`n=pq` , `p,q` 為兩相異質數
`\phi(n)=(p-1)(q-1)`

費馬小定理

假如a是一個整數，p是一個質數，那麼a^p - a 是p的倍數，可以表示為
\(a^p \equiv a \pmod{p}\)
如果a不是p的倍數，這個定理也可以寫成
\(a^{p-1} \equiv 1 \pmod{p}\)

證明
1.若`p`整除`a`，`p`也整除`a^p`
`=>a^p-=a (mod p)`

2.若`p`不整除`a`

令集合`S_1`為`{1,2,...,p-1}`
令集合`S_2`為`S_1xxa形成的集合{a,2a,...,(p-1)a}`
`S_1為所有mod p可能出現的值形成的集合(0 除外)`
`S_2的值mod p之後都會對應到S_1而且不會重複`，這點可以用反證法證明

`假設存在整數 k,l`
`k != l` , `1 <= k,l < p` 使得 `ka -= la (mod p)` 又因為`1 <= k , l < p`，上式要成立必須`k=l`，與假設矛盾 `=>S_2的值mod p之後都會對應到S_1而且不會重複`

`令S_1所有值的乘積為W則S_2所有值的乘積為a^(p-1)W`

`a^(p-1)W -= W (mod p)`
因為`gcd(W,p) = 1可以同除W`
`a^(p-1) -= 1 (mod p)`