[Week 4] SIDH
- SIDH后量子安全密钥交换协议，嗐（学不懂
- 但是
- DH，说的很明白了，就是密钥交换
- 看源码发现只要模仿靶机生成密钥然后和靶机进行交互就可以了
- 实测：9.3版本代码无法正常运行，建议用10.4
- 抄靶机代码
from pwn import *
ea, eb = 110, 67
p = 2**ea * 3**eb - 1
F.<i> = GF(p**2, modulus=[1,0,1])
E0 = EllipticCurve(F, [1,0])
addr = "nc 118.195.138.159 10009".split(" ")
io = remote(addr[1],int(addr[2]))
recv = io.recvline().decode()[10:-2]
RA_ = re.split(r"\*i \+ |,", recv)
RA = E0(int(RA_[0])*i + int(RA_[1]), int(RA_[2])*i + int(RA_[3]))
print(f"RA={RA.xy()}")
PB = E0.random_point()
QB = E0.random_point()
sB = randint(0, 2**ea)
RB = PB + sB * QB
xy = [str(i).split("*i + ") for i in RB.xy()]
payload1 = ",".join(",".join(i) for i in xy)
print(f"RB={RB.xy()}")
print(f"payload1={payload1}")
phi_A = E0.isogeny(RA, algorithm='factored')
E_A = phi_A.codomain()
R_share = phi_A(PB) + sB * phi_A(QB)
phi_share = E_A.isogeny(R_share, algorithm='factored')
secret = phi_share.codomain().j_invariant()
payload2 = ",".join(i for i in str(secret).split("*i + "))
print(f"secret={secret}")
print(f"payload2={payload2}")
io.sendlineafter("[+] Give me RB:\n>",payload1.encode())
io.sendlineafter("[+] Tell me the secret\n>",payload2.encode())
flag = io.recvline()
print(flag)
io.interactive()
- 可能要多跑几次，因为secret出现整数的可能性还是挺大的（不知道为什么
- 0xGame{4179c8c3-db69-4fb0-bd14-ef6c76ddb973}
[Week 4] RNG
from pwn import *
import random
from sympy import invert
addr = "nc 118.195.138.159 10006".split(" ")
io = remote(addr[1],int(addr[2]))
io.recvline()
result = [int(i) for i in io.recvline().decode()[1:-2].split(", ")]
# 逆向MT19937
class MT19937Recover:
def unshiftRight(self, x, shift):
res = x
for i in range(32):
res = x ^ res >> shift
return res
def unshiftLeft(self, x, shift, mask):
res = x
for i in range(32):
res = x ^ (res << shift & mask)
return res
def untemper(self, v):
v = self.unshiftRight(v, 18)
v = self.unshiftLeft(v, 15, 0xefc60000)
v = self.unshiftLeft(v, 7, 0x9d2c5680)
v = self.unshiftRight(v, 11)
return v
def go(self, outputs, forward=True):
result_state = None
assert len(outputs) >= 624
ivals = []
for i in range(624):
ivals.append(self.untemper(outputs[i]))
if len(outputs) >= 625:
challenge = outputs[624]
for i in range(1, 626):
state = (3, tuple(ivals+[i]), None)
r = random.Random()
r.setstate(state)
if challenge == r.getrandbits(32):
result_state = state
break
else:
result_state = (3, tuple(ivals+[624]), None)
rand = random.Random()
rand.setstate(result_state)
if forward:
for i in range(624, len(outputs)):
assert rand.getrandbits(32) == outputs[i]
return ivals
# 逆向twist
def untwist(newState, flag: bool = True):
oldState = [0] * 624
for i in range(624 - 1, -2, -1):
x = newState[i] ^ newState[(i + 397) % 624]
if x & 0x80000000 == 0x80000000:
x ^= 0x9908b0df
x <<= 1
x |= 1
else:
x <<= 1
if i > -1:
oldState[i] |= x & 0x80000000
if i + 1 < 624:
oldState[i + 1] |= x & 0x7fffffff
if i == 227 and flag:
newState = list(newState[:227]) + oldState[227:]
return oldState
# 逆向__init__
def _int32(x):
return int(0xFFFFFFFF & x)
def invert_right(res,shift):
tmp = res
for i in range(32//shift):
res = tmp^res>>shift
return _int32(res)
def recover(last):
n = 1<<32
inv = invert(1812433253,n)
for i in range(623,0,-1):
last = ((last-i)*inv)%n
last = invert_right(last,30)
return last
mtc = MT19937Recover()
newstate = mtc.go(result)
oldstate = untwist(newstate)
seed = recover(oldstate[-1])
print(f"seed={seed}")
io.sendlineafter("[+] seed = ?\n>",str(seed).encode())
io.interactive()
- 0xGame{2569bd55-a14d-46d8-81f5-e1397e4be7bc}
- p.s. extract逆向还是比较好理解（博客讲的很清楚），其他两种操作就难理解了
[Week 4] Coppersmith-I
- 这是RSA已知p高位攻击Factoring with High Bits Known
- 所以可以构造出p用sage求解小根
- 参考博客
n = 135500646574582511239845764710311769260801998982429500680171919823431178899526463566215834234383331374445093363969218810906991784569340270510936759183504496584225937614940086329775325893307453919055830270986601152002191368431527285285313669979358099782497422114870417519470053198217401297960844455029559146309
c = 41763956818640145556632229720626372656921875856507389014855753965024986594502113237270745517422792354256348958542864591249410500750410658988509136242435502259172258432676502846729088278202750721760451160668653746019965695721844819587671602925551448624324524027931677927410810126647175483982178300855471710099
e = 65537
p_high = 918578024558168836638919636090777586135497638818209533615420650282292168631485
for i in range(2**5):
p4 = p_high << 5 #这里需要先爆破5位，使得知道264位以后再恢复p
p4 = p4 + i
kbits = 248
p4 = p4 << kbits
R.<x> = PolynomialRing(Zmod(n))
f = x + p4
res = f.small_roots(X=2^kbits, beta=0.4, epsilon=0.01)
if res != []:
p = p4 + res[0]
print(p)
break
- 得到p之后常规解密文就行
- 0xGame{8f4c17cb-442a-49bd-830a-d16af225a5c5}