NSSCTF-Round#11-Crypto

Match

Created At : 2023-04-15 19:37

Count:845 Views 👀 :

ez_signin
ez_fac
NTR

忘了打这个比赛，佛了。题目还是得看看。

简单的不提了（指我这种菜鸡都能写的！！！）

from Crypto.Util.number import *
from secret import flag
p = getPrime(512)
q = getPrime(512)
while p < q:
    p = getPrime(512)
    q = getPrime(512)
n = p*q
e = 65536
m = bytes_to_long(flag)
num1 = (pow(p,e,n)-pow(q,e,n)) % n
num2 = pow(p-q,e,n)
c = pow(m,e,n)
print((pow(p,e,n)+pow(q,e,n)) % n)
print("num1=",num1)
print("num2=",num2)
print("n=",n)
print("c=",c)

两个关系：

$num_1 = ((p^e mod n)-(q^e mod n)) (mod n) = (p^e-q^e) mod n$

$num_2 = (p-q)^e mod n$

通过二项式定理化简第二个式子：

$num_2 = (p^e+q^e) mod n = p^e+q^e + kn$

第一个式子也可以写成：

$num_1 = p^e-q^e + kn$

（上面的一些等号不太规范。。。懒得改了，dddd）联立两式子得到：

$num_2 - num_1 = 2q^e$

故$q = gcd(num_2 - num_1,n)$

求出来发现$gcd(e,(p-1)*(q-1))==4$，我想着4不算大直接让e除上4，最后对m开4次方，但似乎这种方法不行。看了佬的wp，需要用到Rabin加密，之前写过Rabin的题，但没深入了解过，只知道e=2的情况。

此题中$e=65536=2^{16}$，进行16轮的Rabin求解：

num1= 44206098867921683934417336928985233025588668574343656117948540310110160027490983465415295177743546580694164644832046493330614725811380213519602775631490351664564138310053844939631114079065200612184580240438753793686596989511468932557217502300794435521797743787140897559589105842948072603012026732015159248161
num2= 13158554656623888251824342126888607296067884540206118434955743058207129333043696077566891529996443016879725943567450351660563839393324019719008854051662141369878552172587549722070113268453351045007269083352241057488869085531749477212341631467982511665359513684209818635259722897425450783278277211506057798953
n= 79495062269474059086610613577653461910599876749939821437096699098249180733016958347986361199400546365733098911391037456170325538796659332027061077293239358103033820573421427489291236167744598406251949902736785724133465146856453942849365511326183495398523343220715512931188931073129826736676070363871532058109
c= 78298975734843045778143611287902361805173888506727676771128811291335684212793777448528291817658781055139497267284952107724635579920126188479830442375942623845306975960733313270523277119682271415799574929673202157230774136292774956846148838799371832656652762824040928434071621787980715438170808189641131633842
e = 65536

q = gcd(num2 - num1,n)
p = n // q

def rabin_decrypt(c, p, q, e=2):
    n = p * q
    mp = pow(c, (p + 1) // 4, p)
    mq = pow(c, (q + 1) // 4, q)
    yp = invert(p, q)
    yq = invert(q, p)
    r = (yp * p * mq + yq * q * mp) % n
    rr = n - r
    s = (yp * p * mq - yq * q * mp) % n
    ss = n - s
    return (r, rr, s, ss)
for i in range(16):
    a,b,c,d=rabin_decrypt(c,p,q)
print(long_to_bytes(a))
print(long_to_bytes(b))
print(long_to_bytes(c))
print(long_to_bytes(d))

#正确flag：b'NSSCTF{6bcf361d-b371-4869-83f8-ac1682546933}'

不是很理解为何从Rabin入手

ez_fac

from Crypto.Util.number import *
import random
from secret import flag,a0,a1,b0,b1

p = getPrime(512)
q = getPrime(512)
e = getPrime(128)
n = p*q
assert pow(a0,2) + e * pow(b0,2) == n
assert pow(a1,2) + e * pow(b1,2) == n
m = bytes_to_long(flag)
c = pow(m,e,n)

print("c=",c)
print("n=",n)
print("a0=",a0)
print("a1=",a1)
print("b0=",b0)
print("b1=",b1)

有两个关系：

$a_0 ^ 2 + eb_0 ^ 2 = n$

$a_1 ^ 2 + eb_1 ^ 2 = n_0$

可通过两个等式求出e来：

e = (pow(a0,2)-pow(a1,2)) // (pow(b1,2)-pow(b0,2))
print(e)
#255348562315891975282864504628198394319

然后就不会了。

看了佬的wp，论文题。

9a5c8ce9f778b30adc150f375325ece0

c = 34007465638566836660852768374211870538357285529060206826620688555044780516477877596651414637089490522614456532732711803500304737160162560168303462221485961593760966240770414498297915175227814336224871400766371471776600674705757656616409870237891336752248110367865552469248343708419900511716030176178698949179
n = 70043427687738872803871163276488213173780425282753969243938124727004843810522473265066937344440899712569316720945145873584064860810161865485251816597432836666987134938760506657782143983431621481190009008491725207321741725979791393566155990005404328775785526238494554357279069151540867533082875900530405903003
a0 = 8369195163678456889416121467476480674288621867182572824570660596055739410903686466334448920102666056798356927389728982948229326705483052970212882852055482
a1 = 8369195163678456889416121462308686152524805984209312455308229689034789710117101859597220211456125364647704791637845189120538925088375209397006380815921158
b0 = 25500181489306553053743739056022091355379036380919737553326529889338409847082228856006303427136881468093863020843230477979
b1 = 31448594528370020763962343185054872105044827103889010592635556324009793301024988530934510929565983517651356856506719032859

e = 255348562315891975282864504628198394319
p = gcd(n,b1*a0-b0*a1)
q = n//p
d = invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))
#b'NSSCTF{ee7f5bf0-13b9-4a61-9b1b-243f2edef2e8}'

NTR

import gmpy2
# from flag import flag
from Crypto.Util.number import *
flag=b'asadsa'
def init():
    p = getPrime(2048)
    while True:
        x = getRandomNBitInteger(1024)
        y = getPrime(768)
        z = gmpy2.invert(x, p) * y % p
        return (p, x, y, z)
 
def encrypt(cipher, p, z):
    message = getRandomNBitInteger(768)
    r = getRandomNBitInteger(1024)
    c = (r * z + message) % p
    print((r*y+x*message) %p)
    return c
p,x,y,z=init()
c = encrypt(flag, p, z)
print('p=',p)
print('z=',z)
print('c=',c)

x = f，y = g，z = h。NTRU基础题型，最近学了下，套下公式：

h = ...
p = ...
c = ...


m = matrix([[1, h],[0, p]])

print(m.LLL())
f, g = m.LLL()[0][0],m.LLL()[0][1]
f = abs(f)
g = abs(g)
a = c*f % p % g
m = inverse_mod(f,g)*a % g
print(long_to_bytes(m))

NSSCTF Round#11 Basic 密码学专场 - 编程猎人 (programminghunter.com)

(4条消息) NSSCTF Round11 Crypto_无趣的浅的博客-CSDN博客 NSSCTF Round11 Crypto_无趣的浅的博客-CSDN博客](https://blog.csdn.net/qq_41626232/article/details/130031871))

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com

NSSCTF-Round#11-Crypto

ez_signin

ez_fac

NTR