21Feb2

ExpLog
CTFSeason2
发布日期:   2021-02-16

huangx607087开学前的切题2

0.简介

一个密码学fw的切题笔记，很菜，别看

之前BUUCTF上到了3000分，进入了Crypto的深水区，题目难度都是很大的，看来我是不是只能看着wp搞懂题目后再做题了，wtcl。

由于题目太难（实际上是自己太菜），这篇文章原计划是12日至13日发布的，最后直到16日才开始写，然后火速发布（并没有）。

1.[BSidesSF2020]decrypto-1

通过观察下面的代码，可以发现，这个实际上是对一个文件进行了加密操作。

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
import sys
import json
import hashlib
class Crypto:
    def __init__(self, key):
        if not isinstance(key, bytes):
            raise TypeError('key must be of type bytes!')
        self.key = key
        self._buf = bytes()
        self._out = open("/dev/stdout", "wb")
    def _extend_buf(self):
        self._buf += self.key
    def get_bytes(self, nbytes):
        while len(self._buf) < nbytes:
            self._extend_buf()
        ret, self._buf = self._buf[:nbytes], self._buf[nbytes:]
        return ret
    def encrypt(self, buf):
        if not isinstance(buf, bytes):
            raise TypeError('buf must be of type bytes!')
        stream = self.get_bytes(len(buf))
        return bytes(a ^ b for a, b in zip(buf, stream))
    def set_outfile(self, fname):
        self._out = open(fname, "wb")
    def encrypt_file(self, fname):
        buf = open(fname, "rb").read()
        self._out.write(self.encrypt(buf))
class JSONCrypto(Crypto):
    def encrypt_file(self, fname):
        buf = open(fname, "r").read().strip()
        h = hashlib.sha256(buf.encode('utf-8')).hexdigest()
        data = {
                "filename": fname,
                "hash": h,
                "plaintext": buf,
        }
        outbuf = json.dumps(data, sort_keys=True, indent=4)
        self._out.write(self.encrypt(outbuf.encode("utf-8")))
def main(argv):
    if len(argv) not in (3, 4):
        print("%s <key> <infile> [outfile]" % sys.argv[0])
        return
    argv.pop(0)
    key = argv.pop(0)
    inf = argv.pop(0)
    crypter = JSONCrypto(key.encode("utf-8"))
    if sys.argv:
        crypter.set_outfile(argv.pop(0))
    crypter.encrypt_file(inf)
if __name__ == '__main__':
    main(sys.argv)

而整个加密过程，实际上就是data和key之间异或的操作。根据平常的经验，key的长度应该不会很长。而密文的加密文档叫flag.txt.enc。因此盲猜filename那一栏的值是flag.txt。这样子的话，data的长度已经超过了15。

然后我们就可以构造一个data，模仿他的构造字符串的过程对data异或密文，可以看出最前面实际上出现了循环结构，说明这就是我们需要的key。n0t4=l4g

最后我们将key和data进行异或，就可以得到明文内容了。

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
from Crypto.Util.number import *
import sys
import hashlib
import json
fp=open("flag.txt.enc","rb")
b=fp.read()
fp.close()
data = {
            "filename": 'flag.txt',
            "hash": '000000000000000000000000000000000000000',
            "plaintext":'000000000000000000000000000000000000'
        }
outbuf = json.dumps(data, sort_keys=True, indent=4)
s=""
for i in range(min(len(outbuf),len(b))):
    s+=chr(b[i]^ord(outbuf[i]))
print(s)
#n0t4=l4gn0t4=l4gn0t4=l4gn0t4=l4gn0t4=l4gn0t6ke<5fa"e=m0589q18o76mes6n9agj1s0<......
key=b'n0t4=l4g'
ans=''
for i in range(len(b)):
    ans+=chr(b[i]^key[i%len(key)])
print(ans)
'''
{
    "filename": "flag.txt",
    "hash": "2f98b8afa014bf955533a3e72cee0417413ff744e25f2b5b5838f5741cd69547",
    "plaintext": "CTF{plz_dont_r0ll_ur_own_crypto}"
}
'''

2.[羊城杯 2020]GMC

