格密码入门刷题

(Updated: )

入门题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import gmpy2
from secret import flag
from Crypto.Util.number import *

f = bytes_to_long(flag)
p = getPrime(512)
g = getPrime(128)
h = gmpy2.invert(f+20192020202120222023, p) * g % p

print('h =', h)
print('p =', p)
"""
h = 2230300126583677861466927910427460605336142000604400796769019169330805327830058127399640469637301157563524664730082687590109425103649095203274991089542329
p = 6950733137747588463708927295050453925761832477377823596882238234496472403054344156839969133381577140118982692621000380716326275220824006196311323447685281
"""

已知我们有 f′ = f + 20192020202120222023 h = f′−1 ⋅ g (mod  P) ∴ hf′ = g (mod  P) ∴ g = hf′ − kP 构造格 然后这里用Hermite定理检验一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import gmpy2
from Crypto.Util.number import *

m = b'testdemo143322333333115343444444'#猜测的flag长度，一般都是32位
print('flag:',len(m))
f = bytes_to_long(m)
print(f.bit_length()) #flag长度

b = 2**128
print('系数长',b.bit_length())#配平系数

p = getPrime(512)
high_len = gmpy2.iroot(2 * p, 2)[0]
print('Hermite定理上限长度',high_len.bit_length()) #Hermite定理上限

g = getPrime(128)
g = g
f = f + 20192020202120222023 
temp = gmpy2.iroot(f**2+(g)**2, 2)[0] 
print('实际配平数:',temp.bit_length())  #实际配平数
'''
flag: 32
255
系数长 129
Hermite定理上限长度 257
实际配平数: 255
'''

在没有配平的情况下基本上已经卡住上界了，所以这个格就可以得到我们想要的结果了

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *

h = 2230300126583677861466927910427460605336142000604400796769019169330805327830058127399640469637301157563524664730082687590109425103649095203274991089542329
p = 6950733137747588463708927295050453925761832477377823596882238234496472403054344156839969133381577140118982692621000380716326275220824006196311323447685281

G = Matrix(ZZ,[[1,h],[0,p]])#构造整数域矩阵
print(G.LLL())#LLL算法求格
f,g = G.LLL()[0]
f,g = abs(f),abs(g)#取绝对值

print(long_to_bytes(int(f-20192020202120222023)))

2024极客大挑战LLL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *

flag = b'******'
m = bytes_to_long(flag)

assert m.bit_length() == 327
p = getPrime(1024)
a = getPrime(1024)
c = getPrime(400)

b = (a*m + c) % p

print(f'a = {a}')
print(f'b = {b}')
print(f'p = {p}')

'''
a = 169790849804323540946197204708402762862586197604183102589270741859708550301920348112941305999764092197996929298474590062625556806793613268527763774013772685954699561684244945434843656515307801882995934869499880288594142919381501796488815033294127591623260894764750214588993456840404443515671353802614450411717
b = 87985708831523238980948938165414984318379459926002798504435964538203443877988599888615810231215118828138306895572062833107988965151522391460216837691927960249874511818878134399363147008042562222910234739940697553852540265617603482995091203105040187460485673579382171260197291783748886765929376179151804062085
p = 131724494512065658801039766546788821718063963144467818735768040631367069153816254855229655449559099188694403260044990366292026916085340250077198735215774149087025577263769846650728593180101073940507285459917860726551385227481715873503612683249433020201729190862430476054822102865441136763977415824331858801617
'''

这里我们有

b = am + c − kp c = b + kp − am

此时是不平衡的，所以需要我们自己配平一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import gmpy2
from Crypto.Util.number import *

m = b'testdemo143322333333115343444444444444444'
print('flag:',len(m))
f = bytes_to_long(m)
print(f.bit_length()) #flag长度

b = 2**180
print('系数长',b.bit_length())#配平系数

p = getPrime(1024)
high_len = gmpy2.iroot(3 * p *b, 3)[0]
print('Hermite定理上限长度',high_len.bit_length()) #Hermite定理上限

