huangx607087学习RSA的笔记1
I-What is RSA
体制:
1.选择两个大质数$p$,$q$,计算$n=p×q$
2.计算$\phi=(p-1)(q-1)$,也就是$n$的欧拉函数(也就是小于$n$的正整数中与$n$互质数量的个数)
3.取一个数字$e$,使$e,\phi$互质
4.计算$d$,使$ed\equiv 1 \mod \phi$
5.加密函数:$c=E(m)=m^e \mod n $
6.解密函数:$m=D(c)=c^d \mod n $
II-11种RSA题型的总结
0x01 直接给出$p,q,c,e$或者$n=p^k$的题目
直接根据加密体制计算即可,有crypto这个python库的可以直接用inverse(e, (p-1)*(q-1))
求出$d$
$n=p^k$时,$\phi=p^k-p^{k-1}$
0x02 只给出了$n,c,e$
这种情况一般$n$是可以暴力分解的,上yafu即可
0x03 只给出了$n,c,e$并且$e=3$的情况
根据$c=E(m)=m^3 \mod n $,也就是$m^3=c+kn,k∈${$0,1,2,3,…$},这个时候可以枚举$k$的值,通过二分$m$确定$m$的值,一般$k$不会太大的
0x04 只给出了$n,c,e$并且$\ln e≈\ln n$(也就是$e$非常大的时候)
使用winnerattack算法,具体代码见下(别看,这个代码不是本fw打的)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
| from __future__ import print_function import libnum def continued_fractions_expansion(numerator,denominator): result=[] divident = numerator % denominator quotient = numerator // denominator result.append(quotient) while divident != 0: numerator = numerator - quotient * denominator tmp = denominator denominator = numerator numerator = tmp divident = numerator % denominator quotient = numerator // denominator result.append(quotient) return result def convergents(expansion): convergents=[(expansion[0], 1)] for i in range(1, len(expansion)): numerator = 1 denominator = expansion[i] for j in range(i - 1, -1, -1): numerator += expansion[j] * denominator if j==0: break tmp = denominator denominator = numerator numerator = tmp convergents.append((numerator, denominator)) return convergents def newtonSqrt(n): approx = n // 2 better = (approx + n // approx) // 2 while better != approx: approx = better better = (approx + n // approx) // 2 return approx def wiener_attack(cons, e, N): for cs in cons: k,d = cs if k == 0: continue phi_N = (e * d - 1) // k a = 1 b = -((N - phi_N) + 1) c = N delta = b * b - 4 * a * c if delta <= 0: continue x1 = (newtonSqrt(delta) - b)//(2 * a) x2 = -(newtonSqrt(delta) + b)//(2 * a) if x1 * x2 == N: return [x1, x2, k, d] if __name__ == "__main__": n = e = c = expansion = continued_fractions_expansion(e, n) cons = convergents(expansion) p, q, k, d = wiener_attack(cons, e, n) m = pow(c, d, n) print(libnum.n2s(m))
|
0x05 给出了$n,c,e$并且给出$f(d,\phi)$的一个一次式
直接求出$ef(d,\phi)$的值,然后确定模数
0x06 已知$n,c,e$,$e=3$,并且得知$m-(m \mod 2^k)$的值
这种情况下根本不可能用0x03的方法,因为$k$值也很大
在Sagemath中的Notebook上打开网页,创建一个Sagemath网页文件,把以下代码补完整后运行
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| n = e = 3 m = randrange(n) c = pow(m, e, n) beta = 1 epsilon = beta^2/7 nbits = n.nbits() kbits= print(nbits,kbits) mbar = c = print ("upper %d bits (of %d bits) is given" % (nbits-kbits, nbits)) PR.<x> = PolynomialRing(Zmod(n)) f = (mbar + x)^e - c print (m) x0 = f.small_roots(X=2^kbits, beta=1)[0] print( mbar + x0)
|
0x07 Parity Oracle
直接看0xGame Div 2的相关内容
0x08已知$n,c,e$,$e=3$和$p-(p \mod 2^k)$的值
在Sagemath中的Notebook上打开网页,创建一个Sagemath网页文件,把以下代码补完整后运行
1 2 3 4 5 6 7 8 9 10 11
| n = p_fake = pbits = p_fake.nbits() kbits = pbar = p_fake & (2^pbits-2^kbits) print "upper %d bits (of %d bits) is given" % (pbits-kbits, pbits) PR.<x> = PolynomialRing(Zmod(n)) f = x + pbar x0 = f.small_roots(X=2^kbits, beta=0.4)[0] p= x0 + pbar print p
|
有$p$就可以得到$q$,进而就很简单了
0x09 已知$n,c,e$,$e=3$和$d \mod 2^k$值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| def partial_p(p0, kbits, n): PR.<x> = PolynomialRing(Zmod(n)) nbits = n.nbits() f = 2^kbits*x + p0 f = f.monic() roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3) if roots: x0 = roots[0] p = gcd(2^kbits*x0 + p0, n) return ZZ(p) def find_p(d0, kbits, e, n): X = var('X') for k in xrange(1, e+1): results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits) for x in results: p0 = ZZ(x[0]) p = partial_p(p0, kbits, n) if p: return p if __name__ == '__main__': n = e = 3 d = beta = 0.5 epsilon = beta^2/7 nbits = n.nbits() print "nbits:%d:"%(nbits) kbits = nbits - d.nbits()-1 print "kbits:%d"%(kbits) d0 = d & (2^kbits-1) print "lower %d bits (of %d bits) is given" % (kbits, nbits) p = find_p(d0, kbits, e, n) print "found p: %d" % p q = n//p print d print inverse_mod(e, (p-1)*(q-1))
|
0x0A 两个模数$n_1,n_2$不互素(模不互素)
这种题目一般给出$2$组$n,e,c$的值,我们可以求一下$\gcd (n_1,n_2)$ 如果不等于$1$的话,我们就得到了$n$的一个因数$p$,一除就得到了$q_1,q_2$,分别求解即可得到明文。
0x0B 模数$n$相同,指数$e$不同(共模攻击)
这种题目一般也是给出$2$组$n,e,c$的值。也就是$5$个数字:$n,e_1,e_2,c_1,c_2$。此时可以不求$d_1,d_2$也可以直接获得明文。
步骤:
显然,多数情况下$\gcd(e_1,e_2)=1$,所以有$e_1s_1+e_2s_2=1$,一般$s_1,s_2$为一正一负的两个整数,用EXGCD可以求得该式子的一组解
我们可以得到算式 :$(c1^{s1}c2^{s2})\mod n = ((m^{e1}\mod n)^{s1}(m^{e2}\mod n)^{s2})\mod n$ .(1)
化简,有:$(c1^{s1}c2^{s2})\mod n = (m^{(e1^{s1}+e2^{s2})})\mod n$ .(2)
又$e_1s_1+e_2s_2=1$ . (3)
所以由**(2)(3)**可知:$c1^{s1}*c2^{s2} \equiv m \mod n $
所以我们可以写出以下的脚本:别膜,这很显然不是我这个fw能够写出来的!,我有过这样的码风?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| from libnum import n2s,s2n from gmpy2 import invert def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) def main(): n = c1 = c2 = e1 = e2 = s = egcd(e1, e2) s1 = s[1] s2 = s[2] if s1<0: s1 = - s1 c1 = invert(c1, n) elif s2<0: s2 = - s2 c2 = invert(c2, n) m = pow(c1,s1,n)*pow(c2,s2,n) % n print n2s(m)
if __name__ == '__main__': main()
|
0x0C 给出pem和bin文件的RSA题目
在脚本前加上这些内容。然后pub1和pub2都有两个值(n和e,没有c)
这个脚本的后半部分也可以作为一个更加简洁的共模攻击觉得脚本。我就是个只会利用别人脚本的fw55555555555
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| from Crypto.PublicKey import RSA from Crypto.Util.number import * import gmpy2 import libnum c1=libnum.s2n(open('cipher1.txt','rb').read()) c2=libnum.s2n(open('cipher2.txt','rb').read()) pub1=RSA.importKey(open('publickey1.pem').read()) pub2=RSA.importKey(open('publickey2.pem').read())
n=pub1.n e1,e2=pub1.e,pub2.e s = gmpy2.gcdext(pub1.e,pub2.e) s1,s2=s[1],s[2] if s1<0: s1 = -s1 c1 = gmpy2.invert(c1, n) elif s2<0: s2 = -s2 c2 = gmpy2.invert(c2, n) m=pow(c1,s1,n)*pow(c2,s2,n)%n print(long_to_bytes(m))
|