拿到题目，很显然啊，看到了有随机数的平方，容易想到使用之前提到过的二次剩余的相关知识来解决。

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
from Crypto.Util.number import getPrime,bytes_to_long,getRandomNBitInteger
from secret import flag
from gmpy2 import gcd
def gmc(a, p):
    if pow(a, (p-1)//2, p) == 1:
        return 1
    else:
        return -1
def gen_key():
    [gp,gq] = [getPrime(512) for i in range(2)]
    gN = gp * gq
    return gN, gq, gp
def gen_x(gq,gp):
    while True:
        x = getRandomNBitInteger(512)
        if gmc(x,gp) ^ gmc(x,gq) == -2:
            return x 
def gen_y(gN):
    gy_list = []
    while len(gy_list) != F_LEN:
        ty = getRandomNBitInteger(768)
        if gcd(ty,gN) == 1:
            gy_list.append(ty)
    return gy_list
if __name__ == '__main__':
    flag = bin(bytes_to_long(flag))[2:]
    F_LEN = len(flag)
    N, q, p = gen_key()
    x = gen_x(q, p)
    y_list = gen_y(N)
    ciphertext = []
    for i in range(F_LEN):
        tc = pow(y_list[i],2) * pow(x,int(flag[i])) % N
        ciphertext.append(tc)
    with open('./output.txt','w') as f:
        f.write(str(N) + '\n')
        for i in range(F_LEN):
            f.write(str(ciphertext[i]) + '\n')

很显然，gmc函数就是判断一个数是不是二次剩余的函数，因为在有限域里，二次剩余的ord值一定是$\dfrac{p-1}2$的因数。因此如果$a$是有限域中的二次剩余，那么$a^{\frac{p-1}2} \equiv 1 \pmod p$。

不过这里判断的是$n=pq$的二次剩余情况。根据阅读代码，两个异或值等于$-2$的话，只有可能是一个$1$一个$-1$。而二次剩余的符号是可以相乘的。因此我们可以知道，生成的数字肯定不是二次剩余。

根据最后给出的数字：$y_i^2x^{f_i}$，其中$f_i$的取值为$0,1$。因此如果最后给出数字是二次剩余，那么对应的flag位是$0$，如果给出的数字是二次非剩余，那么对应的flag位是$1$。

这道题还算是比较简单的，直接上脚本，具体讲解可以回顾**0xGame Div 4[2020.10.29]**。

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
from Crypto.Util.number import *
def isqr(x,p):
    if p==1 or x==1:
        return 1
    sgn=1
    while x%2==0:
        x=x//2
        if p%8==3 or p%8==5:
            sgn=-sgn
    if x<p:
        _tmp=p
        p=x
        x=_tmp
        if x%4==3 and p%4==3 :
            sgn=-sgn
    return sgn*isqr(x%p,p)
n,s=0,[]
fp=open("output.txt","r")
n=int(fp.readline())
while True:
    try:
        a=int(fp.readline())
        s.append(a)
    except:
        break
assert len(s)+1==304
ans=""
for i in s:
    if(isqr(i,n)==1):
        ans+='0'
    else:
        ans+='1'
print(long_to_bytes(int(ans,2)))

3.[b01lers2020]Des-MMXX

首先看一下题目的加密代码

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
import sys
from hashlib import sha256
from Crypto.Cipher import DES
SECRET = 0xa########e          # remember to erase this later..
seed = b'secret_sauce_#9'   
def keygen(s):
   keys = []
   for i in range(2020):
      s = sha256(s).digest()
      keys.append(s)
   return keys
def scramble(s):
   ret = "".join( [format(s & 0xfffff, '020b')]*101 )
   ret += "".join( [format(s >> 20, '020b')]*101 )
   return int(ret, 2)
def encrypt(keys, msg):
   dk = scramble(SECRET)
   for v in keys:
      idx = dk & 3
      dk >>= 2
      k = v[idx*8:(idx+1)*8]
      cp = DES.new(k, DES.MODE_CBC, bytes(8))  
      msg = cp.encrypt(msg)
   return msg
keys = keygen(seed)
with open("flag.txt", "rb") as f:
   msg = f.read()
ctxt = encrypt(keys, msg)
print(ctxt)
#Plaintext: b'Attack at DAWN!!'
#Ciphertext: b'\x15\x08T\xff<\xf4\xc4\xc0\xd2;\xd6\x8a\x824\x83\xbe'

通过题目给出的加密代码中，我们发现了最后还给出了一组附加的明文和密文，看来是有一定用处的。而SECRET虽然中间八位十六进制数被擦去，但给出了最高位的$\text{AH}$和最低位的$\text{EH}$（$\text H$后缀表示十六进制）。

观察一下scramble函数，与secret密切相关，因此我构造了一个十位的十六进制数$\text{123456789AH}$放进去，得出来的结果是$\text{6789A6789A6789A……123451234512345H}$。而加密的时候，取这个数字作为dk，然后dk每次除以$4$并获取余数。余数作为对应keys密钥中的密钥段。

注意到加密的前半段和后半段基本无关，而题目又给出了一个附加明文和附加密文。很显然，可以使用中间碰撞法进行攻击，通过分别枚举两端SECRET的值，然后比对输出结果，在两组每组$60000$多个输出中寻找到相同的输出。

构造密钥直接模仿其构造密钥的过程即可。而最需要主义的就是对key进行下标关系的计算，以及对生成的半密钥除以多少（也就是需要右移多少位）的问题，反正都是线性函数，举两个例子就可以判断了。

枚举前半段加密密钥脚本（对附加明文加密到一半的操作）

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
#10.py
from Crypto.Util.number import *
from Crypto.Cipher import DES
from hashlib import sha256
m=b"Attack at DAWN!!"
def keygen(s):
   keys = []
   for i in range(2020):
      s = sha256(s).digest()
      keys.append(s)
   return keys
def K(x):
   ret = "".join( [format(x & 0xfffff, '020b')]*101 )
   return int(ret,2)
def incrypt(kinum,cip,keys):
   for i in range(1010):
      idx=(kinum>>(2*i))&3
      k=keys[i][idx*8:idx*8+8]
      cp = DES.new(k, DES.MODE_CBC, bytes(8))
      cip=cp.encrypt(cip)
   return cip
keys = keygen(b'secret_sauce_#9')
fp=open("ENCMID.txt","w")
for i in range(0,65536):
    if(i%150==0):
        print(i)
    keynum=K(0xa0000+i)
    fp.write(hex(bytes_to_long(incrypt(keynum,m,keys)))[2:]+'\n')

枚举后半段加密密钥（对附加密文进行解密到一半的操作）

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
#11.py
from Crypto.Util.number import *
from Crypto.Cipher import DES
from hashlib import sha256
c=b"\x15\x08\x54\xff\x3c\xf4\xc4\xc0\xd2\x3b\xd6\x8a\x82\x34\x83\xbe"
def keygen(s):
   keys = []
   for i in range(2020):
      s = sha256(s).digest()
      keys.append(s)
   return keys
def K(x):
   ret = "".join( [format(x & 0xfffff, '020b')]*101 )
   return int(ret,2)
def dicrypt(kinum,cip,keys):
   for i in range(1010):
      idx=(kinum>>(2018-2*i))&3
      k=keys[2019-i][idx*8:idx*8+8]
      cp = DES.new(k, DES.MODE_CBC, bytes(8))
      cip=cp.decrypt(cip)
   return cip
keys = keygen(b'secret_sauce_#9')
fp=open("DECMID.txt","w")
for i in range(0,65536):
    if(i%150==0):
        print(i)
    keynum=K(i*16+0xe)
    fp.write(hex(bytes_to_long(dicrypt(keynum,c,keys)))[2:]+'\n')

在两组文件中寻找配对，大概需要用$20$秒左右。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#6.py
s=[]
f=open("ENCMID.txt","r")
for i in range(65536):
    a=int(f.readline(),16)
    s.append(a)
f.close()
print(1)
f=open("DECMID.txt","r")
for i in range(65536):
    b=int(f.readline(),16)
    if b in s:
        print(hex(i))
        print(hex(s.index(b)))
        print(hex(b))
f.close()
'''
0x3618
0x4d9e
0x8ac245ba53950c4fb8352bfe2639fcd9
'''

我们可以看出，加密ID是$\text{3618H}$，解密ID是$\text{4D9EH}$，所以我们恢复了最后的SECRET的值为$\text{A4D9E3618EH}$。然后简单修改一下解密脚本就可以得出flag了。不过重要的是注意下标计算的问题，比如最终解密脚本中的 $4038-2i$和$2019-i$是如何算的。

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
#4.py
import sys
from hashlib import sha256
from Crypto.Cipher import DES
SECRET=0xa4d9e3618e 
seed = b'secret_sauce_#9'   
def keygen(s):
   keys = []
   for i in range(2020):
      s = sha256(s).digest()
      keys.append(s)
   return keys
def scramble(s):
   ret = "".join( [format(s & 0xfffff, '020b')]*101 )
   ret += "".join( [format(s >> 20, '020b')]*101 )
   return int(ret, 2)
def decrypt(keys, msg):
   dk = scramble(SECRET)
   for i in range(2020):
      idx = (dk>>(4038-(2*i)))&3
      k = keys[2019-i][idx*8:(idx+1)*8]
      cp = DES.new(k, DES.MODE_CBC, bytes(8))  
      msg = cp.decrypt(msg)
   return msg
keys = keygen(seed)
with open("flag.enc", "rb") as f:
   msg = f.read()
ctxt = decrypt(keys, msg)
print(ctxt)

pctf{Two_tO_thE_s1xt33n7h?_E4sy-p3asy..}

4.[pasecactf_2019]tornado_casino

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
from sys import argv
from random import getrandbits
flag = '<redacted>'
tornado_banner = '''
                                                              88              
  ,d                                                          88              
  88                                                          88              
MM88MMM ,adPPYba,  8b,dPPYba, 8b,dPPYba,  ,adPPYYba,  ,adPPYb,88  ,adPPYba,   
  88   a8"     "8a 88P'   "Y8 88P'   `"8a ""     `Y8 a8"    `Y88 a8"     "8a  
  88   8b       d8 88         88       88 ,adPPPPP88 8b       88 8b       d8  
  88,  "8a,   ,a8" 88         88       88 88,    ,88 "8a,   ,d88 "8a,   ,a8"  
  "Y888 `"YbbdP"'  88         88       88 `"8bbdP"Y8  `"8bbdP"Y8  `"YbbdP"' '''
casino_banner = '''
                                88                          
                                ""                          
                                                            
 ,adPPYba, ,adPPYYba, ,adPPYba, 88 8b,dPPYba,   ,adPPYba,   
a8"     "" ""     `Y8 I8[    "" 88 88P\'   `"8a a8"     "8a  
8b         ,adPPPPP88  `"Y8ba,  88 88       88 8b       d8  
"8a,   ,aa 88,    ,88 aa    ]8I 88 88       88 "8a,   ,a8"  
 `"Ybbd8"' `"8bbdP"Y8 `"YbbdP"\' 88 88       88  `"YbbdP"\' '''
tornado_art = '''

   ((  "####@@!!$$    ))
       `#####@@!$$`  ))
    ((  '####@!!$:
   ((  ,####@!!$:   ))
       .###@!!$:
       `##@@!$:
        `#@!!$
  !@#    `#@!$:       @#$
   #$     `#@!$:       !@!
            '@!$:
        '`\   "!$: /`'
           '\  '!: /'
             "\ : /"
  -."-/\\\-."//.-"/:`\."-.JrS"."-=_\\
" -."-.\\"-."//.-".`-."_\\-.".-\".-//'''
welcome = 'Welcome!\n[1] - To slotmachine\n[2] - Enter promocode\n[3] - Exit\n'''
def sltmchn_wndw(num):
    print(num)
    return '|' + '|'.join(list(hex(num)[2:].zfill(8))) + '|'
slotmachine_menu = '[$] - $$$SPIN$$$\n'
print(tornado_banner)
print(casino_banner)
print(tornado_art)
user_balance = 10#$
promo = ''
while True:
    choice1 = input(welcome)
    if choice1 == '1':
        print('$$$Its point of no return!$$$\n$$$     all or nothing    $$$\n')
        print(f'Your balance: {user_balance}')
        while True:
            if user_balance > 0:
                spin = input(slotmachine_menu)
                if spin == '$':
                    state = getrandbits(32)
                    try:
                        pff_try = int(input('It will be: '), 16)
                    except:
                        exit(0)
                    if pff_try == state:
                        print(sltmchn_wndw(state))
                        print('OMGWTF$$$$$$$$$$$$')
                        print(flag)
                        exit(0)
                    else:
                        print(sltmchn_wndw(state))
                        print('Nice try!')
                        user_balance -= 1
                        print(f'Your balance: {user_balance}')
                else:
                    exit(0)
            else:
                print('Sorry!')
                exit(0)                   
    elif choice1 == '2':
        if not promo:
            promo = input('Enter your promocode: ')
            if promo == 'b33_1_4m_b3333':
                print('Great!')
                user_balance += 1000#$
        else:
            print('Only once!')      
    elif choice1 == '3':
        exit(0)

观察加密脚本可以发现，很容易地发现getrandbits(32)。而根据之前做题经验，这个就是让你预测MT19937。

首先上一下自己做的一个MT19937的工具包

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
def _int32(x):
    return int(0xFFFFFFFF & x)
class MT19937:
    def __init__(self, seed):
        self.mt = [0] * 624
        self.mt[0] = seed
        self.mti = 0
        for i in range(1, 624):
            self.mt[i] = _int32(1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)
    def extract_number(self):
        if self.mti == 0:
            self.twist()
        y = self.mt[self.mti]
        y = y ^ y >> 11
        y = y ^ y << 7 & 2636928640
        y = y ^ y << 15 & 4022730752
        y = y ^ y >> 18
        self.mti = (self.mti + 1) % 624
        return _int32(y)
    def twist(self):
        for i in range(0, 624):
            y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
            self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]
            if y % 2 != 0:
                self.mt[i] = self.mt[i] ^ 0x9908b0df
