索引

保密通讯仿射密码例子 指数密码 ( Pohlig, Hellman, 1978 )例子 RSA公开密钥体制( Rivest, Shamir, Adleman, 1977; 英国情报部门的Cocks 1973年已发明 )例子

保密通讯

  保密通讯分为3步：

发送方使用密钥把明码转换成密码；密码的传输；接收方使用解钥把密码转换成明码。

  在公开密钥体制中，密钥和加密程序是公开的；解钥不公开，仅信息接收方知道。   第三方若要破解收到的密码，首先要得到或者破解解钥。

仿射密码

概述   以明码为英语字母为例，将字母按照下表转化为数字$x$（明码的等价表示），通过 $$x\mapsto \left(ax+b\mathrm{m}\mathrm{o}\mathrm{d}26\right):=y$$ 加密成密码（$a,b\in \mathbb{Z}$未知，$\gcd \left(a,26\right)=1$），再通过 $$y\mapsto (a^{11}\left(y-b\right)\mathrm{m}\mathrm{o}\mathrm{d}26)=x$$ 解密出数字（明码），最后将数字按下表转换回字母。 $$\begin{array}{ccccccccccccc}0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12\\ A& B& C& D& E& F& G& H& I& J& K& L& M\\ 13& 14& 15& 16& 17& 18& 19& 20& 21& 22& 23& 24& 25\\ N& O& P& Q& R& S& T& U& V& W& X& Y& Z\end{array}$$

注

$ax+b\mathrm{m}\mathrm{o}\mathrm{d}26$表示取$ax+b$模掉（除以）26后剩下的余数$d$, $d\in {\mathbb{Z}}_{\ge 0},0\le d\le 25$。要求$\gcd \left(a,26\right)=1$，是因为$A,B,\cdots ,Y,Z$对应的数字$0,1,\cdots ,24,25$构成模$26$的完全剩余系$K$。设$x$通过$K$，当$\gcd \left(a,26\right)=1$时，$ax+b$ (即$y$) 也才通过模$26$的完全剩余系$aK+b$。 此时也才成立$x$到$ax+b\text{ mod26}$的单射关系，而不至于两个不同的明码加密成同一个密码。$\gcd \left(a,26\right)=1\Rightarrow \text{ gcd}\left(a^{11},26\right)=1$，也就有$y$到$a^{11}\left(y-b\right)=a^{11}y-a^{11}b\mathrm{m}\mathrm{o}\mathrm{d}26$的单射关系，不至于两个不同的密码解密出同一个明码。

概括

密钥: $a,b\in \mathbb{Z},\gcd \left(a,26\right)=1$解钥: $a,b\in \mathbb{Z},\gcd \left(a,26\right)=1$加密: 明码$r\in \left\{0,1,\cdots ,25\right\}$， $ar+b\equiv s\left(\mathrm{m}\mathrm{o}\mathrm{d}26\right)$解密: 密码$s$，$a^{11}\left(s-b\right)\equiv r\left(\mathrm{m}\mathrm{o}\mathrm{d}26\right)$ 解密式子的证明如下。 一方面， $$\begin{array}{c}\gcd \left(a,26\right)=1\\ \phi \left(26\right)=\phi \left(2\times 13\right)=\phi \left(2\right)\times \phi \left(13\right)=12\end{array}\}\Rightarrow a^{\phi \left(26\right)}=a^{12}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}26\right)$$ 另一方面， $$ar+b\equiv s\left(\mathrm{m}\mathrm{o}\mathrm{d}26\right)\iff ar\equiv s-b\left(\mathrm{m}\mathrm{o}\mathrm{d}26\right)$$ 因此有 $$\begin{array}{rl}& r\mathrm{m}\mathrm{o}\mathrm{d}26\\ & =1\cdot r\\ & \equiv a^{12}r\\ & =a^{11}\left(ar\right)\\ & \equiv a^{11}\left(s-b\right)\mathrm{m}\mathrm{o}\mathrm{d}26\end{array}$$

加密过程

例子

已知仿射密码用 $$x\mapsto x+k\mathrm{m}\mathrm{o}\mathrm{d}26$$ 加密。现有一密码为$LBSLY$，请解密。 （注：这个加密方式并不好，解密只需减$k\text{ mod26}$。对于计算机，使用穷举法，很快就能完成） 解   英语中各字母出现频率从高到低依次为 $$etaoinsrhldcumfpgwybvkxjqz$$ 而密码$LBSLY$中$L$出现次数最多，故猜想$E\to L$，即有$k\equiv 7\mathrm{m}\mathrm{o}\mathrm{d}26$, 也就有解密 $$y\mapsto y-k\mathrm{m}\mathrm{o}\mathrm{d}26$$ 下面解密： $$\begin{array}{rl}& LBSLY\\ & \leftrightarrow 11,1,18,11,24\\ & -7\mathrm{m}\mathrm{o}\mathrm{d}264,20,11,4,17\\ & \leftrightarrow EULER\end{array}$$ 已经有意义，如果合理，不需要进行其它尝试。

