学生组
赛题一
from secret import flag
from Crypto.Util.number import *
total_bit = 512
def make_para(bit_size):
P = getStrongPrime(bit_size)
Q = getStrongPrime(bit_size)
N = P * Q
magic = (N + 1) * (N + P + Q + 1) + (P - Q) ** 2 + N
d = int(0.394 * bit_size)
e = inverse(d, magic)
k = d * e // magic
return (N, e), (P, Q, k)
pubkey, sec_key = make_para(2 * total_bit)
flag = bytes_to_long(flag) * sec_key[2]
p = getStrongPrime(total_bit)
q = getStrongPrime(total_bit)
n = p * q
e = 65537
c = pow(flag, e, n)
t = ((p - getRandomNBitInteger(16)) * sec_key[0] + q) % sec_key[1]
with open('output.txt', 'w') as f:
f.write(str(pubkey) + 'n')
f.write(str((t, c)))
d = int(0.394 * bit_size)，原来 是一个已知整数。from gmpy2 import *
N,e = (21136120517038375343657055317361461947217610380415290931285704769845405139443342030139838613845989765254932385503454684656325859309861269837188207923942223163348944160792729101485975484543693998035828762630825174735962679103457025646672449491007685400869138263581883506767852264244013623583813540066115060793144049256890248337903932112449333735324371400873419104520104079223733159263094092843185909770131443506433825708789563521497940390674504488024226655482568491358458107989880756229607524452273305978138461190013290440068226454238375505010225133919526068226837545142734502100757510899741312502285931571783851666429, 291542085122413541028076006933740091355832744332602513957292369860771664833892358795585946753279254101863581542678927529330607906769804928526978686071141386341893467977451552634615917127445748737712286687041822255325772392569586666055711202824870471562051621883329559663555059967665101455578668904247279540014709971958403913939101728330638301270881265277488332145439522278871554725936095617940701105161078332467466405454007283937177070102098256744642045839067405705972784471374421818844770106228499198315920181837950503279178647052157269318876892192700670366858062171759498850112906238502375693099462427930964555274451795362167393410749436026095037695100430810204847979914959732383773952788768239221142673268839750770222737928397507645337714199166919835667638401309062163501094032890215821366318775462220119081175885338966308921205861717088926659072208866126879068213582499260316364548817213314952246293713853884872460934174624844462586276340207505217646013915381902979372875919823493439285174120160656952728493383464761519634974414670811896809158801804891938928244053980210687334268664219571818927285279999791212932795196689285015367417706597781418431735001428656415752334850685705212368666855124013583549768407830008606258798409140)
d = int(0.394 * 1024)
k = (e*d-1)//N**2
p_a_q = (e*d-1)//(k*N) - N - 3
p_s_q = iroot(p_a_q**2-4*N,2)[0]
p = (p_a_q+p_s_q)//2
q = p_a_q - p
assert p*q == N
print(p)
print(q)
print(k)
# 143078039642881652792725771784213914569207427179221450527831176525315265565238257928580110111049486656241446498753952813958174255162082586211603455849496271101246800300949146175660103176787576526962695816071099455794179935847192303931252206979980383408582225496150194196048569906497422686531669037370362490591
# 147724420671358625656073728988251990709657136203479220456044242791542317692661747967991832853881462444146194371982730793349362452137634455888399765514368115413509137529033492152562833458082422584778299506218002962422410654802940055372919228164309566932084727942623228573408370823021433452034727423294317997219
# 263
from Crypto.Util.number import *
p = getPrime(510)
q = getPrime(510)
n = p * q
t = ((p - getRandomNBitInteger(16)) * P + q) % Q
shift = 2^1024
m = matrix(ZZ,[[shift*P,1,0,0,0],
[shift*1,0,1,0,0],
[shift*Q,0,0,1,0],
[shift*t,0,0,0,2^512]])
m = m.LLL()
assert abs(m[1][2])==q
t,c = (18872151984199200051633005759140295224788252451326410141022483203855894790958837408470348915966212063467995292461061069273539234939320647533902914083943444743748789975745514239518406829738286900177972974033143896932863898553599888597165054837513698667686277110587659188172271629973371164557353473146831275972, 47672712219012743425382676880904671136942826695249149129159924785186563239747047304204962529935078111450524236186612259355850306867579998685662967391936502046679744616903469002187225791339629835786750259999982506494377133775859573660632942293353420327987860136624649402598383416748766985203781387716072244402)
k = 263
P = 143078039642881652792725771784213914569207427179221450527831176525315265565238257928580110111049486656241446498753952813958174255162082586211603455849496271101246800300949146175660103176787576526962695816071099455794179935847192303931252206979980383408582225496150194196048569906497422686531669037370362490591
Q = 147724420671358625656073728988251990709657136203479220456044242791542317692661747967991832853881462444146194371982730793349362452137634455888399765514368115413509137529033492152562833458082422584778299506218002962422410654802940055372919228164309566932084727942623228573408370823021433452034727423294317997219
# 猜测 p,q 高位
ph = 0b11<<510
qh = 0b11<<510
# 根据 p,q 高位， t 做相应处理
tbar = (t-qh-ph*P)%Q
shift = 2^1024
m = matrix(ZZ,[[shift*P,1,0,0,0],
[shift*1,0,1,0,0],
[shift*Q,0,0,1,0],
[shift*tbar,0,0,0,2^512]])
m = m.LLL()
if isPrime(int(abs(m[1][2])+qh)):
q = abs(m[1][2])+qh
e = 65537
d = inverse(e,q-1)
mm = pow(c,d,q)
print(long_to_bytes(int(mm//k)))
b'flag{6db64079-711c-4d80-86c6-baec1023d44d}'
赛题二
然后我把第二题给问过来了，
from Crypto.Util.number import *
from Crypto.Util.strxor import strxor
from random import randint
from gmpy2 import invert
import os
flag = b'xxx'
def mypad(m):
l = len(m)
r = 190 - l
padded_m = m + os.urandom(r)
return padded_m
def myfunction(num):
output = 0
j = 0
for i in range(num):
output += (i+j)*6 + 1
j += i
return output
def mix(a,b):
return a | b , a * b
class MySeries():
def __init__(self, num):
self.num = num
def Coe(self, n):
i = 0
c = 1
while i < n:
i += 1
c = (c * (1 / 2 - i + 1)) / i
return c
def Point(self, center):
sum = 0
center -= 1
i = 0
while i < self.num:
sum += (center ** (1 / 2 - i) * self.Coe(i))
i += 1
return sum
def All(bound):
num = randint(1111, 2222)
T = MySeries(num)
output = 0
i = 3
while i < bound:
b1 = T.Point(i)
b2 = T.Point(i + 1)
output += (b1 + b2) / 2
i += 1
return output
if __name__ == '__main__':
flag_len = len(flag)
p,q = getPrime(512),getPrime(512)
while True:
r = getPrime(512)
R = bytes_to_long(str(r).encode())
if isPrime(R):
break
n = p * q * r
hint1 = R * r
mod = myfunction(n)
hint2 = pow(3*n+1,p % (2 ** 400),mod)
k = int(All(n))
xor_flag = strxor(long_to_bytes(k >> (k.bit_length() - 8 * flag_len)),flag)
pad_flag = mypad(xor_flag)
m = bytes_to_long(pad_flag)
c = pow(m,65537,n)
print('All data:')
print(f'flag_len = {flag_len}')
print(f'n = {n}')
print(f'c = {c}')
print(f'hint1 = {hint1}')
print(f'hint2 = {hint2}')
'''
All data:
flag_len = 42
n = 1885106209951408608833065466098355578239648885277085979696889428331716535742564778501798478665957825315340421821880653818505857049636611632357321104069926874970489073929053910350131880591544986024406953378391135673202854750625745159391997973535848495128365477217006260495413869532372418221652962946340513593002422433536479789576519469228846773250447077165756739529520975715667675188738514871033908115371290569902086064227476952606366538782284487477820835988316471
c = 696238728213276154324787695659767792043458798396732235983493075871691401810545168845655490352789752222363100922123671319198981013421632076090146254867823593523050502577701155837063376958530879006719716789887624440134559774538443909463537086796915613123528679984244371544503657821859556837415229166015914540860398289216765611441964228176020361651359395184571105468667815326494558761738459063914192172836518999575866452752941368767971539919141604299843463853501960
hint1 = 47533994701669017942592643580845693193316601935087923279407365999451221242084261195588230994183718077379066856479267476895986608547324057765879168010176037349172136581929046771540241367625486215731295814611283581608613208990206581757576978017732022062210538697720930605552259306749633658032304554578427461842934055558865521604512892691323385156889995854702621568441768712619224249280792783364635307739215957762771386413831279443875185633720270001928747743847856394847878232194076679733830705297410959656270945532930199517880949
hint2 = 1345739841248959791137389026125065605121513428784838684290299665636596562317989590469829195181078904857051392378877013458099983407103737518119999468489762053545474516182879516762580472262640794849609626308003164739287189671066241628052826558582865342176036139097546843281565147798609965645514151827840249686650855385385323417455247722134760335695053787221300451942370377598800841980049138341564555801417479362085565640973199260631136149016266661293883650801813550118778433333591258278147003619871962070136454674193198696690506092831171400435490432196636796719177624389194619648086397178720207413652618636521150924913978530986709499047969775311955879302418093270101476537853298615347062384026172441455857088955847766335746521291043747795520485020303040819568036819058385444936925860671650596681910380157657689041971132993731048618045570715513584627109356139903842365556697314631573799394266292587334468008221427502353566938518574247502783245674619641519095644135976062817840893465238031354234069073928763492529419021632732679912738674105898149050223970723297059883534089683179512881491210176114419520070007595698242827625902377045860953285447617249204919971737086366
'''
gcd 求出 ，myfuction 其实就是一个计算三次方的函数，All 函数其实就是一个泰勒展开在求 的积分，所以 n = 1885106209951408608833065466098355578239648885277085979696889428331716535742564778501798478665957825315340421821880653818505857049636611632357321104069926874970489073929053910350131880591544986024406953378391135673202854750625745159391997973535848495128365477217006260495413869532372418221652962946340513593002422433536479789576519469228846773250447077165756739529520975715667675188738514871033908115371290569902086064227476952606366538782284487477820835988316471
r = 13064264216014600984590013161094647588688097945008015283029781423081403612570218487688473281971441574006356719607329041516297420593832435695152551495621303
# n = p * q * r
# mod = myfunction(3)
# print(mod==n**3)
# hint2 = pow(3*n+1,p % (2 ** 400),n**3)
# hint2 = pow(3*n+1,400,n**3)
# print((hint2%(n**2))//n)
# pbar = (hint2%(n**2))//(3*n)
# # pbar = 290093818088445232385211155295987419950746202522777816778903667287369882202987169000686051435796089920601608052312746065
# R.<x> = Zmod(n)[]
# f = (2^400) * x + pbar
# x0 = f.monic().small_roots(X=2^112,beta=0.49)[0]
# p = int(f(x0))
# q = int(n)//p
# p = 10835491201779459536146517032534966141751744767433086585469873899474443209697998673019277269625767885233333299822821960132722036029334072360300733477529681
# q = 13316873218544878416280346742338579649540959399378233738197413050519025036683226049252858246940675299712559597339200613975360145818807371576573913305896497
# phi = (p-1)*(q-1)*(r-1)
# d = inverse(e,phi)
# m = pow(c,d,p*q*r)
# m = long_to_bytes(m)
#
k = 2*(n*iroot(n,2)[0])//3
xor_flag = strxor(long_to_bytes(k >> (k.bit_length() - 8 * flag_len)),flag[:42])
xor_flag
b'flag{84934a62-f932-968c-fa88-22f0284c0e8e}'
社会组
from secret import flag, genPrime, generate_g
import random
import math
import os
sieve_base = # from Crypto.Util.number import sieve_base
def rabinMillerTest(n, rounds):
tested = []
if n < 3 or (n & 1) == 0:
return n == 2, tested
# n might be very large so it might be beneficial to precalculate n-1
n_1 = n - 1
# determine m and b so that 2**b * m = n - 1 and b maximal
b = 0
m = n_1
while (m & 1) == 0:
b += 1
m >>= 1
#a smaller number might be faster...
upper = 2**(max(n.bit_length() >> 5, 10))
# we need to do at most n-2 rounds.
for i in range(min(rounds, n - 2)):
a = random.randint(2, upper)
while a in tested:
a = random.randint(2, upper)
tested.append(a)
# do the rabin-miller test
z = pow(a, m, n) # (a**m) % n
if z == 1 or z == n_1:
continue
composite = 1
for r in range(b):
z = (z * z) % n
if z == 1:
return 0, tested
elif z == n_1:
composite = 0
break
if composite:
return 0, tested
return 1, tested
def is_prime(N, false_positive_prob=1e-6):
tested = []
if N < 3 or N & 1 == 0:
return N == 2, []
for p in sieve_base:
if N == p:
return 1, tested
if N % p == 0:
tested.append(p)
return 0, tested
rounds = int(math.ceil(-math.log(false_positive_prob)/math.log(4)))
return rabinMillerTest(N, rounds)
print("Welcome to my secure key exchange systemn")
while True:
q = int(input("q:"))
if q.bit_length() < 256:
print("oh! too small!!!")
continue
jud, tested = is_prime(q)
if not jud:
print(f"Bad parameters! test set {tested} not pass.")
else:
break
x = int.from_bytes(os.urandom(q.bit_length() // 8), byteorder='big')
p = genPrime(q)
g = generate_g(q, p)
print(f"p: {p}")
print(f"g: {g}")
A = pow(g, x, p)
print(f"Calculate the public key in this way: pow(g, secret, p)")
print(f"eg. pow(g, x, p) = {A}")
print(f"I can give you a hint:)")
r = int(input("r:"))
if r < x and ((p - 1) % r == 0):
print(pow(g, x, r))
else:
print("don't need hint?")
for i in range(100):
B = int(input("give me your public key:"))
if 1 < B < p:
shared = pow(B, x, p)
print(f"our shared key: {shared}")
x_ = int(input("x?").strip())
if x_ == x:
print(flag)
else:
print("sorry~")
genPrime, generate_g 给偷摸隐藏了起来，估计是有点问题。看一下题目流程：-
用户端输入一个大于 256 比特的素数 -
服务端随机生成一个秘密数 ，并根据用户的 生成一个素数 ，在根据 生成一个 ，并给出 。（由于没有源码，这里合理猜测生成的 具有因子 ，而 是一个在模 阶为 的一个元素，这是 Elgamal 参数生成的标准） -
服务端允许用户输入一个 ，如果满足 ，服务端就会输出 -
之后服务端让用户输入一个 ，并给出 （就是一个 ECDH），然后让用户猜 ，猜对了就给 ，一共一百次交互机会。
rabinMillerTest 还以为让绕过素数检测，但根据后面的流程来看，估计预期应该是根据 hint 得到一些关于 信息，再利用一百次交互，每次搞到一点额外的信息，最后恢复完整的 叭。genPrime 函数猜测的正确的话，那就直接设 为 ，而 是一个光滑数就行了。至于和 的大小关系，由于 的生成和 的比特有关 x = int.from_bytes(os.urandom(q.bit_length() // 8), byteorder='big') ，注意这里 并不是严格小于 ，所以爆！为了消去“地板除”的影响，要找比特长度刚好是 8 的倍数的 ，然后多跑几次等 比 大，我们就可以直接解 得到 ，然后根据大小关系，对结果加一个 就是 了。from Crypto.Util.number import *
import random
def genPrime(bit_len):
while True:
x = 2
while x < 2**bit_len:
x *= random.choice(sieve_base)
if isPrime(x+1) and x.bit_length() % 8 == 0:
return x+1
print(genPrime(256))
（不过由于没有赛题源码，以上想法全是基于猜测正确的前提下）
免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉。
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论