def inverse_right(res, shift, mask=0xffffffff, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift & mask
    return tmp
def inverse_left(res, shift, mask=0xffffffff, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift & mask
    return tmp
def extract_number(y):
    y = y ^ y >> 11
    y = y ^ y << 7 & 2636928640
    y = y ^ y << 15 & 4022730752
    y = y ^ y >> 18
    return y&0xffffffff
def recover(y):
    y = inverse_right(y,18)
    y = inverse_left(y,15,4022730752)
    y = inverse_left(y,7,2636928640)
    y = inverse_right(y,11)
    return y&0xffffffff

然后我们根据题目的提示，获取$624$个内部状态就可以预测随机数了。

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
from pwn import *
from MT19937 import *
from mt19937predictor import MT19937Predictor
def getnumber(s29):
	assert len(s29)==29
	s=s29[13]+s29[15]+s29[17]+s29[19]+s29[21]+s29[23]+s29[25]+s29[27]
	return int(s,16)
sh=remote("node3.buuoj.cn",29601)
str1=sh.recvuntil('[3] - Exit')
sh.sendline('2')
str1=sh.recvuntil('Enter your promocode:')
sh.sendline('b33_1_4m_b3333')
str1=sh.recvuntil('[3] - Exit')
sh.sendline('1')
S=[]
for i in range(624):
	if(i%31==0):
		print(i)
	str1=sh.recvuntil('N$$$')
	sh.sendline('$')
	sh.sendline('10000000')
	str1=sh.recvline(keepends=False)
	str2=sh.recvline(keepends=False)
	S.append(getnumber(str2))
Q=[]
R=[]
for i in S:
	Q.append(recover(i))
B=MT19937(0)
assert len(Q)==624
B.mt=Q
for i in range(10):
	print(i,hex(extract_number(B.mt[i])))
predictor = MT19937Predictor()
for i in range(624):
		predictor.setrandbits(S[i],32)
Y2=predictor.getrandbits(32)
print('ans=',hex(Y2))
sh.interactive()

当然，也可以使用专门的包用来预测，这个包网上可以通过pip下载下来。

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
from pwn import *
from mt19937predictor import MT19937Predictor
def getnumber(s29):
	assert len(s29)==29
	s=s29[13]+s29[15]+s29[17]+s29[19]+s29[21]+s29[23]+s29[25]+s29[27]
	return int(s,16)
sh=remote("node3.buuoj.cn",29601)
str1=sh.recvuntil('[3] - Exit')
sh.sendline('2')
str1=sh.recvuntil('Enter your promocode:')
sh.sendline('b33_1_4m_b3333')
str1=sh.recvuntil('[3] - Exit')
sh.sendline('1')
S=[]
for i in range(624):
	if(i%31==0):
		print(i)
	str1=sh.recvuntil('N$$$')
	sh.sendline('$')
	sh.sendline('10000000')
	str1=sh.recvline(keepends=False)
	str2=sh.recvline(keepends=False)
	S.append(getnumber(str2))
predictor = MT19937Predictor()
for i in range(624):
		predictor.setrandbits(S[i],32)
ans=predictor.getrandbits(32)
sh.sendline('$')
sh.sendline(hex(ans)[2:])
sh.interactive()

5.[羊城杯 2020]RRRRRRSA

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
import hashlib
import sympy
from Crypto.Util.number import *
flag = 'GWHT{************}'
flag1 = flag[:19].encode()
flag2 = flag[19:].encode()
assert(len(flag) == 38)
P1 = getPrime(1038)
P2 = sympy.nextprime(P1)
assert(P2 - P1 < 1000)
Q1 = getPrime(512)
Q2 = sympy.nextprime(Q1)
N1 = P1 * P1 * Q1
N2 = P2 * P2 * Q2
E1 = getPrime(1024)
E2 = sympy.nextprime(E1)
m1 = bytes_to_long(flag1)
m2 = bytes_to_long(flag2)
c1 = pow(m1, E1, N1)
c2 = pow(m2, E2, N2)
output = open('secret', 'w')
output.write('N1=' + str(N1) + '\n')
output.write('c1=' + str(c1) + '\n')
output.write('E1=' + str(E1) + '\n')
output.write('N2=' + str(N2) + '\n')
output.write('c2=' + str(c2) + '\n')
output.write('E2=' + str(E2) + '\n')
output.close()

这道题中，$n$具有$n=p^2q$的形式，并且构成$n_1,n_2$中的$p,q$都是非常非常接近的（就是相邻两个素数的关系）不过，$p$和$q$的位数相差较大。

Insert：关于连分数逼近的问题

在之前RSA的笔记中，我们使用的WienerAttack的原理就是连分数逼近，所以我们这里补充介绍一下勒让德定理：、

勒让德定理：假设$x\in R_+$，那么在$x$的连分数逼近展开中，如果有$|x-\dfrac a b|<\dfrac 1 {2b^2}$，其中$\gcd (a,b)=1$，那么可以认为$\dfrac ab$是$x$的连分数展开中的其中一项的值。

我们来回顾一下RSA中wienerattack的过程：

由$ed\equiv 1 \pmod \phi$，我们可以得到$ed-k\phi=1$。两边同时除以$d\phi$，那么就有$|\dfrac e \phi-\dfrac k d |=\dfrac 1 {d\phi}$。

又因为$n-\phi=p+q-1<3\sqrt n$。

所以根据勒让德定理，我们需要证明$|\dfrac e \phi-\dfrac k d |<\dfrac 1 {2d^2}$，下面简单地给出证明：：

左边分式通分，得
$$
|\dfrac {ed-nk}{dn}|
$$
分母凑一个$k\phi$，可以有
$$
|\dfrac {ed-k\phi-nk+k\phi}{dn}|
$$
又因为$ed-k\phi=1$，那么分子化简得
$$
|\dfrac {1-k(n-\phi)}{dn}|
$$
这个数字是小于$\dfrac{3k\sqrt n}{dn}=\dfrac{3k}{d\sqrt n}$。因此我们根据前面的几个条件，可以推出最后的结果小于$\dfrac{1}{2d^2}$。所以，在整个连分数逼近的过程中，中间的结果必然准确覆盖了$\dfrac k d$的值。

回到上面这道题，由于$p$是$1024$位，$p^2$是$2048$位，$q$是$512$位，比$2048$位小得多。而$p_1,p_2$、$q_1,q_2$是两组非常接近的数字，考虑到$p$更大，因此，当我们对$\dfrac {n_1} {n_2}$进行连分数逼近时，一定会准确覆盖到$\dfrac{p_1^2}{p_2^2}$或者$\dfrac {q_1}{q_2}$。

下面上一下解题过程,其中solve函数是连分数展开的过程，simplify函数和getmidfrac可以计算g数组中所涉及的所有的分数，以分子和分母形成的数对形式表现。最后枚举这个数对即可。

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
from Crypto.Util.number import *
from gmpy2 import *
from given import *
def solve(a, b):
    g=[]
    while(a!=1):
        g.append(a//b)
        a,b=b,a%b
    g.append(b)
    return g
def simplify(x):
    n,d=0,1
    for i in x[::-1]:
        n,d=d,i*d+n
    return n,d
def getmidfrac(x):
    r=[]
    for i in range(1,len(x)):
        r.append(simplify(x[:i]))
    return r
g=solve(N1,N2)
g=getmidfrac(g)
q1,q2=None,None
for (a,b) in g:
    if b==0:
        continue
    if N1%b==0 and b-1 and b-N1:
        q1=b
        q2=a
        break
p1,p2=iroot(N1//q1,2)[0],iroot(N2//q2,2)[0]
phi1,phi2=p1*(p1-1)*(q1-1),p2*(p2-1)*(q2-1)
d1,d2=inverse(E1,phi1),inverse(E2,phi2)
print(long_to_bytes(pow(c1,d1,N1)))
print(long_to_bytes(pow(c2,d2,N2)))
文章作者: huangx607087
文章链接: http://example.com/2021/02/16/21Feb2/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 huangx607087 !
ExpLog
赏
  目录