- vừa được xem lúc

Lattices in Cryptography - Mật mã học trên lưới (phần 2)

0 0 3

Người đăng: Viblo Security

Theo Viblo Asia

III. Một số bài toán trên lưới

1. Bài toán Knapsack và Subset Sum

Bài toán:

Tìm các giá trị x1,x2,...xnx_1,x_2,...x_n biết rằng:

  • xi{0,1}x_i \in \{0,1\}
  • A=xiaiA = \sum x_i a_i

Với A,aiA, a_i là các giá trị cho trước.

Bài toán này có hai cách gọi phổ biến:

  • Knapsack Problem (bài toán balo), xuất phát từ ý tưởng chọn một tập hợp con tối ưu từ các vật phẩm.
  • Subset Sum Problem (bài toán tổng tập con), tập trung vào việc tìm một tập con của các số aia_i sao cho tổng của chúng bằng AA.

Bài toán này liên quan mật thiết đến mật mã công khai Merkle-Damgård, trong đó bài toán subset sum được sử dụng làm cơ sở toán học để xây dựng các hệ thống mã hóa. Tuy nhiên, nếu bài toán subset sum có mật độ thấp (low-density subset sum), nó có thể bị phá vỡ bằng phương pháp Lattice Reduction, cụ thể là thuật toán LLL (Lenstra–Lenstra–Lovász).

Phân tích và ý tưởng giải

Bài toán có thể được đưa về bài toán trên mạng số nguyên (lattice). Cụ thể, ta dựng một ma trận BB có kích thước (n+1)×(n+1)(n+1)\times (n+1) như sau:

(2a1.a2..2.2an11.11A)\begin{pmatrix} 2 & & & & & a_1 \\ & . & & & & a_2\\ & & . & & & .\\ & & & 2 & & .\\ & & & & 2 & a_n\\ 1 & 1 & . & 1 & 1 & A \\ \end{pmatrix}

Xét các Vector theo hàng ta thấy v=(2x11,2x21,...,2xn1,0)Lv = (2x_1-1,2x_2-1,...,2x_n-1,0) \in \mathcal{L}

Vector này chỉ nhận giá trị ±1\pm 1 nên ta mong nó có thể đủ nhỏ để hoặc vv hoặc v-v lọt vào mạng LLL.

Mẫu giải bài toán này sử dụng Sagemath:

def solve(A, a: list): """ Return tuple (x1,x2,...xn) such x1*a1 + x2*a2 + ... + xn*an = A for xi in {0,1} """ # Generate Matrix n = len(a) list_mat = [] for i in range(0,n): v = [0,] * i + [2,] + [0,] * (n - 1 - i) + [a[i],] list_mat.append(v) v = [1,] * n + [A,] list_mat.append(v) B = matrix(ZZ, list_mat) B = B.LLL() # Find solution in B after LLL solution = [] for v in B: if v[n] == 0: x = [] for i in range(n): if v[i] != 1 and v[i] != -1: break x.append((v[i]+1) // 2) if len(x) == n: # Check solution t = 0 for i in range(0,n): t += x[i] * a[i] if t == A: solution.append(x) t = 0 for i in range(0, n): t += (1-x[i]) * a[i] x[i] = 1 - x[i] if t == A: solution.append(x) return solution 

Thuật toán giải

Xây dựng ma trận B\mathbf{B}:

  • Với mỗi aia_i, tạo một hàng trong ma trận vi=(0,,2,,0,ai)v_i = (0, \ldots, 2, \ldots, 0, a_i), với 22 nằm ở vị trí thứ ii.
  • Hàng cuối cùng là (1,1,,1,A)(1, 1, \ldots, 1, A).

Áp dụng thuật toán LLL trên ma trận:

  • Thuật toán LLL sẽ tìm các vector ngắn trong lattice.
  • Một vector ngắn có dạng (2x11,2x21,,2xn1,0)(2x_1-1, 2x_2-1, \ldots, 2x_n-1, 0) có thể được tìm ra.

Xác định nghiệm từ vector ngắn:

  • Từ vector ngắn v=(2x11,2x21,,2xn1,0)v = (2x_1-1, 2x_2-1, \ldots, 2x_n-1, 0), tính:

    xi=vi+12,i{1,,n}.x_i = \frac{v_i + 1}{2}, \forall i \in \{1, \ldots, n\}.

  • Kiểm tra tính chính xác của nghiệm:

    i=1nxiai=A.\sum_{i=1}^n x_i a_i = A.

Xét các hoán vị khác:

  • Có thể cần xem xét nghiệm đảo 1xi1 - x_i (vì xix_i thuộc {0,1}\{0, 1\}) để tìm tất cả các nghiệm.

Lưu ý

  • Thuật toán LLL hiệu quả cho bài toán mật độ thấp (low-density subset sum). Nếu mật độ cao, bài toán trở nên khó hơn và có thể yêu cầu các kỹ thuật khác.
  • SageMath hoặc các thư viện toán học tương tự như NumPy không tích hợp trực tiếp LLL, vì vậy cần cài đặt thư viện hoặc sử dụng SageMath.