已知某通讯使用仿射密码 $$x\mapsto 7x+3\mathrm{m}\mathrm{o}\mathrm{d}26$$ 请加密$GAUSS$和解密$MFSJDG$。 解

对$GAUSS$加密过程如下。 $$\begin{array}{rl}& GAUSS\\ & \leftrightarrow 6,0,20,18,18\\ & 7x+345,3,143,129,129\\ & \mathrm{m}\mathrm{o}\mathrm{d}2619,3,13,25,25\\ & \leftrightarrow TDNZZ\end{array}$$首先解$7^{11}\mathrm{m}\mathrm{o}\mathrm{d}26$如下。 $$\begin{array}{rl}& 7^{11}\mathrm{m}\mathrm{o}\mathrm{d}26\\ & ={49}^5\times 7\\ & \equiv {\left(-3\right)}^5\times 7\left(\because 49-26\times 2=-3\right)\\ & =9^2\times \left(-21\right)\\ & \equiv 3\times 5\left(\because -21+26=5,9^2=81=26\times 3+3\right)\\ & =15\mathrm{m}\mathrm{o}\mathrm{d}26\end{array}$$ 然后对$MFSJDG$解密如下。 $$\begin{array}{rl}& MFSJDG\\ & \leftrightarrow 12,5,18,9,3,6\\ & 7^{11}\left(y-3\right)\equiv 15\left(y-3\right)\left(\mathrm{m}\mathrm{o}\mathrm{d}26\right)135,30,225,90,0,45\\ & \mathrm{m}\mathrm{o}\mathrm{d}265,4,17,12,0,19\\ & \leftrightarrow FERMAT\end{array}$$

指数密码 ( Pohlig, Hellman, 1978 )

概述   设$p$（可公开）是一个素数。

密钥; $e\in {\mathbb{Z}}_{>0}$（可公开）,$0\le e\le p-1$, $\gcd \left(e,p-1\right)=1$

解钥: $d\in {\mathbb{Z}}_{>0}$（保密）,$0\le d\le p-1$, $ed\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}\left(p-1\right)$

加密过程: 设$a\in {\mathbb{Z}}_{>0}$是明码，$0\le a\le p-1$，通过$a^e\equiv b\mathrm{m}\mathrm{o}\mathrm{d}p$得到密码$b$

解密过程: $b^d\equiv a\mathrm{m}\mathrm{o}\mathrm{d}p$   证明 $$\begin{array}{c}p是素数\\ 0\le a\le p-1\end{array}\}\Rightarrow \gcd \left(a,p\right)=1\Rightarrow a^{p-1}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right)$$ $$\begin{array}{rl}& ed\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}\left(p-1\right)\iff ed-1\equiv 0\mathrm{m}\mathrm{o}\mathrm{d}\left(p-1\right)\iff \left(p-1\right)|\left(ed-1\right)\\ & \iff \exists k\in \mathbb{Z},s.t.ed-1=k\left(p-1\right)\end{array}$$ 因此有 $$b^d={\left(a^e\right)}^d=a^{ed}=a^{1+k\left(p-1\right)}=a\cdot {\left(a^{p-1}\right)}^k\equiv a\mathrm{m}\mathrm{o}\mathrm{d}p$$

第三方破解: 已知$p,e$，未知解钥$d$，通过求解 $$ed\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}\left(p-1\right)$$ 得到解钥（不难解），进而破解密码。

例子

已知某通讯使用指数密码，$p=29$，$e=5$。请加密$9$，解密$11$。 解

以下对$9$进行加密。 $$\begin{array}{rl}& 9^5\mathrm{m}\mathrm{o}\mathrm{d}29\\ & ={81}^2\times 9\\ & ={\left(-6\right)}^2\times 9\left(\because 21-29\times 3=-6\right)\\ & =36\times 9\\ & \equiv 7\times 9\left(\because 36=29\times 1+7\right)\\ & =63\\ & \equiv 5\mathrm{m}\mathrm{o}\mathrm{d}29\end{array}$$ 因此$9$被加密成$5$。未知解钥$d$，先求解$$ed=5d\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}\left(29-1=28\right)$$

法一 $$\begin{array}{c}\gcd \left(5,28\right)=1\\ \phi \left(28\right)=\phi \left(2^2\times 7\right)=12\end{array}\}\Rightarrow 5^{\phi \left(28\right)}=5^{12}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}28$$ $$\begin{array}{rl}& d=1\cdot d\\ & \equiv 5^{12}\cdot d\\ & =5^{11}\left(5d\right)\\ & \equiv 5^{11}\\ & ={25}^5\times 5\\ & \equiv {\left(-3\right)}^5\times 5\left(\because 25-28=-3\right)\\ & =9^2\times \left(-15\right)\\ & =81\times \left(-15\right)\\ & \equiv \left(-3\right)\times \left(-15\right)\left(\because 81-28\times 3=-3\right)\\ & =45\\ & \equiv 17\mathrm{m}\mathrm{o}\mathrm{d}28\end{array}$$

