EN | ZH

# CVP¶

CVP是Lattice-based cryptography中尤为重要的一个问题。

## Algorithms¶

### Babai's nearest plane algorithm¶

• 近似因子为$\gamma = 2^{\frac{n}{2}}$

• 其中$c_j$为Gram-schmidt正交化中的系数取整，也即$proj_{b_{j}}(b)$的取整。

### Babai’s Rounding Technique¶

N = rank(B), w = target
- B' = LLL(B)
- Find a linear combination [l_0, ... l_N] such that w = sum(l_i * b'_i).
* (b'_i is the i-th vector in the LLL-reduced basis B')
- Round each l_i to it's closest integer l'_i.
- Result v = sum(l'_i * b'_i)

## 相关内容¶

### Hidden number problem¶

HNP的定义如下：

• $MSB_{l,p}(x)$表示任一满足 $\lvert (x \mod p) - u \rvert \le \frac{p}{2^{l+1}}$ 的整数 $u$，近似为取$x \mod p$$l$个最高有效位。

$\left[ \begin{matrix} p & 0 & \dots & 0 & 0 \\ 0 & p & \ddots & \vdots & \vdots \\ \vdots & \ddots & \ddots & 0 & \vdots \\ 0 & 0 & \dots & p & 0 \\ t_1 & t_2 & \dots & t_{n} & \frac{1}{2^{l+1}} \end{matrix} \right]$

### BCTF 2018 - guess_number¶

import random, sys
from flag import FLAG
import gmpy2

def msb(k, x, p):
delta = p >> (k + 1)
ui = random.randint(x - delta, x + delta)
return ui

def main():
p = gmpy2.next_prime(2**160)
for _ in range(5):
alpha = random.randint(1, p - 1)
# print(alpha)
t = []
u = []
k = 10
for i in range(22):
t.append(random.randint(1, p - 1))
u.append(msb(k, alpha * t[i] % p, p))
print(str(t))
print(str(u))
guess = raw_input('Input your guess number: ')
guess = int(guess)
if guess != alpha:
exit(0)

if __name__ == "__main__":
main()
print(FLAG)

import socket
import ast
import telnetlib

#HOST, PORT = 'localhost', 9999
HOST, PORT = '60.205.223.220', 9999

s = socket.socket()
s.connect((HOST, PORT))
f = s.makefile('rw', 0)

def recv_until(f, delim='\n'):
buf = ''
while not buf.endswith(delim):
return buf

p = 1461501637330902918203684832716283019655932542983
k = 10

def solve_hnp(t, u):
# http://www.isg.rhul.ac.uk/~sdg/igor-slides.pdf
M = Matrix(RationalField(), 23, 23)
for i in xrange(22):
M[i, i] = p
M[22, i] = t[i]

M[22, 22] = 1 / (2 ** (k + 1))

def babai(A, w):
A = A.LLL(delta=0.75)
G = A.gram_schmidt()[0]
t = w
for i in reversed(range(A.nrows())):
c = ((t * G[i]) / (G[i] * G[i])).round()
t -= A[i] * c
return w - t

closest = babai(M, vector(u + [0]))
return (closest[-1] * (2 ** (k + 1))) % p

for i in xrange(5):