Challenge CTF bạn có thể thử: Knapsack Ls Cookie Arena CTF 2022.

2. Approximate GCD

Bài toán:

Cho các số xi=qip+rix_i = q_i p + r_i, với rir_i nhỏ. Tìm ppước chung lớn nhất (GCD) của các mẫu, với sai số rir_i

Trong một số trường hợp r0=0r_0 = 0: Tức là x0=q0px_0 = q_0p, ta có thể nghĩ đến trường hợp RSA với 1 số thông tin bổ sung

Phân tích và ý tưởng

Với xi=qip+rx_i=q_ip+r, ta có thể viết:

q0xiqix0=q0riqir0q_0x_i-q_ix_0=q_0r_i-q_ir_0

Vế trái q0xiqix0q_0x_i-q_ix_0 phụ thuộc vào các xi,x0,qi,q0x_i, x_0, q_i, q_0, vế phải q0riqir0q_0r_i-q_ir_0 rất nhỏ vì ri,r0r_i, r_0 rất nhỏ.

Do đó, ta có thể tạo ra một vector ngắn trong một lattice (mạng số nguyên) chứa các phần tử của q0xiqix0q_0x_i-q_ix_0. Kỹ thuật lattice reduction (LLL) sẽ giúp chúng ta tìm các vector ngắn, từ đó suy ra pp.

Giới hạn rir_i bẳng cách đặt W=2λW = 2^\lambda thoả mãn riWr_i \leq WWW nhỏ nhất.

Tăng trọng số các sai số rir_i trong lattice để tối ưu tìm vector ngắn.

Xây dựng ma trận:

\begin{pmatrix} 2^{\lambda+1} & x_1 & x_2 & \ldots & x_n \ 0 & x_0 & 0 & \ldots & 0 \ 0 & 0 & x_0 & \ldots & 0 \ \vdots & \vdots & \vdots & \ddots & \vdots \ 0 & 0 & 0 & \ldots & x_0 \end{pmatrix}

Để ý rằng $$q_0x_i - q_ix_0 = q_0r_i - q_ir_0$$.

Nên shortvector là $$v = (2^{\lambda+1} q_0, q_0 r_1 - q_1 r_0, ...,q_0r_n - q_nr_0)$$ sẽ lọt vào mạng lưới Lattice, và để ý rằng q0xiqix0q_0x_i - q_ix_0 sẽ có giá trị rất nhỏ do $$ \frac{x_i}{x_0} \approx \frac{q_i}{q_0}$$.

Vì vậy ta có thể tìm ra giá trị q0q_0.

Bạn đọc có thể dựng lại Code để có thể hiểu hơn về bài toán này.

Một challenge CTF có thể thử: Sign trong ISITDTU CTF Quals 2024.

#!/usr/bin/env python3 import os from Crypto.Util.number import *
from Crypto.Signature import PKCS1_v1_5
from Crypto.PublicKey import RSA
from Crypto.Hash import SHA256 flag = b'ISITDTU{aaaaaaaaaaaaaaaaaaaaaaaaaa}'
flag = os.urandom(255 - len(flag)) + flag def genkey(e=11): while True: p = getPrime(1024) q = getPrime(1024) if GCD(p-1, e) == 1 and GCD(q-1, e) == 1: break n = p*q d = pow(e, -1, (p-1)*(q-1)) return RSA.construct((n, e, d)) def gensig(key: RSA.RsaKey) -> bytes: m = os.urandom(256) h = SHA256.new(m) s = PKCS1_v1_5.new(key).sign(h) ss = bytes_to_long(s) return s def getflagsig(key: RSA.RsaKey) -> bytes: return long_to_bytes(pow(bytes_to_long(flag), key.d, key.n)) key = genkey() while True: print( """=================
1. Generate random signature
2. Get flag signature
=================""" ) try: choice = int(input('> ')) if choice == 1: sig = gensig(key) print('sig =', sig.hex()) elif choice == 2: sig = getflagsig(key) print('sig =', sig.hex()) except Exception as e: print('huh') exit(-1)

Đoạn mã trên chứa một hệ RSA với:

  • n=p×qn=p\times q là module RSA
  • e=11e=11 là số mũ công khai
  • d=e1modϕ(n)d = e^{-1} \mod \phi(n) là số mũ bí mật

Trường hợp sai số nhỏ: Sai số rir_i có thể được mô hình hóa, và bài toán trở thành Approximate GCD. Sử dụng các chữ ký xi=qip+rx_i=q_ip+r, ta có thể xây dựng lattice để tìm 𝑝 p

Trong trường hợp r0=0r_0=0, tấn công có thể dễ dàng hơn nếu x0x_0 là một bội của pp.

3. Một số ứng dụng khác

Recovery a Polynomial from one solution in C\mathbb{C}