法二 问题等价于求解不定方程 $$5d+28y=1$$ $\gcd \left(5,28\right)=1|1$，因此有解。 $$\begin{array}{c}\begin{array}{rl}& 28=5\times 5+3\\ & 5=3\times 1+2\\ & 3=2\times 1+1\\ & \end{array}\\ P_0=1,P_1=5,P_2=1\times 5+1=6,P_3=1\times 6+5=11\\ Q_0=0,Q_1=1,Q_2=1,Q_3=1\times 1+1=2\end{array}$$ 因此$5d+28y=1$有特解$\left({\left(-1\right)}^3{P}_3,{\left(-1\right)}^2{Q}_3\right)=\left(-11,2\right)$，通解为 $$\{\begin{array}{rl}& d=-11-28t\equiv 17\mathrm{m}\mathrm{o}\mathrm{d}28\\ & y=2+5t\end{array},\forall t\in \mathbb{Z}$$

在此基础上，解密$11$如下。 $$\begin{array}{rl}& {11}^{17}\mathrm{m}\mathrm{o}\mathrm{d}29\\ & ={121}^8\times 11\\ & \equiv 5^8\times 11\left(\because 121=29\times 4+5\right)\\ & ={25}^4\times 11\\ & \equiv {\left(-4\right)}^4\times 11\left(\because 25-29=-4\right)\\ & =256\times 11\\ & \equiv \left(-5\right)\times 11\left(\because 256-29\times 9=-5\right)\\ & =-55\\ & \equiv 3\mathrm{m}\mathrm{o}\mathrm{d}29\end{array}$$ 因此$11$被解密为$3$.

（离散对数问题）已知某通讯使用指数密码，$p=29$，设$10$是明码，对应的密码是$27$。求密钥$e$和解钥$d$。 解

先解出$e$。 $10$是明码，$27$是对应的密码，因此有 $${10}^e\equiv 27\mathrm{m}\mathrm{o}\mathrm{d}29$$ 其中$0\le e\le 28\&\gcd \left(e,28\right)=1$，即有 $$e\in \left\{1,3,5,9,11,13,15,17,19,23,25,27\right\}$$ 通过使用穷举法（多次使用$100\equiv 13\mathrm{m}\mathrm{o}\mathrm{d}29$）得到正确的$e$。有下表。 $$\begin{array}{ccccccccccccc}e& 1& 3& 5& 9& 11& 13& 15& 17& 19& 23& 25& 27\\ {10}^e\mathrm{m}\mathrm{o}\mathrm{d}29& 10& 14& 8& 18& 2& 26& 19& 15& 21& 11& 27& 3\end{array}$$ 具体计算如下。 ${10}^1=10\text{ mod29}$ ${10}^3=100\times 10\equiv 13\times 10=29\times 4+14\equiv 14\mathrm{m}\mathrm{o}\mathrm{d}29$ ${10}^5={10}^3\times 100\equiv 14\times 13=182=29\times 6+8\equiv 8\mathrm{m}\mathrm{o}\mathrm{d}29$ ${10}^9={10}^5\times {100}^2\equiv 8\times {13}^2=1352=29\times 46+18\equiv 18\mathrm{m}\mathrm{o}\mathrm{d}29$ ${10}^{11}={10}^9\times 100\equiv 18\times 13=234=29\times 8+2\equiv 2\mathrm{m}\mathrm{o}\mathrm{d}29$ ${10}^{13}={10}^{11}\times 100\equiv 2\times 13=26\mathrm{m}\mathrm{o}\mathrm{d}29$ ${10}^{15}={10}^{13}\times 100\equiv 26\times 13\equiv \left(-3\right)\times 13=-39\equiv 19\mathrm{m}\mathrm{o}\mathrm{d}29$ ${10}^{17}={10}^{15}\times 100\equiv 19\times 13=247=29\times 8+15\equiv 15\mathrm{m}\mathrm{o}\mathrm{d}29$ ${10}^{19}={10}^{17}\times 100\equiv 15\times 13=195=29\times 6+21\equiv 21\mathrm{m}\mathrm{o}\mathrm{d}29$ ${10}^{23}={10}^{19}\times {100}^2\equiv 21\times {13}^2=21\times 169\equiv \left(-8\right)\times \left(-5\right)=40\equiv 11\mathrm{m}\mathrm{o}\mathrm{d}29$ ${10}^{25}={10}^{23}\times 100\equiv 11\times 13=143=29\times 4+27\equiv 27\mathrm{m}\mathrm{o}\mathrm{d}29$ ${10}^{27}={10}^{25}\times 100\equiv 27\times 13\equiv \left(-2\right)\times 13=-26\equiv 3\mathrm{m}\mathrm{o}\mathrm{d}29$ 因此有$e=25$。由于计算较多，再检查一遍。 $$\begin{array}{rl}& {10}^{25}\mathrm{m}\mathrm{o}\mathrm{d}29\\ & ={100}^{12}\times 10\\ & \equiv {13}^{12}\times 10\left(\because 100=29\times 3+13\right)\\ & ={169}^6\times 10\\ & \equiv {\left(-5\right)}^6\times 10\left(\because 169-29\times 6=-5\right)\\ & ={25}^3\times 10\\ & \equiv {\left(-4\right)}^3\times 10\left(\because 25-29=-4\right)\\ & =16\times \left(-40\right)\\ & \equiv 16\times 18\left(\because -40+29=-18\right)\\ & =288\\ & \equiv 27\mathrm{m}\mathrm{o}\mathrm{d}29\end{array}$$

再通过解$25d\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}29-1=28$求解$d$ $$25d\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}28\iff -3d\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}28$$

