密码学 - 练习题
说明AES和DES设计的不同之处。
AES和DES设计的不同之处
密钥长度：
- AES：支持128位、192位和256位的密钥长度。
- DES：固定56位的密钥长度（尽管通常表示为64位，但其中8位用于奇偶校验）。
分组长度：
- AES：固定128位的分组长度。
- DES：固定64位的分组长度。
算法结构：
- AES：基于替代-置换网络（Substitution-Permutation Network, SPN）。使用S盒和P盒来实现复杂的替代和置换操作。
- DES：基于费斯妥尔网络（Feistel Network）。每一轮将数据分成两半，交替进行加密和交换。
轮数：
- AES：轮数取决于密钥长度：128位密钥为10轮，192位密钥为12轮，256位密钥为14轮。
- DES：固定为16轮。
安全性：
- AES：设计更为现代，考虑了更多的密码分析攻击，现阶段没有已知的有效攻击方式。
- DES：由于密钥长度较短，容易受到暴力破解攻击，已经被认为是不安全的。
硬件和软件实现：
- AES：设计时考虑了高效的硬件和软件实现，特别是对现代处理器进行了优化。
- DES：设计较早，硬件实现相对简单，但在现代处理器上的效率较低。
总结
AES设计更加现代化，具有更高的安全性和灵活性，已经取代DES成为主流的对称加密标准。
LFSR的初始值被称为伪随机序列的种子，影响下一个状态的比特位叫做抽头。LFSR的触发器编号一般从1开始，抽头取值范围是1到2n-1。抽头序列可以用来描述该LFSR的反馈多项式。由n个触发器构成的LFSR电路可以产生一个周期为2n-1的序列。理论表明，要使LFSR得到最长的周期，这个抽头序列构成的多项式加1就是其反馈多项式，必须是一个本原多项式，也就是说这个多项式不可约，比方下图的抽头序列为$(4,1)$，其对应的反馈多项式为$f\left( x \right)=x{}^\text{4}+x+1$，其对应的线性反馈移位寄存器电路如下所示。
假设$a_3$,$a_2$,$a_1$,$a_0$的初始值各自是1 0 0 0，反馈函数选取$f\left( x \right)=x{}^\text{4}+x+1$，那么得到例如以下序列
能够看出周期为15。在这一个周期里面涵盖了开区间$(0,2^4)$内的全部整数，而且都是没有固定顺序出现的，有非常好的随机性。
4级$LFSR$的特征多项式为 $f\left( x \right)=x+x{}^\text{2}+1$初始态为$(0,0,1,1)$。求输出序列及其周期。
为了求解4级LFSR的输出序列及其周期，我们需要了解$LFSR$的工作机制。特征多项式为$f(x) = x + x^2 + 1$，这意味着$LFSR$的反馈函数是基于特定位置的位进行异或操作。
初始态 $(0, 0, 1, 1)$
我们从这个初始态开始，依次计算$LFSR$的输出序列。
计算过程
- 当前状态： (0, 0, 1, 1)
- 新的比特：$1 \oplus 1 = 0$
- 更新状态：$(0, 0, 0, 1)$
- 输出比特：$1$
- 当前状态： (0, 0, 0, 1)
- 新的比特：$0 \oplus 1 = 1$
- 更新状态：$(1, 0, 0, 0)$
- 输出比特：$1$
- 当前状态： (1, 0, 0, 0)
- 新的比特：$0 \oplus 0 = 0$
- 更新状态：$(0, 1, 0, 0)$
- 输出比特：$0$
- 当前状态： (0, 1, 0, 0)
- 新的比特：$0 \oplus 0 = 0$
- 更新状态：$(0, 0, 1, 0)$
- 输出比特：$0$
- 当前状态： (0, 0, 1, 0)
- 新的比特：$1 \oplus 0 = 1$
- 更新状态：$(1, 0, 0, 1)$
- 输出比特：$0$
- 当前状态： (1, 0, 0, 1)
- 新的比特：$0 \oplus 1 = 1$
- 更新状态：$(1, 1, 0, 0)$
- 输出比特：$1$
- 当前状态： (1, 1, 0, 0)
- 新的比特：$0 \oplus 0 = 0$
- 更新状态：$(0, 1, 1, 0)$
- 输出比特：$0$
- 当前状态： (0, 1, 1, 0)
- 新的比特：$1 \oplus 0 = 1$
- 更新状态：$(1 ,0, 1, 1)$
- 输出比特：$0$
- 当前状态： (1, 0, 1, 1)
- 新的比特：$1 \oplus 1 = 0$
- 更新状态：$(0 ,1, 0, 1)$
- 输出比特：$1$
- 当前状态： (0, 1, 0, 1)
- 新的比特：$0 \oplus 1 = 1$
- 更新状态：$(1 ,0, 1, 0)$
- 输出比特：$1$
- 当前状态： (1, 0, 1, 0)
- 新的比特：$0 \oplus 1 = 1$
- 更新状态：$(1 ,1, 0, 1)$
- 输出比特：$0$
- 当前状态： (1, 1, 0, 1)
- 新的比特：$0 \oplus 1 = 1$
- 更新状态：$(1 ,1, 1, 0)$
- 输出比特：$1$
- 当前状态： (1, 1, 1, 0)
- 新的比特：$0 \oplus 1 = 1$
- 更新状态：$(1 ,1, 1, 1)$
- 输出比特：$0$
- 当前状态： (1, 1, 1, 1)
- 新的比特：$1 \oplus 1 = 0$
- 更新状态：$(0 ,1, 1, 1)$
- 输出比特：$1$
- 当前状态： (0, 1, 1, 1)
- 新的比特：$1 \oplus 1 = 0$
- 更新状态：$(0 ,0, 1, 1)$
- 输出比特：$1$
- 当前状态： (0, 0, 1, 1)
- 新的比特：$1 \oplus 1 = 0$
- 更新状态：$(0 ,0, 0, 1)$
- 输出比特：$1$
输出序列及周期
- 输出序列： 11000 10011 01011 1…
- 周期： 15（此处说明：在计算过程中发现某些状态（如$(1, 0, 0, 1)$）会重复，而生成的比特序列也重复）
总结
通过以上计算，我们得到了4级LFSR的输出序列和其周期。根据给定的特征多项式$f(x) = x + x^2 + 1$，初始态(0, 0, 1, 1)产生了周期为15的输出序列11000 10011 01011。
公钥密码算法一般是建立在对一个特定的数学难题求解上，该难题无法求解则密码算法安全，$RSA$算法基于大整数的素因子分解难题，如果该难题可以求解，简述一下，你是如何利用发送者的公钥和截取的密文破译求解出明文的。
RSA算法简介
RSA（Rivest-Shamir-Adleman）是一种基于大整数分解难题的公钥密码算法。RSA算法的核心在于两个大素数的乘积，以及在大素数分解上计算的困难性。其主要包括三个步骤：密钥生成、加密和解密。
密钥生成：
- 选择两个大素数 $p $ 和 $q $。
- 计算 $n = pq $，这是模数。
- 计算 $\phi(n) = (p-1)(q-1) $，这是欧拉函数。
- 选择一个整数 $e $，满足 $1 < e < \phi(n) $ 且 $e $ 与 $\phi(n) $ 互质。
- 计算 $d $，满足 $ed \equiv 1 \ (\text{mod} \ \phi(n)) $。
公钥为 $(e, n) $，私钥为 $(d, n) $。
加密：
使用公钥 $(e, n) $，将明文 $M $ 转换为密文 $C $：
$ C = M^e \ (\text{mod} \ n) $
解密：
使用私钥 $(d, n) $，将密文 $C $ 还原为明文 $M $：
$ M = C^d \ (\text{mod} \ n) $
破译RSA的过程
假设敌手（攻击者）可以解决大整数的素因子分解问题，他们可以破译RSA的过程如下：
截取密文：
攻击者截取发送者发送的密文 $C $。已知公钥：
攻击者已知发送者的公钥 $(e, n) $。分解模数 $n $：
攻击者利用素因子分解技术将 $n $ 分解为两个大素数 $p $ 和 $q $。计算欧拉函数：
攻击者计算欧拉函数 $\phi(n) $：
$ \phi(n) = (p-1)(q-1) $求解私钥 $d $：
攻击者利用已知的 $e $ 和 $\phi(n) $ 计算私钥 $d $：
$ d \equiv e^{-1} \ (\text{mod} \ \phi(n)) $
即找到一个 $d $ 使得 $ed \equiv 1 \ (\text{mod} \ \phi(n)) $。解密密文：
使用计算得到的私钥 $d $，攻击者将密文 $C $ 解密为明文 $M $：
$ M = C^d \ (\text{mod} \ n) $
示例解密过程
假设截取的密文为 $C $ ，公钥为 $(e, n) $，且攻击者能够分解 $n $ 。
已知公钥 $(e, n) $：
$ e = 7, \ n = 33 $分解模数 $n $：
$ n = 33 = 3 \times 11 $
这样 $p = 3 $ 和 $q = 11 $。计算欧拉函数 $\phi(n) $：
$ \phi(n) = (3-1)(11-1) = 2 \times 10 = 20 $求解私钥 $d $：
$ d \equiv 7^{-1} \ (\text{mod} \ 20) $
求解得到 $d = 3 $，因为 $7 \times 3 = 21 \equiv 1 \ (\text{mod} \ 20) $。解密密文 $C $：
假设截获的密文 $C = 10 $，使用私钥 $d = 3 $ 进行解密：
$ M = 10^3 \ (\text{mod} \ 33) = 1000 \ (\text{mod} \ 33) = 10 $所以解密得到的明文 $M = 10 $。
通过上述过程，攻击者能够成功解密密文，破译出原文。这也说明了RSA算法的安全性依赖于大整数分解问题的计算复杂度。如果这个问题可以被有效解决，RSA算法就会被攻破。
在RSA加密算法中, 设 $p=3,q=7,e=5,$计算d并求出明文 $m=2$所对应的密文c。
在RSA加密算法中，给定素数 $ p = 3 $ 和 $ q = 7 $，以及公钥指数 $ e = 5 $，我们需要计算私钥 $ d $ 并求出明文 $ m = 2 $ 所对应的密文 $ c $。
计算步骤
- 计算模数 $ n $
$ n = p \times q = 3 \times 7 = 21 $
- 计算欧拉函数 $ \phi(n) $
$ \phi(n) = (p - 1)(q - 1) = (3 - 1)(7 - 1) = 2 \times 6 = 12 $
- 计算私钥 $ d $
私钥 $ d $ 满足下列同余式：
$ d \equiv e^{-1} \pmod{\phi(n)} $
我们需要找到一个 $ d $ 使得：
$ 5d \equiv 1 \pmod{12} $
使用扩展欧几里得算法或者通过试验可以找到 $ d $：
$ 5d \equiv 1 \pmod{12} $
逐次尝试 $ d $ 的值：
- 当 $ d = 1 $ 时，$ 5 \times 1 = 5 \not\equiv 1 \pmod{12} $
- 当 $ d = 2 $ 时，$ 5 \times 2 = 10 \not\equiv 1 \pmod{12} $
- 当 $ d = 3 $ 时，$ 5 \times 3 = 15 \not\equiv 1 \pmod{12} $
- 当 $ d = 4 $ 时，$ 5 \times 4 = 20 \not\equiv 1 \pmod{12} $
- 当 $ d = 5 $ 时，$ 5 \times 5 = 25 \equiv 1 \pmod{12} $
所以 $ d = 5 $。
- 加密明文 $ m = 2 $
加密公式为：
$ c = m^e \pmod{n} $
将值代入公式：
$c = 2^5 \pmod{21}$
$c = 32 \pmod{21} = 11$
结果
- 私钥 $ d = 5 $
- 明文 $ m = 2 $ 所对应的密文 $ c = 11 $
因此，使用给定的参数 $ p = 3 $、$ q = 7 $、$ e = 5 $，计算得出私钥 $ d = 5 $ 和密文 $ c = 11 $。
在$ElGamal$公钥密码体制中, $Bob$选取$p=17$,生成元$g=3$,私钥$x=6$,Alice选取$Bob$的公钥对消息明文$m=5$进行加密，随机数为$3$。求$m$的密文。
在$ElGamal$公钥密码体制中，我们有以下参数：
- $ p = 17 $
- 生成元 $ g = 3 $
- Bob 的私钥 $ x = 6 $
- Alice 选择的随机数 $ k = 3 $
- 明文 $ m = 5 $
我们需要计算消息 $ m $ 的密文。
计算步骤
计算$ Bob$ 的公钥 $ y $
$ y = g^x \mod p $
$ y = 3^6 \mod 17 $
$ y = 729 \mod 17 $
$ y = 15 $
计算密文的两个部分 $ C_1 $ 和 $ C_2 $
计算 $ C_1 $
$ C_1 = g^k \mod p $
$ C_1 = 3^3 \mod 17 $
$ C_1 = 27 \mod 17 $
$ C_1 = 10 $
计算 $ C_2 $
$ C_2 = m \times y^k \mod p $
$ C_2 = 5 \times 15^3 \mod 17 $
计算 $ 15^3 \mod 17 $:
$ 15^3 = 3375 $
$ 3375 \mod 17 = 3375 - 17 \times 198 = 3375 - 3366 = 9 $
计算 $ 5 \times 9 \mod 17 $:
$ C_2 = 5 \times 9 \mod 17 = 11 $
因此，明文 $ m = 5 $ 所对应的密文为 $ (C_1, C_2) = (10, 11) $
所以，加密后的密文是：
$ (C_1, C_2) = (10, 11) $
若某LFSR的级数为 $n=3$，已知$2n$长密文段 $c=\left( 011001 \right),$对应明文段 $m=\left( 101101 \right),$请给出其反馈函数表达式。
为了找到这个$LFSR$的反馈函数，我们需要用给出的明文段和密文段推导出反馈多项式。
给定：
$ n = 3 $
$ c = (011001) $
$ m = (101101) $
我们知道密文 $ c $ 和明文 $ m $ 的关系是通过$LFSR$生成序列 $ k $ 进行异或得到的，即：
$ c_i = m_i \oplus k_i $
通过这个关系我们可以求出$LFSR$生成序列 $ k $：
- $ c_1 = m_1 \oplus k_1 \rightarrow 0 = 1 \oplus k_1 \rightarrow k_1 = 1 $
- $ c_2 = m_2 \oplus k_2 \rightarrow 1 = 0 \oplus k_2 \rightarrow k_2 = 1 $
- $ c_3 = m_3 \oplus k_3 \rightarrow 1 = 1 \oplus k_3 \rightarrow k_3 = 0 $
- $ c_4 = m_4 \oplus k_4 \rightarrow 0 = 1 \oplus k_4 \rightarrow k_4 = 1 $
- $ c_5 = m_5 \oplus k_5 \rightarrow 0 = 0 \oplus k_5 \rightarrow k_5 = 0 $
- $ c_6 = m_6 \oplus k_6 \rightarrow 1 = 1 \oplus k_6 \rightarrow k_6 = 0 $
所以$LFSR$生成序列 $ k $ 为 $ (110100) $。
假设反馈多项式为 $ f(x) = 1 + c_1 x + c_2 x^2 + c_3 x^3 $，我们需要找到 $ c_1 $, $ c_2 $, 和 $ c_3 $。
观察$LFSR$生成序列 $ k = (110100) $：
- $ k_4 = c_1 k_3 \oplus c_2 k_2 \oplus c_3 k_1 \rightarrow 1 = c_1 \cdot 0 \oplus c_2 \cdot 1 \oplus c_3 \cdot 1 \rightarrow 1 = c_2 \oplus c_3 $
- $ k_5 = c_1 k_4 \oplus c_2 k_3 \oplus c_3 k_2 \rightarrow 0 = c_1 \cdot 1 \oplus c_2 \cdot 0 \oplus c_3 \cdot 1 \rightarrow 0 = c_1 \oplus c_3 $
- $ k_6 = c_1 k_5 \oplus c_2 k_4 \oplus c_3 k_3 \rightarrow 0 = c_1 \cdot 0 \oplus c_2 \cdot 1 \oplus c_3 \cdot 0 \rightarrow 0 = c_2 $
从方程3可以得到 $ c_2 = 0 $。
代入方程1，得到 $ 1 = 0 \oplus c_3 \rightarrow c_3 = 1 $。
代入方程2，得到 $ 0 = c_1 \oplus 1 \rightarrow c_1 = 1 $。
所以反馈函数的表达式为：
$ f(x) = 1 + x + x^3 $
总结
$S {n+3} = S {n+2} \oplus S_n$
反馈函数为$f(a_1,a_2,a_3) \equiv (a_1+a_3) \mod{2}$
在 $GF_{23}$ 上的一条椭圆曲线 $y{}^\text{2}=x{}^\text{3}+x+1$ , 设 $g=\left( 6\text{,}4 \right)$ , 取私钥 $a=3$ 。公钥为 $b=a \cdot g=3\left( 6\text{,}4 \right)=\left( 7\text{,}12 \right)$ 。若想加密明文 $m=\left( 5\text{,}4 \right)$, 随机选取 $k=2$，则密文 $c$ 是什么？请给出加解密过程。
要加密明文 $ m = (5, 4) $ ，需要用到椭圆曲线上的点运算和公钥。已知椭圆曲线为 $ y^2 = x^3 + x + 1 $ ，基点 $ g = (6, 4) $ ，私钥 $ a = 3 $ ，公钥 $ b = a \cdot g = 3 \cdot (6, 4) = (7, 12) $ ，随机选取的 $ k = 2 $ 。下面是加密和解密的详细过程：
加密过程
计算 $ k \cdot g $ ：
$ k \cdot g = 2 \cdot (6, 4) $计算点倍乘 $ 2 \cdot (6, 4) $：
使用椭圆曲线上的点倍乘公式计算：
先计算 $ 2 \cdot (6, 4) $：
设 $ P = (6, 4) $，首先计算斜率 $ \lambda $：
$ \lambda = \frac{3x_1^2 + a}{2y_1} \mod 23 $
其中 $ a = 1 $， $ P = (x_1, y_1) = (6, 4) $，
$ \lambda = \frac{3(6)^2 + 1}{2(4)} \mod 23 = \frac{3 \cdot 36 + 1}{8} \mod 23 = \frac{109}{8} \mod 23 $
首先计算 $ 109 \mod 23 $：
$ 109 \mod 23 = 17 $
接下来计算 $ \frac{17}{8} \mod 23 $ ，可以通过计算 $ 8 $ 在模 $ 23 $ 下的逆元：
$ 8^{-1} \mod 23 = 3 $
因为 $ 8 \cdot 3 = 24 \equiv 1 \mod 23 $，所以 $ 8^{-1} = 3 $。
$ \frac{17}{8} \equiv 17 \cdot 8^{-1} \mod 23 = 17 \cdot 3 \mod 23 = 51 \mod 23 = 5 $
所以 $ \lambda = 5 $。计算 $ (2x_1, 2y_1) $：
$ x_2 = \lambda^2 - 2x_1 \mod 23 = 5^2 - 2 \cdot 6 \mod 23 = 25 - 12 \mod 23 = 13 $
$ y_2 = \lambda (x_1 - x_2) - y_1 \mod 23 = 5(6 - 13) - 4 \mod 23 = 5(-7) - 4 \mod 23 = -35 - 4 \mod 23 = -39 \mod 23 = 7 $
所以 $ 2 \cdot (6, 4) = (13, 7) $。
因此 $ k \cdot g = 2 \cdot (6, 4) = (13, 7) $。
计算 $ k \cdot b $ ：
$ k \cdot b = 2 \cdot (7, 12) $计算 $ 2 \cdot (7, 12) $ ，类似上面的计算：
先计算 $ 2 \cdot (7, 12) $：
设 $ Q = (7, 12) $，首先计算斜率 $ \lambda $：
$ \lambda = \frac{3x_1^2 + a}{2y_1} \mod 23 $
其中 $ a = 1 $， $ Q = (x_1, y_1) = (7, 12) $，
$ \lambda = \frac{3(7)^2 + 1}{2(12)} \mod 23 = \frac{3 \cdot 49 + 1}{24} \mod 23 = \frac{148}{24} \mod 23 $
首先计算 $ 148 \mod 23 $：
$ 148 \mod 23 = 10 $
接下来计算 $ \frac{10}{24} \mod 23 $ ，可以通过计算 $ 24 $ 在模 $ 23 $ 下的逆元：
$ 24^{-1} \mod 23 = 1 $
因为 $ 24 \cdot 1 = 24 \equiv 1 \mod 23 $，所以 $ 24^{-1} = 1 $。
$ \frac{10}{24} \equiv 10 \cdot 24^{-1} \mod 23 = 10 \cdot 1 \mod 23 = 10 \mod 23 = 10 $
所以 $ \lambda = 10 $。计算 $ (2x_1, 2y_1) $：
$ x_2 = \lambda^2 - 2x_1 \mod 23 = 10^2 - 2 \cdot 7 \mod 23 = 100 - 14 \mod 23 = 86 \mod 23 = 17 $
$ y_2 = \lambda (x_1 - x_2) - y_1 \mod 23 = 10(7 - 17) - 12 \mod 23 = 10(-10) - 12 \mod 23 = -100 - 12 \mod 23 = -112 \mod 23 = 3 $
所以 $ 2 \cdot (7, 12) = (17, 3) $。
因此 $ k \cdot b = 2 \cdot (7, 12) = (17, 3) $。
计算密文 $ c = (k \cdot g, m + k \cdot b) $ ：
$ c_1 = k \cdot g = (13, 7) $
$ c_2 = m + k \cdot b = (5, 4) + (17, 3) $点加法公式：
设 $ P = (x_1, y_1) $ 和 $ Q = (x_2, y_2) $，
斜率 $ \lambda = \frac{y_2 - y_1}{x_2 - x_1} \mod 23 $
$ x_3 = \lambda^2 - x_1 - x_2 \mod 23 $
$ y_3 = \lambda (x_1 - x_3) - y_1 \mod 23 $计算：
$ \lambda = \frac{3 - 4}{17 - 5} \mod 23 = \frac{-1}{12} \mod 23 = 22 \cdot 2 \mod 23 =21$
所以 $ \lambda = 21 $。$ x_3 = 21^2 - 5 - 17 \mod 23 = 441 - 22 \mod 23 = 419 \mod 23 = 5 $
$ y_3 = 21(5 - 5) - 4 \mod 23 = 0 - 4 \mod 23 = -4 \mod 23 = 19 $所以 $ m + k \cdot b = (5, 19) $。
因此，密文 $ c = (k \cdot g, m + k \cdot b) = ((13, 7), (5, 19)) $。
解密过程
接收者使用私钥 $ a = 3 $ 解密密文 $ c = ((13, 7), (5, 19)) $。
计算 $ a \cdot c_1 $：
$ a \cdot c_1 = 3 \cdot (13, 7) $计算点倍乘 $ 3 \cdot (13, 7) $：
使用椭圆曲线上的点倍乘公式：
先计算 $ 2 \cdot (13, 7) $：
$ \lambda = \frac{3(13)^2 + 1}{2(7)} \mod 23 = \frac{3 \cdot 169 + 1}{14} \mod 23 = \frac{508}{14} \mod 23 $
首先计算 $ 508 \mod 23 $：
$ 508 \mod 23 = 2 $
接下来计算 $ \frac{2}{14} \mod 23 $ ，可以通过计算 $ 14 $ 在模 $ 23 $ 下的逆元：
$ 14^{-1} \mod 23 = 5 $
因为 $ 14 \cdot 5 = 70 \equiv 1 \mod 23 $，所以 $ 14^{-1} = 5 $。
$ \frac{2}{14} \equiv 2 \cdot 14^{-1} \mod 23 = 2 \cdot 5 \mod 23 = 10 $
所以 $ \lambda = 10 $。计算 $ (2x_1, 2y_1) $：
$ x_2 = \lambda^2 - 2x_1 \mod 23 = 10^2 - 2 \cdot 13 \mod 23 = 100 - 26 \mod 23 = 74 \mod 23 = 5 $
$ y_2 = \lambda (x_1 - x_2) - y_1 \mod 23 = 10(13 - 5) - 7 \mod 23 = 10 \cdot 8 - 7 \mod 23 = 80 - 7 \mod 23 = 73 \mod 23 = 4 $
所以 $ 2 \cdot (13, 7) = (5, 4) $。计算 $ 3 \cdot (13, 7) $:
使用上一步计算得到的 $ 2 \cdot (13, 7) = (5, 4) $，再计算 $ (5, 4) + (13, 7) $：
$ \lambda = \frac{7 - 4}{13 - 5} \mod 23 = \frac{3}{8} \mod 23 = 3 \cdot 8^{-1} \mod 23 $
计算 $ 8^{-1} \mod 23 $:
使用扩展欧几里得算法，得到 $ 8^{-1} \mod 23 = 3 $。
因为 $ 8 \cdot 3 = 24 \equiv 1 \mod 23 $，所以 $ 8^{-1} = 3 $。
$ \lambda = 3 \cdot 3 \mod 23 = 9 \mod 23 = 9 $
所以 $ \lambda = 9 $。计算 $ (x_3, y_3) $：
$ x_3 = 9^2 - 5 - 13 \mod 23 = 81 - 18 \mod 23 = 17 $
$ y_3 = 9(5 - 17) - 4 \mod 23 = 9\cdot(-12) - 4 \mod 23 = 3 $所以 $ 3 \cdot (13, 7) = (17, 3) $。
计算 $ m = c_2 - a \cdot c_1 $ ：
$ m = (5, 19) - (17, 3) $使用点减法公式：
- 点减法可以表示为点加法 $ (5, 19) + (17, -3)=(5, 19) + (17, 20) $。
计算斜率 $ \lambda $：
$ \lambda = \frac{20 - 19}{17 - 5} \mod 23 = \frac{1}{12} \mod 23 = \frac{1}{12} \mod 23 $计算 $ 12^{-1} \mod 23 $:
使用扩展欧几里得算法，得到 $ 12^{-1} \mod 23 = 2 $。
因为 $ 12 \cdot 2 = 24 \equiv 1 \mod 23 $，所以 $ 12^{-1} = 2 $。
$ \lambda = 1 \cdot 2 \mod 23 = 2 \mod 23 = 2 $计算 $ x_3 $ 和 $ y_3 $：
$ x_3 = 2^2 - 5 - 17 \mod 23 = 4 - 22 \mod 23 = -18 \mod 23 = 5 $
$ y_3 = 2(5 - 19) - 22 \mod 23 = 2 \cdot (-14) - 22 \mod 23 = -50 \mod 23 = 4 $所以 $ (5, 19) - (17, 3) = (5, 4) $。
解密得到的明文 $ m = (5, 4) $。
考虑有限域 $F_{23}$上的椭圆曲线E： $y{}^\text{2}=x{}^\text{3}-4x+1,$令$P=\left( 4\text{,}7 \right),Q=\left( 10\text{,}31 \right)$ 求: (1) P+Q; (2) 2P。
我们需要在给定的椭圆曲线上进行点的加法和倍乘运算。椭圆曲线为 $ E: y^2 = x^3 - 4x + 1 $ ，有限域 $ F $ 上的点 $ P = (4, 7) $ 和 $ Q = (10, 31) $。
(1) 计算 $ P + Q $
首先，计算 $ \lambda $ ，即过 $ P $ 和 $ Q $ 的直线的斜率：
$ \lambda = \frac{y_2 - y_1}{x_2 - x_1} = \frac{31 - 7}{10 - 4} \mod 23= \frac{24}{6} \mod 23= 1\cdot 4 \mod23 =4$
计算 $ x_3 $ 和 $ y_3 $：
$ x_3 = \lambda^2 - x_1 - x_2 = 4^2 - 4 - 10 \mod23 = 16 - 4 - 10 \mod23 = 2 \mod23$
$ y_3 = \lambda(x_1 - x_3) - y_1 = 4(4 - 2) - 7 \mod23= 4 \cdot 2 - 7 \mod23= 8 - 7 \mod23= 1 \mod23$
因此，$ P + Q = (2, 1) $。
(2) 计算 $ 2P $
首先，计算 $ \lambda $ ，即过 $ P $ 点的切线的斜率：
$ \lambda = \frac{3x_1^2 + a}{2y_1} $
其中 $ a = -4 $， $ P = (4, 7) $，
$ \lambda = \frac{3 \cdot 4^2 - 4}{2 \cdot 7} \mod23= \frac{3 \cdot 16 - 4}{14} \mod23= \frac{48 - 4}{14} \mod23= \frac{44}{14}\mod23 =21 \cdot 5 \mod23 = 13$
因此：
$ \lambda = 13 $
计算 $ x_3 $ 和 $ y_3 $：
$ x_3 = \lambda^2 - 2x_1 = 13^2 - 2 \cdot 4 \mod23= 169 - 8 \mod23= 0 $
$ y_3 = \lambda(x_1 - x_3) - y_1 = 13(4 + 0) - 7 \mod23= 52 - 7 \mod23= 45 \mod23= 22 $
因此，$ 2P = (0, 22) $。
所以：
- $ P + Q = (2, 1) $
- $ 2P = (0, 22) $
背景知识
椭圆曲线密码学（ECC）是一种基于椭圆曲线数学结构的公钥密码系统。以下是椭圆曲线加密和解密的公式和步骤：
基本概念和符号
- 椭圆曲线方程：常见形式为 $ E: y^2 = x^3 + ax + b $。
- 有限域 $ F_p $：在有限域上的椭圆曲线，所有的计算都在模 $ p $ 的情况下进行。
- 基点 $ G $：一个预先选定的曲线上非零点。
- 私钥 $ d $：一个随机选定的整数，范围是 $ [1, n-1] $，其中 $ n $ 是 $ G $ 的阶。
- 公钥 $ Q $：通过 $ Q = dG $ 计算得到。
椭圆曲线加密
加密过程涉及到明文点 $ M $，需要将其映射到椭圆曲线上，并使用接收者的公钥进行加密。加密的步骤如下：
- 随机选择一个整数 $ k $，范围是 $ [1, n-1] $。
- 计算点 $ C_1 = kG $。
- 计算点 $ C_2 = M + kQ $，其中 $ Q $ 是接收者的公钥。
- 密文为 $ (C_1, C_2) $。
具体公式为：
$ C_1 = kG $
$ C_2 = M + kQ $
椭圆曲线解密
解密过程使用接收者的私钥 $ d $ 来恢复明文点 $ M $。解密的步骤如下：
- 接收密文 $ (C_1, C_2) $。
- 计算点 $ dC_1 $，其中 $ d $ 是接收者的私钥。
- 计算点 $ M = C_2 - dC_1 $。
具体公式为：
$ dC_1 = d(kG) = k(dG) = kQ $
$ M = C_2 - kQ $
详细的计算示例
假设有一个椭圆曲线 $ E: y^2 = x^3 + ax + b $ ，有限域 $ F_p $ 上的基点 $ G $，私钥 $ d $ 和公钥 $ Q = dG $，以及明文点 $ M $。
加密过程
选择随机数 $ k $：
$ k = 2 $计算 $ C_1 $：
$ C_1 = kG = 2G $计算 $ C_2 $：
$ C_2 = M + kQ $
其中 $ Q = dG $，假设 $ d = 3 $，那么 $ Q = 3G $，则 $ kQ = 2 \cdot 3G = 6G $。密文为 $ (C_1, C_2) $：
$ (C_1, C_2) = (2G, M + 6G) $
解密过程
接收密文 $ (C_1, C_2) $：
$ (C_1, C_2) = (2G, M + 6G) $计算 $ dC_1 $：
$ dC_1 = 3 \cdot 2G = 6G $恢复明文 $ M $：
$ M = C_2 - dC_1 = (M + 6G) - 6G = M $
具体公式说明
点加法：
若 $ P = (x_1, y_1) $ 和 $ Q = (x_2, y_2) $ 是椭圆曲线上的两个点，且 $ P \neq Q $，则 $ P + Q = (x_3, y_3) $ 的计算公式为：
$\lambda = \frac{y_2 - y_1}{x_2 - x_1} \mod p$
$x_3 = \lambda^2 - x_1 - x_2 \mod p$
$y_3 = \lambda(x_1 - x_3) - y_1 \mod p$点倍乘：
若 $ P = (x_1, y_1) $ 是椭圆曲线上的一个点，则 $ 2P = (x_3, y_3) $ 的计算公式为：
$ \lambda = \frac{3x_1^2 + a}{2y_1} \mod p $
$ x_3 = \lambda^2 - 2x_1 \mod p $
$ y_3 = \lambda(x_1 - x_3) - y_1 \mod p $
这些公式和步骤适用于任何给定的椭圆曲线和有限域，并通过实际计算实现加密和解密过程。