Như mình đã biết một đa thức bậc nn thì phải cần ít nhất n+1n+1 cặp giá trị (xi,f(xi))(x_i,f(x_i)) để khôi phục lại nó, hoặc là nn nghiệm phức của nó.

Như vậy nếu có 1 thì sao? LLL cho phép ta làm điều đó!

Challenge:

import os
import random
bits = 1111
C = ComplexField(bits)
P = PolynomialRing(C, names='x')
(x,) = P.gens()
key = os.urandom(256)
coeff = [int.from_bytes(key[i:i+16], 'little') for i in range(0, len(key), 16)]
f = sum([a * x ** i for i, a in enumerate(coeff)])
r = random.choice(f.roots())[0]
print(r) # Hint

Xét đa thức f(x)=a0+a1x+a2x2+...+anxnf(x) = a_0 + a_1x+ a_2x^2 + ... + a_nx^n có nghiệm rr.

Đặt rj=re(rj),ij=im(rj)r_j = re(r^j), i_j = im(r^j) với j=1,nj = \overline{1,n}.

Xét ma trận kích thức n+1×n+3n+1 \times n+3 sau:

(1011.i1r11.i2r21...1.in1rn1..1inrn)\begin{pmatrix} 1 & & & & & & 0 & 1 \\ & 1 & . & & & & i_1 & r_1\\ & & 1 & . & & & i_2 & r_2\\ & & & 1 &. & &. & .\\ & & & & 1 & . & i_{n-1} & r_{n-1}\\ .& & . & & & 1 & i_n & r_n \\ \end{pmatrix}

Ta thấy Vector (a0,a1,a2,...,an,ϵ0,ϵ1)(a_0, a_1 , a_2, ..., a_n , \epsilon_0, \epsilon_1) sẽ thuộc LLL nhưng mà LLL không dùng được trong số thực, vậy làm sao để fix.

Như ta đã biết thì số thực trong máy tính sẽ được lưu với độ chính xác nhất định, như ở code trên có lấy độ chính xác là 1111 bits, như vậy ta chỉ cần nhân với 211112^{1111} và làm tròn về số nguyên, khi dùng LLL thì Vector (a0,a1,a2,...,an,k0,k1)(a_0, a_1 , a_2, ..., a_n , k_0, k_1) cũng sẽ thuộc LLL với k0k_0, k1k_1 là 2 số gần 00.

round(2**1111 * i_j)

Như vậy ta có hàm giải bài này như sau:

def solve(n, bits, r): """ ::param n số bậc của đa thức ::param bits độ chính xác của số thực ::param r nghiệm của đa thức có thể ở dạng (re,im) return tuple của hệ số (a_0, a_1, ..., a_n) """ C = ComplexField(bits) r = C(r) real = [(r ** i)[0] for i in range(n + 1)] imag = [(r ** i)[1] for i in range(n + 1)] K = 2 ** (bits) M = matrix([ [round(K * x) for x in imag], [round(K * x) for x in real] ]) M = matrix.identity(n + 1).stack(M) M = M.T.LLL() coeff = M[0].list()[:n+1] if all(i < 0 for i in coeff): coeff = [-i for i in coeff] return coeff M = solve(15, 1111, r)
print(M)

Tài liệu tham khảo

Bình luận

Bài viết tương tự

- vừa được xem lúc

[Cryptopals] Set 8: Abstract Algebra (Challenge 63-66)

Đây là một bài trong series Cùng giải Cryptopals!.Các bạn nên tự làm hoặc vừa đọc vừa làm thay vì đọc lời giải trực tiếp. . Cẩn thận nhé, phần này rất rất dài, và khó hơn các phần trước rất nhiều.

0 0 53

- vừa được xem lúc

Get Paid with Crypto in your App // Coinbase Commerce Tutorial

Learn how to accept cryptocurrency payments, like $BTC or $ETH, in your webapp with Coinbase Commerce. https://fireship.io/lessons/crypto-payments-web-firebase. .

0 0 63

- vừa được xem lúc

Tản mạn về lỗ hổng trong smart contract của Fairmoon Token, các dấu hiệu bất thường và nguy cơ từ crypto

Hôm nay (19/05/2021) là một ngày đen tối đối với cộng đồng crypto khi:. .

0 0 73

- vừa được xem lúc

Tạo mạng P2P trên blockchain và phát hành tiền điện tử của riêng bạn

Chào các bạn, trong bài viết Tự tạo Blockchain trong 60 dòng code Javascript , mình đã hướng dẫn cách tạo blockchain trong 60 dòng Javascript. Trong bài viết này, mình sẽ tạo bộ phận quan trọng nhất c

0 0 60

- vừa được xem lúc

What happens if you hack 4.5 billion BTC? // The Code Report

Blockchain networks are virtually unhackable, but crypto exchanges not so much. In 2016, hackers stole 4.

0 0 35

- vừa được xem lúc

Web5... The Web3 Killer?

Web5 is a new decentralized web framework based on the Bitcoin Lightning Network designed to replace Web3. . Resources. .

0 0 41