【NSSRound6】write up

Posted on | In

前言

做了两题密码，也是学了一些东西吧。

binary(V1)

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
from gmpy2 import *

flag = b'NSSCTF{xxxxx}'
m = bytes_to_long(flag)
e = 65537
p = getPrime(512)
q = next_prime(p ^ (1 << 512) - 1 ^ 3)
n = p * q
c = powmod(m, e, n)

print('n =', n)
print('c =', c)
# n = 28439705991045663908857355142942262888109378224567220640321971170147687906191867226507772290105722468453003997560405961037860301720566204163583071580117631863630591384712172525673589612679984312909885721474004407318513252973235607119935090030342220110613332646827222206888937013221686874130002976891337482347
# c = 19147147229180935592900776234339673387299394177535713949270580797239517644947690854918878134729963297207021578792506584675663899080028514789587402852322201811049767759204792874820803675496704837543205833779286293353943614755261264004375211872686806028504902564331881943276490126603876805247247189761895772971

这题我参考了【zer0pts CTF 2022】 Anti-Fermat的解法，求出近似值。

首先我们发现我们知道q是p ^ (1 << 512) - 1 ^ 3的下一个素数，而我们知道p ^ (1 << 512) - 1实际上就是2**1024-1，作用就是给p取反，所以p^2**1024-1的结果x是把p的每一位取反，所以x+p=2**1024-1。由于q是x的下一个素数所以q=x+r，带进去p+q=2**1024-1+r，所以p+q就约等于2**1024。

之后就是带入n=((p+q)/2)**2 - ((p-q)/2)**2，得到p的近似值，再爆破p即可。由于异或的值为3，实际上只影响到了最后两位，因此对这个方法不影响。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
import gmpy2
n= 28439705991045663908857355142942262888109378224567220640321971170147687906191867226507772290105722468453003997560405961037860301720566204163583071580117631863630591384712172525673589612679984312909885721474004407318513252973235607119935090030342220110613332646827222206888937013221686874130002976891337482347
c = 19147147229180935592900776234339673387299394177535713949270580797239517644947690854918878134729963297207021578792506584675663899080028514789587402852322201811049767759204792874820803675496704837543205833779286293353943614755261264004375211872686806028504902564331881943276490126603876805247247189761895772971
e=65537
t1=1<<512
p=((2**512+gmpy2.iroot((2**512)**2-4*n,2)[0])//2)
p=int(p)
while n%p!=0:
    p=gmpy2.next_prime(p)
q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

#NSSCTF{a974e2f02002874825ab6e8123eaef42}

binary(V2)

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from gmpy2 import *

flag = b'NSSCTF{xxxxxx}'
m = bytes_to_long(flag)
e = 65537
p = getPrime(512)
q = next_prime(p ^ (1 << 512) - 1 ^ 386031728400388)
n = p * q
c = powmod(m, e, n)

print('n =', n)
print('c =', c)

# n = 30922990347456222917444539556680823943887227159919972225540984336960832339775501069487618715102061181838518715208122786885229224735713077740655704542042089733020521332143961366919882134247596845707777520653357831207540764924471585714534980480437755533066407887622784022020839396643521892154136823395518763847
# c = 14404101377910063215556811836598054698395805241539170278590413082852350322381754181749356420746244575121938620896549335174534133100850321380464588512818088008879625862657133634998081654516156005613557049123826706652115924967600775632920027926373724318084460740820944304520569864767315879749100114552218784151

这题我参考的题目是【*CTF】ezRSA 这题。它的原题长这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import getStrongPrime
from gmpy import next_prime
from random import getrandbits
from libnum import s2n
#from flag import flag
flag = 'this_is_f1ag'
p=getStrongPrime(1024)
q=next_prime(p^((1<<900)-1)^getrandbits(300))
n=p*q
e=65537

m=int(flag.encode('hex'),16)
assert m<n
c=pow(m,e,n)

print(hex(n))
print(hex(c))

两题的区别在于移位不一样以及异或的位数不一样。*ctf中的题目由于只移位了900位，所以前124位是不变的，采用开根号的方式可以解出高124位。接下来因为300-900位是相反的，中间600位通过爆破可以得到一个大概值，最后300位coppersmith解出。

爆破过程就是p * q < n所以可以从高位开始，让p，q同位置的比特同时亦或1，若p * q < n则保留当前的p，q，一直循环600次，即遍历900~301比特。

而这道题由于没有留下高位不异或，所以没有开方这个过程，我们直接爆破p高位：

1
2
3
4
5
6
7
8
9
10
11
12
n=30922990347456222917444539556680823943887227159919972225540984336960832339775501069487618715102061181838518715208122786885229224735713077740655704542042089733020521332143961366919882134247596845707777520653357831207540764924471585714534980480437755533066407887622784022020839396643521892154136823395518763847

p = (1<<512)-1  
q = 1<<60-1
assert p * q < n
for i in range(511, 60, -1):
    cur = 1<<i
    if (p^cur) * (q^cur) < n:
        p ^= cur
        q ^= cur
print(p0)
#p0 = 10448144612165556385206311886141360231410940981240932869029890970634461091646882845169987826840400211179280084597554623669476308095974836695836265075965951

有了p的高位后，我们只要恢复p的低60位了：

1
2
3
4
5
PR.<x> = PolynomialRing(Zmod(n))
f = p0 + x
x0 = f.small_roots(X=2^216, beta=0.4)[0]
p = x0 + p0
#p=10448144612165556385206311886141360231410940981240932869029890970634461091646882845169987826840400211179280084597554623669476308095974834953990213093053961

得出了p的结果，就可以计算密文了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
import libnum

n=30922990347456222917444539556680823943887227159919972225540984336960832339775501069487618715102061181838518715208122786885229224735713077740655704542042089733020521332143961366919882134247596845707777520653357831207540764924471585714534980480437755533066407887622784022020839396643521892154136823395518763847
c=14404101377910063215556811836598054698395805241539170278590413082852350322381754181749356420746244575121938620896549335174534133100850321380464588512818088008879625862657133634998081654516156005613557049123826706652115924967600775632920027926373724318084460740820944304520569864767315879749100114552218784151
p=10448144612165556385206311886141360231410940981240932869029890970634461091646882845169987826840400211179280084597554623669476308095974834953990213093053961
e = 65537

q = n//p
d = gmpy2.invert(e, (p-1)*(q-1))
m = pow(c, d, n)
print(libnum.n2s(int(m)))

#NSSCTF{0c9ff400e7296837fd85890866a48cdd}