SCERush's Blog
0%

几道RSA基础题

发表于 更新于 分类于
本文字数： 5.7k 阅读时长 ≈ 5 分钟

记录几道RSA入门题

RSA

题目：在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17
求解出d作为flga提交

基础题，直接解

1
2
3
4
5
6
import gmpy2
p=473398607161
q=4511491
e=17
d=gmpy2.invert(e,(p-1)*(q-1))
print d

rsarsa

题目给出了RSA的相关参数，直接求解

1
2
3
4
5
6
7
8
9
10
import gmpy2

p = 
q = 
e = 
c = 
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
n = p * q
print pow(c, d, n)

RSA1

  • p，q，dp，dq，c

脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import gmpy2
import libnum
p = 
q = 
dp = 
dq = 
c = 

n = p*q
phi =(p-1)*(q-1)
dd = gmpy2.gcd(p-1,q-1)

d=(dp-dq)//dd * gmpy2.invert((q-1)//dd,(p-1)//dd) * (q-1) + dq

m = pow(c,d,n)
print libnum.n2s(m)

RSA2

  • e，n，c，dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gmpy2
import libnum

e = 
n = 
c = 
dp = 

for x in range(1,e):
	if(e*dp%x==1):
        	p=(e*dp-1)//x+1
        	if(n%p!=0):
        	    continue
        	q=n//p
        	phin=(p-1)*(q-1)
        	d=gmpy2.invert(e, phin)
        	m=gmpy2.powmod(c, d, n)
        	if(len(hex(m)[2:])%2==1):
        	    continue
            print libnum.n2s(m)

RSA3

  • 共模攻击
  • n，e1，e2，c1，c2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2
import libnum

n=
e1=
e2=
c1=
c2=

gcd, s, t = gmpy2.gcdext(e1, e2) #扩展欧几里得算法
if s < 0:
	s = -s
	c1 = gmpy2.invert(c1, n)
if t < 0:
	t = -t
	c2 = gmpy2.invert(c2, n)

m = gmpy2.powmod(c1,s,n) * gmpy2.powmod(c2,t,n) % n
print libnum.n2s(m)

RSA

1
2
3
4
5
# openssl rsa -pubin -text -modulus -in warmup -in pub.key

# pyhton rsatool.py -o private.pem -e '' -p '' -q ''

# openssl rsautl -decrypt -in flag.enc -inkey private.pem

RSAROLL

  • 给出多个密文，逐一解密
    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
    import gmpy2
    n = 920139713
    q = 18443
    p = 49891
    e = 19
    d = int(gmpy2.invert(e , (p-1) * (q-1)))  

    c = '''704796792
    752211152
    274704164
    18414022
    368270835
    483295235
    263072905
    459788476
    483295235
    459788476
    663551792
    475206804
    459788476
    428313374
    475206804
    459788476
    425392137
    704796792
    458265677
    341524652
    483295235
    534149509
    425392137
    428313374
    425392137
    341524652
    458265677
    263072905
    483295235
    828509797
    341524652
    425392137
    475206804
    428313374
    483295235
    475206804
    459788476
    306220148'''
    falg = ''
    for i in c.split('\n'):
    	falg += chr(pow(int(i),d,n))
    print falg

Dangerous RSA

  • 低加密指数攻击（e=3）
1
2
3
4
5
6
7
8
9
import gmpy2
import libnum

c =
n = 
e = 3

m = gmpy2.iroot(c,3)[0]
print libnum.n2s(m)

rsa2

  • 低解密指数攻击（e非常大）
    rsa-wiener-attack
    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
    import gmpy2
    import hashlib
    import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator

    def hack_RSA(e,n):
        
        # Finds d knowing(e,n)
        # applying the Wiener continued fraction attack
        
        frac = ContinuedFractions.rational_to_contfrac(e, n)
        convergents = ContinuedFractions.convergents_from_contfrac(frac)

        for (k,d) in convergents:
            
    	# check if d is actually the key
    	if k!=0 and (e*d-1)%k == 0:
    	    phi = (e*d-1)//k
    	    s = n - phi + 1
    	    # check if the equation x^2 - s*x + n = 0
    	    # has integer
    	    discr = s*s - 4*n
    	    if(discr >= 0):
    		t = Arithmetic.is_perfect_square(discr)
    		if t!=-1 and (s+t)%2==0:
    		    print("Hacked!")
    		    return d
            
    n =
    e = 
    d = hack_RSA(e,n)
    flag = "flag{" + hashlib.md5(hex(d)).hexdigest() + "}"
    print flag

RSA5

题目给出了20对n，c

先将20个n两两取最大公因数，即可得到p（q），然后选取得到这个最大公因数的两个n中的其中一个，即可得到另一个素数

