期末

字数

1158 字

阅读时间

5 分钟

---

一、求逆元

• 视频链接：扩展欧几里得求逆元（辗转相除法） 使用扩展欧几里得方法来求逆元（前提：$a\mathrm{与}p\mathrm{互}\mathrm{质}$），其中使用到了辗转相除法，如：$ax\equiv 1(modp)$ 每次运算的式子均为：余数 = 被除数 - 商×除数，再将此次的商作为下一个式子的被除数，余数作为下一个式子的除数
• 举个例子，当 $a=5,p=14$ 时，使用辗转相除法如下：
  • 例式如下：首先用 $14÷5$ 得到商：2，余数为4，则辗转相除法的式子为：$4=14-5\times 2$
  • 继续使用上一个式子的除数和余数去做运算，用大数去除以小数，即：$5÷4$，商为1，余数为1，式子为：$1=5-4\times 1$，直到式子左侧得到的余数为1
  • 如此得到最终式子后，再使用上面的式子进行代换，即： 1 = 5 - 4×1 = 5 - （14 - 5×2） = 5×3 - 14，故 5 的逆元为 3
  • 
  • 

二、数字签名，公钥加密和私钥加密，消息认证

• 数字签名技术原理解析：
  • 其中，公钥是是用户向权威机关CA申请的，无法抵赖
    • 
    • 该单位的私钥是由该单位自己产生的一串随机数并存储在单位计算机内，将私钥和企业信息发送给CA后，CA机构会根据私钥生成对应的公钥，实际上，发送给CA机构的并不是该单位的实际公钥，而是与公钥一共生成的证书签名请求文件（CSR文件），而CA机构拿到的所谓私钥也就是这个CSR文件
  • 如何保证CA的权威性：每次都由更高一级的CA来给低一级的CA机构发证书来担保，最高可追溯到CA根证书机构

（一）Elgamal加密算法

• 密钥生成：
  1. 选择一个大质数 p，选择 p 的本原元 g
  2. 选择一个随机数 $\alpha \in Z_p$ (p阶循环阶群)
  3. $g_1=g^{\alpha }modp$
     • 本原元：$g^{\varphi (p)}modp=1$
     • g 是群中的生成元
     • $Z_p=0,1,...,p-1$，$gcd(\alpha ,p)=1$
• 公钥：$(Z_p,p,g,g_1)$
• 私钥：$\alpha$
• 加密过程：
  1. 选择一个随机数 $r\in Z_p$，m 为消息
  2. 计算 $C_1=g^{r}modp$，$C_2=g_1^r\times mmodp$
  3. 密文为：$(C_1,C_2)$
• 解密过程：
  • $D(C_1,C_2)=C_2\times C_1^{-\alpha }=m$
• 签名过程：$S=(g^{r}modp,(m-\alpha S_1)r^{-1}mod(p-1))=(S_1,S_2)$
• 验证签名：$g_1^{S_1}\times S_1^{S_2}\equiv g^{m}modp$

三、RSA加密

• 非对称加密算法
• 计算方法：给定 n, e 的值和用户密文，求明文？
  1. 选择两个大素数 p 和 q，计算 $n=p\times q$ 和 $\varphi (n)=(p-1)\times (q-1)$
  2. 取素数 e，$e\in (1,\varphi (n))$ 并且 $gcd(e,\varphi (n))=1$
  3. 求 d，使得 $e\times d\equiv 1(mod\varphi (n))$ ，最好使用使用扩展欧几里得算法的辗转相除法，或可用公式：$\frac{e\times d-1}{\varphi (n)}=k$ (k 是一个整数)
  4. 生成公钥 (e, n) 和私钥 d，d 叫做 e 的模反元素
  5. 公钥加密：$C=M^{e}modn$
  6. 私钥解密：$M=C^{d}modn$

四、ECC加密

• 参数选择：
  1. 选取一条椭圆曲线，得到$E_p(a,b)$，即：代表椭圆：$y^3=x^3+ax+b(modp)$ 的参数，将明文消息嵌入曲线得到点$M=P_m$ 。
  2. $E_p(a,b)$的生成元是 $G$ ，$E_p(a,b)$ 和 $G$ 是公开参数
• 产生公钥和私钥：用户选取整数 $S_k$ 为私钥，$P_k=S_{k}G$ 为公钥
• 加密：选随机正整数 $k$ ，密文为 $C=(C_1,C_2)$ ，其中，$C_1=kG，C_2=M+k{P}_k$
• 解密：
  • $M=C_2-S_k{C}_1$
    • 具体解释过程：$C_2-S_k{C}_1=M+k{P}_k-S_{k}kG=M$
• 其中，加密和解密过程计算需要对生成元个数取模，即：$C_1=kGmodq$ ，其中 $q$ 代表生成元的个数
• 椭圆曲线上两点相加公式：

五、仿射加密

• 仿射加密是单表加密的一种
• 密钥：$k=(a,b)$，求出：$a^{-1}(mod26)$
• 加密公式：$y=E(x)=(ax+b)mod26$
• 解密公式：$D(y)=a^{-1}(y-b)mod26$
  • 其中， a 与 m 互质，$a^{-1}$ 是 a 在 $Z_m$ 群中的a乘法逆元

例题

• 题干：
• 加密： 字母下标从0开始
• 解密：

贡献者

freeway348

文件历史

最后编辑于 大约 1 小时前查看完整历史

75912-knowReview