sha & CTF记录

一个密码学菜狗

0%

格密码

发表于 分类于
本文字数： 4.6k 阅读时长 ≈ 5 分钟

格密码

一直想做一个整理，鸽了两个多月，考完试把之前鸽的补一下

格中的困难问题

SVP：最短向量问题

给定一个基为B的Lattice L(B)，找到一个这个基构成的格点Bx:x，使得这个点距离0坐标点的距离最近。

SVP的宽松版本：[公式]，即找到一个基构成的格点Bx:x，使得这个店距离原点的距离小于最短距离的[公式]倍即可。

CVP：最近向量问题

给定连续空间中任意的一个点t，找到距离这个点最近的格点Bx。

同理可得，我们也可以得到CVP的宽松版，即[公式]。

SIVP：最短独立向量问题

给定一个Lattice [公式]，找到[公式]个线性独立的向量[公式]并且这些向量的长度都要小于等于最长的最短向量[公式]。

和SVP与CVP问题一样，我们也可以给出SIVP问题的宽松版定义，即[公式]。

基于lattice的信息传输

首先，我们把需要传输的消息映射到Lattice中的一个点上，即Bx，然后把L和Bx发送出去。因为噪音，Bx会在L上产生偏移，首先我们需要求解SVP问题，寻找到L上的最短向量，并让其与噪音相比较，观察能否恢复出明文。然后若想恢复出明文，需要解决CVP问题，找到被噪声影响的密文的最近格点，一般来说就是映射到格上的明文。

LLL算法

施密特正交化可以让一组坏基变成一组垂直的好基，而LLL算法可以找到在正交化的基础上最短或者近似最短的正交基。

LWE问题：错误学习

先放一道题

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
#python2
from secret import *
import random

prime = 2141
print len(flag)
flag = map(ord, flag)
flag1 = flag[:21]
flag2 = flag[21:]
row = 64


def add(msg1, msg2):
    return [(x + y) % prime for x, y in zip(msg1, msg2)]


def multi(msg1, msg2):
    out = []
    for l in msg1:
        s = 0
        for x, y in zip(l, msg2):
            s += (x * y) % prime
            s %= prime
        out.append(s)
    return out


def genkey(leng):
    l = [[] for i in range(row)]
    for x in range(row):
        for i in range(leng):
            l[x].append(random.randint(0, 511))
    return l


key = genkey(len(flag1))
print key

cipher1 = multi(key, flag1)

print cipher1

cipher2 = multi(key, flag2)

noise = [random.randint(0, 6) for i in range(row)]
print add(noise, cipher2)

flag的前半部分为普通的矩阵相乘，后半部分在矩阵相乘的基础上加入了噪音。

首先如果噪音是0的话，相乘出的结果就是L上的一个格点。现在加入了噪音，我们得到的就是某个格点附近的向量。这时，我们只需要求解CVP问题即可求解LWE问题。同时，CVP问题可以被规约到SIVP问题上，也就是说LWE问题的困难度是基于最坏情况的SIVP困难度的。

给出解密脚本

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
# sage脚本 LWE

from sage.modules.free_module_integer import IntegerLattice
from random import randint
import sys
from itertools import starmap
from operator import mul

key = 
p=2141
b=
A=Matrix(Zmod(p),key)
print(A.solve_right(b))
def closest_vector(M, G, target):
    small = target
    for _ in range(1):
        for i in reversed(range(M.nrows())):
            c = ((small * G[i]) / (G[i] * G[i])).round()
            small -= M[i] * c
    return target - small

m = 64
n = 21
q = 2141

A_values = 

b_values = 
A = matrix(ZZ, m + n, m)
for i in range(m):
    A[i, i] = q
for x in range(m):
    for y in range(n):
        A[m + y, x] = A_values[x][y]
lattice = IntegerLattice(A, lll_reduce=True)
print("LLL done")
gram = lattice.reduced_basis.gram_schmidt()[0]
target = vector(ZZ, b_values)
res = closest_vector(lattice.reduced_basis, gram, target)
print("Closest Vector: {}".format(res))

R = IntegerModRing(q)
M = Matrix(R, A_values)
ingredients = M.solve_right(res)
print("Ingredients: {}".format(ingredients))

NTRU加密

NTRU的本质就是SVP问题。实际上，LLL算法及其变种算法是目前已知在较低维度的lattice中求解SVP的最好的算法，但是在较高维度中就比较乏力。

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

d = 1888131080991802984469142252767428996708357845414525789382920257253450734136628648374571804259719424143388465346476293366644738737089607039465127514487405
p = 30611187447617951438057661643828594439836168499045103637492727875883545693704706710809270955729333435251594169116242188128775616562859932991842965711916421973513501170770682029019363173114263880664543027598219327851802812372758784840490412167556903172872555298867886904331797406762790534760341763270179874103596315439602969532398796744300268959212967152977297923303435136058320818336169166426865495487391347983169818270302355278949814298699167819318471127268309841253880404251042151162557234493453591687370817297674493012095163546638810088146738185919186385185115618449986759562697777952684453338987559120695742612663
h = 21312401103364823065661625965265254047976261102113426643161584691333735528853578330462720782012571325209425607725450902072660790420041271498835143983658324491397948972480792470439905794590608772344151134928174674417907495690758864900707486731428987072095395641677518641643685295486795802883828831926635233976602465690044844008674887604376578289424972631509896184649710918327894604786477135136421222185152303050748164371324119467682895596417745201794158939881061666663709040766320031697689020600295103351632352583239176099726804730980876514993290370570966082812844360442005544939574202193639394320702060361753336559136
c = 16940539604003327722979410435578617956215682038759397881493708848549559668095838737615772551889674113155566943460688615187510308352387746131182860772735244685105354949311113745596385193812888514879929848085807780411336350803009420541916609478955298130063431885517727744668841197297817243205861167004168641880226875601283896199831113765890902106375084917385016349416483298441391462272070565319424930392336694536562067484570233782710064495559877940944602837436374378241977922432719824129042239016560841938886647111460591440853620154778487323813228157104022518913321245126759601657046000849672318847957185592562785436558

m = matrix(ZZ, [[1, h], [0, p]])
f, g = m.LLL()[0]
print(f, g)
a = f*c % p % g
m = a * inverse_mod(f, g) % g
assert m == d
print(long_to_bytes(m))

在格基[1,h]和[0,p]上，[f,g]是其中的最短向量。通过LLL算法求解出f,g后，通过一系列计算可得m。