1
2
3
4
5
6
7
8
9
list=[n,n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11,n12,n13,n14,n15,n16,n17,n18,n19]
for i in range(len(list)):
    for j in range(i+1,len(list)):
	print i,j
	try:  
	    print (gmpy2.gcd(list[i],list[j]))
	except:
	    print "error ",i
	continue

我这选的是n4，q=n4/p

1
2
3
4
5
6
7
p=
q=n4/p
e = 65537
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
nn = p * q
print libnum.n2s(pow(c4,d,nn))

SameMod

  • 共模攻击

脚本跟RSA3相同，但解出的m需要用ASCII码解

1
2
3
4
5
6
7
8
9
10
11
12
string = str(m)
flag=''
i=0
j=1
while i < len(string):
    if int(string[i:i+j]) >= 33 and int(string[i:i+j]) <=126:
        flag+=chr(int(string[i:i+j]))
        i=i+j
        j=1
    else:
        j+=1
print(flag)

RSA4

  • 中国剩余定理

使用中国剩余定理求解，但之前需做些转换，题目给出的n和c是5进制的
求出m之后转换出错，估计不是直接模的n，然后猜测e=3，开个根即可

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
import gmpy2
import libnum
n1=  
c1= 

n2=  
c2= 

n3=  
c3= 

ms=[n1,n2,n3]
cs=[c1,c2,c3]
for i in range(len(ms)):
    ms[i]=int(str(ms[i]),5)
    cs[i]=int(str(cs[i]),5)

def CRT(bs,ms):
    m = reduce(lambda x,y: x*y, ms)
    re = 0
    for i in range(len(ms)):
        M = m / ms[i]
        gcd, n1, M1 = gmpy2.gcdext(ms[i], M)# ms[i]*n1 + M*M1 = 1
        re += bs[i] * M * M1
    return re % m

m = CRT(cs,ms)
mm = gmpy2.iroot(m,3)[0]
print libnum.n2s(mm)

RSA&what

  • 共模攻击
  • base64隐写
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
import gmpy2
import libnum

n=
e1=
e2=
cc1=
cc2=

def samemod(c1,c2):
    gcd, s, t = gmpy2.gcdext(e1, e2) 
    if s < 0:
        s = -s
	c1 = gmpy2.invert(c1, n)
    if t < 0:
        t = -t
        c2 = gmpy2.invert(c2, n)

    m = gmpy2.powmod(c1,s,n) * gmpy2.powmod(c2,t,n) % n
    return m


for i in range(len(cc1)):
    print libnum.n2s(samemod(cc1[i],cc2[i]))

在将结果写进txt时，注意将base64合并一下，确保每行结尾为’=’
base64隐写脚本

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
#https://www.jianshu.com/p/48fe4dd3e5ce
def get_base64_diff_value(s1, s2):
    base64chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
    res = 0
    for i in xrange(len(s2)):
        if s1[i] != s2[i]:
            return abs(base64chars.index(s1[i]) - base64chars.index(s2[i]))
    return res


def solve_stego():
    with open('0.txt', 'rb') as f:
        file_lines = f.readlines()
        bin_str = ''
        for line in file_lines:
            steg_line = line.replace('\n', '')
            norm_line = line.replace('\n', '').decode('base64').encode('base64').replace('\n', '')
            diff = get_base64_diff_value(steg_line, norm_line)
            print diff
            pads_num = steg_line.count('=')
            if diff:
                bin_str += bin(diff)[2:].zfill(pads_num * 2)
            else:
                bin_str += '0' * pads_num * 2
            print goflag(bin_str)


def goflag(bin_str):
    res_str = ''
    for i in xrange(0, len(bin_str), 8):
        res_str += chr(int(bin_str[i:i + 8], 2))
    return res_str


if __name__ == '__main__':
    solve_stego()

坏蛋是雷宾

  • Rabin算法

原理详见：https://wiki.x10sec.org/crypto/asymmetric/rsa/rsa_e_attack/

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
from gmpy2 import *
import hashlib

n=523798549
p=10663
q=49123
e=2
c=162853095
inv_p = invert(p, q)
inv_q = invert(q, p)

mp = pow(c, (p + 1) / 4, p)
mq = pow(c, (q + 1) / 4, q)

a = (inv_p * p * mq + inv_q * q * mp) % n
b = n - int(a)
c = (inv_p * p * mq - inv_q * q * mp) % n
d = n - int(c)

for i in (a, b, c, d):
    print(bin(i)[2:])

#10010011100100100101010110001  
m='10010011100100100101010'
mc=str(int(m,2))
md=hashlib.md5()
md.update(mc.encode("utf8"))
flag = md.hexdigest()
print("flag{"+str(flag)+'}')