Gröbner基学习

我是跟着这篇博客学习的

把Gröbner基当作一个求解同余方程组的工具

一般可以用 Ideal.groebner_basis() 来解方程组

先来看具体的实例

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

p, q = getPrime(256), getPrime(256)
N = p * q
m1 = bytes_to_long(b"flag{12345678901234567890")
m2 = bytes_to_long(b"1234567890123456789012345")
m3 = bytes_to_long(b"6789012345678901234567890}")
e = 17
c1 = pow(m1, e, N)
c2 = pow(m2, e, N)
c3 = pow(m3, e, N)
s = m1 + m2 + m3
print(c1, c2, c3, s)

在模N下我们四个多项式

这里我们分别令m1为x,m2为y,m3为z,那么就有 $$ \left\{\begin{matrix} c1 \equiv x^{e} \pmod{m} & & \\ c2 \equiv y^{e} \pmod{m} & & \\ c3 \equiv z^{e} \pmod{m}& & \\ s = x+y+z& & & \end{matrix}\right. $$ 只用函数来求即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N=6692434017773440901248121759230203884669652891236382545508663615676035479987773547505464584353329866914742957979141553622146733464850815080629365624379661

c1=6294223839685137499726737781983492967563396041579323354548108273486961766839855110958582837836573667831355607882147069375574615907174235819382393052064712

c2=2355259547993286540978061636880099825491329223751206565879912833948894372462090796183687409866004603490962605529353088987352747169970344471183426245997531

c3=2011974695677576957012977241403922796249826368393888262804878442982415978383853838832938995817328691364405808525857332470653202730633495810754380967508255

s= 88073004323587205189890331392766979758851902387842188382084578

e = 17

R = PolynomialRing(Zmod(N), 'x, y, z')

x, y, z = R.gens()

I = Ideal([x^e-c1,y^e-c2,z^e-c3,s-x-y-z])

for g in I.groebner_basis():

  print(g)

这样我们就会得到

1
2
3
x + 6692434017773440901248121759230203884669652891236382545508663615676035479987773547505464584352686945055967763051253384582848668908358844732787988168531933
y + 6692434017773440901248121759230203884669652891236382545508663615676035479987773547505464584353021058028913502500738301171768271035200132773757499925488856
z + 6692434017773440901248121759230203884669652891236382545508663615676035479987773547505464584266208593335760403195542643719056280692141565347500420397033616

此时我们求解的结果是模n下等于0的，也就是 x + a = 0 mod  n

y + b = 0 mod  n

z + c = 0 mod  n

我们直接取反后模n得到结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
N = 6692434017773440901248121759230203884669652891236382545508663615676035479987773547505464584353329866914742957979141553622146733464850815080629365624379661
a = 6692434017773440901248121759230203884669652891236382545508663615676035479987773547505464584352686945055967763051253384582848668908358844732787988168531933
b = 6692434017773440901248121759230203884669652891236382545508663615676035479987773547505464584353021058028913502500738301171768271035200132773757499925488856
c = 6692434017773440901248121759230203884669652891236382545508663615676035479987773547505464584266208593335760403195542643719056280692141565347500420397033616
s = 88073004323587205189890331392766979758851902387842188382084578

m1 = (-a) % N
m2 = (-b) % N
m3 = (-c) % N

print("m1 =", long_to_bytes(m1))
print("m2 =", long_to_bytes(m2))
print("m3 =", long_to_bytes(m3))



print("Sum:", m1 + m2 + m3)

LCG

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
**from** Crypto.Util.number **import** *
flag = b'Spirit{****************************************}'

plaintext = bytes_to_long(flag)
length = plaintext.bit_length()

a = getPrime(length)
b = getPrime(length)
n = getPrime(length)

seed = plaintext
output = []
for i in range(10):
    seed = (a*seed+b)%n
    output.append(seed)

print("output = ",output)
# output =  [9997297986272510947766344959498975323136012075787120721424325775003840341552673589487134830298427997676238039214108, 4943092972488023184271739094993470430272327679424224016751930100362045115374960494124801675393555642497051610643836, 6774612894247319645272578624765063875876643849415903973872536662648051668240882405640569448229188596797636795502471, 9334780454901460926052785252362305555845335155501888087843525321238695716687151256717815518958670595053951084051571, 2615136943375677027346821049033296095071476608523371102901038444464314877549948107134114941301290458464611872942706, 11755491858586722647182265446253701221615594136571038555321378377363341368427070357031882725576677912630050307145062, 7752070270905673490804344757589080653234375679657568428025599872155387643476306575613147681330227562712490805492345, 8402957532602451691327737154745340793606649602871190615837661809359377788072256203797817090151599031273142680590748, 2802440081918604590502596146113670094262600952020687184659605307695151120589816943051322503094363578916773414004662, 5627226318035765837286789021891141596394835871645925685252241680021740265826179768429792645576780380635014113687982]

这个LCG生成器，让我们可以得到同余数方程组 $$ \begin{array}{ll} X_{1} \equiv a X_{0}+b & \bmod n \\ X_{2} \equiv a X_{1}+b & \bmod n \\ X_{3} \equiv a X_{2}+b & \bmod n \\ ...\\ \end{array} $$ 只用Gröbner基来求

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
28
29
30
31
32
33
34
35
36
37
38
39
import gmpy2

from Crypto.Util.number import *

output =  [9997297986272510947766344959498975323136012075787120721424325775003840341552673589487134830298427997676238039214108, 4943092972488023184271739094993470430272327679424224016751930100362045115374960494124801675393555642497051610643836, 6774612894247319645272578624765063875876643849415903973872536662648051668240882405640569448229188596797636795502471, 9334780454901460926052785252362305555845335155501888087843525321238695716687151256717815518958670595053951084051571, 2615136943375677027346821049033296095071476608523371102901038444464314877549948107134114941301290458464611872942706, 11755491858586722647182265446253701221615594136571038555321378377363341368427070357031882725576677912630050307145062, 7752070270905673490804344757589080653234375679657568428025599872155387643476306575613147681330227562712490805492345, 8402957532602451691327737154745340793606649602871190615837661809359377788072256203797817090151599031273142680590748, 2802440081918604590502596146113670094262600952020687184659605307695151120589816943051322503094363578916773414004662, 5627226318035765837286789021891141596394835871645925685252241680021740265826179768429792645576780380635014113687982]

R.<a,b> = PolynomialRing(ZZ)

f1 = output[0]*a + b - output[1]

f2 = output[1]*a + b - output[2]

f3 = output[2]*a + b - output[3]

f4 = output[3]*a + b - output[4]

f5 = output[4]*a + b - output[5]

F = [f1,f2,f3,f4,f5]

ideal = Ideal(F)

# 计算Ideal的Gröbner基I

I = ideal.groebner_basis()

print(I)

res=[x.constant_coefficient() for x in I]

n = res[2]

a = -res[0]%n

b = -res[1]%n

flag = (output[0] - b) * gmpy2.invert(a,n) % n

print(long_to_bytes(flag))