Điểm:5

Một loạt các phản xạ tam giác có thể được sử dụng cho mật mã không?

lá cờ at

(Tôi đoán là không nhưng tại sao lại như vậy? Có cách nào để thực hiện được không?)

Cho tam giác đều T1 (có 3 đỉnh A,B,C nằm trong một trường hữu hạn $\mathbb F_N^D $) một tam giác đều T2 khác có thể được dựng bằng cách đối xứng một trong 3 đỉnh ở cạnh nằm giữa hai đỉnh còn lại. Điều này sẽ được lặp đi lặp lại nhiều lần.

Chỉ cho hai tam giác ngẫu nhiên T1 và T2 (và $\mathbb F_N^D $) một đối thủ có thể tính toán con đường ngắn nhất từ ​​​​T1 đến T2 không?
(Giả sử có một cách và modulo $N$ và kích thước $D$ được chọn đủ cao để kiểm tra tất cả tam giác sẽ mất nhiều thời gian)
Hay anh ta có thể làm điều đó (nhiều) nhanh hơn là chỉ áp dụng từng bước một?
(ví dụ như tại EC một máy phát điện $g$ không cần phải được áp dụng $m$ lần nếu chúng ta muốn tính toán $g^m$. Tôi đang tìm kiếm một kỹ thuật nhiều chiều không thể giảm thành vấn đề một chiều và cần được tính toán từng bước. 'Độ dài' của 'cách ngắn nhất' sẽ là số phép tính (tam giác) cần thiết)


Để phản chiếu điểm A tại cạnh BC, chúng tôi đang tìm kiếm một điểm $S$ và biến $r$ với $$S = B + r (C-B)$$ Để cho $v$ phương của cạnh BC: $$v = \vec{v} = C-B$$

Cái này $S$ sẽ cho phép chúng ta tính toán hướng từ $A$ đến $BC$ và với tính toán này, điểm được nhân đôi $A_M$ $$A_M = A + 2(S-A)$$

Để làm điều này $S-A$ cần phải trực giao với $v$. Vì vậy, sản phẩm vô hướng cần phải là 0: $$(S-A)' v = 0$$ $$(B+rv-A)' v = 0$$ $$(B-A)' v = -rv'v$$ $$r = \frac{(B-A)'v}{-(v'v)}$$