法一 $$\begin{array}{rl}& \begin{array}{c}\gcd \left(3,28\right)=1\\ \phi \left(28\right)=\phi \left(2^2\times 7\right)=2^{2-1}\times \left(2-1\right)\times \left(7-1\right)=12\end{array}\}\\ & \Rightarrow 3^{\phi \left(28\right)}=3^{12}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}28\end{array}$$ $$\begin{array}{rl}& d=1\cdot d\\ & \equiv 3^{12}d\\ & =-3^{11}\left(-3d\right)\\ & \equiv -3^{11}\\ & =-9^5\times 3\\ & \equiv -{81}^2\times 27\\ & \equiv -{\left(-3\right)}^2\times \left(-1\right)\left(\because 81-28\times 3=-3,27-28=-1\right)\\ & =9\mathrm{m}\mathrm{o}\mathrm{d}28\end{array}$$

法二：等价于解不定方程$-3d-28y=1$ $$\begin{array}{c}28=3\times 9+1\\ P_0=0,P_1=9;Q_0=0,Q_1=1\end{array}$$ 因此$-3d-28y=1$有特解$$\left(d,y\right)=\left({\left(-1\right)}^{1+1}{P}_1,{\left(-1\right)}^{1-1+1}{Q}_1\right)=\left(9,-1\right)$$通解为 $$\{\begin{array}{rl}& d=9+28t\equiv 9\\ & y=-1-3t\end{array},\forall t\in \mathbb{Z}$$

法三 $$\begin{array}{rl}& -3d\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}28\\ & \iff -3d\equiv 1-28\mathrm{m}\mathrm{o}\mathrm{d}28\\ & \iff -3d\equiv -27\mathrm{m}\mathrm{o}\mathrm{d}28\\ & \iff d\equiv 9\mathrm{m}\mathrm{o}\mathrm{d}28\left(\because \gcd \left(-3,28\right)=1\right)\end{array}$$

RSA公开密钥体制( Rivest, Shamir, Adleman, 1977; 英国情报部门的Cocks 1973年已发明 )

概述   设$N\in {\mathbb{Z}}_{>0}$（可公开），$N=pq$，$p,q$均为素数（保密），且$p,q$的位数很大，往往超过100位。

密钥: $e\in {\mathbb{Z}}_{>0}$（可公开）

解钥: $d\in {\mathbb{Z}}_{>0}$（保密）, $ed\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}\left(\phi \left(N\right)=\phi \left(pq\right)=\left(p-1\right)\left(q-1\right)\right)$

加密过程: 设$a\in {\mathbb{Z}}_{>0}$是明码（可选为4位数），$0\le a\le N-1$。通过 $$a^e\equiv b\mathrm{m}\mathrm{o}\mathrm{d}N$$ 得到密码$b$。

解密过程: 通过 $$b^d\equiv a\mathrm{m}\mathrm{o}\mathrm{d}N$$ 得到明码$a$   证明 $$\begin{array}{rl}& ed\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}\phi \left(N\right)\iff ed-1\equiv 0\mathrm{m}\mathrm{o}\mathrm{d}\phi \left(N\right)\\ & \iff \exists k\in \mathbb{Z},s.t.ed-1=k\phi \left(N\right)\end{array}$$ $$b^d\equiv {\left(a^e\right)}^d=a^{ed}=a^{1+k\phi \left(N\right)}\mathrm{m}\mathrm{o}\mathrm{d}N$$

若$\gcd \left(a,N\right)=1$，由欧拉定理有 $$a^{\phi \left(N\right)}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}N$$ 此时有 $$b^d\equiv a^{1+k\phi \left(N\right)}=a\cdot {\left(a^{\phi \left(N\right)}\right)}^k\equiv a\mathrm{m}\mathrm{o}\mathrm{d}N$$

若$\gcd \left(a,N\right)>1$，   若$p|a$，则$$b^d\equiv a^{1+k\phi \left(N\right)}\equiv 0\equiv 0+a=a\mathrm{m}\mathrm{o}\mathrm{d}p$$   若$p|a$，则由费马小定理，有 $$\begin{array}{rl}& a^{p-1}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}p\\ & \Rightarrow b^d\equiv a^{1+k\phi \left(N\right)}=a^{1+k\left(p-1\right)\left(q-1\right)}=a{\left(a^{p-1}\right)}^{k\left(q-1\right)}\equiv a\mathrm{m}\mathrm{o}\mathrm{d}p\end{array}$$ 因此一定有 $$b^d\equiv a\mathrm{m}\mathrm{o}\mathrm{d}p$$ 同理可得 $$b^d\equiv a\mathrm{m}\mathrm{o}\mathrm{d}q$$ 故有 $$b^d\equiv a\mathrm{m}\mathrm{o}\mathrm{d}lcm\left(p,q\right)=pq=N$$

