代数

中国剩余定理 设$m_1,m_2,\dots,m_k$两两互素，则方程组： $$ \begin{equation} \begin{cases} x\equiv a_1(\bmod\space m_1) \\ x\equiv a_2(\bmod\space m_2) \\ \dots \\ x\equiv a_k(\bmod\space m_k) \end{cases} \end{equation} $$有唯一解：$x\equiv M_1M_1^{-1}a_1+M_2M_2^{-1}a_2+\dots+M_kM_k^{-1}a_k(\bmod\space m)$ 其中，$m=m_1m_2\dots m_k$，$M_i=\frac m{m_i}$，$M_iM_i^{-1}\equiv 1(\bmod\space m_i)$ RSA密码算法 密钥生成 选择两个保密的大素数$p$、$q$ 取$n=p*q$，并计算$n$的欧拉函数值：$\varphi(n)=(p-1)*(q-1)$ 选择一个介于1与$\varphi(n)$之间的整数$e$，且满足$\gcd(\varphi(n),e)=1$，即与$\varphi(n)$互素 计算$e^{-1}(\bmod\space\varphi(n))$得到$d$ 将公钥设为$(e,n)$，私钥为$(d,n)$ 加密 $$ c\equiv m^e(\bmod\space n) $$解密 $$ m\equiv c^d(\bmod\space n) $$Rabin密码算法 密钥生成 固定了$e=2$，且p、q的阶需要相同 公钥为$n$，私钥为$(p,q)$ 加密 $$ c\equiv m^2(\bmod\space n) $$解密 相当于求解二次同余方程$x^2\equiv c\bmod n$，等价于求解$x^2\equiv c\bmod p$与$x^2\equiv c\bmod q$，即： $$ \begin{equation} \begin{cases} x\equiv \sqrt c\bmod p \\ x\equiv \sqrt c\bmod q \\ x\equiv -\sqrt c\bmod p \\ x\equiv -\sqrt c\bmod q \end{cases} \end{equation} $$求解后一共会产生四组解，逐个验证并选择有意义的一项作为明文即可 ...