g = getPrime(400)
g = g
b = b
f = f
temp = gmpy2.iroot((g)**2+(f)**2+(b)**2, 2)[0] 
print('实际配平数:',temp.bit_length())  #实际配平数

测一测数据最后选择将左上角的1替换为2180后满足

exp

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *

a = 169790849804323540946197204708402762862586197604183102589270741859708550301920348112941305999764092197996929298474590062625556806793613268527763774013772685954699561684244945434843656515307801882995934869499880288594142919381501796488815033294127591623260894764750214588993456840404443515671353802614450411717
b = 87985708831523238980948938165414984318379459926002798504435964538203443877988599888615810231215118828138306895572062833107988965151522391460216837691927960249874511818878134399363147008042562222910234739940697553852540265617603482995091203105040187460485673579382171260197291783748886765929376179151804062085
p = 131724494512065658801039766546788821718063963144467818735768040631367069153816254855229655449559099188694403260044990366292026916085340250077198735215774149087025577263769846650728593180101073940507285459917860726551385227481715873503612683249433020201729190862430476054822102865441136763977415824331858801617


M = matrix([[2^180,0, b], [0,1, -a],[0,0,p]])
L = M.LLL()[0][1]

print(long_to_bytes(L))

NSS工坊格密码P1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *

p = getPrime(1024)

f = getPrime(400)
g = getPrime(512)
r = getPrime(400)

h = inverse(f, p) * g % p

m = b'******'
m = bytes_to_long(m)

c = (r*h + m) % p

print(f'p = {p}')
print(f'h = {h}')
print(f'c = {c}')

和上题相同，已知我们有 c = rh + m − kp m = c + kp − rh

