糖醋小鸡块的blog
0%

NSSCTF-2nd-wp-crypto

发表于 更新于 分类于 Valine：

这次crypto题目总体难度不大，重点是对一些基础知识的理解运用。

EzRSA

题目:

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 *
from secret import flag
m = bytes_to_long(flag)
assert m.bit_length()<200
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 3
c = pow(m, e, n)
kbits = 103
m = (m >> kbits) << kbits
Mod = getPrime(1024)
hint1 = (2021-2023*m) % Mod
hint2 = pow(2, 2023, Mod)
print('n =',n)
print('c =',c)
print('hint1 =',hint1)
print('hint2 =',hint2)
'''
n = ...
c = ...
hint1 = ...
hint2 = ...
'''

有以下信息:

  • m.bit_length()<200 , 说明明文较小
  • kbits = 103 , m = (m >> kbits) << kbits , 隐藏了明文低位
  • hint1 = (2021-2023*m) % Mod
  • hint2 = pow(2, 2023, Mod)

种种都指向coppersmith , 首先看hint2，

利用同余关系,

得到Mod的k倍,因此可以利用k*Mod建立环，解出hint1中的小根m，解得m高位后已知高位攻击即可。


exp.ipynb:

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 *

n = ...
c = ...
hint1 = ...
hint2 = ...
e = 3
kM = 2**2023-hint2

PR.<x> = PolynomialRing(Zmod(kM))
f = 2023*x + hint1 - 2021
f = f.monic()
roots = f.small_roots(X=2^200,beta=0.4)
if roots:
    mhigh = roots[0]

mhigh = 1746716778150027565782467891299010283212636160
PR.<y> = PolynomialRing(Zmod(n))
f = (mhigh + y)^3 - c
f = f.monic()
roots = f.small_roots(X=2^104,beta=0.4)
if roots:
    m = mhigh + roots[0]
    print(m)
m = 1746716778150037336346788439252154990602710653
print(long_to_bytes(m))

得到flag:

NSSCTF{Rea1_Si9n3n}


(赛中的时候，这题解数比funnyencrypt还多，当时就感觉有点诡异。赛后才发现因为明密文都很小，所以直接开三次根就可以了。。)




FunnyEncrypt

题目:

1
2
3
4
5
6
7
8
✧✡✭
✡✮ ✣✴✯ ✤✶✬✬✱ ✬✤ ✱✦✢✥✮✯✧✧, ✴✬✷✯ ✡✧ ✣✴✯ ✶✡✰✴✣. ✡✣ ❂✢✡✮✰✧ ✩✬✸✤✬✢✣, ✤✦✡✣✴, ✦✮✱ ✩✬✮✤✡✱✯✮✩✯. ✡✣ ✰✡✲✯✧ ✳✧ ✰✳✡✱✦✮✩✯ ★✴✯✮ ★✯ ✦✢✯ ✶✬✧✣, ✦✮✱ ✰✡✲✯✧ ✧✳✷✷✬✢✣ ★✴✯✮ ★✯ ✦✢✯ ✦✤✢✦✡✱. ✦✮✱ ✣✴✯ ✸✬✸✯✮✣ ★✯ ✰✡✲✯ ✳✷ ✴✬✷✯, ★✯ ✰✡✲✯ ✳✷ ✬✳✢ ✶✡✲✯✧. ✣✴✯ ★✬✢✶✱ ★✯ ✶✡✲✯ ✡✮ ✡✧ ✱✡✧✡✮✣✯✰✢✦✣✡✮✰ ✡✮✣✬ ✦ ✷✶✦✩✯ ✬✤ ✸✦✶✡✩✯ ✦✮✱ ✴✦✣✢✯✱, ★✴✯✢✯ ★✯ ✮✯✯✱ ✴✬✷✯ ✦✮✱ ✤✡✮✱ ✡✣ ✴✦✢✱✯✢. ✡✮ ✣✴✡✧ ★✬✢✶✱ ✬✤ ✤✯✦✢, ✴✬✷✯ ✣✬ ✤✡✮✱ ❂✯✣✣✯✢, ❂✳✣ ✯✦✧✡✯✢ ✧✦✡✱ ✣✴✦✮ ✱✬✮✯, ✣✴✯ ✸✬✢✯ ✸✯✦✮✡✮✰✤✳✶ ✶✡✤✯ ✬✤ ✤✦✡✣✴ ★✡✶✶ ✸✦✥✯ ✶✡✤✯ ✸✯✦✮✡✮✰✤✳✶.
✧✬✸✯✣✡✸✯✧ ★✯ ✣✴✡✮✥ ✬✤ ✱✢✯✦✸✧ ✦✧ ✤✦✮✣✦✧✡✯✧ - ✡✣'✧ ✯✦✧✵ ✣✬ ✱✬ ★✴✯✮ ✵✬✳ ✴✦✲✯ ✸✬✮✯✵, ✢✯✮✣, ✦✮✱ ★✬✢✥. ❂✳✣ ✵✬✳ ✩✦✮'✣ ✷✢✯✷✦✢✯ ✵✬✳✢✧✯✶✤ ✦✮✱ ✫✳✸✷ ✬✤✤ ✣✴✯ ✩✶✡✤✤: ✵✬✳ ✧✴✬✳✶✱ ✰✢✬★ ✵✬✳✢ ★✡✮✰✧ ✤✡✢✧✣. ✦ ✶✡✣✣✶✯ ❂✡✣ ✣✬★✦✢✱ ✣✴✯ ✱✢✯✦✸. ✧✣✯✷ ❂✵ ✧✣✯✷. ✣✦✥✯ ✦ ✧✣✯✷ ✤✬✢★✦✢✱. ✦✤✣✯✢ ✦✶✶, ✡✣'✧ ✵✬✳✢ ✸✡✧✧✡✬✮.
✥✯✯✷ ✤✦✡✣✴ ✦✮✱ ✴✬✷✯ ✤✬✢ ✣✴✯ ✤✳✣✳✢✯. ✸✦✥✯ ✵✬✳✢ ✸✬✧✣ ✧✡✮✩✯✢✯ ✱✢✯✦✸✧, ✦✮✱ ★✴✯✮ ✣✴✯ ✬✷✷✬✢✣✳✮✡✣✡✯✧ ✩✬✸✯, ✣✴✯✵ ★✡✶✶ ✤✡✰✴✣ ✤✬✢ ✣✴✯✸. ✡✣ ✸✦✵ ✣✦✥✯ ✦ ✧✯✦✧✬✮ ✬✢ ✸✬✢✯, ❂✳✣ ✣✴✯ ✯✮✱✡✮✰ ★✡✶✶ ✮✬✣ ✩✴✦✮✰✯. ✦✸❂✡✣✡✬✮, ❂✯✧✣, ❂✯✩✬✸✯ ✦ ✢✯✦✶✡✣✵. ✦✮ ✳✮✩✯✢✣✦✡✮ ✤✳✣✳✢✯, ✬✮✶✵ ✬✮✯ ✧✣✯✷ ✦✣ ✦ ✣✡✸✯, ✣✴✯ ✴✬✷✯ ✩✦✮ ✢✯✦✶✡✪✯ ✣✴✯ ✱✢✯✦✸ ✬✤ ✣✴✯ ✴✡✰✴✯✧✣. ★✯ ✸✳✧✣ ✣✢✯✦✧✳✢✯ ✣✴✯ ✱✢✯✦✸, ✣✬ ✷✢✬✣✯✩✣ ✡✣ ✦ ✧✯✦✧✬✮, ✶✯✣ ✡✣ ✡✮ ✣✴✯ ✴✯✦✢✣ ❋✳✡✯✣✶✵ ✰✯✢✸✡✮✦✶.
✬✮✶✵ ★✴✯✮ ✵✬✳ ✳✮✱✯✢✧✣✦✮✱ ✣✴✯ ✣✢✳✯ ✸✯✦✮✡✮✰ ✬✤ ✶✡✤✯ ✩✦✮ ✵✬✳ ✶✡✲✯ ✣✢✳✶✵. ❂✡✣✣✯✢✧★✯✯✣ ✦✧ ✶✡✤✯ ✡✧, ✡✣'✧ ✧✣✡✶✶ ★✬✮✱✯✢✤✳✶, ✦✮✱ ✡✣'✧ ✤✦✧✩✡✮✦✣✡✮✰ ✯✲✯✮ ✡✮ ✣✢✦✰✯✱✵. ✡✤ ✵✬✳'✢✯ ✫✳✧✣ ✦✶✡✲✯, ✣✢✵ ✴✦✢✱✯✢ ✦✮✱ ✣✢✵ ✣✬ ✶✡✲✯ ★✬✮✱✯✢✤✳✶✶✵.
✡ ❂✯✶✡✯✲✯ ✣✴✯✢✯ ✡✧ ✦ ✷✯✢✧✬✮ ★✴✬ ❂✢✡✮✰✧ ✧✳✮✧✴✡✮✯ ✡✮✣✬ ✵✬✳✢ ✶✡✤✯. ✣✴✦✣ ✷✯✢✧✬✮ ✸✦✵ ✴✦✲✯ ✯✮✬✳✰✴ ✣✬ ✧✷✢✯✦✱ ✦✢✬✳✮✱. ❂✳✣ ✡✤ ✵✬✳ ✢✯✦✶✶✵ ✴✦✲✯ ✣✬ ★✦✡✣ ✤✬✢ ✧✬✸✯✬✮✯ ✣✬ ❂✢✡✮✰ ✵✬✳ ✣✴✯ ✧✳✮ ✦✮✱ ✰✡✲✯ ✵✬✳ ✦ ✰✬✬✱ ✤✯✯✶✡✮✰, ✣✴✯✮ ✵✬✳ ✸✦✵ ✴✦✲✯ ✣✬ ★✦✡✣ ✦ ✶✬✮✰ ✣✡✸✯.
✡✮ ✦ ★✬✢✱,✡ ✴✬✷✯ ✵✬✳ ★✡✶✶ ✶✡✥✯ ✩✢✵✷✣✬✰✢✦✷✴✵.✣✴✡✧ ✡✧ ✵✬✳✢ ✤✶✦✰:✮✧✧✩✣✤{✩✢✵✷✣✬_✡✧_✧✬_✡✮✣✯✢✯✧✣✡✮✰_★✴✵_✱✬✮'✣_✵✬✳_✫✬✡✮_✳✧}

见过的图形加密中并没有类似这个的，不过翻看一下马上就能发现文件尾部的这一串：

1
✮✧✧✩✣✤{✩✢✵✷✣✬_✡✧_✧✬_✡✮✣✯✢✯✧✣✡✮✰_★✴✵_✱✬✮'✣_✵✬✳_✫✬✡✮_✳✧}

前缀肯定是nssctf，是对的上的，猜测是简单的替换密码，写个脚本后交给quipqiup即可

exp.py:

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
c = """
✧✡✭
✡✮ ✣✴✯ ✤✶✬✬✱ ✬✤ ✱✦✢✥✮✯✧✧, ✴✬✷✯ ✡✧ ✣✴✯ ✶✡✰✴✣. ✡✣ ❂✢✡✮✰✧ ✩✬✸✤✬✢✣, ✤✦✡✣✴, ✦✮✱ ✩✬✮✤✡✱✯✮✩✯. ✡✣ ✰✡✲✯✧ ✳✧ ✰✳✡✱✦✮✩✯ ★✴✯✮ ★✯ ✦✢✯ ✶✬✧✣, ✦✮✱ ✰✡✲✯✧ ✧✳✷✷✬✢✣ ★✴✯✮ ★✯ ✦✢✯ ✦✤✢✦✡✱. ✦✮✱ ✣✴✯ ✸✬✸✯✮✣ ★✯ ✰✡✲✯ ✳✷ ✴✬✷✯, ★✯ ✰✡✲✯ ✳✷ ✬✳✢ ✶✡✲✯✧. ✣✴✯ ★✬✢✶✱ ★✯ ✶✡✲✯ ✡✮ ✡✧ ✱✡✧✡✮✣✯✰✢✦✣✡✮✰ ✡✮✣✬ ✦ ✷✶✦✩✯ ✬✤ ✸✦✶✡✩✯ ✦✮✱ ✴✦✣✢✯✱, ★✴✯✢✯ ★✯ ✮✯✯✱ ✴✬✷✯ ✦✮✱ ✤✡✮✱ ✡✣ ✴✦✢✱✯✢. ✡✮ ✣✴✡✧ ★✬✢✶✱ ✬✤ ✤✯✦✢, ✴✬✷✯ ✣✬ ✤✡✮✱ ❂✯✣✣✯✢, ❂✳✣ ✯✦✧✡✯✢ ✧✦✡✱ ✣✴✦✮ ✱✬✮✯, ✣✴✯ ✸✬✢✯ ✸✯✦✮✡✮✰✤✳✶ ✶✡✤✯ ✬✤ ✤✦✡✣✴ ★✡✶✶ ✸✦✥✯ ✶✡✤✯ ✸✯✦✮✡✮✰✤✳✶.
✧✬✸✯✣✡✸✯✧ ★✯ ✣✴✡✮✥ ✬✤ ✱✢✯✦✸✧ ✦✧ ✤✦✮✣✦✧✡✯✧ - ✡✣'✧ ✯✦✧✵ ✣✬ ✱✬ ★✴✯✮ ✵✬✳ ✴✦✲✯ ✸✬✮✯✵, ✢✯✮✣, ✦✮✱ ★✬✢✥. ❂✳✣ ✵✬✳ ✩✦✮'✣ ✷✢✯✷✦✢✯ ✵✬✳✢✧✯✶✤ ✦✮✱ ✫✳✸✷ ✬✤✤ ✣✴✯ ✩✶✡✤✤: ✵✬✳ ✧✴✬✳✶✱ ✰✢✬★ ✵✬✳✢ ★✡✮✰✧ ✤✡✢✧✣. ✦ ✶✡✣✣✶✯ ❂✡✣ ✣✬★✦✢✱ ✣✴✯ ✱✢✯✦✸. ✧✣✯✷ ❂✵ ✧✣✯✷. ✣✦✥✯ ✦ ✧✣✯✷ ✤✬✢★✦✢✱. ✦✤✣✯✢ ✦✶✶, ✡✣'✧ ✵✬✳✢ ✸✡✧✧✡✬✮.
✥✯✯✷ ✤✦✡✣✴ ✦✮✱ ✴✬✷✯ ✤✬✢ ✣✴✯ ✤✳✣✳✢✯. ✸✦✥✯ ✵✬✳✢ ✸✬✧✣ ✧✡✮✩✯✢✯ ✱✢✯✦✸✧, ✦✮✱ ★✴✯✮ ✣✴✯ ✬✷✷✬✢✣✳✮✡✣✡✯✧ ✩✬✸✯, ✣✴✯✵ ★✡✶✶ ✤✡✰✴✣ ✤✬✢ ✣✴✯✸. ✡✣ ✸✦✵ ✣✦✥✯ ✦ ✧✯✦✧✬✮ ✬✢ ✸✬✢✯, ❂✳✣ ✣✴✯ ✯✮✱✡✮✰ ★✡✶✶ ✮✬✣ ✩✴✦✮✰✯. ✦✸❂✡✣✡✬✮, ❂✯✧✣, ❂✯✩✬✸✯ ✦ ✢✯✦✶✡✣✵. ✦✮ ✳✮✩✯✢✣✦✡✮ ✤✳✣✳✢✯, ✬✮✶✵ ✬✮✯ ✧✣✯✷ ✦✣ ✦ ✣✡✸✯, ✣✴✯ ✴✬✷✯ ✩✦✮ ✢✯✦✶✡✪✯ ✣✴✯ ✱✢✯✦✸ ✬✤ ✣✴✯ ✴✡✰✴✯✧✣. ★✯ ✸✳✧✣ ✣✢✯✦✧✳✢✯ ✣✴✯ ✱✢✯✦✸, ✣✬ ✷✢✬✣✯✩✣ ✡✣ ✦ ✧✯✦✧✬✮, ✶✯✣ ✡✣ ✡✮ ✣✴✯ ✴✯✦✢✣ ❋✳✡✯✣✶✵ ✰✯✢✸✡✮✦✶.
✬✮✶✵ ★✴✯✮ ✵✬✳ ✳✮✱✯✢✧✣✦✮✱ ✣✴✯ ✣✢✳✯ ✸✯✦✮✡✮✰ ✬✤ ✶✡✤✯ ✩✦✮ ✵✬✳ ✶✡✲✯ ✣✢✳✶✵. ❂✡✣✣✯✢✧★✯✯✣ ✦✧ ✶✡✤✯ ✡✧, ✡✣'✧ ✧✣✡✶✶ ★✬✮✱✯✢✤✳✶, ✦✮✱ ✡✣'✧ ✤✦✧✩✡✮✦✣✡✮✰ ✯✲✯✮ ✡✮ ✣✢✦✰✯✱✵. ✡✤ ✵✬✳'✢✯ ✫✳✧✣ ✦✶✡✲✯, ✣✢✵ ✴✦✢✱✯✢ ✦✮✱ ✣✢✵ ✣✬ ✶✡✲✯ ★✬✮✱✯✢✤✳✶✶✵.
✡ ❂✯✶✡✯✲✯ ✣✴✯✢✯ ✡✧ ✦ ✷✯✢✧✬✮ ★✴✬ ❂✢✡✮✰✧ ✧✳✮✧✴✡✮✯ ✡✮✣✬ ✵✬✳✢ ✶✡✤✯. ✣✴✦✣ ✷✯✢✧✬✮ ✸✦✵ ✴✦✲✯ ✯✮✬✳✰✴ ✣✬ ✧✷✢✯✦✱ ✦✢✬✳✮✱. ❂✳✣ ✡✤ ✵✬✳ ✢✯✦✶✶✵ ✴✦✲✯ ✣✬ ★✦✡✣ ✤✬✢ ✧✬✸✯✬✮✯ ✣✬ ❂✢✡✮✰ ✵✬✳ ✣✴✯ ✧✳✮ ✦✮✱ ✰✡✲✯ ✵✬✳ ✦ ✰✬✬✱ ✤✯✯✶✡✮✰, ✣✴✯✮ ✵✬✳ ✸✦✵ ✴✦✲✯ ✣✬ ★✦✡✣ ✦ ✶✬✮✰ ✣✡✸✯.
✡✮ ✦ ★✬✢✱,✡ ✴✬✷✯ ✵✬✳ ★✡✶✶ ✶✡✥✯ ✩✢✵✷✣✬✰✢✦✷✴✵.✣✴✡✧ ✡✧ ✵✬✳✢ ✤✶✦✰:✮✧✧✩✣✤{✩✢✵✷✣✬_✡✧_✧✬_✡✮✣✯✢✯✧✣✡✮✰_★✴✵_✱✬✮'✣_✵✬✳_✫✬✡✮_✳✧}
"""

table = "abcdefghijklmnopqrstuvwxyz{} _-,.':"
list1 = ['✧', '✡', '✭', '✮', '✣', '✴', '✯', '✤', '✶', '✬', '✱', '✦', '✢', '✥', '✷', '✰', '❂', '✩', '✸', '✲', '✳', '★', '✵', '✫', '✪', '❋'] 
print(len(list1))

cfinal = []

for i in range(len(c)):
    if(c[i] not in table):
        if(c[i] == "\n"):
            cfinal.append(c[i])
        else:
            ind = list1.index(c[i])
            cfinal.append(table[ind])
    else:
        cfinal.append(c[i])
print("".join(cfinal))

#quipqiup
"""
six
in the flood of darkness, hope is the light. it brings comfort, faith, and confidence. it gives us guidance when we are lost, and gives support when we are afraid. and the moment we give up hope, we give up our lives. the world we live in is disintegrating into a place of malice and hatred, where we need hope and find it harder. in this world of fear, hope to find better, but easier said than done, the more meaningful life of faith will make life meaningful.
sometimes we think of dreams as fantasies - it's easy to do when you have money, rent, and work. but you can't prepare yourself 
and jump off the cliff: you should grow your wings first. a little bit toward the dream. step by step. take a step forward. after all, it's your mission.
keep faith and hope for the future. make your most sincere dreams, and when the opportunities come, they will fight for them. it may take a season or more, but the ending will not change. ambition, best, become a reality. an uncertain future, only one step at a time, the hope can realize the dream of the highest. we must treasure the dream, to protect it a season, let it in the heart quietly germinal.
only when you understand the true meaning of life can you live truly. bittersweet as life is, it's still wonderful, and it's fascinating even in tragedy. if you're just alive, try harder and try to live wonderfully.
i believe there is a person who brings sunshine into your life. that person may have enough to spread around. but if you really 
have to wait for someone to bring you the sun and give you a good feeling, then you may have to wait a long time.
in a word,i hope you will like cryptography.this is your flag:nssctf{crypto_is_so_interesting_why_don't_you_join_us}
"""

得到flag:

NSSCTF{crypto_is_so_interesting_why_don't_you_join_us}

(前缀居然要大写，这就有点坑了。。)




Math

题目：

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
40
41
42
43
44
45
46
47
from secret import flag
from Crypto.Util.number import *
import gmpy2

length = len(flag)
flag1 = flag[:length//2]
flag2 = flag[length//2:]
e = 65537

m1 = bytes_to_long(flag1)
p = getPrime(512)
q = getPrime(512)
n = p*q
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)

p1 = gmpy2.invert(p,q)
q1 = gmpy2.invert(q,p)
c = pow(m1,e,n)

print("p1=",p1)
print("q1=",q1)
print("c=",c)
print("phi=",phi)

"""
p1= ...
q1= ...
c= ...
phi= ...
"""

m2 = bytes_to_long(flag2)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
c = pow(m2, e, n)
hint = pow(2023 * p + 114514, q, n)
print("n=",n)
print("c=",c)
print("hint=",hint)

"""
n= ...
c= ...
hint= ...
"""

题目将flag分为两部分分别进行加密，分开来说：

  • 第一部分

给了p关于q的逆元及q关于p的逆元，hitconctf 2019 quals出过这个题目，具体推导过程参考这一篇](https://aidaip.github.io/ctf/2019/10/16/HITCON-CTF-2019-Quals-Writeup.html))

  • 第二部分

已知：

这种题目显然是构造出p或q的倍数，从而与n求gcd得到分解的。对于这个等式，很容易就能想到利用同余性质先化为一下两个等式：

乍一看应该是第二个等式更加好用，因为可以利用费马小定理消去指数，变形为:

但是这里就卡壳了，因为即使利用同余性质把模等式转化为等式，得到的依然含有p，q两个因子，没有办法与n求gcd。

所以考虑利用另一个等式，由于指数q没有办法消掉了，所以只能利用二项式定理展开。又由于mod p的关系，模等式正好只剩下了最后一项，即：

怎么利用这个等式呢？这个时候需要敏锐一点察觉到费马小定理(也许刚刚拆分出来的另一个式子的变形就是给我们的提示)，由费马小定理我们知道：

把 $114514^q$ 看作a，就得到：

所以有：

也就是说，将$(hint - 114514^n)$与n求gcd，即可得到p，进而求解RSA


exp.py:

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
from Crypto.Util.number import *

#1
def gcd(a, b):
  while(b): 
    a,b = b, a % b 
  return a 

def mysqrt(d):
  st = 1
  en = 10**1300
  while st<=en:
    mid = (st+en)//2
    if mid*mid == d: return mid
    if mid*mid < d: st=mid+1
    else: en=mid-1
  return -1

def egcd(a1, a2):
    x1, x2 = 1, 0
    y1, y2 = 0, 1
    while a2:
        q = a1 // a2
        a1, a2 = a2, a1 - q * a2
        x1, x2 = x2, x1 - q * x2
        y1, y2 = y2, y1 - q * y2
    return (x1, y1, a1)

flag = ""
ipmq= ...
iqmp= ...
phi= ...
e = 65537
enc = ...
d = inverse(e,phi)
gg = gcd(iqmp-1,ipmq-1)

c = phi // gg
a = (ipmq-1)//gg
b = (iqmp-1)//gg
# p*a + q*b = c
pmod = inverse(a, b)*c%b
for j in range(100000):
    p = pmod + j*b
    if p > (1<<1024): break
    if not isPrime(p): continue
    q = (c-p*a)//b
    assert(p*a+q*b==c)
    if (iqmp*q-1)%p == 0 and (ipmq*p-1)%q == 0:
        M = pow(enc,d,p*q)
        flag += str(long_to_bytes(M))[2:-1]
        break

#2
n= ...
c= ...
hint= ...
h2 = pow(114514,n,n)
p = GCD(n,hint-h2)
q = n//p
phi = (p-1)*(q-1)
e = 65537
d = inverse(e,phi)
m = pow(c,d,n)
flag += str(long_to_bytes(m))[2:-1]

print(flag)

得到flag:

NSSCTF{e713afa4-fcd8-419f-a1a6-959449b4df5a}




LatticeLCG

题目：

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
40
41
42
43
44
from Crypto.Util.number import *

flag = b'NSSCTF{******************************}'

a = getPrime(512)
seed = getPrime(512)
b = bytes_to_long(flag)
n = getPrime(1024)

e1 = 2333
e2 = 23333
c1 = pow(a,e1,n)
c2 = pow(a,e2,n)

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

print("c1 = ",c1)
print("c2 = ",c2)
print("output1 = ",output[0])
print("output2 = ",output[1])


e = [getPrime(128) for _ in range(20)]
out = []
m = getPrime(64)

for i in e:
    out.append(pow(m,i,n))

print("e=",e)
print("out=",out)

"""
c1 = ...
c2 = ...
output1 = ...
output2 = ...
e= []
out= []

"""

卡了很久，搜了很多格相关问题也没有搜到类似的，打算放弃这个题去睡觉的时候，突然恍然大悟。这里好好阐述一下我的思路，希望能帮助到一些和我一样刚刚接触格的ctfer。

首先，题目很明显的分成了三个部分：

  • 共模攻击
  • LCG求参数
  • Lattice

首先要明确求解顺序。flag以LCG中参数b的形式存在，因此LCG应该是题目的最后一步。并且要想求解出这个LCG的b，是需要知道a与n的值的，在第一部共模攻击中显然是已知n求解a。所以就明确了如下的解题顺序：

  1. Lattice求解模数n
  2. 共模攻击求解a
  3. LCG恢复参数b，得到flag

后面两个步骤非常容易，主要问题就在第一步：为什么要利用格求解n？ 怎么用格求解n？下面是我对这个问题的分析：

先来看看给了些什么条件：一个64bit的小量m，依次产生20个128bit的素数对其进行类似RSA的加密，并且给了我们加密指数的列表以及密文的列表。题目满足两个经典条件：存在小量 ，提供多个方程组参数，这样的问题在很多crypto题目中都是用格方法求解的，所以要想到利用格方法(题目的名字虽然说得很明白，但是如果没有，看到这种形式也应该联想到这个方法)

注意到m不变，模数n也不变，同时加密指数互素，这其实很像共模攻击的情景，只是n未知。回想一下在已知模数n的情况下共模攻击的实施方法，不难产生下面这个解题思路：

取20个方程的前三个如下：

因为e1，e2互素，所以存在a，b，使得：

所以可以得到：

这有什么用呢？我们同样也对2、3两式，1、3两式进行这样的操作，结合上面这个式子能得到三组模等式：

1、2式作差，2、3式作差，就得到：

而现在等式左侧已经没有未知量了(a,b,c,d,f,g均能够通过扩展欧几里得求出)，那么就可以求解他们的gcd得到n。

可以说，想到这个思路的时候我为之一振，可惜实际操作的时候这个方法并不能实施，原因也很简单，我们进行的并非模幂运算，而是普通幂运算，并且a，b这些指数数量级很大(注意这一点)，所以是完全没有办法照这个思路解下去的。这时候我也没有想到怎么利用格，所以进度也停滞了，一卡卡到了晚上。

晚上我反复思考的时候，又想到了我刚刚说的那一点，也就是实施不了共模攻击的原因，在于指数的数量级很大，没有办法幂运算。我也突然联想到了Lattice中LLL算法的重要应用——求解最短向量。那么一切也就说得通了，之所以给20个素数作为加密指数，就是可以应用于格密码中，克服刚才共模攻击中两两组合时计算出的a，b过大的问题。所以构造格的思路就来了：

因为20个指数e均互素，所以一定存在a1，a2，a3…a20，使得

所以可以列出等式：

很明显，这个格符合我们的要求，我们只需要从规约出来的短向量中挑出两组，按理来说，我们只需要类似的进行刚才的共模攻击即可。

可是实际操作又遇到了问题，这样规约出来的向量组是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
[ 45 -58   5 -16  12  -7 -27  19   6  14  29 -23 -36  44 -15   1   8  14  -7  11  -9]
[-14 -27  20   6 -40  20 -34  -2 -16  51  35 -23 -51  13   3 -21   0  17  11  -7   1]
[ 15 -36 -21 -13   6  -7  -1 -59 -23  42 -33  15 -30  -4  39  26  41   1  19  10   9]
[-23   4  49 -19  22  -9  24 -20 -20   3 -24   4 -43 -86  40  44  -1  -1  26  25   1]
[ 72  15 -11 -19  26 -31 -56 -25   5  33 -27 -23  12  22  11  -1  21 -17  51 -31   9]
[-35 -73  -8  19 -29  23  -3  20 -10  18  46  29  -9  69 -30   9 -64  13  10 -26   3]
[ 20  46  12  -3  28  -1 -68  15   3 -21 -48 -20  43  54   9  14  -5   0 -44 -24   8]
[ 49   0 -10   0 -46 -47  24  -2  13  10  -3  48  43 -28  -3  53 -15  -6  31 -23  12]
[ -6   0   9  42 -49 -38   8  12   7  39  30 -26  18  37  28 -28   8   2 -67 -21 -15]
[-56  23  22  29  -7 -19  19  -8   6  35   4  -8  22  -2 -44 -69  16  -8  -7 -45  21]
[-21  16  34 -39  36   1  57 -30  -2  -2 -36  -9   9 -27   8 -31 -31  32  12  -2  15]
[ -9  -7   6  40  32 -49 -26 -60  17   0 -13   7  25  57 -19  28  -3 -34  11 -12 -17]
[-30 -13  28 -42   8 -46  56  33 -56 -40 -24   4  10  15  46  50 -13  18 -21  17  16]
[-17 -11  -5  29  14   6 -13   4  42 -69  30   9   3 -37   5   7 -17  50   6  14 -38]
[ 53 -12  16  36   1  38 -52  25 -10 -41  -3 -37   6 -12   1  -4 -25  41   5   1  29]
[ -3   1  36  22   7  -5 -10  15 -10 -27  35 -60 -36   9 -57  33 -21  43  28 -44   8]
[ 32 -26  18  -9  -5  37  -8   2 -36 -28  43  10 -32  37 -24 -70  22 -35  49  -2  31]
[-33  15 -25   1 -40   3  -2 -32  15   9 -20 -27 -27  35  26  -1 -45 -12  45  23  36]
[-17   0  18 -20 -75  -5  55  42  16   8 -45   5 -24 -20 -50 -11   0  27  40  18   8]
[ 11   5  16  37  -2  -6  28  19 -21   5  -8  63  -8 -21  22 -23 -57  13  -5  15 -39]

第一列并不是我们想要的1，说明第一列是1的向量对比起来长度并不小。再想一下规约的目的，其实很容易就能想通第一列是多少并不重要，重要的是短向量的第一列相同(这一点非常容易想通，没理解的话仔细想想)。而要让他们相同，最有效的办法就是让他们均为0，想到这一点后，就可以在格的第一列乘上一个大数K，从而有效的调整一下格，如下：

这样一来，最短向量的第一列就不太可能不是0了(因为会对应的扩大K倍，显著地使规约向量变长)，我测试出取100左右即可，然后就可以求解最大公约数(此时还需注意两点小问题：一是规约出的短向量有负数，普通幂运算中会变成分数形式，通分至等式右侧即可；二是求得的公约数仍有可能是k倍的n，需要去除一些小因子)，最终得到n。


recovern.ipynb:

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
e= []
c= []

#step1
L = Matrix(ZZ, 20, 21)
for i in range(20):
    L[i,0] = e[i]*1000
    L[i,i+1] = 1
L = L.LLL()

alist1 = L[0][1:]
k1nl = 1
k1nr = 1
for i in range(20):
    if(alist1[i]<0):
        k1nr *= c[i]**(-alist1[i])
    else:
        k1nl *= c[i]**alist1[i]
k1n = k1nl-k1nr

alist2 = L[1][1:]
k2nl = 1
k2nr = 1
for i in range(20):
    if(alist2[i]<0):
        k2nr *= c[i]**(-alist2[i])
    else:
        k2nl *= c[i]**alist2[i]
k2n = k2nl-k2nr

n = gcd(k1n,k2n)

for i in range(2,10000):
    while(n % i == 0):
        n //= i

#检查一下n的长度是否为1024bit
print(len(bin(n)[2:]))
print(n)

后两个问题也就迎刃而解，最终得到flag：

NSSCTF{407f8832-6ffd-43bf-91a0-6900758cdff7}




总结

总的说来，对格的应用还不够灵活，还需要加深学习。

如果各位有不懂的地方或者发现了文中的问题，欢迎联系我，一起学习进步。