第三方破解: 已知$N,e$，未知$d$。最关键的是快速猜出$p,q$。

例子

  已知某通讯使用RSA密码，$N=2537,e=13$，请加密$PUBLIC$，解密$1299$。 解

首先将$PUBLIC$转化为数字。 $$PUBLIC\leftrightarrow 15,20,1,11,8,2$$

若直接对每个数字进行加密，则有 $$\begin{array}{rl}& {15}^{13}\mathrm{m}\mathrm{o}\mathrm{d}2537\\ & ={\left({15}^3\right)}^4\times 15\\ & \equiv {838}^4\times 15\left(\because {15}^3=3375=2537\times 1+838\right)\\ & \equiv {2032}^2\times 15\left(\because {838}^2=702244=2537\times 276+2032\right)\\ & \equiv {\left(-505\right)}^2\times 15\left(\because 2032-2537=-505\right)\\ & \equiv 1325\times 15\left(\because {505}^2=255025=2537\times 100+1325\right)\\ & \equiv 2116\mathrm{m}\mathrm{o}\mathrm{d}2537\end{array}$$ $$\begin{array}{rl}& {20}^{13}\mathrm{m}\mathrm{o}\mathrm{d}2537\\ & ={\left({20}^4\right)}^3\times 20\\ & \equiv {169}^3\times 20\left(\because {20}^4=160000=2537\times 63+169\right)\\ & ={169}^2\times \left(169\times 20\right)\\ & \equiv 654\times 843\left(\begin{array}{rl}& \because {169}^2=28561=2537\times 11+654\\ & 169\times 20=3380=2537\times 1+843\end{array}\right)\\ & \equiv 793\mathrm{m}\mathrm{o}\mathrm{d}2537\end{array}$$ $$1^{13}\mathrm{m}\mathrm{o}\mathrm{d}2537=1\mathrm{m}\mathrm{o}\mathrm{d}2537$$ $$\begin{array}{rl}& {11}^{13}\mathrm{m}\mathrm{o}\mathrm{d}2537\\ & ={\left({11}^4\right)}^3\times 11\\ & \equiv {1956}^3\times 11\left(\because {11}^4=14641=2537\times 5+1956\right)\\ & \equiv {\left(-581\right)}^3\times 11\left(\because 1956-2537=-581\right)\\ & ={581}^2\times \left(-581\times 11\right)\\ & \equiv -140\times 1317\left(\begin{array}{rl}& \because {581}^2=337561=2537\times 133+140\\ & 581\times 11=6391=2537\times 2+1317\end{array}\right)\\ & \equiv -1716\\ & \equiv 821\mathrm{m}\mathrm{o}\mathrm{d}2537\end{array}$$ $$\begin{array}{rl}& 8^{13}\mathrm{m}\mathrm{o}\mathrm{d}2537\\ & ={\left(8^4\right)}^3\times 8\\ & \equiv {1559}^3\times 8\left(\because 8^4=4096=2537\times 1+1559\right)\\ & \equiv {\left(-978\right)}^3\times 8\left(\because 1569-2537=-978\right)\\ & ={978}^2\times \left(-978\times 8\right)\\ & \equiv 35\times 213\left(\begin{array}{rl}& \because {978}^2=956484=2537\times 377+35\\ & 978\times 8=7824=2537\times 3+213\end{array}\right)\\ & \equiv 2381\mathrm{m}\mathrm{o}\mathrm{d}2537\end{array}$$ $$\begin{array}{rl}& 2^{13}\mathrm{m}\mathrm{o}\mathrm{d}2537\\ & =2^{12}\times 2\\ & \equiv 1559\times 2\left(\because 2^{12}=4096=2537\times 1+1559\right)\\ & \equiv 581\mathrm{m}\mathrm{o}\mathrm{d}2537\end{array}$$ 因此密码为 $$2116,0793,0001,0821,2381,581$$

