ComSec作业三：RSA

ComSec作业三：RSA

为什么RSA加解密互逆

$已知p,q均为质数\\$
$\begin{aligned} n & = p q \\ e d & \equiv 1 (\mod λ (n)) \\ λ (n) & = l c m (p - 1, q - 1) \\ e 与 λ (n) 互素 \end{aligned}$ $已知 p, q 均为质数 n e d λ (n) = pq \equiv 1 (mod λ (n)) = l c m (p - 1, q - 1) e 与 λ (n) 互素$

证明加解密互逆
$c\equiv m^e \pmod{n}\\ m\equiv c^d \pmod{n}\\ c^d\equiv (m^e)^d \equiv m^{ed} \equiv m^{1+k\lambda(n)} \equiv m \cdot m^{\lambda(n)} \equiv m \cdot 1 \equiv m \pmod{n}\\ 接下来就是证明m^{\lambda(n)}\equiv 1 \pmod{n}\\ 由于\lambda(n)=lcm(p-1,q-1)\\ 则有\left \{$
$\begin{aligned} m^{λ (n)} \equiv 1 (\mod p) \\ m^{λ (n)} \equiv 1 (\mod q) \end{aligned}$ \right. \\ 变换之后 \left \{ $\begin{matrix} m^{λ (n)} = 1 + k_{1} p \\ m^{λ (n)} = 1 + k_{2} q \end{matrix}$ \right. \\ 再次变换\left \{ $\begin{matrix} 2 m^{λ (n)} - 2 = k_{1} p + k_{2} q \\ m^{2 λ (n)} = (1 + k_{1} p) (1 + k_{2} q) = 1 + k_{1} p + k_{2} q + k_{1} k_{2} p q \end{matrix}$ \right.\\ $c \equiv m^{e} (mod n) m \equiv c^{d} (mod n) c^{d} \equiv (m^{e})^{d} \equiv m^{e d} \equiv m^{1 + kλ (n)} \equiv m \cdot m^{λ (n)} \equiv m \cdot 1 \equiv m (mod n) 接下来就是证明 m^{λ (n)} \equiv 1 (mod n) 由于 λ (n) = l c m (p - 1, q - 1) 则有 {m^{λ (n)} \equiv 1 (mod p) m^{λ (n)} \equiv 1 (mod q) 变换之后 {m^{λ (n)} = 1 + k_{1} p m^{λ (n)} = 1 + k_{2} q 再次变换 {2 m^{λ (n)} - 2 = k_{1} p + k_{2} q m^{2 λ (n)} = (1 + k_{1} p) (1 + k_{2} q) = 1 + k_{1} p + k_{2} q + k_{1} k_{2} pq$
带入后得到
$\begin{aligned} m^{2 λ (n)} & = 1 + (2 m^{λ (n)} - 2) + k_{1} k_{2} p q \\ = 2 m^{λ (n)} - 1 + k_{1} k_{2} p q \\ m^{2 λ (n)} - 2 m^{λ (n)} + 1 & = k_{1} k_{2} p q \\ (m^{λ (n)} - 1)^{2} & = k_{1} k_{2} p q \end{aligned}$
则有
$(m^{\lambda(n)}-1)^2 \equiv 0 \pmod{pq}\\ m^{\lambda(n)}-1 \equiv 0 \pmod{pq}\\ m^{\lambda(n)} \equiv 1 \pmod{pq}$
即证

后来才发现，过程搞复杂了其实只要在这一步，移动一下就好
$\left \{$
$\begin{matrix} m^{λ (n)} - 1 = k_{1} p \\ m^{λ (n)} - 1 = k_{2} q \end{matrix}$ \right.\\ ${m^{λ (n)} - 1 = k_{1} p m^{λ (n)} - 1 = k_{2} q$

9.2 Perform encryption and decryption using the RSA algorithm, as in Figure 9.5, for the following:

a. $p = 3; q = 7, e = 5; M = 10$

$\begin{array}{l} n = p q = 21 \\ ϕ (n) = (p - 1) (q - 1) = 2 \times 6 = 12 \\ e x g c d : {\begin{aligned} ((1)) & x & = ϕ (n) = 12 \\ ((2)) & y & = e = 5 \\ ((3)=(1)-2(2)) & x - 2 y & = 2 \\ ((4)=(2)-2(3)) & - 2 x + 5 y & = 1 \end{aligned} \\ d = 5 \\ e n c r y p t : C \equiv M^{e} (\mod n) \\ 10^{5} \equiv 16^{2} \times 10 \equiv (- 5)^{2} \times 10 \equiv 25 \times 10 \equiv 40 \equiv 19 (\mod 21) \\ d e c r y p t : M \equiv C^{d} (\mod n) \\ 19^{5} \equiv (- 2)^{5} \equiv - 32 \equiv - 11 \equiv 10 (\mod 21) \end{array}$ $n = pq = 21 ϕ (n) = (p - 1) (q - 1) = 2 \times 6 = 12 e xg c d : ⎩ ⎨ ⎧ x y x - 2 y - 2 x + 5 y = ϕ (n) = 12 = e = 5 = 2 = 1 ((1)) ((2)) ((3)=(1)-2(2)) ((4)=(2)-2(3)) d = 5 e n cry pt : C \equiv M^{e} (mod n) 1 0^{5} \equiv 1 6^{2} \times 10 \equiv (- 5)^{2} \times 10 \equiv 25 \times 10 \equiv 40 \equiv 19 (mod 21) d ecry pt : M \equiv C^{d} (mod n) 1 9^{5} \equiv (- 2)^{5} \equiv - 32 \equiv - 11 \equiv 10 (mod 21)$

b. $p = 5; q = 13, e = 5; M = 8$

$\begin{array}{l} n = p q = 65 \\ ϕ (n) = (p - 1) (q - 1) = 4 \times 12 = 48 \\ e x g c d : {\begin{aligned} x & = ϕ (n) = 48 \\ y & = e = 5 \\ x - 9 y & = 3 \\ - x + 10 y & = 2 \\ 2 x - 19 y & = 1 \end{aligned} \\ d = 48 - 19 = 29 \\ e n c r y p t : C \equiv M^{e} (\mod n) \\ 8^{5} \equiv 64^{2} \times 8 \equiv (- 1)^{2} \times 8 (\mod 65) \\ d e c r y p t : M \equiv C^{d} (\mod n) \\ 8^{29} \equiv 64^{14} \times 8 \equiv (- 1)^{14} \times 8 \equiv 8 (\mod 65) \end{array}$ $n = pq = 65 ϕ (n) = (p - 1) (q - 1) = 4 \times 12 = 48 e xg c d : ⎩ ⎨ ⎧ x y x - 9 y - x + 10 y 2 x - 19 y = ϕ (n) = 48 = e = 5 = 3 = 2 = 1 d = 48 - 19 = 29 e n cry pt : C \equiv M^{e} (mod n) 8^{5} \equiv 6 4^{2} \times 8 \equiv (- 1)^{2} \times 8 (mod 65) d ecry pt : M \equiv C^{d} (mod n) 8^{29} \equiv 6 4^{14} \times 8 \equiv (- 1)^{14} \times 8 \equiv 8 (mod 65)$

c. $p = 7; q = 17, e = 11; M = 11$

$\begin{array}{l} n=pq=119\\ \phi(n)=(p-1)(q-1)=6\times16=96\\ exgcd:\left\{ \begin{align} x&=\phi(n)=96\\ y&=e=11\\ x-8y&=8\\ -x+9y&=3\\ 3x-26y&=2\\ -4x+35y&=1\\ \end{align}\right.\\ d=35\\ encrypt: C \equiv M^e \pmod{n} \\ 11^11\equiv 121^{5} \times 11 \equiv 2^5 \times 11 \equiv 114\pmod{119} \\ decrypt: M \equiv C^d \pmod{n} \\ 114^{35}\pmod{119} \\ \begin{array}{l} crt:\left\{ \begin{array}{l} 114^{35} &\equiv 4 \mod 7 \\ 114^{35} &\equiv 11 \mod 17 \end{array}$ \right. \\ exgcd:\left\{ $\begin{array}{cl} x & = 17 \\ y & = 7 \\ x - 2 y & = 3 \\ - 2 x + 5 y & = 1 \end{array}$ \right. \\ \end{array} \\ 114^{35} \equiv 5\times4\times17+5\times11\times7\equiv 11\pmod{119} \\ \end{array} $n = pq = 119 ϕ (n) = (p - 1) (q - 1) = 6 \times 16 = 96 e xg c d : ⎩ ⎨ ⎧ x y x - 8 y - x + 9 y 3 x - 26 y - 4 x + 35 y = ϕ (n) = 96 = e = 11 = 8 = 3 = 2 = 1 d = 35 e n cry pt : C \equiv M^{e} (mod n) 1 1^{1} 1 \equiv 12 1^{5} \times 11 \equiv 2^{5} \times 11 \equiv 114 (mod 119) d ecry pt : M \equiv C^{d} (mod n) 11 4^{35} (mod 119) cr t : {11 4^{35} 11 4^{35} \equiv 4 mod 7 \equiv 11 mod 17 e xg c d : ⎩ ⎨ ⎧ x y x - 2 y - 2 x + 5 y = 17 = 7 = 3 = 1 11 4^{35} \equiv 5 \times 4 \times 17 + 5 \times 11 \times 7 \equiv 11 (mod 119)$

d. $p = 7; q = 13, e = 11; M = 2$

$\begin{array}{l} n=pq=91\\ \phi(n)=(p-1)(q-1)=6\times12=72\\ exgcd:\left\{ \begin{align} x&=\phi(n)=72\\ y&=e=11\\ x-6y&=6\\ -x+7y&=5\\ 2x-13y&=1\\ \end{align}\right.\\ d=72-13=59\\ encrypt: C \equiv M^e \pmod{n} \\ 2^11\equiv 37 \times 16 \equiv 57 \times 4 \equiv 46 \pmod{91} \\ decrypt: M \equiv C^d \pmod{n} \\ 46^{59}\pmod{91} \\ crt:\left\{ \begin{array}{l} 46^{59} &\equiv 2 \mod 7 \\ 46^{59} &\equiv 2 \mod 13 \end{array}$ \right. \\ 斌头剩余定理:46^{59} \equiv 2 \mod 91 \end{array} $n = pq = 91 ϕ (n) = (p - 1) (q - 1) = 6 \times 12 = 72 e xg c d : ⎩ ⎨ ⎧ x y x - 6 y - x + 7 y 2 x - 13 y = ϕ (n) = 72 = e = 11 = 6 = 5 = 1 d = 72 - 13 = 59 e n cry pt : C \equiv M^{e} (mod n) 2^{1} 1 \equiv 37 \times 16 \equiv 57 \times 4 \equiv 46 (mod 91) d ecry pt : M \equiv C^{d} (mod n) 4 6^{59} (mod 91) cr t : {4 6^{59} 4 6^{59} \equiv 2 mod 7 \equiv 2 mod 13 斌头剩余定理 : 4 6^{59} \equiv 2 mod 91$

e. $p = 17; q = 23, e = 9; M = 7$

$\begin{array}{l} n = p q = 391 \\ ϕ (n) = (p - 1) (q - 1) = 16 \times 22 = 352 \\ e x g c d : {\begin{aligned} x & = ϕ (n) = 352 \\ y & = e = 9 \\ x - 39 y & = 1 \end{aligned} \\ d = 352 - 39 = 313 \\ e n c r y p t : C \equiv M^{e} (\mod n) \\ 7^{9} \equiv 61 (\mod 391) \\ d e c r y p t : M \equiv C^{d} (\mod n) \\ 61^{313} \equiv 7 (\mod 119) \end{array}$ $n = pq = 391 ϕ (n) = (p - 1) (q - 1) = 16 \times 22 = 352 e xg c d : ⎩ ⎨ ⎧ x y x - 39 y = ϕ (n) = 352 = e = 9 = 1 d = 352 - 39 = 313 e n cry pt : C \equiv M^{e} (mod n) 7^{9} \equiv 61 (mod 391) d ecry pt : M \equiv C^{d} (mod n) 6 1^{313} \equiv 7 (mod 119)$

9.3 In a public-key system using RSA, you intercept the ciphertext C = 20 sent to user whose public key is e=13, n=77. What is the plaintext M?

$\begin{array}{l} n=77=7\times11\\ p=7,q=11\\ \phi(n)=6\times10=60\\ e=13\\ exgcd:\left\{ \begin{array}{l} x&=60\\ y&=13\\ x-4y&=8\\ -x+5y&=5\\ 2x-9y&=3\\ -3x+14y&=2\\ 5x-23y&=1 \end{array}$ \right.\\ d=60-23=37\\ m=c^{d}\mod n\\ m=20^{37}\equiv 48 \pmod{77} \end{array} $n = 77 = 7 \times 11 p = 7, q = 11 ϕ (n) = 6 \times 10 = 60 e = 13 e xg c d : ⎩ ⎨ ⎧ x y x - 4 y - x + 5 y 2 x - 9 y - 3 x + 14 y 5 x - 23 y = 60 = 13 = 8 = 5 = 3 = 2 = 1 d = 60 - 23 = 37 m = c^{d} mod n m = 2 0^{37} \equiv 48 (mod 77)$

9.4 In an RSA system, the public key of a given user is e=65, n=2881.What is the private key of this user? Hint: First use trial-and-error to determine p and q; then use the extended Euclidean algorithm to find the multiplicative inverse of 31 modulo $\phi(n)$ .

$\begin{array}{l} n=43\times67=2881 \\ p=43, q=67 \\ \phi(n)=42\times66=2772\\ exgcd: \left\{ \begin{array}{cl} x&=2772\\ y&=65\\ x-42y&=42\\ -x+43y&=23\\ 2x-85y&=19\\ -3x+128y&=4\\ 14x-597y&=3\\ -17x+725y&=1 \end{array}$ \right.\\ 私钥d=725\\ exgcd: \left\{ $\begin{array}{cl} x & = 2772 \\ y & = 31 \\ x - 89 y & = 13 \\ - 2 x + 179 y & = 5 \\ 5 x - 447 y & = 3 \\ - 7 x + 626 y & = 2 \\ 12 x - 1073 y & = 1 \end{array}$ \right.\\ (31)^{-1}\equiv 1699 \mod 2772 \end{array} $n = 43 \times 67 = 2881 p = 43, q = 67 ϕ (n) = 42 \times 66 = 2772 e xg c d : ⎩ ⎨ ⎧ x y x - 42 y - x + 43 y 2 x - 85 y - 3 x + 128 y 14 x - 597 y - 17 x + 725 y = 2772 = 65 = 42 = 23 = 19 = 4 = 3 = 1 私钥 d = 725 e xg c d : ⎩ ⎨ ⎧ x y x - 89 y - 2 x + 179 y 5 x - 447 y - 7 x + 626 y 12 x - 1073 y = 2772 = 31 = 13 = 5 = 3 = 2 = 1 (31)^{- 1} \equiv 1699 mod 2772$
相关阅读:
WebSocket和Html通讯
 MySQL中的SHOW FULL PROCESSLIST命令
 黑马瑞吉外卖之菜品的启售停售
 eclipse项目导入教程
 什么是Bean的循环依赖?解决方案是什么？
TCP三次握手四次挥手
 算法2：链表的逆转
 常见大厂面试题（SQL）02
让实时操作系统助力电力电子系统设计
 python读取.txt文件中某些关键字后面的内容并根据该数据画图
原文地址：https://blog.csdn.net/weixin_45004513/article/details/127452641

为什么RSA加解密互逆

9.2 Perform encryption and decryption using the RSA algorithm, as in Figure 9.5, for the following:

9.3 In a public-key system using RSA, you intercept the ciphertext C = 20 sent to user whose public key is e=13, n=77. What is the plaintext M?

9.4 In an RSA system, the public key of a given user is e=65, n=2881.What is the private key of this user? Hint: First use trial-and-error to determine p and q; then use the extended Euclidean algorithm to find the multiplicative inverse of 31 modulo ϕ ( n ) \phi(n) ϕ(n).

9.4 In an RSA system, the public key of a given user is e=65, n=2881.What is the private key of this user? Hint: First use trial-and-error to determine p and q; then use the extended Euclidean algorithm to find the multiplicative inverse of 31 modulo $\phi(n)$ .