然后就是配平问题，测一测往左上角丢2270(测数据测出来的，因为k和m的长度都未知）

1
2
3
4
5
6
7
8
from gmpy2 import*
from Crypto.Util.number import*
p = 
h = 
c = 
L=Matrix([[2**270,0,c],[0,1,p],[0,0,-h]])
m=L.LLL()[0][2]
print(long_to_bytes(m))

预期解 NTRU格 h = gf−1 (mod  p) c = r ⋅ h + m (mod  p) ∴ a = rg + mf = mf (mod  g) ∴ m = af−1 (mod  g) 所以需要求私钥(f, g)，这里我们有 h = gf−1 (mod  p)

f ⋅ h = g (mod  p) = g + kp

求解即可

1
2
3
4
5
6
7
8
from Crypto.Util.number import *
p = 
h = 
c = 
L = matrix([[1,h],[0,p]])
f,g = L.LLL()[0]
m = (f*c) % p  * inverse(f,g) % g
print(long_to_bytes(int(m)))

NSS工坊格密码P2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from Crypto.Util.number import *
import random
from gmpy2 import *

flag = bytes_to_long(b'******')
flag = bin(flag)[2:]
n = len(flag)

a = [random.randint(1, 4**n)]
s = a[0]
for i in range(1, n):
    a.append(random.randint(s+1, 4**(n+i)))
    s += a[i]

m = random.randint(a[-1] + 1, 2*a[-1])
w = random.randint(1, m)

assert gcd(w, m) == 1
b = [w*i % m for i in a]

c = 0
for i in range(len(b)):
    c = (c + b[i]*int(flag[i]))
with open('output', 'w+') as f:
    print(f'b = {b}', file=f)
    print(f'c = {c}', file=f)

超递增背包密码 解决 已知我们有 c ≡ b ⋅ flagbit (mod  m) 其实就是 全部移项到一边 构造格 所以我们就可以得到明文的flagbit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
b = 
c = 
n = len(b)
G = matrix(ZZ,n+1,n+1)

for i in range(n):
    G[i,i] = 1
    G[i,n] = b[i]

G[-1,-1] = -c
res = L.LLL()
for i in res:
    if len(set(i[:-1])) < 3:
        print("OK")
        print(i[:-1])
        flag = [str(i) for i in i[:-1]]
        break

from Crypto.Util.number import *
print(long_to_bytes(int("".join(flag),2)))

NSS工坊格密码P3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from Crypto.Util.number import *
import random

flag = b'******'
m = bytes_to_long(flag)

a = getPrime(1024)
b = getPrime(1536)

p = getPrime(512)
q = getPrime(512)
r = random.randint(2**14, 2**15)
assert ((p-r) * a + q) % b < 50

c = pow(m, 65537, p*q)

print(f'c = {c}')
print(f'a = {a}')
print(f'b = {b}')

'''
c = 
a = 
b = 
'''

已知我们有 设X < 50，X ≡ (p − r) ⋅ a + q (mod  b) 化简得X = (p − r) ⋅ a + q + k ⋅ b X − q = (p − r) ⋅ +k ⋅ b 构造格 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
c = 
a = 
b = 
e = 
L = matrix([[1,a],[0,b]])
pq = L.LLL()
pp = abs(pq[0][0]) 
qq = abs(pq[0][1]) 
from tqdm import trange
from Crypto.Util.number import *
for i in trange(2**14,2**15):
    for j in range(50): 
        p= pp + i
        q= qq + j
        phi = (p-1)*(q-1)
        if gcd(e, phi) != 1:
            continue
        n = p * q
        d= inverse(e, phi)
        m = pow(c, d, n)
        flag = long_to_bytes(m)
        if b'NSSCTF' in flag:
            print(flag)
            exit(0)

NSS工坊格密码P4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
from gmpy2 import *

flag = b'******'
flag = bytes_to_long(flag)

p = getPrime(1024)
r = getPrime(175)
a = inverse(r, p)
a = (a*flag) % p

print(f'a = {a}')
print(f'p = {p}')
'''
a = 
p = 
'''

a * r ≡ flag (mod  p) 构造格 

1
2
3
4
5
6
7
8
a = 
p = 
G=matrix([[p, 0], [a, 1]])
M=G.LLL()
m=abs(M[0,0])
from Crypto.Util.number import long_to_bytes
flag=long_to_bytes(m)
print(flag)

NSS工坊格密码P5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
from gmpy2 import *

flag = b'******'
m = bytes_to_long(flag)

assert m.bit_length() == 351
p = getPrime(1024)
b = getPrime(1024)
c = getPrime(400)

a = (b*m + c) % p

print(f'a = {a}')
print(f'b = {b}')
print(f'p = {p}')

'''
a = 92716521851427599147343828266552451834533034815416003395170301819889384044273026852184291232938197215198124164263722270347104189412921224361134013717269051168246275213624264313794650441268405062046423740836145678559969020294978939553573428334198212792931759368218132978344815862506799287082760307048309578592
b = 155530728639099361922541063573602659584927544589739208888076194504495146661257751801481540924821292656785953391450218803112838556107960071792826902126414012831375547340056667753587086997958522683688746248661290255381342148052513971774612583235459904652002495564523557637169529882928308821019659377248151898663
p = 100910862834849216140965884888425432690937357792742349763319405418823395997406883138893618605587754336982681610768197845792843123785451070312818388494074168909379627989079148880913190854232917854414913847526564520719350308494462584771237445179797367179905414074344416047541423116739621805238556845903951985783
'''

已知有 a = b ⋅ m + c − k ⋅ p c = −a + k ⋅ p − b ⋅ m

构造格 然后配平一下，往左上角丢180即可

1
2
3
4
5
6
7
8
9
a = 
b = 
p = 
G=matrix([[2^180, 0, a], [0, 1, b], [0, 0, p]])
M=G.LLL()
m=abs(M[0,1])
from Crypto.Util.number import long_to_bytes
flag=long_to_bytes(m)
print(flag)

NSS工坊格密码P6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *

flag = b'******'
flag = bytes_to_long(flag)
d = getPrime(400)

for i in range(4):
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    e = inverse(d, (p-1)*(q-1))
    c = pow(flag, e, n)
    print(f'e{i} =', e)
    print(f'n{i} =', n)
    print(f'c{i} =', c)

'''

'''

论文题