dssssa1
附件下载得到的encode脚本：
from Crypto.Util.number import *
import random
from gmpy2 import *
from hashlib import sha1
from secret import flag
m = bytes_to_long(flag)
q = getPrime(160)
while True:
p = getPrime(1024)
if (p-1) % q == 0:
break
h = random.randint(1, p-2)
g = powmod(h, (p-1)//q, p)
x = random.randint(1, q-1)
y = powmod(g, x, p)
k = random.randint(1, q-1)
h = bytes_to_long(sha1(flag).digest())
r = powmod(g, k, p) % q
s = (h + x*r) * invert(k, q) % q
c = powmod(m, x, p*q)
print(p, q, g, y, h, r, s, c, k, sep=',')
# p = 94515040220263097875872541668071470619435707358211716562219917331797767488022053087267566586709944785329708571559126640339609375166385904147189950035630910404534642622114804635856314928438531544553236458244225698694846607333226704467932079712515971615643868209281460429629880920550469170449935295454629293399
# q = 1001535514136994695529636128311212301250326767869
# g = 89288700225171676599759774184146798321191748739703246395529001979988401303800066044674449834184095667747898974375431700503800142840899194492182057885675147681600217979466719692984863330298347742657472936559041930489702116255999412448996714923112824244267910808782794442895518685864174817501040060680962447941
# y = 93887528695360292524813814240190328732283663255426806128197957720674496260060703595933676082882204724501085633424942582304707395449222043328895852812543576418567716781870179606049899540449729036771290550645770978667075821043797569255787271932556218014920373462882329802597672026806552417735660553144344650642
# h = 775593521305134275967472254218401264703166138817
# r = 75084117510316201869105133948164969652170742276
# s = 599417004454208825884865529281453774324093134827
# c = 94203926294365722030261882520165826558476099177297861176153811285238289485953276649563642144753132730431066372867407177248194182778827143183520415437355921352580608448713381897280433120409711633310458263502217605470824497215111936036532237050330222480782799188409969149722885261258984444311562364318406725475829089368796269160936194172040318140462371217663
# k = 208672457767877303895327222020982963931779123819
题给的变量很多，开始拿到这题的时候愣住了，但是不难看出来x是这题的关键，求出x即可正常解RSA。
赛后看了4xwi11佬的博客才发现，这题真的不难QAQ
告诉了
s = (h + x*r) * invert(k, q) % q
根据这一加密就不难推测出x
x = ((s * k -h)*invert(r,q))%q
呜呜呜，佬说简单推导都不算。
贴上exp：
from gmpy2 import *
from Crypto.Util.number import *
p = 94515040220263097875872541668071470619435707358211716562219917331797767488022053087267566586709944785329708571559126640339609375166385904147189950035630910404534642622114804635856314928438531544553236458244225698694846607333226704467932079712515971615643868209281460429629880920550469170449935295454629293399
q = 1001535514136994695529636128311212301250326767869
g = 89288700225171676599759774184146798321191748739703246395529001979988401303800066044674449834184095667747898974375431700503800142840899194492182057885675147681600217979466719692984863330298347742657472936559041930489702116255999412448996714923112824244267910808782794442895518685864174817501040060680962447941
y = 93887528695360292524813814240190328732283663255426806128197957720674496260060703595933676082882204724501085633424942582304707395449222043328895852812543576418567716781870179606049899540449729036771290550645770978667075821043797569255787271932556218014920373462882329802597672026806552417735660553144344650642
h = 775593521305134275967472254218401264703166138817
r = 75084117510316201869105133948164969652170742276
s = 599417004454208825884865529281453774324093134827
c = 94203926294365722030261882520165826558476099177297861176153811285238289485953276649563642144753132730431066372867407177248194182778827143183520415437355921352580608448713381897280433120409711633310458263502217605470824497215111936036532237050330222480782799188409969149722885261258984444311562364318406725475829089368796269160936194172040318140462371217663
k = 208672457767877303895327222020982963931779123819
n = p * q
phi = (p-1) * (q-1)
#s = (h + x*r) * invert(k, q) % q
x = ((s * k -h)*invert(r,q))%q
#print(x.bit_length())
d = invert(x,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
运行即可得到：
160
b'DASCTF{1d6f9460a596a4b38acc7263ea37b84d}'
easyNTRU
附件信息：
easyNTRU.sage：
from Crypto.Hash import SHA3_256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import flag
# parameters
N = 10
p = 3
q = 512
d = 3
assert q>(6*d+1)*p
R.<x> = ZZ[]
#d1 1s and #d2 -1s
def T(d1, d2):
assert N >= d1+d2
s = [1]*d1 + [-1]*d2 + [0]*(N-d1-d2)
shuffle(s)
return R(s)
def invertModPrime(f, p):
Rp = R.change_ring(Integers(p)).quotient(x^N-1)
return R(lift(1 / Rp(f)))
def convolution(f, g):
return (f*g) % (x^N-1)
def liftMod(f, q):
g = list(((f[i] + q//2) % q) - q//2 for i in range(N))
return R(g)
def polyMod(f, q):
g = [f[i]%q for i in range(N)]
return R(g)
def invertModPow2(f, q):
assert q.is_power_of(2)
g = invertModPrime(f,2)
while True:
r = liftMod(convolution(g,f),q)
if r == 1: return g
g = liftMod(convolution(g,2 - r),q)
def genMessage():
result = list(randrange(p) - 1 for j in range(N))
return R(result)
def genKey():
while True:
try:
f = T(d+1, d)
g = T(d, d)
Fp = polyMod(invertModPrime(f, p), p)
Fq = polyMod(invertModPow2(f, q), q)
break
except:
continue
h = polyMod(convolution(Fq, g), q)
return h, (f, g)
def encrypt(m, h):
e = liftMod(p*convolution(h, T(d, d)) + m, q)
return e
# Step 1
h, secret = genKey()
m = genMessage()
e = encrypt(m, h)
print('h = %s' % h)
print('e = %s' % e)
# Step 2
sha3 = SHA3_256.new()
sha3.update(bytes(str(m).encode('utf-8')))
key = sha3.digest()
cypher = AES.new(key, AES.MODE_ECB)
c = cypher.encrypt(pad(flag, 32))
print('c = %s' % c)
out:
h = 39*x^9 + 60*x^8 + 349*x^7 + 268*x^6 + 144*x^5 + 469*x^4 + 449*x^3 + 165*x^2 + 248*x + 369
e = -144*x^9 - 200*x^8 - 8*x^7 + 248*x^6 + 85*x^5 + 102*x^4 + 167*x^3 + 30*x^2 - 203*x - 78
c = b'\xb9W\x8c\x8b\x0cG\xde\x7fl\xf7\x03\xbb9m\x0c\xc4L\xfe\xe9Q\xad\xfd\xda!\x1a\xea@}U\x9ay4\x8a\xe3y\xdf\xd5BV\xa7\x06\xf9\x08\x96="f\xc1\x1b\xd7\xdb\xc1j\x82F\x0b\x16\x06\xbcJMB\xc8\x80'
学习4WXi11佬的NTRU系统：https://4xwi11.github.io/posts/a2b6ecd3/
exp:
#!/usr/bin/env sage
# -*- coding: utf-8 -*-
from Crypto.Hash import SHA3_256
from Crypto.Cipher import AES
import sys
from Crypto.Util.Padding import unpad
N = 10
p = 3
q = 512
d = 3
R.<x> = ZZ[]
c = b'\xb9W\x8c\x8b\x0cG\xde\x7fl\xf7\x03\xbb9m\x0c\xc4L\xfe\xe9Q\xad\xfd\xda!\x1a\xea@}U\x9ay4\x8a\xe3y\xdf\xd5BV\xa7\x06\xf9\x08\x96="f\xc1\x1b\xd7\xdb\xc1j\x82F\x0b\x16\x06\xbcJMB\xc8\x80'
table = [-1, 0, 1]
for i1 in table:
for i2 in table:
for i3 in table:
for i4 in table:
for i5 in table:
for i6 in table:
for i7 in table:
for i8 in table:
for i9 in table:
for i10 in table:
result = [i1, i2, i3, i4, i5, i6, i7, i8, i9, i10]
m = R(result)
sha3 = SHA3_256.new()
key = sha3.update(bytes(str(m).encode('utf-8'))).digest()
dypher = AES.new(key, AES.MODE_ECB)
try:
flag = unpad(dypher.decrypt(c), 32)
if flag.startswith(b'flag') or flag.startswith(b'DASCTF'):
print(flag)
sys.exit(0)
except:
pass
#b'DASCTF{b437acf4-aaf8-4f8f-ad84-5b1824f5af9c}'
运行得到flag：
本文参考4WXi11佬的省赛WP：https://4xwi11.github.io/posts/2e516684/