若将数字按两个一组进行整理，即得 $$1520,0111,0802$$ 在此基础上对整理后的数字进行加密。 $$\begin{array}{rl}& {1520}^{13}\mathrm{m}\mathrm{o}\mathrm{d}2537\\ & ={\left({1520}^2\right)}^6\times 1520\\ & ={2310400}^6\times 1520\\ & \equiv {1730}^6\times 1520\\ & ={\left({1730}^2\right)}^3\times 1520\\ & ={2992900}^3\times 1520\\ & \equiv {1777}^3\times 1520\\ & ={1777}^2\times \left(1777\times 1520\right)\\ & =3157729\times 2701040\\ & \equiv 1701\times 1672\\ & =2844072\\ & \equiv 95\mathrm{m}\mathrm{o}\mathrm{d}2537\end{array}$$ $$\begin{array}{rl}& {111}^{13}\mathrm{m}\mathrm{o}\mathrm{d}2537\\ & ={\left({111}^2\right)}^6\times 111\\ & ={12321}^6\times 111\\ & \equiv {2173}^6\times 111\\ & ={\left({2173}^2\right)}^3\times 111\\ & ={4721929}^3\times 111\\ & \equiv {572}^3\times 111\\ & ={572}^2\times \left(572\times 111\right)\\ & =327184\times 63492\\ & \equiv 2448\times 67\\ & =164016\\ & \equiv 1648\mathrm{m}\mathrm{o}\mathrm{d}2537\end{array}$$ $$\begin{array}{rl}& {802}^{13}\mathrm{m}\mathrm{o}\mathrm{d}2537\\ & ={\left({802}^2\right)}^6\times 802\\ & ={643204}^6\times 802\\ & \equiv {1343}^6\times 802\\ & ={\left({1343}^2\right)}^3\times 802\\ & ={1803649}^3\times 802\\ & \equiv {2379}^3\times 802\\ & ={2379}^2\times \left(2379\times 802\right)\\ & =5659641\times 1907958\\ & \equiv 2131\times 134\\ & =285554\\ & \equiv 1410\mathrm{m}\mathrm{o}\mathrm{d}2537\end{array}$$ 因此得密码为 $$0095,1648,1410$$

想要解密$1299$，首先需要知道解钥$d$。

首先分解$N=2537$。 $$\lfloor \sqrt[]{2537}\rfloor =50$$ 检查$50$以下的素数是否为因子。   个位是$7$，因此不是$2,5$的倍数。   $3|\left(2+3+5+7=17\right)$，因此非$3$倍数。   $537-2=535=5\times 107$，其中$107$是素数，所以不是$7,11,13$的倍数。 接下来， $$\begin{array}{rl}& 2537=17\times 149+4\\ & 2537=19\times 133+10\\ & 2537=23\times 110+7\\ & 2537=29\times 87+14\\ & 2537=31\times 81+26\\ & 2537=37\times 68+21\\ & 2537=41\times 61+36\\ & 2537=43\times 59\end{array}$$ 所以有 $$\phi \left(2537\right)=\phi \left(43\times 59\right)=\phi \left(43\right)\phi \left(59\right)=42\times 58=2436$$

通过求解$13d\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}2436$来求解$d$，此处通过求解等价不定方程 $$13d+2436y=1$$ 来求解$d$。 $\gcd \left(13,2436\right)=1|1$，因此有解。 $$\begin{array}{c}\begin{array}{rl}& 2436=13\times 187+5\\ & 13=5\times 2+3\\ & 5=3\times 1+2\\ & 3=2\times 1+1\end{array}\\ P_0=1,P_1=187,P_2=2\times 187+1=375,\\ P_3=1\times 375+187=562,P_4=1\times 562+375=937\\ Q_0=0,Q_1=1,Q_2=2\\ Q_3=1\times 2+1=3,Q_3=1\times 3+2=5\end{array}$$ 因此$13d+2436y=1$有特解$\left({\left(-1\right)}^4{P}_4,{\left(-1\right)}^{4-1}{Q}_4\right)=\left(937,-5\right)$，也就有 $$d\equiv 937\mathrm{m}\mathrm{o}\mathrm{d}2436$$

得知$d$可取$937$后，开始解密$1299$。

法一（直接解${1299}^{937}\mathrm{m}\mathrm{o}\mathrm{d}2537$） $$\begin{array}{rl}& {1299}^{937}\mathrm{m}\mathrm{o}\mathrm{d}2537={\left({1299}^2\right)}^{468}\times 1299\\ & ={1687401}^{468}\times 1299\\ & \equiv {296}^{468}\times 1299={\left({296}^2\right)}^{234}\times 1299\\ & ={87616}^{234}\times 1299\\ & \equiv {1358}^{234}\times 1299={\left({1358}^2\right)}^{117}\times 1299\\ & ={1844164}^{117}\times 1299\\ & \equiv {\left(-235\right)}^{117}\times 1299=-{\left({235}^2\right)}^{58}\times \left(235\times 1299\right)\\ & =-{55225}^{58}\times 305265\\ & \equiv -{1948}^{58}\times 825={\left({1948}^2\right)}^{29}\times 825\\ & =-{3794704}^{29}\times 825\\ & \equiv -{1889}^{29}\times 825=-{\left({1889}^2\right)}^{14}\times \left(825\times 1889\right)\\ & =-{3568321}^{14}\times 1558425\\ & \equiv -{1299}^{14}\times 707={\left({1299}^2\right)}^7\times 707\\ & \equiv -{296}^7\times 707=-{\left({296}^2\right)}^3\times \left(296\times 707\right)\\ & \equiv -{1358}^3\times 209272\\ & \equiv -{1358}^3\times 1238=\left(-{1358}^2\right)\times \left(1358\times 1238\right)\\ & \equiv 235\times 1710\\ & =401850\\ & \equiv 1004\mathrm{m}\mathrm{o}\mathrm{d}2537\end{array}$$

