2022赣育杯–Wilson
题目：
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
'''
先想办法求出m来。因为p、q相近，所以对a开方得到p（或q）的近似值：$p_{near}$（$p<p_{near}<q$），对$p_{near}逐步求nextprime$，直至$amodp_{near}==0$：
a = 156853895847604116708242664263151514811095704969640303272039451331791888050995073274981545693518063639560286348739938318495685137088495867703518198511200409009953879436648706837731243061114851474801565873584183542649886358523850682697732574913523360866915083642887238043256280849100274825940626065115676325169
c = 3459715117165130065996389169943285249501133832272446001239391765859259811270526185228996906338576254353123756173289118671028939933226544773197852424767051933844004667155191851195814295922794480300237399956789038592856532530692732011427288405114650955620859282144504446058845961744702163836107847961388150810
p_near = iroot(a,2)[0]
while True:
q = next_prime(p_near)
if a%q==0:
print(q)
break
p = a // q
根据Wilson定理（$(p-1)! \equiv -1 \space mod \space p$），再结合题目的条件有：
$m = (p-1)!flag = -flag\space mod\space p $
$\Rightarrow flag = -m \space mod \space p$
再由：
$m \equiv (p-1)!flag \space mod \space (pq)$
$两侧同乘上p(p+1)…q \Rightarrow$
$mp(p+1)…q \equiv (q-1)!flag \space mod \space (pq)$
$再用Wilson定理 \Rightarrow$
$m^{‘} \equiv -flag \space mod \space q \Rightarrow$
$flag \equiv -m^{‘} \space mod \space q$
对比常规RSA里的$m=c^{e}modn$，可以看作已知两组c和n，利用中国剩余定理求m：
def broadcast_attack(data):
def extended_gcd(a,b):
x,y = 0,1
lastx,lasty = 1,0
while b:
a,(q,b) = b,divmod(a,b)
x,lastx = lastx-q*x,x
y,lasty = lasty-q*y,y
return (lastx,lasty,a)
def chinese_remaindor_theorem(items):
N = 1
for a,n in items:
N *= n
result = 0
for a,n in items:
m = N//n
r,s,d = extended_gcd(n,m)
if d != 1:
N = N//n
continue
result += a*s*m
return result%N ,N
x, n = chinese_remaindor_theorem(data)
return x
m = pow(c,d,a)
mp = -m % p
mq = -m % q
for i in range(p,q):
mq = mq * i % q
data = (mp,p),(mq,q)
flag = broadcast_attack(data)
print(long_to_bytes(flag))
考点
Wilson定理，剩余定理应用
一步到喂
from Crypto.Util.number import *
from secret import flag,x,y
p=getPrime(512)
q=getPrime(512)
n=p*q
e=x
assert 1293023064232431070902426583269468463*pow(x,2)==105279230912868770223946474836383391725923*pow(y,2)+1293023064232431070902426583269468463
m=bytes_to_long(flag)
c=pow(m,e,n)
print(p,q)
print(c)
#9850212100620338486478343799784951721581757936621772924971218807300819701941457605399099898870264241518769370682330612103782092302148525012450902351701339
#10749429992014823019923966246896511618886613763258781706004694804949547801668777655988055847885755337127548775758133804022361510427909703124161450470578543
#66847321508502017574023222490247591875197038421108556106531660421662626233521063441647157067220450229816184622038471812597874582613385516838920632450015292570673816423432903604941781889308906893966588610214614726388822851471695742453496232748358301888465563812947038856742838097152549971517159475947566599664
来自杭师大校赛。
分析断言处，记为：
$$
num_1 * x^2 = num_2 * y^2 + num1
\两边同除num_1，并记num_2/num_1为D
\ \Rightarrow x^2-D*y^2 = 1
$$
通过了解，是Pell方程，还未成涉猎过，比赛中大致看了下，一顿搜才找到了个脚本（问就是菜没本事自己写😥），解出e来，之后便是基础RSA了。
def pell_equation(D):
a0 = int(D**0.5)
a1 = int(2*a0/(D-a0**2))
seq,P,Q = [a0,a1],[a0,a1*a0+1],[1,a1]
m,d = a0,D-a0**2
while seq[-1] != 2*a0:
m = d*seq[-1]-m
d = (D-m**2)//d
seq.append(int((a0+m)/d))
P.append(seq[-1]*P[-1]+P[-2])
Q.append(seq[-1]*Q[-1]+Q[-2])
if (len(seq)-1) % 2 == 0:
return (P[-2],Q[-2])
else:
return (P[-2]**2+Q[-2]**2*D,2*P[-2]*Q[-2])
res = pell_equation(81421)#D的值为81421
print(res)
考点
Pell方程（有待进一步深入学习。。。）
baby_reverse
# python3
from badmonkey import flag
message = bytes_to_long(flag)
enc = message ^ message>>23
print("enc = ",enc)
# enc = 696190889020604856890193198853561201348825165171326836202150445122902404137656377702109518236445
从enc = message ^ (message>>23)入手，注意运算顺序。
分析可知：$message$前23位与$enc$的前23位相同，$message$的23-46位与本身的前23位异或得到$enc$的23-46位。通过不断往低位推最终可以得到完整的$message$
enc = ...
tmp = enc
for i in range(enc.bit_length()//23):
tmp = enc ^ tmp >> 23
print(long_to_bytes(tmp))
easy_reverse
from Crypto.Util.number import *
from badmonkey import flag
m = bytes_to_long(flag)
BITS = m.bit_length()
a,b,c,d = 15,27,19,23
mask1 = 3698415493855604199601451107484163420720646551661606649093806737041154400431942060340531696401
mask2 = 3460949362284136053271491912952156811286686375965162899233783178191434976143378804364416056910
def encrypt(y):
y = y ^ y >> a
y = y ^ y << b & mask1
y = y ^ y << c & mask2
y = y ^ y >> d
return y&((2<<BITS)-1)
enc = encrypt(m)
print("enc = ",enc)
# enc = 1050202800288756594888207862919284086044293654918425636192291797436341243157293011540594049798
思路与上一题大致相同，y&((2<<BITS)-1)的作用是对2^bits取模。
a,b,c,d = 15,27,19,23
mask1 = ...
mask2 = ...
BITS = mask1.bit_length()
enc = ...
def inverse_right(res, shift, BITS):
tmp = res
for i in range(BITS // shift):
tmp = res ^ tmp >> shift
return tmp
def inverse_left_mask(res, shift, mask, BITS):
tmp = res
for i in range(BITS // shift):
tmp = res ^ tmp << shift & mask
return tmp
def encrypt(y):
y = y ^ y >> a
y = y ^ y << b & mask1
y = y ^ y << c & mask2
y = y ^ y >> d
return y&((2<<BITS)-1)
def recover(y):
y = inverse_right(y,d,BITS)
y = inverse_left_mask(y,c,mask2,BITS)
y = inverse_left_mask(y,b,mask1,BITS)
y = inverse_right(y,a,BITS)
return y&((2<<BITS)-1)
flag = recover(enc)
print(long_to_bytes(flag))
baby_math
# baby math
from math import factorial
from badmonkey import flag
p = 6754809195983416889371518438404230464318771258362527973287334033265667200119099459184180646680169474847824019197256829826149222241090098845978570412659797
def my_wilson(x,p):
return factorial(x)%p
res = my_wilson(p-2333,p)
mid = md5(str(res).encode()).hexdigest()
assert mid == "a3fe2bd4fb7c2f3642d57d67967c649b"
print("Spirit{{{}}}".format(res%(2**100)))
有下面的关系：
$res = (p-2333)! \space mod \space p$
关键在求res，我们由威尔逊定理：$(p-1)! \equiv -1 mod p$
$\Rightarrow (p-2)!(p-1) \equiv (p-1)mod p$
$\Rightarrow(p-2)! \equiv 1mod p$
$\Rightarrow (p-2)(p-3)…(p-2332)res \equiv 1 mod p$
依次对每部分求逆即可：
p = ...
res = 1
for i in range(2,2333):
res = res*inverse((p-i),p)
res %= p
mid = md5(str(res).encode()).hexdigest()
assert mid == "a3fe2bd4fb7c2f3642d57d67967c649b"
print("Spirit{{{}}}".format(res%(2**100)))
考点
威尔逊定理
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com