题目源码
from Crypto.Util.number import *
from random import randrange
from secret import flag
def pr(msg):
print(msg)
pr(br"""
....''''''....
.`",:;;II;II;;;;:,"^'.
'"IlllI;;;;;;;;;;;;;Il!!l;^.
`l><>!!!!!!!!iiiii!!!!!!!!i><!".
':>?]__++~~~~~<<<<<<<<<<<<<<<<~~+__i".
.:i+}{]?-__+++~~~~~~<<<<<~~~~~~+_-?[\1_!^
.;<_}\{]-_++~<<<<<<<<<<<<<<<<<<<~+-?]\|]+<^
.!-{t|[?-}(|((){_<<<<<<<<<_}1)))1}??]{t|]_"
!)nf}]-?/\){]]]_<<<<<<<<<_]]}}{\/?-][)vf?`
'!tX/}]--<]{\Un[~~<<<<<~~<~-11Yz)<--?[{vv[".
.<{xJt}]?!ibm0%&Ci><<<<<<<<!0kJW%w+:-?[{uu)},
!1fLf}]_::xmqQj["I~<<<<<<>"(ZqOu{I^<?[{cc)[`
`}|x\}]_+<!<+~<<__~<<<<<<+_<<_+<><++-[1j/(>
!\j/{]-++___--_+~~<i;I>~~~__-______?}(jf}`
;~(|}?_++++~~++~+]-++]?+++~~~~+++-[1/]>^
;\([?__+_-?]?-_-----__-]?-_+++-]{/].
l||}?__/rjffcCQQQQQLUxffjf}+-]1\?'
,[\)[?}}-__[/nzXXvj)?__]{??}((>.
.I[|(1{]_+~~~<~~<<<~+_[}1(1+^
,~{|\)}]_++++++-?}1)1?!`
."!_]{11))1{}]-+i:'
.`^","^`'.
""".decode())
def gen_prime(bit):
while 1:
P = getPrime(bit)
if len(bin(P)) - 2 == bit:
return P
pq_bit = 512
offset = 16
P,Q = [gen_prime(pq_bit) for i in range(2)]
N = P * Q
gift = int(bin(P ^ (Q >> offset))[2+offset:],2)
pr(N)
pr(gift)
inpP = int(input())
if inpP != P:
pr(b"you lose!")
exit()
secret = randrange(0,P)
bs = [randrange(0,P) for _ in range(38)]
results = [(bi * secret) % P for bi in bs]
rs = [ri & (2 ** offset - 1) for ri in results]
pr(bs)
pr(rs)
inpsecret = int(input())
if inpsecret == secret:
pr(flag)分析
RSA
给出了p^(q>>16)的低512-16位，还原P。已知p^(q>>16)以前见过，直接套脚本；另外，这一题删掉了高16位，所以要加个爆破。
HNP
Intended Solution to NHP in GxzyCTF 2020
HNP问题，给出bs和results的低16位rs。
下面为了易于区分变量，以A、B、b、x命名，其中b是B的低位，已知A和b。
\(B_i \equiv A_i x \mod{p} \\ 2^{16} k_i + b_i \equiv A_i x \mod{p} \\ 2^{16} k_i \equiv A_i x - b_i \mod{p} \\ k_i \equiv 2^{-16} A_i x - 2^{-16} b_i \mod{p} \\ 令 \begin{cases} AA_i = 2^{-16} A_i \\ BB_i = -2^{-16} b_i \end{cases} \\ k_i \equiv AA_i \times x + BB_i \mod{p}\)
最终计算用的是LLL结果的第二行，原因如下
题目给出t=38组，并且每组给出的位数是低16bit，本地测试了一下，这样的数据量能计算出来的成功率不是很高，所以需要多试几次。
本地复现
RSA
from Crypto.Util.number import *
def pq_xor(x, tp, tq):
if len(x) == 0:
return
if ((tp+(1<<len(x))) * (tq+(1<<len(x)+16)) < N) or (tp * tq > N):
return
if N % (tp+1) == 0:
pq.append(tp+1)
return
if x[0] == '0':
pq_xor(x[1:], tp, tq) # p[]=0, q[]=0
pq_xor(x[1:], tp+(1<<len(x)-1), tq+(1<<len(x)-1+16)) # p[]=1, q[]=1
else:
pq_xor(x[1:], tp+(1<<len(x)-1), tq) # p[]=1, q[]=0
pq_xor(x[1:], tp, tq+(1<<len(x)-1+16)) # p[]=0, q[]=1
P = getPrime(512)
Q = getPrime(512)
N = P * Q
gift = int(bin(P ^ (Q >> 16))[2:][16:], 2)
print(f"N = {N}")
print(f"gift = {gift}")
for i in range(2**15, 2**16): #爆破gift的高16bit
gift_ = int(bin(i)[2:].zfill(16) + bin(gift)[2:].zfill(512-16), 2)
pq = []
x = bin(gift_)[2:].zfill(512)
if x[16] == '0':
tp = (gift_ >> 512-16 << 512-16) + (1 << 512-16-1) # p[16]=1
else:
tp = (gift_ >> 512-16 << 512-16) # p[16]=0
tq = 1 << 512-1 # q[0]=1
pq_xor(x[1+16:], tp, tq)
if pq != []:
if pq[0] == P or pq[0] == Q:
print(pq)
breakHNP
from sage.all import *
from Crypto.Util.number import *
Pbits = 512
kbits = 16
t = 38
P = getPrime(Pbits)
x = randrange(0, P)
A = [randrange(0, P) for _ in range(t)]
B = [(bi * x) % P for bi in A]
b = [ri & (2 ** kbits - 1) for ri in B]
print(f'P = {P}')
print(f'A = {A}')
print(f'b = {b}')
AA = [inverse_mod(2**kbits,P) * Ai for Ai in A]
BB = [inverse_mod(2**kbits,P) * (-bi) for bi in b]
M = Matrix(QQ, t+2, t+2)
for i in range(t):
M[i, i] = P
M[t, i] = AA[i]
M[t+1, i] = BB[i]
M[t, t] = 2**(Pbits-kbits)/P
M[t+1, t+1] = 2**(Pbits-kbits)
res = M.LLL()
B_high = [abs(int(i)) for i in res[1]]
B_ = [(B_high[i]<<kbits) + int(b[i]) for i in range(t)]
print(B == B_)
x_ = (B_[0] * inverse_mod(A[0],P)) % P
print(x == x_)转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 skatexu@qq.com