法二（解同余式组，推荐） $$\begin{array}{rl}& 1299=43\times 30+9\equiv 9\mathrm{m}\mathrm{o}\mathrm{d}43\Rightarrow {1299}^{937}\equiv 9^{937}\mathrm{m}\mathrm{o}\mathrm{d}43\\ & 1299=59\times 22+1\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}59\Rightarrow {1299}^{937}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}59\end{array}$$ 进一步化简$9^{937}\mathrm{m}\mathrm{o}\mathrm{d}43$如下。 $43$是素数且$43|9$，于是由费马小定理有 $$\begin{array}{rl}& 9^{43-1}=9^{42}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}43\\ & \Rightarrow 9^{937}=9^{42\times 22+13}={\left(9^{42}\right)}^{22}\cdot 9^{13}\equiv 9^{13}\mathrm{m}\mathrm{o}\mathrm{d}43\end{array}$$ 再化简$9^{13}\text{ mod43}$如下。 $$\begin{array}{rl}& 9^{13}\mathrm{m}\mathrm{o}\mathrm{d}43\\ & ={81}^6\times 9\\ & \equiv {\left(-5\right)}^6\times 9\\ & ={25}^3\times 9\\ & ={25}^2\times \left(25\times 9\right)\\ & =625\times 225\\ & \equiv 23\times 10\\ & =230\\ & \equiv 15\mathrm{m}\mathrm{o}\mathrm{d}43\end{array}$$ 于是我们得到了以下同余式组 $$\begin{array}{rl}& \{\begin{array}{rl}& {1299}^{937}\equiv 15\mathrm{m}\mathrm{o}\mathrm{d}43\\ & {1299}^{937}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}59\end{array}\\ & \iff \exists x_0,y_0\in \mathbb{Z},s.t.43x_0+15=59y_0+1={1299}^{937}\end{array}$$ 这给出了一个不定方程 $$59y-43x=14$$ $\gcd \left(59,43\right)=1|14$，因此有解。 $$\begin{array}{c}\begin{array}{rl}& 59=43\times 1+16\\ & 43=16\times 2+11\\ & 16=11\times 1+5\\ & 11=5\times 2+1\end{array}\\ P_0=1,P_1=1,P_2=2\times 1+1=3,P_3=1\times 3+1=4,P_4=2\times 4+3=11\\ Q_0=0,Q_1=1,Q_2=2,Q_3=1\times 2+1=3,Q_4=2\times 3+2=8\end{array}$$ 因此$59y-43x=1$有特解$\left(y,x\right)=\left({\left(-1\right)}^{4-1}{Q}_4,{\left(-1\right)}^{4+1}{P}_4\right)=\left(-8,-11\right)$ $59y-43x=14$有特解$\left(y,x\right)=\left(-8\times 14,-11\times 14\right)=\left(-112,-154\right)$，通解为 $$\{\begin{array}{rl}& y=-112+43t\\ & x=-154+59t\end{array},\forall t\in \mathbb{Z}$$ 因此$\exists t_0\in \mathbb{Z},s.t.y_0=-112+43t_0$， $$\begin{array}{rl}& {1299}^{937}=59y_0+1\\ & =59\times \left(-112+43t_0\right)+1\\ & \equiv -112\times 59+1\\ & =-6607\\ & \equiv -6607+2537\times 3\\ & =1004\mathrm{m}\mathrm{o}\mathrm{d}2537\end{array}$$ 注 （$2537=43\times 59$，$43$和$59$都是素数，这样子最终化简${1299}^{937}=59y_0+1$过程中才会出现含$59\times 43=2537$的形式，方便直接模掉$2537$。）

法三 $$\begin{array}{rl}& 43|1299\Rightarrow \gcd \left(1299,43\right)=1\Rightarrow {1299}^{42}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}43\\ & 59|1299\Rightarrow \gcd \left(1299,59\right)=1\Rightarrow {1299}^{58}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}59\end{array}$$ 又$lcm\left(42,58\right)=2lcm\left(21,29\right)=2\times 21\times 29=1218$，因此有 $$\begin{array}{rl}& {1299}^{1218}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}43\\ & {1299}^{1218}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}59\end{array}\}\Rightarrow {1299}^{1218}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}lcm\left(43,58\right)=2537$$ 设${1299}^{937}\equiv a\mathrm{m}\mathrm{o}\mathrm{d}2537$，则有 $$1\equiv {1299}^{1218}={1299}^{281}\times {1299}^{937}\equiv {1299}^{281}a\mathrm{m}\mathrm{o}\mathrm{d}2537$$ 因此接下来可以先解$${1299}^{281}\equiv b\mathrm{m}\mathrm{o}\mathrm{d}2537$$解出$b$，然后再（用解不定方程法）解$$ba\equiv 1\text{ mod27}$$解出$a\mathrm{m}\mathrm{o}\mathrm{d}2537$。 后面过程省略。

