[SWPUCTF 2021 新生赛]crypto2

共模攻击

顺便巩固下rsa

符号 c:密文 m:明文 (d,n):私钥 (e,n):公钥

p q 为生成n的两个大质数

有$n=pq$ 由欧拉函数的定义得$\varphi (n)=\varphi (p)\varphi (q)=(p-1)(q-1)$

任意选一正整数e 使得$gcd(e,\varphi (n))=1$

$d$ 满足 $(de)\space mod \space \varphi (n)=1$ 即 $(de) = k\varphi (n)+1,k \ge 1$

将$m$加密为$c$ $c=m^e\space mod \space n$

将$c$解密为$m$

$m=c^d\space mod \space n$

证明 $$ \because c=m^e\space mod \space n\ \therefore c \equiv m^e\space mod \space n\ \therefore c^d \equiv m^{ed}\space mod \space n\ \therefore c^d \equiv m^{k\varphi (n)+1}\space mod \space n\ \space\ 当gcd(m,n)=1时有:\ c^d \equiv (m^{\varphi (n)})^{k}\times m\space mod \space n\ c^d \equiv 1^k\times m\space mod \space n\ c^d \equiv m\space mod \space n\ \space\ 当gcd(m,n)\ne1时有:\ 此时必定有gcd(q,m)=1或gcd(p,m)=1\ 设m=m^{'}p \space 此时 gcd(q,m)=1\ c^d \equiv m^{k\varphi (p)\varphi (q)}\times m\space mod\space n\ c^d \equiv (m^{\varphi(q)\varphi(p)})^{k}\times m\space mod \space n\ 又\because m^{\varphi(q)}\equiv 1 \space mod \space q\ \therefore m^{k\varphi(q)\varphi(p)}\equiv 1^{k\varphi(p)} \space mod \space q\ \therefore m^{k\varphi(q)\varphi(p)}=(k_2q+1) 代入得\ c^d \equiv (k_2q+1)\times m\space mod \space n\ c^d \equiv (k_2m^{'}pq+m)\times m\space mod \space n\ c^d \equiv m\space mod \space n\ 证毕. $$

附: 1. 欧拉定理 $$ a^{\varphi(n)}\equiv 1\space mod\space n,当gcd(n,a)=1且n,a\ge0 $$ 且当n为质数时为费马小定理 $$ a^{n-1}\equiv 1(mod\space n) $$

共模攻击原理

$e_1,e_2,n,c_1,c_2$ 已知 且 $c_1=m^{e_1}\space mod \space n$ $c_2=m^{e_2}\space mod \space n$ 当$gcd(e_1,e_2)=1$

有$m=(c_1^{s_1}\times c_2^{s_2})\space mod \space n$ 其中$e_1s_1+e_2s_2=1$ 证明 $$ m\ =m^1\ =m^{e_1s_1+e_2s_2}\ =(m^{e_1})^{s_1}(m^{e_2})^{s_2}\ \equiv c_1^{s_1}c_2^{s_2}\space mod\space n\ 证毕. $$

所以解共模题时只要用exgcd求出 $s_1,s_2$

附: 1. 贝祖定理 $$ ax+by=gcd(a,b) $$

评论