LWE High Bits Message

python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# dimension
n = 64
# plaintext modulus
p = 257
# ciphertext modulus
q = 0x10001
# bound for error term
error_bound = int(floor((q/p)/2))
# message scaling factor
delta = int(round(q/p))


V = VectorSpace(GF(q), n)
S = V.random_element()
print("S = ", S, "\n")

m = ?

A = V.random_element()
error = randint(-error_bound, error_bound)
b = A * S + m * delta + error

print("A = ", A)
print("b = ", b)

缩放因子delta=round(q/p)

b=A * S+m * delta+e(mod q)

所以$m*{\delta}+e=b-A*S=t$

$m + \frac{e}{\delta} = \frac{t}{\delta}$

e在$(-\frac{\delta}{2},\frac{\delta}{2})$之间，所以相当于m+x,x∈$(-\frac{1}{2},\frac{1}{2})$所以四舍五入就是m

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

from sage.all import *
from Crypto.Util.number import*

S =  (55542, 19411, 34770, 6739, 63198, 63821, 5900, 32164, 51223, 38979, 24459, 10936, 17256, 20215, 35814, 42905, 53656, 17000, 1834, 51682, 43780, 22391, 33012, 61667, 37447, 16404, 58991, 61772, 44888, 43199, 32039, 26885, 17206, 62186, 58387, 57048, 38393, 29306, 58001, 57199, 33472, 56572, 53429, 62593, 14134, 40522, 25106, 34325, 37646, 43688, 14259, 24197, 33427, 43977, 18322, 38877, 55093, 12466, 16869, 25413, 54773, 59532, 62694, 13948) 

A =  (13759, 12750, 38163, 63722, 39130, 22935, 58866, 48803, 15933, 64995, 60517, 64302, 42432, 32000, 22058, 58123, 53993, 33790, 35783, 61333, 53431, 43016, 60795, 25781, 28091, 11212, 64592, 11385, 24690, 40658, 35307, 63583, 60365, 60359, 32568, 35417, 22078, 38207, 16331, 53636, 28734, 30436, 18170, 15939, 966, 48519, 41621, 36371, 41836, 4026, 33536, 57062, 52428, 59850, 476, 43354, 61614, 32243, 42518, 19733, 63464, 29357, 56039, 15013)
b =  44007
# dimension
n = 64
# plaintext modulus
p = 257
# ciphertext modulus
q = 0x10001


error_bound = int(floor((q/p)/2))
delta = int(round(q/p))
AS=sum(A[i]*S[i] for i in range(len(S)))%q
t = (b-AS)%q
m = int(round(t/delta))%p
print(m)

LWE Low Bits Message

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

# dimension
n = 64
# plaintext modulus
p = 257
# ciphertext modulus
q = 0x10001
# bound for error term
error_bound = int(floor((q/p)/2))


V = VectorSpace(GF(q), n)
S = V.random_element()
print("S = ", S, "\n")

m = ?

A = V.random_element()
error = randint(-error_bound, error_bound)
b = A * S + error * p + m

print("A = ", A)
print("b = ", b)

模q的值可能是：

  • x
  • x+q

范围在[0,q-1]，所以当x+q(即x<0)时，减一个q就可以复原，然后因为x=p*e+m，所以对m取模就可以得到m

python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

from sage.all import *
n = 64
# plaintext modulus
p = 257
# ciphertext modulus
q = 0x10001
# bound for error term
S =  (10082, 48747, 17960, 55638, 37012, 51876, 10128, 37750, 7608, 58952, 33296, 25463, 38900, 85, 65248, 42153, 44966, 31594, 40676, 56828, 30325, 38502, 65083, 7497, 2667, 54022, 24029, 32162, 57267, 12253, 6668, 5181, 14906, 51655, 61347, 4722, 22227, 23606, 63183, 52860, 1670, 31085, 42633, 47197, 7255, 16150, 9574, 62956, 26742, 57998, 49467, 31224, 60073, 12730, 41419, 41042, 53032, 16339, 32913, 16351, 34283, 47845, 3617, 35718) 

A =  (53751, 21252, 55954, 16345, 60990, 2822, 56279, 37048, 36153, 52141, 2121, 56565, 48112, 43755, 12951, 22539, 29478, 28421, 62175, 10265, 36378, 21305, 42402, 26359, 939, 60690, 1161, 65097, 34505, 19777, 29652, 42868, 49148, 38296, 31916, 25606, 18700, 12655, 35631, 64674, 29018, 21021, 14865, 40196, 14036, 40278, 37209, 35585, 34344, 33030, 285, 58536, 56121, 40899, 24262, 62326, 57433, 5765, 24456, 28859, 45170, 14799, 21567, 55484)
b =  11507

error_bound = int(floor((q/p)/2))
AS = sum(A[i]*S[i] for i in range(len(A)))%q
x = (b-AS)%q
if x > q//2:
    x -= q
m=int(x)%p
print(m)

Noise Free

python 
 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

from utils import listener
from sage.all import *
FLAG = b"crypto{????????????????????????}"
# dimension
n = 64
# plaintext modulus
p = 257
# ciphertext modulus
q = 0x10001

V = VectorSpace(GF(q), n)
S = V.random_element()

def encrypt(m):
    A = V.random_element()
    b = A * S + m
    return A, b
class Challenge:
    def __init__(self):
        self.before_input = "Would you like to encrypt your own message, or see an encryption of a character in the flag?\n"

    def challenge(self, your_input):
        if 'option' not in your_input:
            return {'error': 'You must specify an option'}

        if your_input['option'] == 'get_flag':
            if "index" not in your_input:
                return {"error": "You must provide an index"}
                self.exit = True

            index = int(your_input["index"])
            if index < 0 or index >= len(FLAG) :
                return {"error": f"index must be between 0 and {len(FLAG) - 1}"}
                self.exit = True

            A, b = encrypt(FLAG[index])
            return {"A": str(list(A)), "b": str(int(b))}

        elif your_input['option'] == 'encrypt':
            if "message" not in your_input:
                return {"error": "You must provide a message"}
                self.exit = True

            message = int(your_input["message"])
            if message < 0 or message >= p:
                return {"error": f"message must be between 0 and {p - 1}"}
                self.exit = True

            A, b = encrypt(message)
            return {"A": str(list(A)), "b": str(int(b))}

        return {'error': 'Unknown action'}


import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
listener.start_server(port=13411)

有两个选项：

  1. get_flag:可以得到flag字符的加密
  2. encrypt:可以加密自定义m

所以选encrypt，且令m=0，就可以得到式子b = A * S，这样就可以把S算出来、

再选get_flag，由于不知道flag的长度，所以进行100轮循环把flag遍历完

然后每次循环执行m=b-A * S（mod q）

python 
 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

from pwn import *
import json
from sage.all import *
io = remote("socket.cryptohack.org",13411)
io.recvline()
n = 64
p = 257
q = 0x10001
row = []
bs = []
for i in range(64):
    io.sendline(json.dumps({
        "option":"encrypt",
        "message":0
	}).encode())
    r = json.loads(io.recvline().decode())
    A = eval(r["A"])
    b = int(r["b"])
    row.append(A)
    bs.append(b)
A = matrix(GF(q),row)
b = vector(GF(q),bs)
S = A.solve_right(b)
flag = ""
for i in range(100):
    io.sendline(json.dumps({
        "option":"get_flag",
        "index":i
    }).encode())
    r = json.loads(io.recvline().decode())
    if "error" in r:
        break
    A = vector(GF(q),eval(r["A"]))
    b = int(r["b"])
    m = (b-A*S)%q
    flag += chr(int(m))
print(flag)

评论