法四 同法二前面的过程，推出了 $$\{\begin{array}{rl}& {1299}^{937}\equiv 15\mathrm{m}\mathrm{o}\mathrm{d}43\\ & {1299}^{937}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}59\end{array}$$ 因此有 $${1299}^{937}\in A=\left\{x:\{\begin{array}{rl}& x\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}59\\ & x\equiv 15\mathrm{m}\mathrm{o}\mathrm{d}43\end{array}\right\}$$ 令 $$B=\left\{x:x=59y\times 15+43z\times 1,\{\begin{array}{rl}& 59y\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}43\\ & 43z\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}59\end{array}\right\}$$ 为了严谨起见，现先证明 $$A=B$$ 一方面，$\forall x\in B,\exists y,z,s.t.$ $$x=59y\times 15+43z\times 1$$ $$\begin{array}{rl}& \begin{array}{rl}& 59y\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}43\\ & 43z\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}59\end{array}\}\Rightarrow \{\begin{array}{rl}& 59y\times 15+43z\times 1\equiv 0\times 15+1\times 1=1\mathrm{m}\mathrm{o}\mathrm{d}59\\ & 59y\times 15+43z\times 1\equiv 1\times 15+0\times 1=15\mathrm{m}\mathrm{o}\mathrm{d}43\end{array}\\ & \\ & \Rightarrow \{\begin{array}{rl}& x\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}59\\ & x\equiv 15\mathrm{m}\mathrm{o}\mathrm{d}43\end{array}\Rightarrow x\in A,B\subseteq A\end{array}$$ 另一方面，$\forall x\in A$， 考虑关于$y,z$的二元一次方程 $$59y\times 15+43z\times 1=x$$ 由于$\gcd \left(59\times 15,43\times 1\right)=1|x$，因此方程有解。且有 $$\begin{array}{rl}& \{\begin{array}{rl}& x\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}59\\ & x\equiv 15\mathrm{m}\mathrm{o}\mathrm{d}43\end{array}\\ & \Rightarrow \{\begin{array}{rl}& 59y\times 15+43z\times 1\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}59\\ & 59y\times 15+43z\times 1\equiv 15\mathrm{m}\mathrm{o}\mathrm{d}43\end{array}\\ & \Rightarrow \{\begin{array}{rl}& 43z\times 1\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}59\\ & 59y\times 15\equiv 15\mathrm{m}\mathrm{o}\mathrm{d}43\end{array}\\ & \Rightarrow \{\begin{array}{rl}& 43z\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}59\\ & 59y\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}43\end{array}\left(\because \gcd \left(1,59\right)=1,\gcd \left(15,43\right)=1\right)\end{array}$$ 因此有$x\in B,A\subseteq B$。 综上有$A=B$。 基于此，我们可考虑通过解 $$\{\begin{array}{rl}& 59y\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}43\\ & 43z\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}59\end{array}$$ 间接解出 $${1299}^{937}=59y_0\times 15+43z_0\times 1\mathrm{m}\mathrm{o}\mathrm{d}2537\left(\exists y_0,z_0\right)$$ $$\begin{array}{ccc}\begin{array}{rl}& 59y\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}43\\ & \iff \left(59-43\right)y=16y\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}43\\ & \iff 16y\equiv 1+43=44\mathrm{m}\mathrm{o}\mathrm{d}43\\ & \iff 4y\equiv 11\mathrm{m}\mathrm{o}\mathrm{d}43\left(\because \gcd \left(4,43\right)=1\right)\\ & \iff 4y\equiv 11+43=54\mathrm{m}\mathrm{o}\mathrm{d}43\\ & \iff 2y\equiv 27\mathrm{m}\mathrm{o}\mathrm{d}43\left(\because \gcd \left(2,43\right)=1\right)\\ & \iff 2y\equiv 27+43=70\mathrm{m}\mathrm{o}\mathrm{d}43\\ & \iff y\equiv 35\mathrm{m}\mathrm{o}\mathrm{d}43\end{array}& & \begin{array}{rl}& 43z\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}59\\ & \iff \left(43-59\right)z=-16z\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}59\\ & \iff -16z\equiv 1+59=60\mathrm{m}\mathrm{o}\mathrm{d}59\\ & \iff -4z\equiv 15\mathrm{m}\mathrm{o}\mathrm{d}59\left(\because \gcd \left(4,59\right)=1\right)\\ & \iff -4z\equiv \left(15-59\right)=-44\mathrm{m}\mathrm{o}\mathrm{d}59\\ & \iff z\equiv 11\mathrm{m}\mathrm{o}\mathrm{d}59\end{array}\end{array}$$ 于是对于${1299}^{937}\in A=B$，$\exists y_0\equiv 35\mathrm{m}\mathrm{o}\mathrm{d}43,z_0\equiv 11\mathrm{m}\mathrm{o}\mathrm{d}59$，使得 $$\begin{array}{rl}& {1299}^{937}\mathrm{m}\mathrm{o}\mathrm{d}2537\\ & \equiv 59y_0\times 15+43z_0\times 1\\ & \equiv 59\times 35\times 15+43\times 11\times 1\\ & =31448\\ & \equiv 1004\mathrm{m}\mathrm{o}\mathrm{d}2537\end{array}$$

上面不同的方法都将$1299$解密为$1004\leftrightarrow 10,04\leftrightarrow K,E$。