Tham gia Đăng nhập
Điểm:0
arsenne lupulupin avatar Crypto

Giải quyết một bản ghi rời rạc với BsGs

lá cờ jo
arsenne lupulupin

Nếu chúng ta xem xét một nhóm G với mô đun p, thứ tự q với $p=2*q+1$, và máy phát điện $g=2$ ($p$, $q$ số nguyên tố khổng lồ), có cách nào để giải quyết vấn đề nhật ký rời rạc $ g^x = y $ đối với một y đã cho, sử dụng thuật toán bước khổng lồ cho từng bước nhỏ VÀ thực tế là $x$ có dạng: $ x = \sum_{i=0}^{10} \alpha_i * 2^i $ $:\alpha_i \in \mathbb{N} $ mà không yêu cầu lưu trữ tất cả các bước nhỏ trong một bảng băm, điều này là không thể với độ lớn của các con số $p$ và $q$.

chỉnh sửa: Các $ \alpha_i $ kẻ tấn công không biết các giá trị.

chỉnh sửa 2: $\alpha_i \in [0,\infty] $

96
0 + 0
poncho avatar
lá cờ my
poncho
Kẻ tấn công có biết các giá trị $\alpha_i$ không?
0
Hồi đáp
kelalaka avatar
lá cờ in
kelalaka
$\alpha_i \in \{0,1\}$ có thực sự không? $\mathbb{N} = \mathbb{Z}^+$ hay $\mathbb{N} = \mathbb{Z}^+ \cup \{0\}$, không có thỏa thuận chung về điều này.
1
Hồi đáp
Điểm:0
poncho avatar Crypto
lá cờ my
poncho

có cách nào để giải quyết vấn đề nhật ký rời rạc không $g^x=y$ cho một $y$ đã cho, sử dụng thuật toán bước khổng lồ baby step

Không có cách nào thực tế nếu $p, q$ lớn.

Thậm chí nếu $x$ được biết là ở dạng $ x = \sum_{i=0}^{10} \alpha_i * 2^i $ $:\alpha_i \in \mathbb{N} $ ?

Mọi tiềm năng $x$ có thể được thể hiện trong hình thức đó; xem xét $\alpha_1 = \alpha_2 = ... = \alpha_{10} = 0$ và $\alpha_{0} = x$. Do đó, biết rằng $x$ có thể diễn đạt ở dạng đó không cung cấp bất kỳ thông tin bổ sung nào; BsGs chỉ có thể sử dụng được nếu mô đun đủ nhỏ (và câu hỏi giả định là không)

0 + 0
Ievgeni avatar
lá cờ cn
Ievgeni
Không $x
0
Hồi đáp
poncho avatar
lá cờ my
poncho
@levgeni: nếu chúng ta đang nói về các giá trị mà **có thể** được thể hiện ở dạng đó, thì chúng ta có $x \ge 2047$ (và đó là với quy ước rằng $0 \not\in \mathbb{N}$; ngược lại , tất cả các giá trị $x$ có thể được biểu thị dưới dạng đó).
0
Hồi đáp
poncho avatar
lá cờ my
poncho
@levgeni: và, nếu $x
0
Hồi đáp
kelalaka avatar
lá cờ in
kelalaka
@poncho Tôi nghĩ levgeni lập luận rằng ngay cả khi $x>2046$, điều đó không có nghĩa là $x$ không nhỏ một cách tầm thường. Cái lớn là rõ ràng, tuy nhiên cái nhỏ cần một thước đo.
0
Hồi đáp
poncho avatar
lá cờ my
poncho
@kelalaka: Tôi không hiểu lập luận của bạn; nếu chúng tôi giải thích câu hỏi "DLog có thể giải được không nếu chúng tôi cho rằng số mũ là ngẫu nhiên, với điều kiện là có thể biểu thị được ở dạng đã cho?" Với sự hiểu biết đó, câu trả lời của tôi là chính xác - làm thế nào để bạn giải thích câu hỏi?
0
Hồi đáp
kelalaka avatar
lá cờ in
kelalaka
@poncho nếu $x$ nhỏ (không có số liệu ở đây) nhưng chúng tôi biết giới hạn, thì BsG có thể được tham số hóa để giải quyết nhanh hơn, phải không? Và một lần nữa, nếu $x$ nhỏ thì thực tế chúng tôi không cần BsG, chúng tôi có thể cưỡng bức nó giống như chúng tôi có thể cưỡng bức từ 1 đến $2^{48}$ để có được $x$'. Hoặc, bạn đang mặc nhiên giả định $x$ thống nhất ngẫu nhiên?
0
Hồi đáp
Ievgeni avatar
lá cờ cn
Ievgeni
@poncho Ok, tôi nghĩ $\alpha$ là bit. Tôi hơi lạc lõng với tất cả các chỉnh sửa. Tôi vẫn không hiểu tại sao bạn lại nói về $2046$. Tôi muốn xóa $-1$ của mình, nhưng tôi chỉ có thể xóa nếu bạn chỉnh sửa tin nhắn của mình.
0
Hồi đáp
poncho avatar
lá cờ my
poncho
@levgeni: nếu $0 \not\in \mathbb{N}$, thì $\sum_1^{10} 2^i\alpha_i$ tối thiểu có thể là năm 2046. Một số định nghĩa về $\mathbb{N}$ không bao gồm 0, những người khác làm.
0
Hồi đáp
Ievgeni avatar
lá cờ cn
Ievgeni
Nhưng tổng trong câu hỏi bắt đầu bằng 0, vậy nó phải là $2047$?
0
Hồi đáp
poncho avatar
lá cờ my
poncho
@levgeni: Tôi đang sử dụng $\alpha_0$ làm giá trị thay đổi và vì vậy chúng tôi thực sự có $x = \alpha_0 + 2046$ - $\alpha_0 = 0$ không được phép, vì vậy chúng tôi có $x > 2046$
0
Hồi đáp
Ievgeni avatar
lá cờ cn
Ievgeni
@Ievgeni: Được rồi, Thx vì lời giải thích. Tôi đã hiểu. Nhưng có vẻ như cuối cùng $alpha$ có thể bằng không.
0
Hồi đáp
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.