MAXIMA測試
4-1.針對大的\(r\)和\(s\)，分解RSA公鑰\(n=p^rq^s\)[table][tr][td][align=center]RSA \(n=p^rq\)[/align][/td][td][align=center]RSA \(n=p^rq^s\)[/align][/td][/tr]
[tr][td=2,1][b][align=center]產生公鑰和私鑰[/align][/b][/td][/tr]
[tr][td]產生兩個隨機質數\(p,q\)
計算\(n=p^r q\)
計算\(L=LCM(p-1.q-1)\)
找\(e,d\)符合\(ed \equiv 1\pmod{L}\)和\(GCD(e,p)=1\)
\(e,n\)是公鑰，\(d,p,q\)是私鑰[/td][td]產生兩個隨機質數\(p,q\)
計算\(n=p^rq^s\)
計算\(L=LCM(p-1,q-1)\)
找\(e,d\)符合\(ed\equiv 1\pmod{L}\)和\(GCD(e,L)=GCD(e,n)=1\)
\(e,n\)是公鑰，\(d,p,q\)是私鑰[/td][/tr]
[tr][td=2,1][b][align=center]加密[/align][/b][/td][/tr]
[tr][td]\(c\equiv m^e \pmod{n}\)
\(m\)為明文，\(c\)為密文[/td][td]相同[/td][/tr]
[tr][td=2,1][b][align=center]解密[/align][/b][/td][/tr]
[tr][td]無法使用\(m\equiv c^d \pmod{n}\)來回復明文[/td][td]無法使用\(m\equiv c^d \pmod{n}\)來回復明文[/td][/tr]
[tr][td=2,1][b][align=center]利用中國餘數定理快速解密[/align][/b][/td][/tr]
[tr][td]\(m_q\equiv c^d\pmod{q}\)
設\(d_q\equiv d\pmod{q-1}\)，\(m_q\equiv c^{d_q}\pmod{q}\)
利用中國餘數定理
\(m\equiv (m_p\cdot q(q^{-1}\pmod{p^r})+m_q\cdot p^r(p^{-r}\pmod{q}))\pmod{n}\)
\(m_p\equiv m\pmod{p^r}\)的\(m_p\)無法用\(m_p\equiv c^d\pmod{p^r}\)直接計算
用[url=https://math.pro/db/viewthread.php?tid=3498&page=2#pid25299]Takagi[/url]的方法計算\(m_p\)[/td]
[td]利用中國餘數定理
\(m\equiv (m_p\cdot q^s(q^{-s}\pmod{p^r})+m_q\cdot p^r(p^{-r}\pmod{q^s}))\pmod{n}\)
\(m_p\equiv m\pmod{p^r}\)的\(m_p\)無法用\(m_p\equiv c^d\pmod{p^r}\)直接計算
\(m_q\equiv m\pmod{q^s}\)的\(m_q\)無法用\(m_q\equiv c^d\pmod{q^s}\)直接計算
用[url=https://math.pro/db/viewthread.php?tid=3498&page=2#pid25299]Takagi[/url]的方法分別計算\(m_p,m_q\)[/td][/tr][/table]
先介紹\(n=p^rq^s\)
假設密文\(c\)經\(p^r\)同餘後為\(c_p\)，明文\(m\)經\(p^r\)同餘後為\(m_p\)，密文\(c_p\)和明文\(m_p\)的關係為\(c_p\equiv m_p^e \pmod{p^r}\)。
設明文\(m_p\)以\(p\)進位表示成\(m_p\equiv X_0+pX_1+p^2X_2+\ldots+p^{r-1}X_{r-1}\pmod{p^r}\)
設密文\(c_p\)以\(p\)進位表示成\(c_p\equiv A_0+pA_1+p^2A_2+\ldots+p^{r-1}A_{r-1}\pmod{p^r}\)
\(c_p[ i ]=A_0+pA_1+\ldots+p^iA_i=(X_0+pX_1+\ldots+p^iX_i)^e \pmod{p^{i+1}}\)
設\(F_i=(X_0+pX_1+\ldots+p^iX_i)^e\)
注意到\(F_r\pmod{p^r}=A\)和\(A[r-1]=A\)
\(c_p[ i ]=A_0+pA_1+\ldots+p^iA_i\pmod{p^{i+1}}\)
\(=(X_0+pX_1+\ldots+p^iX_i)^e\pmod{p^{i+1}}\)
\(=(X_0+pX_1+\ldots+p^{i-1}X_{i-1})^e+eX_0^{e-1}p^iX_i\pmod{p^{i+1}}\)
\(=F_i+eX_0^{e-1}p^iX_i\pmod{p^{i+1}}\)
得到
\(X_0=A_0^{d\pmod{p-1}}\pmod{p}\)
\(\displaystyle X_i=\frac{e^{-1}X_0^{1-e}(c_p[ i ]-F_i\pmod{p^{i+1}})}{p^i}\pmod{p}\)，\(1\le i \le r-1\)
[table][tr][td][align=center]RSA \(n=p^rq\)的遞迴關係式[/align][/td][td][align=center]RSA \(n=p^rq^s\)的遞迴關係式[/align][/td][/tr]
[tr][td]\(K_0=c^{d_p}\pmod{p}\)
\(A_{i+1}=A_i+p^iK_i\)
\(F_i=(A_i)^e\pmod{p^{i+1}}\)
\(\displaystyle K_{i}\equiv \frac{(c_p-F_i)(eF_i)^{-1}A_i}{p^i}\pmod{p^{i+1}}\)，\(1\le i \le r-1\)[/td][td]\(X_0=c^{d_p}\pmod{p}\)
\(A_{i+1}=A_i+p^iX_i\)
\(F_i=(A_i)^e\pmod{p^{i+1}}\)
\(\displaystyle X_i=\frac{e^{-1}X_0^{1-e}(c_p[ i ]-F_i\pmod{p^{i+1}})}{p^i}\pmod{p}\)，\(1\le i \le r-1\)
\(e^{-1}\)和\(X_0^{1-e}\)同餘\(p\)，與Takagi演算法相比，雖然整體速度影響不大，但比較簡單。[/td][/tr]
[/table]
Lim, S., Kim, S., Yie, I., Lee, H. (2000). A Generalized Takagi-Cryptosystem with a Modulus of the Form prqs . In: Roy, B., Okamoto, E. (eds) Progress in Cryptology —INDOCRYPT 2000. INDOCRYPT 2000. Lecture Notes in Computer Science, vol 1977. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44495-5_25
[url]https://link.springer.com/chapter/10.1007/3-540-44495-5_25[/url]
再介紹如何分解
4-2.針對大的\(r\)和\(s\)，分解RSA公鑰\(n=p^rq^s\)
[table][tr][td=2,1][b][align=center]問題敘述[/align][/b]
令\(N=p^rq^s\)是未知分解的整數，\(r>s\)和\(gcd(r,s)=1\)，給定\(N\)作為輸入，能在多項式時間\(log N\)，在\(r=\Omega(log^3 max(p,q))\)情況下回復質因數\(p\)和\(q\)。[/td][/tr]
[tr][td=2,1][b][align=center]步驟1：從\(r\)和\(s\)找出\(u,\alpha,\beta,a,b\)使得\(\cases{r=u\cdot \alpha+a\cr s=u\cdot \beta+b}\)[/align][/b][/td][/tr]
[tr][td=2,1]引理1
令\(r\)和\(s\)是兩個整數，\(r>s>0\)，能在多項式時間內計算\(u,\alpha,\beta,a,b\)使得\(\cases{r=u\cdot \alpha+a\cr s=u\cdot \beta+b}\)。
其中\(\displaystyle 0<\alpha\le 2r^{1/3},0\le \beta\le \alpha,|\;a|\;<\alpha,|\;b|\;\le \frac{6r^{2/3}}{\alpha},u>\frac{r}{\alpha}-1\)，這裡\(a\)和\(b\)都同時\(\ge 0(Case1)\)，或同時\(\le 0(Case2)\)。[/td][/tr]
[tr][td][align=center]當\(a\)和\(b\)都同時\(\ge 0(Case1)\)
[b]步驟2：\(N=P^u\cdot Q\)利用BDH方法解出\(P\)和\(Q\)[/align][/b][/td][td][align=center]當\(a\)和\(b\)都同時\(\le 0(Case2)\)
[b]步驟2：\(\displaystyle N=\frac{P^u}{Q}\)利用Coppersmith方法解出\(P\)和\(Q\)[/align][/b][/td][/tr]
[tr][td]\(a\ge 0,b\ge 0\)
\(N=p^rq^s=p^{u\cdot α+a}\cdot q^{u\cdot β+b}=(p^{α}q^{β})^u\cdot p^a q^b=P^u\cdot Q\)，其中\(P=p^αq^β\)和\(Q=p^aq^b\)
論文的定理6
令\(p\)和\(q\)是兩個整數且\(p\ge 2\)和\(q\ge 2\)，令\(N=p^rq\)。假如\(r=\Omega(log q)\)，能在多項式時間\(log N\)內分解出因數\(p\)和\(q\)。
[/td][td]\(a\le 0,b\le 0\)
\(\displaystyle N=p^rq^s=p^{u\cdot α+a}q^{u\cdot β+b}=(p^{α}q^{β})^up^aq^b=\frac{P^u}{Q}\)，其中\(P=p^αq^β\)和\(Q=p^{-a}q^{-b}\)
從\(P^u=Q\cdot N\)得到\(P^u\equiv 0\pmod{N}\)
\(P=X\cdot t+x_0\)，其中\(X=\lfloor\;N^{1/u}\rfloor\;\)和\(|\;x_0|\;\le X\)
多項式方程式\((X\cdot t+x_0)^u\equiv 0\pmod{N}\)
\(\displaystyle 0\le t\le \frac{P}{X}\le 2\frac{P}{N^{1/u}}=2Q^{1/u}\)
應用Coppersmith方法求\(x_0\)，進而得到\(N\)的因數\(P=X\cdot t+x_0\)[/td][/tr]
[tr][td=2,1][b][align=center]步驟3：從\(P=p^{\alpha}q^{\beta}\)和\(Q=p^aq^b\)回復質因數\(p\)和\(q\)[/align][/b][/td][/tr]
[tr][td=2,1]設矩陣\(\left[\matrix{a&b\cr \alpha&\beta}\right]\)，其行列式值為\(a\beta-b\alpha=\gamma\)
若\(\gamma=0\)，則\(\beta \cdot r=\alpha \cdot s\)
則\(\gamma\ne 0\)
\(\cases{\displaystyle Q^{\frac{β}{γ}}\cdot P^{\frac{-b}{γ}}=(p^aq^b)^{\frac{β}{γ}}\cdot(p^{α}q^{β})^{\frac{-b}{γ}}=p^{\frac{aβ-bα}{γ}}\cdot q^{\frac{bβ-bβ}{γ}}=p^1\cdot q^0=p\cr Q^{\frac{-α}{γ}}\cdot P^{\frac{a}{γ}}=(p^aq^b)^{\frac{-α}{γ}}\cdot (p^{α}q^{β})^{\frac{a}{γ}}=p^{\frac{aα-aα}{γ}}\cdot q^{\frac{aβ-bα}{γ}}=p^0\cdot q^1=q}\)[/td][/tr][/table]
[table][tr][td]\(a\)和\(b\)都同時\(\ge 0(Case1)\)的範例
\(N=p^rq^s=p^8q^5\)
\(M=\left[\matrix{\lfloor\; r^{1/3} \rfloor\;&-s\cr 0&r}\right]=\left[\matrix{\lfloor\; 8^{1/3} \rfloor\;&-5\cr 0&r}\right]=\left[\matrix{2&-5\cr 0&8}\right]\)
Gauss-Lagrange演算法化簡
\(B=\left[\matrix{2&3\cr 4&-2}\right]\)
較短向量\(v=(4,-2)=(\lfloor 8^{1/3} \rfloor\cdot \alpha,\gamma)\)，\(\gamma=-s\cdot \alpha+r\cdot \beta\)
\(\cases{r=u\cdot \alpha+a\cr s=u\cdot \beta+b}\)，\(\cases{8=4\cdot 2+0\cr 5=4\cdot 1+1}\)
\(N=(p^{\alpha}q^{\beta})^up^aq^b=(p^2q)^4q\)[/td]
[td]\(a\)和\(b\)都同時\(\le 0(Case2)\)的範例
\(N=p^rq^s=p^8q^3\)
\(M=\left[\matrix{\lfloor\; r^{1/3} \rfloor\;&-s\cr 0&r}\right]=\left[\matrix{\lfloor\; 8^{1/3} \rfloor\;&-3\cr 0&8}\right]=\left[\matrix{2&-3\cr 0&8}\right]\)
Gauss-Lagrange演算法化簡
\(B=\left[\matrix{2&-3\cr 4&2}\right]\)
較短向量\(v=(4,2)=(\lfloor 8^{1/3} \rfloor\cdot \alpha,\gamma)\)，\(\gamma=-s\cdot \alpha+r\cdot \beta\)
\(\cases{r=u\cdot \alpha+a\cr s=u\cdot \beta+b}\)，\(\cases{8=4\cdot 2+0\cr 3=4\cdot 1-1}\)
\(N=(p^{\alpha}q^{\beta})^up^aq^b=(p^2q)^4q^{-1}\)[/td][/tr][/table]
－－－－－－－－－－－－－－－－－－－－－
[table][tr][td][align=center]方法[/align][/td][td][align=center]範例[/align][/td][/tr]
[tr][td=2,1][b][align=center]問題敘述[/align][/b]
令\(N=p^rq^s\)是未知分解的整數，\(r>s\)和\(gcd(r,s)=1\)，給定\(N\)作為輸入，能在多項式時間\(log N\)，在\(r=\Omega(log^3 max(p,q))\)情況下回復質因數\(p\)和\(q\)。[/td][/tr]
[tr][td]\(N=p^8q^5=(p^2q)^4q\)[/td][td]\(N=p^8q^3=(p^2q)^4q^{-1}\)[/td][/tr]
[tr][td=2,1][b][align=center]步驟1：從\(r\)和\(s\)找出\(u,\alpha,\beta,a,b\)使得\(\cases{r=u\cdot \alpha+a\cr s=u\cdot \beta+b}\)[/align][/b][/td][/tr]
[tr][td]引理1
令\(r\)和\(s\)是兩個整數，\(r>s>0\)，能在多項式時間內計算\(u,\alpha,\beta,a,b\)使得\(\cases{r=u\cdot \alpha+a\cr s=u\cdot \beta+b}\)。
其中\(\displaystyle 0<\alpha\le 2r^{1/3},0\le \beta\le \alpha,|\;a|\;<\alpha,|\;b|\;\le \frac{6r^{2/3}}{\alpha},u>\frac{r}{\alpha}-1\)，這裡\(a\)和\(b\)都同時\(\ge 0(Case1)\)，或同時\(\le 0(Case2)\)。
\(M=\left[\matrix{\lfloor\; r^{1/3} \rfloor\;&-s\cr 0&r}\right]\)
\(M=\left[\matrix{\lfloor\; 8^{1/3} \rfloor\;&-5\cr 0&r}\right]=\left[\matrix{2&-5\cr 0&8}\right]\)
LLL化簡
\(B=\left[\matrix{2&3\cr 4&-2}\right]\)
較短向量\(v=(4,-2)=(\lfloor 8^{1/3} \rfloor\cdot \alpha,\gamma)\)
[/td][td][/td][/tr]
[tr][td]\(\cases{8=4\cdot 2+0\cr 5=4\cdot 1+1}\)[/td][td]\(\cases{8=4\cdot 2+0\cr 3=4\cdot 1-1}\)[/td][/tr]
[tr][td][b][align=center]步驟2：\(N=P^u\cdot Q\)利用BDH方法解出\(P\)和\(Q\)[/align][/b][/td][td][b][align=center]步驟2：\(\displaystyle N=\frac{P^u}{Q}\)利用Coppersmith方法解出\(P\)和\(Q\)[/align][/b][/td][/tr]
[tr][td]\(a\ge 0,b\ge 0\)
\(N=p^rq^s=p^{u\cdot α+a}\cdot q^{u\cdot β+b}=(p^{α}q^{β})^u\cdot p^a q^b=P^u\cdot Q\)，其中\(P=p^αq^β\)和\(Q=p^aq^b\)
論文的定理6
令\(p\)和\(q\)是兩個整數且\(p\ge 2\)和\(q\ge 2\)，令\(N=p^rq\)。假如\(r=\Omega(log q)\)，能在多項式時間\(log N\)內分解出因數\(p\)和\(q\)。
[/td][td]\(a\le 0,b\le 0\)
\(\displaystyle N=p^rq^s=p^{u\cdot α+a}q^{u\cdot β+b}=(p^{α}q^{β})^up^aq^b=\frac{P^u}{Q}\)，其中\(P=p^αq^β\)和\(Q=p^{-a}q^{-b}\)
從\(P^u=Q\cdot N\)得到\(P^u\equiv 0\pmod{N}\)
\(P=X\cdot t+x_0\)，其中\(X=\lfloor\;N^{1/u}\rfloor\;\)和\(|\;x_0|\;\le X\)
多項式方程式\((X\cdot t+x_0)^u\equiv 0\pmod{N}\)
\(\displaystyle 0\le t\le \frac{P}{X}\le 2\frac{P}{N^{1/u}}=2Q^{1/u}\)
應用Coppersmith方法求\(x_0\)，進而得到\(N\)的因數\(P=X\cdot t+x_0\)
[/td][/tr]
[tr][td][b][align=center]步驟2-1：列舉因數\(P\)的近似值\(\tilde{P}\)[/align][/b][/td][td][b]步驟2-1：[/b][/td][/tr]
[tr][td][/td][td][/td][/tr]
[tr][td=2,1][b][align=center]步驟2-2：設同餘方程式，計算參數\(X\)[/align][/b][/td][/tr]
[tr][td][/td][td][/td][/tr]
[tr][td=2,1][b][align=center]步驟2-3：產生矩陣\(M\)[/align][/b][/td][/tr]
[tr][td][/td][td][/td][/tr]
[tr][td=2,1][b][align=center]步驟2-4：經LLL化簡後的短向量產生不需要同餘\(p^{um}\)的方程式，得到公鑰\(N\)的因數\(P\)[/align][/b][/td][/tr]
[tr][td][/td][td][/td][/tr]
[tr][td=2,1][b][align=center]步驟3：從\(P=p^{\alpha}q^{\beta}\)和\(Q=p^aq^b\)回復質因數\(p\)和\(q\)[/align][/b][/td][/tr]
[tr][td]設矩陣\(\left[\matrix{a&b\cr \alpha&\beta}\right]\)，其行列式值為\(a\beta-b\alpha=\gamma\)
若\(\gamma=0\)，則\(\beta \cdot r=\alpha \cdot s\)
則\(\gamma\ne 0\)
\(\cases{\displaystyle Q^{\frac{β}{γ}}\cdot P^{\frac{-b}{γ}}=(p^aq^b)^{\frac{β}{γ}}\cdot(p^{α}q^{β})^{\frac{-b}{γ}}=p^{\frac{aβ-bα}{γ}}\cdot q^{\frac{bβ-bβ}{γ}}=p^1\cdot q^0=p\cr Q^{\frac{-α}{γ}}\cdot P^{\frac{a}{γ}}=(p^aq^b)^{\frac{-α}{γ}}\cdot (p^{α}q^{β})^{\frac{a}{γ}}=p^{\frac{aα-aα}{γ}}\cdot q^{\frac{aβ-bα}{γ}}=p^0\cdot q^1=q}\)[/td][td][/td][/tr][/table]
[url]https://eprint.iacr.org/2015/071.pdf[/url]
[table][tr][td][align=center]方法[/align][/td][td][align=center]範例[/align][/td][/tr]
[tr][td=2,1][b][align=center]問題敘述[/align][/b][/td][/tr]
[tr][td][/td][td][/td][/tr]
[tr][td=2,1][b][align=center]步驟1：[/align][/b][/td][/tr]
[tr][td][/td][td][/td][/tr]
[tr][td=2,1][b][align=center]步驟2：[/align][/b][/td][/tr]
[tr][td][/td][td][/td][/tr]
[tr][td=2,1][b][align=center]步驟3：[/align][/b][/td][/tr]
[tr][td][/td][td][/td][/tr]
[tr][td=2,1][b][align=center]步驟4：[/align][/b][/td][/tr]
[tr][td][/td][td][/td][/tr][/table]
A Generalized Takagi-Cryptosystem with a Modulus of the Form prqs
\(\matrix{& \matrix{常數項&一次方&二次方}\cr \matrix{1\cr 2\cr 3 \cr}&\left[\matrix{ 1 & 2 & 3 \cr 4&5&6\cr 7&8&9}\right]}\)
[url]https://math.pro/db/viewthread.php?tid=3498&page=1#pid23067[/url]
[table][tr][td]1997年Howgrave-Graham方法[/td][td]1999年Boneh,Durfee,Howgrave-Graham方法[/td][/tr]
[tr][td]\(q_{u,v}(x)=N^{(h-1-v)}x^u(p(x))^v\)
以\(h=3,k=2\)為例計算\(det(M)\)
\(M=\left[\matrix{N^2&&&&&\cr
0&N^2X^1&&&&\cr
*&*&NX^2&&&\cr
0&*&*&NX^3&&\cr
*&*&*&*&X^4&\cr
0&*&*&*&*&X^5}\right]\)
*代表非零數字[/td][td]\(g_{i,k}(x)=N^{m-k}x^i f^k(x)\)[/td][/tr][/table]
由費馬小定理可知\(q^{p-1}\equiv 1\pmod{p}\)，所以\(q^{p-2}\equiv q^{-1}\pmod{p}\)
同理\(p^{q-2}\equiv p^{-1}\pmod{q}\)
得\(m\equiv (m_p\cdot q(q^{p-2}\pmod{p})+m_q (p \cdot p^{p-2}\pmod{q}))\pmod{pq}\)
利用\(a(b\pmod{c})=(ab)\pmod{ac}\)
\(m\equiv (m_p(q^{p-1}\pmod{n})+m_q (p^{p-1}\pmod{n}))\pmod{pq}\)
\(\cases{m\equiv m_p \pmod{p}\cr m\equiv m_q \pmod{q}}\)
設\(m=m_q+hq\)
\(m\equiv m_q+hq\pmod{p}\)
\(m_p \equiv m_q+hq \pmod{p}\)
\(h\equiv q^{-1}(m_p-m_q)\pmod{p}\)
代入\(m=m_q+hq\)
得\(m=m_q+q(q^{-1}(m_p-m_q)\pmod{p})\)
[url]https://stattrek.com/matrix-algebra/echelon-form[/url]
[url]https://rosettacode.org/wiki/Cholesky_decomposition[/url]
計算\(s\)長度
\(\Vert\;s\Vert\;=\sqrt{d_{12}^2N^{6\alpha}+d_{13}^2N^{6\alpha}+d_{14}^2N^{6\alpha}+d_{23}^2N^{6\alpha}+d_{24}^2N^{6\alpha}+d_{34}^2N^{6\alpha}+e_{123}^2+e_{124}^2+e_{134}^2+e_{234}^2}\)
[table]
[tr][td]找共同根-subresultant
[證明]
設\(f(x)\)和\(g(x)\)有共同因式\(h(x)\)
將\(f(x)\)和\(g(x)\)分解成兩個式子相乘\(\matrix{f(x)=h(x)\tilde{f}(x) \cr g(x)=h(x)\tilde{g}(x)}\)
計算\(\tilde{g}(x)f(x)=\tilde{g}(x)h(x)\tilde{f}(x)=g(x)\tilde{f}(x)\)
移項\(\tilde{g}(x)f(x)-\tilde{f}(x)g(x)=0\)
(1)當\(k=0\)時
若存在\(s(x)\)為次方\(m-1\)的多項式和\(t(x)\)為次方\(n-1\)多項式，且滿足\(s(x)f(x)+t(x)g(x)=0\)
則\(f(x)\)和\(g(x)\)至少有一個共同根。
因為\(f(x)\)的\(n個根\)也會是\(t(x)g(x)\)的根，但\(t(x)\)至多\(n-1\)次方，意指\(f(x)\)至少一個根也會是\(g(x)\)的根
將
\(s(x)=s_{m-1}x^{m-1}+s_{m-2}x^{m-2}+\ldots+s_1x+s_0\)(\(m-1\ge 0\))
\(f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0\)
\(t(x)=t_{n-1}x^{n-1}+\ldots+t_1x+t_0\)(\(n-1\ge 0\))
\(g(x)=b_mx^m+b_{m-1}x^{m-1}+\ldots+b_1x+b_0\)
代入\(s(x)f(x)+t(x)g(x)=0\)
得到\((s_{m-1}a_n+t_{n-1}b_m)x^{n+m-1}\)
\(+(s_{m-1}a_{n-1}+s_{m-2}a_n+t_{n-1}b_{m-1}+t_{n-2}b_m)x^{n+m-2}+\ldots\)
\(\displaystyle +\left(\sum_{j=1}^i s_{m-j}a_{n+j-i}+\sum_{k=1}^i t_{n-k}b_{m+k-i}\right)x^{n+m-i}+\ldots\)
\(+(s_1a_0+s_0a_1+t_1b_0+t_0b_1)x\)
\(+(s_0a_0+t_0b_0)=0\)
每個係數都是0，寫成矩陣形式
\(\left[0,\ldots,0\right]=\left[s_{m-1},\ldots,s_0,t_{n-1},\ldots,t_0\right] \left[\matrix{a_n&a_{n-1}&\ldots&\ldots&a_0&0&0\cr
0&a_n&a_{n-1}&\ldots&a_1&a_0&0\cr
0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr
0&0&0&a_n&a_{n-1}&\ldots&a_0\cr
b_m&b_{m-1}&\ldots&\ldots&b_0&0&0\cr
0&b_m&b_{m-1}&\ldots&b_1&b_0&0\cr
0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr
0&0&0&b_m&b_{m-1}&\ldots&b_0}\right]\)
其中\(\left[\matrix{a_n&a_{n-1}&\ldots&\ldots&a_0&0&0\cr
0&a_n&a_{n-1}&\ldots&a_1&a_0&0\cr
0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr
0&0&0&a_n&a_{n-1}&\ldots&a_0\cr
b_m&b_{m-1}&\ldots&\ldots&b_0&0&0\cr
0&b_m&b_{m-1}&\ldots&b_1&b_0&0\cr
0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr
0&0&0&b_m&b_{m-1}&\ldots&b_0}\right]\)為\(f(x)\)和\(g(x)\)的\(Sylvester\)矩陣
若\(\left[s_{m-1},\ldots,s_0,t_{n-1},\ldots,t_0\right]\)有非0解，則\(Sylvester\)矩陣的行列式值為0
\(Syl(f,g)=0\)
(2)當\(k=1\)時
若存在\(s(x)\)為次方\(m-2\)的多項式和\(t(x)\)為次方\(n-2\)多項式，且滿足\(s(x)f(x)+t(x)g(x)=0\)
則\(f(x)\)和\(g(x)\)至少有二個共同根。
因為\(f(x)\)的\(n個根\)也會是\(t(x)g(x)\)的根，但\(t(x)\)至多\(n-2\)次方，意指\(f(x)\)至少二個根也會是\(g(x)\)的根
將
\(s(x)=s_{m-2}x^{m-2}+s_{m-3}x^{m-3}+\ldots+s_1x+s_0\)(\(m-1\ge 0\))
\(f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0\)
\(t(x)=t_{n-2}x^{n-2}+t_{n-3}x^{n-3}+\ldots+t_1x+t_0\)(\(n-1\ge 0\))
\(g(x)=b_mx^m+b_{m-1}x^{m-1}+\ldots+b_1x+b_0\)
代入\(s(x)f(x)+t(x)g(x)=0\)
得到\((s_{m-2}a_n+t_{n-2}b_m)x^{n+m-1}\)
\(+(s_{m-2}a_{n-1}+s_{m-3}a_n+t_{n-2}b_{m-2}+t_{n-3}b_m)x^{n+m-2}+\ldots\)
\(\displaystyle +\left(\sum_{j=1}^i s_{m-1-j}a_{n-1+j-i}+\sum_{k=1}^i t_{n-1-k}b_{m-1+k-i}\right)x^{n+m-1-i}+\ldots\)
\(+(s_1a_0+s_0a_1+t_1b_0+t_0b_1)x\)
\(+(s_0a_0+t_0b_0)=0\)
每個係數都是0，寫成矩陣形式
\(\left[0,\ldots,0\right]=\left[s_{m-2},\ldots,s_0,t_{n-2},\ldots,t_0\right] \left[\matrix{a_n&a_{n-1}&\ldots&\ldots&a_0&0&0\cr
0&a_n&a_{n-1}&\ldots&a_1&a_0&0\cr
0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr
0&0&0&a_n&a_{n-1}&\ldots&a_0\cr
b_m&b_{m-1}&\ldots&\ldots&b_0&0&0\cr
0&b_m&b_{m-1}&\ldots&b_1&b_0&0\cr
0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr
0&0&0&b_m&b_{m-1}&\ldots&b_0}\right]\)[/td][td]\(f(x)=x^4+x^3+x^2-x-2=(x^2-1)(x^2+x+2)\)
\(g(x)=x^5+x^4-2x^2-x+1=(x^2-1)(x^3+x^2+x-1)\)
(1)當\(k=0\)時
設\(s(x)=s_4x^4+s_3x^3+s_2x^2+s_1x+s_0\)
\(t(x)=t_3x^3+t_2x^2+t_1x^1+t_0\)
代入\(s(x)f(x)+t(x)g(x)=0\)
得到\((s_4+t_3)x^8+\)
\((s_4+s_3+t_3+t_2)x^7+\)
\((s_4+s_3+s_2+t_2+t_1)x^6+\)
\((-s_4+s_3+s_2+s_1-2t_3+t_1+t_0)x^5+\)
\((-2s_4-s_3+s_2+s_1+s_0-t_3-2t_2+t_0)x^4+\)
\((-2s_3-s_2+s_1+s_0+t_3-t_2-2t_1)x^3+\)
\((-2s_2-s_1+s_0+t_2-t_1-2t_0)x^2+\)
\((-2s_1-s_0+t_1-t_0)x+\)
\((-2s_0+t_0)=0\)
每個係數都是0，寫成矩陣形式
\(\left[0,\ldots,0\right]=\left[\matrix{s_4,s_3,s_2,s_1,s_0,t_3,t_2,t_1,t_0}\right]\left[ \matrix{1&1&1&-1&-2&0&0&0&0\cr
0&1&1&1&-1&-2&0&0&0\cr
0&0&1&1&1&-1&-2&0&0\cr
0&0&0&1&1&1&-1&-2&0\cr
0&0&0&0&1&1&1&-1&-2\cr
1&1&0&-2&-1&1&0&0&0\cr
0&1&1&0&-2&-1&1&0&0\cr
0&0&1&1&0&-2&-1&1&0\cr
0&0&0&1&1&0&-2&-1&1}\right]\)
\(\displaystyle \left[s_4,s_3,s_2,s_1,s_0,t_3,t_2,t_1,t_0\right]\)有無限多組解
\(\left[\frac{t_0-2t_1}{4},-\frac{t_0+2t_1}{4},-\frac{3t_0-2t_1}{4},\frac{t_0}{2},-\frac{t_0-2t_1}{4},\frac{t_0+2t_1}{4},t_1,t_0 \right]\)
例如取\(t_1=4,t_0=4\)，\(\left[s_4,s_3,s_2,s_1,s_0,t_3,t_2,t_1,t_0\right]=\left[-1,-3,-3,-1,2,1,3,4,4 \right]\)
符合\((-x^4-3x^3-3x^2-x+2)f(x)+(x^3+3x^2+4x+4)g(x)=0\)
(2)當\(k=1\)時
設\(s(x)=s_3x^3+s_2x^2+s_1x+s_0\)
\(t(x)=t_2x^2+t_1x+t_0\)
代入\(s(x)f(x)+t(x)g(x)=0\)
得到\((s_3+t_2)x^7+\)
\((s_3+s_2+t_2+t_1)x^6+\)
\((s_3+s_2+s_1+t_1+t_0)x^5+\)
\((-s_3+s_2+s_1+s_0-2t_2+t_0)x^4+\)
\((-2s_3-s_2+s_1+s_0-t_2-2t_1)x^3+\)
\((-2s_2-s_1+s_0+t_2-t_1-2t_0)x^2+\)
\((-2s_1-s_0+t_1-t_0)x+\)
\((t_0-2s_0)=0\)
每個係數都是0，寫成矩陣形式
\(\left[0,\ldots,0\right]=\left[s_3,s_2,s_1,s_0,t_2,t_1,t_0\right]\left[ \matrix{1&1&1&-1&-2&0&0\cr
0&1&1&1&-1&-2&0\cr
0&0&1&1&1&-1&-2\cr
0&0&0&1&1&1&-1\cr
1&1&0&-2&-1&1&0\cr
0&1&1&0&-2&-1&1\cr
0&0&1&1&0&-2&-1}\right]\)
\(\displaystyle \left[s_3,s_2,s_1,s_0,t_2,t_1,t_0\right]\)有無限多組解
\(\displaystyle \left[-\frac{t_0}{2},-\frac{t_0}{2},-\frac{t_0}{2},\frac{t_0}{2},\frac{t_0}{2},\frac{t_0}{2},t_0\right]\)
例如取\(t_0=2\)，\(\left[s_3,s_2,s_1,s_0,t_2,t_1,t_0\right]=\left[-1,-1,-1,1,1,1,2\right]\)
符合\((-x^3-x^2-x+1)f(x)+(x^2+x+2)g(x)=0\)
(3)當\(k=2\)時
設\(s(x)=s_2x^2+s_1x+s_0\)
\(t(x)=t_1x+t_0\)
代入\(s(x)f(x)+t(x)g(x)=0\)
得到
\((s_2+t_1)x^6+\)
\((s_2+s_1+t_1+t_0)x^5+\)
\((s_2+s_1+s_0+t_0)x^4+\)
\((-s_2+s_1+s_0-2t_1)x^3+\)
\((-2s_2-s_1+s_0-t_1-2t_0)x^2+\)
\((-2s_1-s_0+t_1-t_0)x+\)
\((-2s_0+t_0)=0\)
每個係數都是0，寫成矩陣形式
\(\left[0,\ldots,0\right]=\left[s_2,s_1,s_0,t_1,t_0\right]\left[\matrix{1&1&1&-1&-2\cr
0&1&1&1&-1\cr
0&0&1&1&1\cr
1&1&0&-2&-1\cr
0&1&1&0&-2} \right]\)
\(\left[s_2,s_1,s_0,t_1,t_0\right]\)只有0解\(\left[0,0,0,0,0\right]\)[/td][/tr]
[tr][td][/td][td][/td][/tr]
[tr][td][/td][td][/td][/tr]
[tr][td][/td][td][/td][/tr]
[tr][td][/td][td][/td][/tr][/table]
\(\left[\matrix{1&2 \cr 3 &4}\right]\)
[url]https://en.wikipedia.org/wiki/Resultant[/url]
[url]https://reference.wolfram.com/language/ref/Resultant.html[/url]
[url]https://reference.wolfram.com/language/ref/Subresultants.html[/url]
假如\(m_1\)和\(m_2\)滿足隱含的多項式關係\(p(m_1,m_2)=0\pmod{N}\)
在這個範例我們有兩個未知數的三個同餘\(N\)多項式
\(P_1=p(m_1,m_2)=0\pmod{N}\)
\(P_2=m_1^e-c_1=0\pmod{N}\)
\(P_3=m_2^e-c_2=0\pmod{N}\)
使用resultant消除兩個多變數方程式的共同變數
resultant和gcd的運算，可以組合成Groebner basis
jsmath範例
[url]http://web.archive.org/web/20200803020254/http://www.math.union.edu:80/~dpvc/jsMath/examples/welcome.html[/url]
[table][tr][td]Howgrave-Graham[/td][td]Durfee[/td][/tr]
[tr][td]\(q_{u,v}(x)=N^{h-1-v}x^up(x)^v\)[/td][td]\(\displaystyle g_{i,k}(x)=x^i \left(\frac{p(x)}{N}\right)^k\)[/td][/tr]
[tr][td]以\(h=3,k=2\)為例計算\(det(M)\)
\(M=\left[\matrix{N^2&&&&&\cr
0&N^2X^1&&&&\cr
*&*&NX^2&&&\cr
0&*&*&NX^3&&\cr
*&*&*&*&X^4&\cr
0&*&*&*&*&X^5}\right]\)
*代表非零數字[/td][td]以\(h=3,k=2\)為例計算\(det(M)\)
\(M=\left[\matrix{\displaystyle 1&&&&&\cr
0&X^1&&&&\cr
*&*&\frac{X^2}{N}&&&\cr
0&*&*&\frac{X^3}{N}&&\cr
*&*&*&*&\frac{X^4}{N^2}&\cr
0&*&*&*&*&\frac{X^5}{N^2}}\right]\)
*代表非零數字[/td][/tr]
[tr][td][/td][td][/td][/tr]
[/table]
解\( ax \equiv b \pmod n \)
(1)若\( gcd(a,n)=1 \)
有唯一解
(2)若\( gcd(a,n)=d>1 \)
若d能整除b則有多組解
若d不能整除b則無解
例\( 12x \equiv 21 \pmod{39} \)
12和39的最大公因數為3且3能整除21，有多組解
先同除3，\( 4x \equiv 7 \pmod{13} \)
\( x \equiv 7 \times 4^{-1} \equiv 7 \times 10 \equiv 70 \equiv 5 \pmod{13} \)
∵\( 4 \times 10\equiv 1 \pmod{13} \)，∴\( 4^{-1} \equiv 10 \pmod{13} \)
解為\( \displaystyle x \equiv 5,5+1\times \frac{39}{3},5+2\times \frac{39}{3} \pmod{39} \)
\( x \equiv 5,18,31 \pmod{39} \)
但在maxima無法解出多組解
modulus:39;
solve(12*x=21,x);
只出現[x=18]一組解而已
解\( x^2 \equiv n \pmod p \)的方法
Cipolla's algorithm
[url=http://en.wikipedia.org/wiki/Cipolla%27s_algorithm]http://en.wikipedia.org/wiki/Cipolla%27s_algorithm[/url]
Pocklington's algorithm
[url=http://en.wikipedia.org/wiki/Pocklington%27s_algorithm]http://en.wikipedia.org/wiki/Pocklington%27s_algorithm[/url]
Tonelli–Shanks algorithm
[url=http://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm]http://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm[/url]
選擇e注意事項
1.e不可以太小
選e=3
TP 2:Coppersmith Attacks against RSA
[url]http://www.jscoron.fr/cours/mics3crypto/tpcop.pdf[/url]
[url]http://en.wikipedia.org/wiki/Coppersmith's_Attack[/url]
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
The Case for Elliptic Curve Cryptography
[url]http://www.nsa.gov/business/programs/elliptic_curve.shtml[/url]
有RSA和橢圓曲線所需要的bits數的差異
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
數位簽章技術
[url]http://ec2.ba.ntust.edu.tw/mic/download/security/%E5%AF%86%E7%A2%BC%E5%AD%B8%E8%88%87%E8%B3%87%E8%A8%8A%E5%AE%89%E5%85%A8ch6.doc[/url]
Digital Signature Algorithm
[url]http://en.wikipedia.org/wiki/Digital_Signature_Algorithm[/url]
RSA盲簽章
[url]http://en.wikipedia.org/wiki/Blind_signature[/url]
Schnorr signature
[url]http://en.wikipedia.org/wiki/Schnorr_signature[/url]
Elliptic Curve DSA
[url]http://en.wikipedia.org/wiki/Elliptic_Curve_DSA[/url]
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
可驗證的秘密分享(Verifiable Secret Sharing,VSS)
可公開驗證的秘密分享(Publicly Veriable Secret Sharing,PVSS)
VSS參與者只能驗證他自己本身所持有的子秘密是否正確，而無法得知其他參與者是否也收到正確的子秘密
在PVSS方法中，有一個公開驗證演算法可以驗證每位參與者所拿到的子秘密是否正確，
如果驗證時必須與分派者做數回合的互動式溝通，稱為interactive PVSS。
如果不需要和分派者互動的話，則稱為非互動式non-interactive PVSS
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
[url]http://ccclab.csie.ntpu.edu.tw/ccclab_meeting/meeting_index.php?group=title&sort=asc[/url]
Weighted Threshold RSA Based on the Chinese Remainder
也是祕密分享方案(待了解)
[url]http://en.wikipedia.org/wiki/Proactive_secret_sharing[/url]
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
無需信賴者協助的秘密共享
[url]http://130.203.133.150/viewdoc/summary?doi=10.1.1.14.202[/url]
論文下載
[url]http://130.203.133.150/viewdoc/download?doi=10.1.1.14.202&rep=rep1&type=pdf[/url]
橢圓曲線的書
[url]http://books.google.com.tw/books?id=0_vegzgyqGMC&pg=PA57&hl=zh-TW&source=gbs_toc_r&cad=4#v=onepage&q&f=true[/url]
期貨及選擇權數位學習網
[url]http://taifex.learn.hinet.net/elearn/[/url] 用Maxima學密碼學-Lattice Reduction應用-整數關係
整數關係是給定實數\(x_1,x_2,\ldots,x_n\)，要找到不全為0的整數\(a_1,a_2,\ldots,a_n\)使得\(a_1x_1+a_2x_2+\ldots+a_n x_n=0\)。
到[url]https://github.com/andrejv/identify[/url]下載identify.mac和integer_relation.lisp
將兩個檔案放到C:/maxima-5.45.0/share/maxima/5.45.0/share/資料夾
\(x=(4,8,9,10,11)\)
\(-2\times 4+8=0\)
\(8-9-10+11=0\)
\(8-2\times 9+10=0\)
\(4+8+9-10-11=0\)
\(x=(8,16,18,20,22)\)
\(-2\times 8+16=0\)
\(16-18-20+22=0\)
\(16-2\times 18+20=0\)
\(8+16+18-20-22=0\)
[table=100%][tr][td]Coppersmith Splitting System(CSS)[/td][td]可變參數的Splitting System(PSS)[/td][td]參數相依的Splitting System(PDSS)[/td][/tr]
[tr][td]定義
假設\(m\)和\(t\)都是偶數且\(0<t<m\)，定義\((m,t)\)的splitting system是符合以下2點的數對\((X,\cal{B})\)
1.集合\(X\)有\(m\)個元素，集合\(\cal{B}\)有\(\displaystyle \frac{m}{2}\)個\(X\)的子集合，\(\cal{B}\)稱為區塊(blocks)。
2.對所有\(X\)的子集合\(Y\)，\(Y\)有\(t\)個元素，存在一個區塊\(B\)使得\(B\)和\(Y\)的交集個數為\(\displaystyle \frac{t}{2}\)。[/td]
[td]定義
假設\(m\)、\(t\)和\(t_s\)和都是整數且\(0<t<m\)、\(0\le t_s \le t\)，定義\((m,t,t_s)\)的可變參數splitting system是符合以下2點的數對\((X,\cal{B})\)
1.集合\(X\)有\(m\)個元素，集合\(\cal{B}\)有\(\displaystyle \Bigg\lfloor\; \frac{t_s m}{t}\Bigg\rfloor\;\)個\(X\)的子集合，\(\cal{B}\)稱為區塊(blocks)。
2.對所有\(X\)的子集合\(Y\)，\(Y\)有\(t\)個元素，存在一個區塊\(B\)使得\(B\)和\(Y\)的交集個數為\(\displaystyle t_s\)。
[/td][td]定義
假設\(m\)、\(t\)、\(t_1\)、\(t_2\)、\(m_1\)和\(m_2\)和都是整數且\(0<t<m\)、\(t=t_1+t_2\)、\(\displaystyle m_1=\frac{t_1m}{t}\)、\(\displaystyle m_2=\frac{t_2m}{t}\)、，定義\((m,m_1,m_2,t_1,t_2)\)的可變參數splitting system是符合以下2點的數對\((X,\cal{B})\)
1.集合\(X\)有\(m\)個元素\((m=m_1+m_2)\)，集合\(\cal{B}\)有\(m_2\)個\(X\)的子集合，\(\cal{B}\)稱為區塊(blocks)。
2.對所有\(X\)的子集合\(Y\)，\(Y\)有\(t\)個元素，存在一個區塊\(B\)使得\(B\)和\(Y\)的交集個數為\(\displaystyle t_2\)。[/td][/tr]
[tr][td]產生\(\displaystyle (\frac{m}{2};m,t)\)的Coppersmith splitting system方法
令\(X=Z_m\)，定義
\(B_i=\{\;i+j\pmod{m}:0\le j\le m/2-1\}\;\)
\(\cal B\)\(=\{\;B_i:0\le i \le m/2-1\}\;\)[/td]
[td]產生\(\displaystyle (m;m,t,t_s)\)的可變參數splitting system方法
令\(X=Z_m\)，定義
\(B_i=\{\;i+j\pmod{m}:0\le j\le \Bigg\lfloor\;\frac{t_sm}{t}\Bigg\rfloor\;-1\}\;\)
\(\cal B\)\(=\{\;B_i:0\le i \le m-1\}\;\)[/td][td]產生\(\displaystyle (m;m_1,m_2,t_1,t_2)\)的參數相依splitting system方法
令\(X=Z_m\)，定義
\(B_i=\{\;i+j\pmod{m}:0\le j\le m_2\}\;\)
\(\cal B\)\(=\{\;B_i:0\le i \le m_2-1\}\;\)[/td][/tr]
[tr][td]以\(m=8,t=4\)為例(解\(x\)有8位元，其中有4個1，分成2個1和2個1分別列舉)
\(X=Z_m=\{\;0,1,2,3,4,5,6,7\}\;\)，\(B_0=\{\;0,1,2,3\}\;\)，\(B_1=\{\;1,2,3,4\}\;\)，\(B_2=\{\;2,3,4,5\}\;\)，\(B_3=\{\;3,4,5,6\}\;\)，\(\cal B\)\(=\{\;B_0,B_1,B_2,B_3\}\;\)
子集合\(Y=\{\;0,2,4,6\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_3\)和\(Y\)交集2個元素。
子集合\(Y=\{\;1,3,5,7\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_3\)和\(Y\)交集2個元素。
子集合\(Y=\{\;0,1,6,7\}\;\)有4個元素，存在\(B_0\)和\(Y\)交集2個元素。
子集合\(Y=\{\;0,2,5,7\}\;\)有4個元素，存在\(B_0\)和\(Y\)交集2個元素。
子集合\(Y=\{\;4,5,6,7\}\;\)有4個元素，存在\(B_2,B_3\)和\(Y\)交集2個元素。[/td][td]以\(m=8,t=4,t_s=1\)為例(解\(x\)有8位元，其中有4個1，分成1個1和3個1分別列舉)
\(X=Z_m=\{\;0,1,2,3,4,5,6,7\}\;\)，\(B_0=\{\;0,1\}\;\)，\(B_1=\{\;1,2\}\;\)，\(B_2=\{\;2,3\}\;\)，\(B_3=\{\;3,4\}\;\)，\(B_4=\{\;4,5\}\;\)，\(B_5=\{\;5,6\}\;\)，\(B_6=\{\;6,7\}\;\)，\(B_7=\{\;7,0\}\;\)，\(\cal B\)\(=\{\;B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\}\;\)
子集合\(Y=\{\;0,2,4,6\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。
子集合\(Y=\{\;1,3,5,7\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。
子集合\(Y=\{\;0,1,6,7\}\;\)有4個元素，存在\(B_0,B_1,B_5,B_6,B_7\)和\(Y\)交集1個元素。
子集合\(Y=\{\;0,2,5,7\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。
子集合\(Y=\{\;4,5,6,7\}\;\)有4個元素，存在\(B_3,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。[/td][td]以\(m=8,t=4,t_1=3,t_2=1,m_1=6,m_2=2\)為例(解\(x\)有8位元，其中有4個1，分成3個1和1個1分別列舉)
\(X=Z_m=\{\;0,1,2,3,4,5,6,7\}\;\)，\(B_0=\{\;0,1\}\;\)，\(B_1=\{\;1,2\}\;\)，\(B_2=\{\;2,3\}\;\)，\(B_3=\{\;3,4\}\;\)，\(B_4=\{\;4,5\}\;\)，\(B_5=\{\;5,6\}\;\)，\(B_6=\{\;6,7\}\;\)，\(B_7=\{\;7,0\}\;\)，\(\cal B\)\(=\{\;B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\}\;\)
子集合\(Y=\{\;0,2,4,6\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。
子集合\(Y=\{\;1,3,5,7\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。
子集合\(Y=\{\;0,1,6,7\}\;\)有4個元素，存在\(B_0,B_1,B_5,B_6,B_7\)和\(Y\)交集1個元素。
子集合\(Y=\{\;0,2,5,7\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。
子集合\(Y=\{\;4,5,6,7\}\;\)有4個元素，存在\(B_3,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。[/td][/tr][/table]
令\(\displaystyle n_1>\frac{n_2}{2}\)，對任意的\(n_1,n_2\)，令\(k\in Z^{+}\backslash\; \{\;1\}\;\)是大於1的整數且滿足\(\displaystyle \frac{k+1}{2k+1}n_2 \le n_1<\frac{k}{2k-1}n_2\)。
假設\(t_1\)和\(t_2\)滿足\(\matrix{\displaystyle \frac{2k+1}{k+1}t_1-\frac{3k+1}{k+1}\le t_2\le \frac{2k-1}{k}t_1+\frac{3k-2}{k}\cr
\frac{2k-1}{k}t_1<t_2\le \frac{2k+1}{k+1}t_1}\)
則\(N=2n_2-n_1+1\)就足以產生一組參數相依的Splitting system。
\(\cal{B}=\{\;B_i：0 \le i \le 2 n_2-n_1\}\;\)
令\(\displaystyle \frac{1}{2}n_2\le n_1 \le \frac{2}{3}n_2\)，假設\(t_2=2t_1,2t_1-1,2t_1-2\)
則\(N=\cases{\displaystyle 2n_1\frac{1}{3}\lceil\;t_1-1\rceil\;-n_2(\frac{1}{3}\lceil\;t_1-1\rceil\;-1)+1, if t_2=2t_1\cr
2n_1\frac{1}{4}\lceil\;t_1-2\rceil\;-n_2(\frac{1}{4}\lceil\;t_1-2\rceil\;-1)+1, if t_2=2t_1-1\cr
2n_1\frac{1}{5}\lceil\;t_1-3\rceil\;-n_2(\frac{1}{5}\lceil\;t_1-3\rceil\;-1)+1, if t_2=2t_1-2}\)就足夠產生一組參數相依的Splitting system。
\(\cal A, B\)
q:2;
v:2;
node[1,1]:v;
p:181;
for i:0 thru q-1 do
(for j:0 thru 2^i-1 do
(expL:product(X1[k],k,1+(2*j+1)*(2^(q-i-1)),(2*j+2)*(2^(q-i-1))),
print(expL),
node[i+2,2*j+1]:power_mod(node[i+1,j+1],expL,p),
expR:product(X1[k],k,1+2*j*(2^(q-i-1)),(2*j+1)*(2^(q-i-1))),
print(expR),
node[i+2,2*j+2]:power_mod(node[i+1,j+1],expR,p)
)
);
[code]void main()
{
for(i=0;i<5;i++)
{printf(i);
}
}[/code]
Pohlig Hellman
解\( a^x \equiv b \pmod p \)，求\( x= \)？
將\( p-1 \)作質因數分解
\( p-1=q_1^{m_1}\times q_2^{m_2}\times ... \times q_n^{m_n} \)
取\( q=q_1 \)
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
將x用q進位表示
令\( x=x_0+x_1 q+x_2 q^2+...+x_{k-1} q^{k-1} \)，\( 0\le x_i <q \)
代入原式
\( \displaystyle b \equiv a^{x_0+x_1 q+x_2 q^2+...+x_{k-1} q^{k-1}} \pmod p \)
兩邊同取\( \displaystyle \frac{p-1}{q} \)次方
\( \displaystyle b^{\frac{p-1}{q}} \equiv a^{\frac{p-1}{q}x_0} \times a^{(p-1)(x_1+x_2 q+...+x_k q^{k-2})}\pmod p \)
利用費馬小定理\( a^{p-1} \equiv 1\pmod p \)
\( \displaystyle b^{\frac{p-1}{q}} \equiv a^{\frac{p-1}{q}x_0}\pmod p \)
將\( x_0=0,1,2,...,q-1 \)一一代入檢驗上式，符合等式的就是我們要找的\( x_0 \)
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
\( \displaystyle b \equiv a^{x_0+x_1 q+x_2 q^2+...+x_{k-1} q^{k-1}} \pmod p \)
將\( a^{x_0} \)移到另一邊
\( ba^{-x_0}=a^{x_1 q+x_2 q^2+...+x_{k-1} q^{k-1}}\pmod p \)
令\( b_1=ba^{-x_0} \)得
\( b_1=a^{x_1 q+x_2 q^2+...+x_{k-1} q^{k-1}}\pmod p \)
兩邊同取\( \displaystyle \frac{p-1}{q^2} \)次方
\( \displaystyle b_1^{\frac{p-1}{q^2}}=a^{\frac{p-1}{q}x_1}\times a^{(p-1)(x_2+x_3 q+...+x_{k-1} q^{k-3})}\pmod p \)
利用費馬小定理\( a^{p-1} \equiv 1\pmod p \)
\( \displaystyle b_1^{\frac{p-1}{q^2}}=a^{\frac{p-1}{q}x_1}\pmod p \)
將\( x_1=0,1,2,...,q-1 \)一一代入檢驗上式，符合等式的就是我們要找的\( x_1 \)
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
\( b_1=a^{x_1 q+x_2 q^2+...+x_{k-1} q^{k-1}}\pmod p \)
將\( a^{x_1 q} \)移到另一邊
\( b_1 a^{-x_1 q}=a^{x_2 q^2+x_3 q^3+...+x_{k-1} q^{k-1}}\pmod p \)
令\( b_2=b_1 a^{-x_1 q} \)得
\( b_2=a^{x_2 q^2+x_3 q^3+...+x_{k-1} q^{k-1}}\pmod p \)
兩邊同取\( \displaystyle \frac{p-1}{q^3} \)次方
\( \displaystyle b_2^{\frac{p-1}{q^3}}=a^{\frac{p-1}{q}x_2} \times a^{(p-1)(x_3+x_4 q+...+x_{k-1} q^{k-4})}\pmod p \)
利用費馬小定理\( a^{p-1} \equiv 1\pmod p \)
\( \displaystyle b_2^{\frac{p-1}{q^3}}=a^{\frac{p-1}{q}x_2}\pmod p \)
將\( x_2=0,1,2,...,q-1 \)一一代入檢驗上式，符合等式的就是我們要找的\( x_2 \)
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
重複上面的步驟直到\( q^{k+1} \)無法整除\( p-1 \)為止
將收集到的\( x_0,x_1,...,x_k \)重新組合出\( x \equiv x_0+x_1 q_1+x_2 q_1^2+...+x_{k-1} q_1^{k-1}\pmod {q_1^k} \)
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
換第二個質因數\( q_2 \)
令\( q=q_2 \)仿照上面的步驟找出\( x_0,x_1,...,x_k \)
並重新組合出\( x \equiv x_0+x_1 q_2+x_2 q_2^2+...+x_{k-1} q_2^{k-1}\pmod {q_2^k} \)
解\( a^x \equiv b \pmod p \)的方法
(1)baby step,giant step
(2)index caculus
(3)Pohlig Hellman
(4)Pollard's rho
[table=98%][tr][td][/td][td]離散對數問題
Discrete Logarithm Problem，DLP
\( a^x \equiv b \pmod p \)，解\( x \)[/td][td]橢圓曲線離散對數問題
Elliptic Curve Discrete Logarithm Problem，ECDLP
\( P,Q \in E(F_p) \)，\( Q=kP \)，解\( k \)
[/td][/tr][tr][td]baby step,giant step[/td][td]D[/td][td]a[/td][/tr]
[tr][td]index caculus[/td][td]F[/td][td]a[/td][/tr]
[tr][td]Pohlig-Hellman[/td][td]H[/td][td]a[/td][/tr]
[tr][td]Pohlig Hellman[/td][td]J[/td][td]a[/td][/tr]
[tr][td]Pollard's rho[/td][td]J[/td][td]a[/td][/tr][/table]
[url]https://sites.google.com/a/g2.nctu.edu.tw/unimath/2015-08/15th_pentagon[/url]
\( v=\left[ \matrix{1&1&7&2\cr 9&8&4&6\cr 1&8&5&7\cr 2&3&1&1} \right] \)
\( \matrix{arr1 \cr arr2}=\matrix{0&1 \cr 2&3} \)[table=100%][tr][td]\(thread 0\)
\( v_0=\left[ \matrix{1&1&7&2} \right] \)
\( v_2=\left[ \matrix{1&8&5&7} \right] \)
進行\(Gauss\) \(Reduction\)
[/td][td]\(thread 1\)
\( v_1=\left[ \matrix{9&8&4&6} \right] \)
\( v_3=\left[ \matrix{2&3&1&1} \right] \)
進行\(Gauss\) \(Reduction\)
[/td][/tr]
[tr][td]\( \Vert\; v_0 \Vert\;=\sqrt{55}<\Vert\; v_2 \Vert\;=\sqrt{139} \)
兩向量不需交換[/td][td]\( \Vert\; v_1 \Vert\;=\sqrt{197}>\Vert\; v_3 \Vert\;=\sqrt{15} \)
兩向量交換
\( v_1=\left[ \matrix{2&3&1&1} \right] \)
\( v_3=\left[ \matrix{9&8&4&6} \right] \)[/td][/tr]
[tr][td]\( \displaystyle q=\Bigg\lfloor\; \frac{v_0 \cdot v_2}{v_0 \cdot v_0} \Bigg\rceil\;=\Bigg\lfloor\; \frac{58}{55} \Bigg\rceil\;=\Bigg\lfloor\;1.054 \Bigg\rceil\;=1 \)
\( v_2=v_2-q \times v_0=\left[ \matrix{0&7&-2&5} \right] \)
得到更短的向量[/td][td]\( \displaystyle q=\Bigg\lfloor\; \frac{v_1 \cdot v_3}{v_1 \cdot v_1} \Bigg\rceil\;=\Bigg\lfloor\; \frac{52}{15} \Bigg\rceil\;=\Bigg\lfloor\; 3.466 \Bigg\rceil\;=3 \)
\( v_3=v_3-q \times v_1=\left[ \matrix{3&-1&1&3} \right] \)
得到更短的向量[/td][/tr]
[tr][td]\( \Vert\; v_0 \Vert\;=\sqrt{55}<\Vert\; v_2 \Vert\;=\sqrt{78} \)
兩向量不需交換[/td][td]\( \Vert\; v_1 \Vert\;=\sqrt{15}<\Vert\; v_3 \Vert\;=\sqrt{20} \)
兩向量不需交換[/td][/tr]
[tr][td]\( \displaystyle q=\Bigg\lfloor\; \frac{v_0 \cdot v_2}{v_0 \cdot v_0} \Bigg\rceil\;=\Bigg\lfloor\; \frac{3}{55} \Bigg\rceil\;=\Bigg\lfloor\; 0.054 \Bigg\rceil\;=0 \)
\(v_0\)和\(v_2\)化簡結束[/td][td]\( \displaystyle q=\Bigg\lfloor\; \frac{v_1 \cdot v_3}{v_1 \cdot v_1} \Bigg\rceil\;=\Bigg\lfloor\; \frac{7}{15} \Bigg\rceil\;=\Bigg\lfloor\; 0.466 \Bigg\rceil\;=0 \)
\(v_1\)和\(v_3\)化簡結束[/td][/tr][/table]
\( v=\left[ \matrix{1&1&7&2 \cr 2&3&1&1 \cr 0&7&-2&5 \cr 3&-1&1&3} \right] \)
\( \matrix{arr1 \cr arr2}=\matrix{0&2 \cr 3&1} \)[table=100%]
[tr][td]\(thread\) 0
\( v_0=\left[ \matrix{1&1&7&2} \right] \)
\( v_3=\left[ \matrix{3&-1&1&3} \right]\)
進行\(Gauss\) \(Reduction\)[/td][td]\(thread\) 1
\( v_1=\left[ \matrix{2&3&1&1} \right] \)
\( v_2=\left[ \matrix{0&7&-2&5} \right] \)
進行\(Gauss\) \(Reduction\)[/td][/tr]
[tr][td]\( \Vert\; v_0 \Vert\;=\sqrt{55}>\Vert\; v_3 \Vert\;=\sqrt{20} \)
兩向量交換
\( v_0=\left[ \matrix{3&-1&1&3} \right] \)
\( v_3=\left[ \matrix{1&1&7&2} \right] \)[/td][td]\( \Vert\; v_1 \Vert\;=\sqrt{15}<\Vert\; v_2 \Vert\;=\sqrt{78} \)
兩向量不需交換[/td][/tr]
[tr][td]\( \displaystyle q=\Bigg\lfloor\; \frac{v_0 \cdot v_3}{v_0 \cdot v_0} \Bigg\rceil\;=\Bigg\lfloor\; \frac{15}{20} \Bigg\rceil\;=\Bigg\lfloor\; 0.75 \Bigg\rceil\;=1 \)
\( v_3=v_3-q \times v_0=\left[ \matrix{-2&2&6&-1} \right] \)
得到更短的向量[/td][td]\( \displaystyle q=\Bigg\lfloor\; \frac{v_1 \cdot v_2}{v_1 \cdot v_1} \Bigg\rceil\;=\Bigg\lfloor\; \frac{24}{15} \Bigg\rceil\;=\Bigg\lfloor\; 1.6 \Bigg\rceil\;=2 \)
\( v_2=v_2-q \times v_1=\left[ \matrix{-4&1&-4&3} \right] \)
得到更短的向量[/td][/tr]
[tr][td]\( \Vert\; v_0 \Vert\;=\sqrt{20}<\Vert\; v_3 \Vert\;=\sqrt{45} \)
兩向量不需交換[/td][td]\( \Vert\; v_1 \Vert\;=\sqrt{15}<\Vert\; v_2 \Vert\;=\sqrt{42} \)
兩向量不需交換[/td][/tr]
[tr][td]\( \displaystyle q=\Bigg\lfloor\; \frac{v_0 \cdot v_3}{v_0 \cdot v_0} \Bigg\rceil\;=\Bigg\lfloor\; \frac{-5}{20} \Bigg\rceil\;=\Bigg\lfloor\; -0.25 \Bigg\rceil\;=0 \)
\(v_0\)和\(v_3\)化簡結束[/td][td]\( \displaystyle q=\Bigg\lfloor\; \frac{v_1 \cdot v_2}{v_1 \cdot v_1} \Bigg\rceil\;=\Bigg\lfloor\; \frac{-6}{15} \Bigg\rceil\;=\Bigg\lfloor\; -0.4 \Bigg\rceil\;=0 \)
\(v_1\)和\(v_2\)化簡結束[/td][/tr][/table]
\(v=\left[ \matrix{3&-1&1&3 \cr 2&3&1&1 \cr -4&1&-4&3 \cr -2&2&6&-1} \right] \)
\( \matrix{arr1 \cr arr2}=\matrix{0&3 \cr 1&2} \)[table=100%][tr][td]\(thread\) 0
\( v_0=\left[ \matrix{3&-1&1&3} \right] \)
\( v_1=\left[ \matrix{2&3&1&1} \right] \)
進行\(Gauss\) \(Reduction\)[/td][td]\(thread\) 1
\( v_2=\left[ \matrix{-4&1&-4&3} \right] \)
\( v_3=\left[ \matrix{-2&2&6&-1} \right] \)
進行\(Gauss\) \(Reduction\)[/td][/tr]
[tr][td]\( \Vert\; v_0 \Vert\;=\sqrt{20}>\Vert\; v_1 \Vert\;=\sqrt{15} \)
兩向量交換
\( v_0=\left[ \matrix{2&3&1&1} \right] \)
\( v_1=\left[ \matrix{3&-1&1&3} \right] \)[/td][td]\( \Vert\; v_2 \Vert\;=\sqrt{42}<\Vert\; v_3 \Vert\;=\sqrt{45} \)
兩向量不需交換[/td][/tr]
[tr][td]\( \displaystyle q=\Bigg\lfloor\; \frac{v_0 \cdot v_1}{v_0 \cdot v_0} \Bigg\rceil\;=\Bigg\lfloor\; \frac{7}{15} \Bigg\rceil\;=\Bigg\lfloor\; 0.466 \Bigg\rceil\;=0 \)
\(v_0\)和\(v_1\)化簡結束[/td][td]\( \displaystyle q=\Bigg\lfloor\; \frac{v_2 \cdot v_3}{v_2 \cdot v_2} \Bigg\rceil\;=\Bigg\lfloor\; \frac{-17}{42} \Bigg\rceil\;=\Bigg\lfloor\; -0.404 \Bigg\rceil\;=0 \)
\(v_2\)和\(v_3\)化簡結束[/td][/tr][/table]
\( v=\left[ \matrix{2&3&1&1\cr 3&-1&1&3\cr -4&1&-4&3\cr -2&2&6&-1} \right] \)
\(for\) \(i=1\) \(to\) \(n-1\)
\(for\) \(j=i+1\) \(to\) \(n\)
\(v_i\)和\(v_j\)進行\(Gauss\) \(Reduction\)
\(end\)
\(end\)
第1輪
\( \matrix{array1:&1&&2&→&3&→&4\cr &&↗&&&&&↓ \cr array2:&5&←&6&←&7&←&8 }\)，\( \matrix{v_1和v_5\cr v_2和v_6\cr v_3和v_7\cr v_4和v_8} \)同時進行\(Gauss\) \(Reduction\)
第2輪
\( \matrix{array1:&1&&5&→&2&→&3\cr &&↗&&&&&↓ \cr array2:&6&←&7&←&8&←&4 }\)，\( \matrix{v_1和v_6\cr v_5和v_7\cr v_2和v_8\cr v_3和v_4} \)同時進行\(Gauss\) \(Reduction\)
第3輪
\( \matrix{array1:&1&&6&→&5&→&2\cr &&↗&&&&&↓ \cr array2:&7&←&8&←&4&←&3 }\)，\( \matrix{v_1和v_7\cr v_6和v_8\cr v_4和v_5\cr v_2和v_3} \)同時進行\(Gauss\) \(Reduction\)
第4輪
\( \matrix{array1:&1&&7&→&6&→&5\cr &&↗&&&&&↓ \cr array2:&8&←&4&←&3&←&2 }\)，\( \matrix{v_1和v_8\cr v_4和v_7\cr v_3和v_6\cr v_2和v_5} \)同時進行\(Gauss\) \(Reduction\)
第5輪
\( \matrix{array1:&1&&8&→&7&→&6\cr &&↗&&&&&↓ \cr array2:&4&←&3&←&2&←&5 }\)，\( \matrix{v_1和v_4\cr v_3和v_8\cr v_2和v_7\cr v_5和v_6} \)同時進行\(Gauss\) \(Reduction\)
第6輪
\( \matrix{array1:&1&&4&→&8&→&7\cr &&↗&&&&&↓ \cr array2:&3&←&2&←&5&←&6 }\)，\( \matrix{v_1和v_3\cr v_2和v_4\cr v_5和v_8\cr v_6和v_7} \)同時進行\(Gauss\) \(Reduction\)
第7輪
\( \matrix{array1:&1&&3&→&4&→&8\cr &&↗&&&&&↓ \cr array2:&2&←&5&←&6&←&7 }\)，\( \matrix{v_1和v_2\cr v_3和v_5\cr v_4和v_6\cr v_8和v_8} \)同時進行\(Gauss\) \(Reduction\)
第8輪
\( \matrix{array1:&1&&2&→&3&→&4\cr &&↗&&&&&↓ \cr array2:&5&←&6&←&7&←&8 }\)，回到初始值
\( \matrix{1& &2&\rightarriw&3&\rightarriw&4\cr &\nearrow& & & & &\downarrow \cr 5&\leftarrow&6&\leftarrow&7&\leftarrow&8} \)
array1:１ ２→３→４
↗ ↓
array2:５←６←７←８
←→↖↗↓
[tr][td][/td][td][/td][/tr]
\( \left[ \matrix{4 & 9 & 3 & -5 & -5 & -1 & 7 & -1 & -5 \cr -2 & -8 & -7 & -1 & -3 & 6 & -3 & 9 & 8 \cr 1 & -3 & -2 & 3 & 9 & 7 & 2 & 7 & -2 \cr -5 & 6 & 4 & -2 & -2 & -7 & -2 & -9 & 1 \cr 1 & -2 & -2 & 7 & 7 & -3 & -9 & -5 & -4 \cr 7 & 1 & -4 & 3 & -2 & 9 & 9 & 7 & 6} \right] \)
[table=100%][tr][td]\( \matrix{4 & 9 & 3 & -5 & -5 & -1 & 7 & -1 & -5} \)[/td][td]\( \matrix{-2 & -8 & -7 & -1 & -3 & 6 & -3 & 9 & 8} \)[/td][td]\( \matrix{1 & -3 & -2 & 3 & 9 & 7 & 2 & 7 & -2} \)[/td][/tr][/table]
頁:
[1]