(giống như trong không gian euclide ngoại trừ trường hữu hạn $r$ cần phải tính toán với nghịch đảo $(-(v'v))^{-1}$ trên $N$)

Chỉnh sửa: fgrieu đã chỉ ra rằng cũng có một cách dễ dàng hơn nhiều để tính toán hình phản chiếu của một tam giác đều: $$A_M = A' = B+C-A$$ (chỉnh sửa kết thúc)


Tôi đã làm một số thử nghiệm cho 2 chiều và số nguyên tố $N$.
trường hữu hạn $\mathbb F_N^2 $ chỉ có thể tạo ra một tam giác đều nếu $N$ có một gốc cho $3$.

Một tam giác đều với độ dài cạnh cho trước có thể tạo ra $2N^2$ tam giác khác (mỗi tam giác có cùng độ dài cạnh). Mỗi chiều dài cạnh có hai tập hợp như vậy. Tổng cộng $2(N-1) (2N^2)$ mà là rời rạc với nhau.

(Tôi chỉ tính độ dài cạnh bình phương ở giữa hai điểm như trong không gian euclide)


Trong không gian euclide phản chiếu một tam giác xung quanh điểm ($C$) sẽ trông như thế này:
gương đầu tiên $A$ tại $CB$. Sau đó soi gương $B$ tại $CA_M$ và như thế. Nếu nó là một tam giác đều, nó sẽ khớp lại sau khi làm điều này 6 lần.

nhập mô tả hình ảnh ở đây

Trong trường hữu hạn $\mathbb F_{11}^2 $ nó có thể trông như thế này:
Nó cũng khớp sau khi làm điều này 6 lần (khoảng 1 điểm).
Làm nó chỉ theo một hướng nó sẽ khớp sau $2N$

nhập mô tả hình ảnh ở đây


Có một thuật toán mã hóa tương tự như thế này tồn tại?
Tại sao điều này không an toàn? Hoặc là nó? Nhiều kích thước hơn sẽ giúp ích?
Bất kỳ ý tưởng để làm cho nó an toàn hơn?

fgrieu avatar
lá cờ ng
Nếu một tam giác đều là tam giác có khoảng cách giữa các đỉnh bằng nhau, thì làm cách nào để bạn xác định khoảng cách trong trường hữu hạn tổng quát $\mathbb F_{p^k}$, hay bạn giới hạn ở $\mathbb F_p$ với số nguyên tố $p$? Ngoài ra, tôi không hiểu đại số của bạn cho gương $A'$ của điểm $A$ w.r.t. cạnh $BC$, kể cả $T$ là gì, và nếu/như thế nào đối xứng $A'$ của $A$ được xác định _uniquely_ (tôi hiểu điều đó trong trường $\mathbb R^d$, trong đó $A'=B +C-A$ ). Ngoài ra, giả thuyết cho rằng con đường ngắn nhất là một bài toán khó; và gặp bài toán khó là điều kiện cần chứ chưa đủ để xây dựng hệ thống mật mã.
J. Doe avatar
lá cờ at
@fgrieu cảm ơn vì gợi ý. Tôi đã làm một số cập nhật. Tôi chỉ sử dụng các số nguyên tố p cho N. Tôi đã thay đổi đại số thành một số phiên bản thay thế với một số chi tiết hơn. (T chỉ là chuyển vị của vectơ). A' nên được xác định duy nhất với điều này. Ít nhất tôi đã nghĩ như vậy (sẽ nghĩ lại về nó). Tôi không biết $A' = B + C -A$. Bạn có thể đưa ra ví dụ cho $\mathbb{R^d}$ với $A'$ không được xác định duy nhất không?
fgrieu avatar
lá cờ ng
Trong $\mathbb{R^d}$, bài toán có thể rút gọn về mặt phẳng được xác định bởi $ABC$, do đó rút gọn thành $\mathbb{R^2}$ bằng cách thay đổi cơ sở và $A'$ được xác định duy nhất và khớp với $A'=B+C-A$ hoặc có thể chính xác hơn $\vec{OA'}=\vec{OB}+\vec{OC}-\vec{OA}$. Trong ${\mathbb F_p}^d$, nếu chúng ta xác định $A'$ theo cùng phương trình đó, thì $A'$ cũng được xác định duy nhất. Tôi không chắc định nghĩa của bạn (đặc biệt là phần $T$) là gì khi $d\ne2$.
J. Doe avatar
lá cờ at
@fgrieu Tôi đã thay đổi phương trình. Không nên có $T$ nữa. Tôi nghĩ bạn có nghĩa là có một số ngoại lệ cho $A' = B + C -A$ không phải là duy nhất. Nếu đó không phải là trường hợp tôi có thể thay đổi phương trình thành như vậy. Sẽ dễ dàng hơn nhiều. Cũng kết nối tốt hơn với câu trả lời từ Fractalice.
Điểm:7
lá cờ in

Từ tam giác thứ hai, chúng ta có thể tìm thấy một tam giác lân cận có cùng hướng với tam giác thứ nhất (tất cả các điểm sẽ được dịch chuyển bởi cùng một vectơ). Vì vậy, chúng tôi quan tâm đến việc tìm một đường dẫn giữa một góc được phân biệt hoặc hai hình tam giác. Nó tạo thành một mạng hai chiều: ví dụ: $A_M$ Có thể đi tới $A$ hoặc đối tác cấp trên của nó (về phần tiếp theo của $BC$). Hai vectơ này tạo thành một cơ sở. Chúng ta cũng có thể bao gồm vectơ thứ ba (đi từ $A_M$ xuống qua hai tam giác): nó là "dư thừa" nhưng chúng ta cần nó vì chúng ta muốn tìm tọa độ ngắn và ba vectơ này bao phủ tất cả 6 hướng.

Bây giờ chúng ta chỉ muốn biểu diễn vectơ nối góc phân biệt của hai tam giác, trong cơ sở (dư thừa) của chúng ta. Điều này đã gợi ý về điểm yếu của vấn đề, vì chúng ta "chỉ" cần tìm 3 số (tọa độ trong cơ sở), tức là thứ tự các bước không quan trọng.

Điều này dẫn đến trường hợp CVP (vấn đề vectơ đóng), có thể được giải quyết bằng thuật toán của Babai và LLL (bạn sẽ có thêm một vài thứ nguyên cho tọa độ và thêm phần giảm mô đun vào mạng).

Đi vào các chiều cao hơn có thể làm cho LLL kém hiệu quả hơn. Tôi không biết chi tiết về điều đó, nhưng có vẻ như cơ sở mà chúng tôi có đã khá tốt, vì vậy LLL sẽ tìm thấy các đường dẫn được phân tách rất tốt.

J. Doe avatar
lá cờ at
Trời ơi làm sao tôi có thể bỏ lỡ điều đó, tôi cũng đã nghĩ một cái gì đó như thế (được dịch chuyển bởi cùng một vectơ) và thử nghiệm nó với một số ví dụ. Nó đã không thành công vào thời điểm đó. Tôi đã mắc lỗi khi so sánh các hình tam giác sau 3 lần phản chiếu nhưng để có được hình dạng giống nhau thì chỉ cần 2 lần phản chiếu. Cảm ơn bạn đã chỉ ra điều đó một lần nữa. rip ý tưởng. Tôi đoán cũng không tồn tại sự thay thế tương tự nhưng an toàn hơn nhiều.

Đă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.