2022赣育杯CTF---Wilson wp

题目

from os import urandom
from gmpy2 import next_prime
from Crypto.Util.number import getPrime, bytes_to_long

p = getPrime(512)
q = next_prime(p)
f = open('flag.txt', 'rb')
flag = bytes_to_long(f.read() + urandom(80))
f.close()

N = 1
a = p * q
for i in range(1, p):
    N = (N * i) % a
e = 65537
m = N * flag % a
c = pow(m, e, a)
f = open('Encode.txt', 'w')
f.write(f'a = {a}n')
f.write(f'c = {c}n')
f.close()


a = 156853895847604116708242664263151514811095704969640303272039451331791888050995073274981545693518063639560286348739938318495685137088495867703518198511200409009953879436648706837731243061114851474801565873584183542649886358523850682697732574913523360866915083642887238043256280849100274825940626065115676325169
c = 3459715117165130065996389169943285249501133832272446001239391765859259811270526185228996906338576254353123756173289118671028939933226544773197852424767051933844004667155191851195814295922794480300237399956789038592856532530692732011427288405114650955620859282144504446058845961744702163836107847961388150810

题目分析

第一步

由题目可知，p和q是相邻的素数，所以可以直接对n进行开二次方，得到的值q_near，其范围为p<q_near<q。然后不断的进行循环取q_near的下一个素数，直到能被n整除为止，此时的q_near即为q，进而得到p为n//q。

第二步

接下利用威尔逊定理
$(p-1)!\equiv -1modp$

由于flag = bytes_to_long(f.read() + urandom(80))，其中在flag的基础上随机添加了80个字节的字符串，长度已经超过了512bit长度的p,所以我们在mod p情况下求出来的flag实际上是flag mod p的结果，也就是低位部分。
所以需要在mod q一次求得对应的 flag mod q，然后再利用crt处理得到m。
已知$m=flag\cdot (p-1)!modn$,如果给m依次乘上$p,p+1,...,q-1$就有$m1=flag\cdot (q-1)!modn$,此时对m1模q,即$m1modq\equiv flag\cdot (-1)\equiv m1modq$。之后对m1求模逆得到flag mod q,最后用中国剩余定理crt组合一下即可求得原m

解题代码

import gmpy2
from Crypto.Util.number import *
from sympy.ntheory.modular import *

n = 156853895847604116708242664263151514811095704969640303272039451331791888050995073274981545693518063639560286348739938318495685137088495867703518198511200409009953879436648706837731243061114851474801565873584183542649886358523850682697732574913523360866915083642887238043256280849100274825940626065115676325169
c = 3459715117165130065996389169943285249501133832272446001239391765859259811270526185228996906338576254353123756173289118671028939933226544773197852424767051933844004667155191851195814295922794480300237399956789038592856532530692732011427288405114650955620859282144504446058845961744702163836107847961388150810
e = 65537

q_near = gmpy2.iroot(n,2)[0]
while n%q_near!=0:
    q_near=gmpy2.next_prime(q_near)
q = q_near
p = n//q
print(f"p={p}")
print(f"q={q}")

phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
m1= m*gmpy2.invert(-1,p)%p
for i in range(p,q):
    m = m*i%q
m2 = m * gmpy2.invert(-1,q) %q
flag = crt([p,q],[m1,m2])[0]
print(long_to_bytes(flag))

flag：

Sangfor{51083a96-13b4-00c4-36c0-2025c1b46a63}

【真正爱一个人，就算把自己的全世界都给了她，却依然担心给的不够多，不够好。】

最后

以上就是直率毛豆为你收集整理的2022赣育杯CTF---Wilson wp的全部内容，希望文章能够帮你解决2022赣育杯CTF---Wilson wp所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。