如果这篇博客帮助到你,可以请我喝一杯奶茶~
CC BY-NC 4.0 (除特别声明或转载文章外)
RSA——第一次不自闭
理论
基础知识
互质
互质就是两个数的最大公约数是1,gcd(a,b)=1
任意两个质数都互质
同余
给定一个正整数m,如果两个整数a和b满足a-b能够被m整除,那么就称整数a与b对模m同余,记作$a≡b(mod\ m)$ 其实可以这么理解:a对m取余后得到b:$a\ mod\ m=b$
欧拉函数
对正整数n,欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的数目
欧拉函数是积性函数,若m,n互质,则 $φ(mn)=φ(m)φ(n)$ 若n为质数,则 $φ(n)=n-1$
模反元素
如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。这时,b就叫做a对模数n的“模反元素” 。
即 $ab≡1 (mod\ n)$ 也可以这么理解:ab对n取余之后得到1,b就是a的模反元素$ab\ mod\ n = 1$
各种定理和算法
欧拉定理
若n,a为正整数,且n,a互质,则 $a^{φ(n)}=1\ (mod\ n)$
欧几里得算法
是求最大公约数的一种方法。
用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数。
代码实现:
def gcd(a,b): if b==0: return a else: return gcd(b,a%b)
extend_gcd
如果a、b是整数,那么一定存在整数x、y使得:$ax+by=gcd(a,b)$ 这是一个很简单的问题,但是解决它就⑧一定简单了
这时候就要用到extend_gcd算法だよ。
- 显然当 b=0,gcd(a,b)=a。此时 x=1,y=0;
- ab!=0 时, $ax~1~+by~1~=gcd(a,b);$ $bx~2~+(a mod b)y~2~=gcd(b,a mod b);$
- 根据朴素的欧几里德原理有$ gcd(a,b)=gcd(b,a mod b)$;则:$ax~1~+by~1~=bx~2~+(a mod b)y~2~$;
- 即:$ax~1~+by~1~=bx~2~+(a-(a/b)b)y~2~=ay~2~+bx~2~-(a/b)by~2~$;
- 根据恒等定理得:$x~1~=y~2~; y~1~=x~2~-(a/b)*y~2~; $
上面的思想是以递归定义的,因为 gcd 不断的递归求解一定会有个时候 b=0,所以递归可以结束。
所以代码实现:
def egcd(a,b): if b == 0: return 1,0,a else: x,y,q = egcd(b,a % b) return y,x-a/b*y,q
孙子定理(中国剩余定理)
学习的事以后再说——老总
实践
加密过程
随机选两个不相等的质数p和q。
例如:p=14214677
q=15733001
两数相乘得到n
$n=p*q=22363952745677$
将两数分别减一再相乘得到phin
$phin=(p-1)(q-1)=223639497508000$
随机选择一个整数 e ( 1 < e < phin 且 e 与 phin 互质) e=65537
计算e对于phin的模反元素。
$ed≡1\ (\ mod\ φ(n))$ 得到d=156179448585473
n和e组成公钥,n和d组成私钥。 公钥(22363952745677,65537) 私钥(22363952745677,156179448585473)
公钥加密
加密flag
m=int('flag'.encode('hex'),16)
$m^e≡c\ (mod\ n)$
python中可操作:pow(m,e,n)
得到c=32176455243891
私钥解密
$c^d≡m\ (mod\ n)$
题目分析
RSA_small_plain
小公钥指数攻击,e=7还⑧算大
因为 $c≡m^e(mod n)$ 然后可以设 $m\^e=c+kn,m=(c+kn)\^{1/e}$ 然后扯淡的是,直接给c开7次方,是个整数……
直接decode:
RSA_common_modulus
有n,和e1,e2,c1,c2
应该是共模攻击s1e1+s2e2=1
扩展欧几里得算法求一波s1和s2
然后发现s2是个负的,就求c2r取-s2次方
最后解码