Cái nào nhỏ nhất, theo chu kỳ theo 3 hướng, cấu trúc nhất quán của các giá trị ngẫu nhiên có thể ẩn trong máy đối thủ? (một số so sánh)

Hay tổng quát hơn từng thành viên có thể là một phần của tối đa ba mặt phẳng euclide cục bộ 2D có 2 chiều khác nhau.

(mỗi mặt phẳng đó tuần hoàn theo hai hướng trực giao, giống như một hình xuyến)

Chỉ với một thành viên, nó có thể trông giống như một mạng nút:
(chỉ một nút với một số vùng lân cận được hiển thị ở đây. Những nút lân cận đó lại có những hàng xóm không được hiển thị ở đây)
(bên trái: 1 mặt phẳng, giao tuyến bên phải của 2 mặt phẳng)
giao tuyến của 3 mặt phẳng:

Mặc dù vậy, cần phải có một số cách xác định để ánh xạ vùng lân cận của nút thành đồ thị phẳng tại ba mặt phẳng euclide 2D đó (với mật độ nút không đổi). Vì vậy, các nút lân cận lân cận cũng có xu hướng là hàng xóm và không có $n$-tăng trưởng khu phố cần e.g. không gian hypebol để biểu diễn.
Bắt đầu từ một nút $n$ và (chủ yếu) theo một hướng tiến triển sẽ lại dẫn đến cùng một nút sau đó (trong trường hợp tốt nhất) $C_n$ các bước. Vì vậy, nó tuần hoàn với độ dài chu kỳ $C_n$. Trong trường hợp tốt nhất, điều này bằng nhau đối với tất cả các nút theo mọi hướng. Nhưng để ít nghiêm ngặt hơn, một số biến thể có thể xảy ra miễn là độ dài chu kỳ tương tự như các nút lân cận.

Mục đích:
Tìm một cấu trúc như vậy để giảm thiểu độ dài chu kỳ $C$ (tốt $\le 2^{50}$) và tổng số nút $N$ (trường hợp tốt nhất $N=C^3$ hoặc $\le 2^{150}$) trong khi vẫn cố gắng tính toán mối quan hệ giữa hai nút ngẫu nhiên ở mức khó nhất có thể (tốt nhất $\ge O(C^2)$ và $O(\sqrt[3]{N^2})$ hoặc bằng số $\ge 2^{100}$)

Chuyên dùng cho các phương pháp mật mã:

Theo như tôi biết trong mật mã học, chỉ có những cấu trúc chuyên biệt hơn hoặc tổng quát hơn một phần so với cấu trúc được mô tả ở trên.
Nếu ví dụ: số lượng hàng xóm từ một nút được đặt thành giá trị cố định là 6, chúng ta có cấu trúc như sau:
(trái: giao điểm của 3 mặt phẳng tại một nút/số, phải: mọi nút/số đều có cấu trúc này ở đây)

Điều này có thể đạt được với 3 máy phát điện và một $\bmod P$ như được liệt kê dưới đây.
Đối với mỗi loại, tôi sẽ thêm một số lý do tại sao nó không hoạt động và các chủ đề liên quan (của tôi) để biết thêm chi tiết.

So sánh với các phương pháp mật mã đã thử nghiệm:

1. ba máy phát điện $q,r,s$ với $\bmod P = 2\cdot Q \cdot R \cdot S +1$ và $q^Q \equiv r^R \equiv s^S \equiv 1 \bmod P$ $\văn bản{ } $[1]

   • $-$ $P$ cần phải rất lớn để tránh thừa số hóa $\gg 2^{150}$
   • $-$ với việc biết kích thước chu kỳ, nó có thể được giảm xuống thành một vấn đề dễ dàng hơn nhiều với Thuật toán PohligâHellman

2. Đường cong elip với 3 máy phát điện $F,G,H$ và với các giá trị này $i \cdot F + j \cdot G + k \cdot H$ [1] [2]

   • $-$ kích thước chu kỳ cho mỗi hướng là trên toàn bộ miền
   • $+$ chỉ cần số lượng tương đối nhỏ
   • $-$ nhưng vẫn là kích thước miền/chu kỳ của $2^{200}$ cần thiết (chỉ kích thước chu kỳ mục tiêu $2^{50}$)

3. AES hoặc mật mã khối tương tự:

   • $-$ được tách ra trong nhiều chu kỳ với kích thước không xác định, chỉ phân phối được biết [1]
   • $-$ một mỗi hướng? $\rightarrow $ miền của $2^{300}$ cần thiết và có thể được giảm xuống một vấn đề một chiều
   • $-$ nối 3 AES với một thành viên? $\rightarrow $ to lớn $n$-lân cận, tương tự như chỉ sử dụng các giá trị ngẫu nhiên $\rightarrow $ có thể tìm thấy kết quả khớp ở chế độ AES128 (chế độ ECB) xen kẽ sau $\approx {2^{64}}$ các bước tiến bộ [2]

4. trình tự 3 hướng $s_{ijk} = s_0^{\textstyle \beta^i\gamma^j\delta^k} \bmod (N=P\cdot Q)$ - khó giải vì $\phi(N)$ không biết

   • vì $N=(2\cdot p +1)\cdot (2\cdot q +1)$ với thị tộc. $\beta, \gamma, \delta$ rễ nguyên thủy của $p,q$ [1]
     • $+$ $O(\sqrt[2]{C^3})$ (theo như tôi biết)
     • $-$ nhưng chỉ khi $\phi(N)$ là không biết. Để đạt được $100$bảo mật -bit $N$ cần phải được xung quanh $2000$kích thước -bit và với cái này $p, q$ và kích thước chu kỳ cũng tăng lên
   • vì $N=(2\cdot p_s \cdot p_b +1)\cdot (2\cdot q_s \cdot q_b +1)$ dự kiến $\frac{(p_s-1)}{2}\cdot \frac{(q_s-1)}{2}$ với $\gcd(e,\phi(N)) \ne 1$ nhưng $e$ khó phân tích [2], $\beta,\gamma,\delta$ liên quan đến sức mạnh của $e$
     • $+$ $O(\sqrt[2]{C^3})$ (theo như tôi biết) nếu $C$ không xác định
     • $-$ gần như ngay lập tức nếu độ dài chu kỳ $C$ đã biết (rất dễ suy ra các giá trị đích). $C$ sẽ cần phải được $>2^{100}$

5. Phản xạ hình học trên trường hữu hạn (tam giác [1], tứ diện [2] - cả hai đều không có giải pháp) hoặc tổng quát hơn là một chuỗi phép nhân ma trận. để cho $n$-các vùng lân cận không phát triển quá nhanh, chúng cần bất biến theo thứ tự nhân của chúng. Vì vậy, chúng có thể được giảm xuống $A^iB^jC^k$ - nhưng cho đến nay tôi không thể tìm thấy bất kỳ ma trận nào như vậy cũng tạo ra $i,j,j$ khó xác định

   • $-$ hoặc là quá nhiều $n$-hàng xóm hoặc quá dễ dàng để tính toán các chỉ số

Câu hỏi: Nó có thể được thực hiện tốt hơn? có thể ít hơn $N=2^{200}$ các giá trị được phân phối dọc theo 3 chiều với kích thước chu kỳ nhỏ hơn $C=2^{65}$ mỗi khi tìm thấy mối quan hệ giữa hai thành viên phải mất ít nhất $2^{100}$ các bước tính toán (đối với hầu hết các trường hợp)?
Đối với điều này, nó cần phải khó hơn $O(\sqrt{N})$ (với $N<2^{200}$ và $C<2^{65}$)

Ghi chú thêm:

• bên cạnh 3 hướng theo hướng thuận cũng cần tồn tại nghịch đảo của chúng theo hướng ngược lại. Tất cả nên có cùng thời gian tính toán.
• trong trường hợp tốt nhất, tất cả các giá trị ngẫu nhiên hợp lệ có thể tạo ra cùng một cấu trúc. Nhưng một nhỏ ($<\xấp xỉ 10$) tập hợp các cấu trúc tương tự rời rạc (như trong 4.) cũng có thể thực hiện được.
• trong trường hợp sử dụng, một giá trị bắt đầu ngẫu nhiên sẽ được tạo và được sử dụng lặp đi lặp lại với các hàng xóm gần nhất của nó (sau đó là hàng xóm của các hàng xóm, v.v.).Cuối cùng, chúng đã dẫn (sau (gần như) thời gian vô tận để tạo ra) vào cùng một cấu trúc (bí mật) nhất quán. Việc ưu tiên bất kỳ hướng tiến triển nào để đạt được một giá trị mục tiêu nhất định nhanh hơn phải càng khó càng tốt. Vì vậy, việc tạo ra các điểm ngẫu nhiên sẽ không hiệu quả. Các giá trị tiếp theo được tạo phải luôn gần với các giá trị đã được tạo. Điều đó cũng có nghĩa là tạo ra các $i-$giá trị tiếp theo là không cần thiết (vì nó thường có thể được thực hiện với trình tạo), một bước theo một hướng là đủ (như trong AES/mật mã khối)
• không có chức năng kéo dài như chỉ đếm mỗi $n$-th thành viên là hợp lệ (để tăng tính bảo mật (kích thước thành viên cao hơn $N$) với kích thước thành viên thực không đổi $\frac{N}{n}$). Điều này sẽ được sử dụng. - Về mặt kỹ thuật - có thể (nếu ai đó thực sự muốn nó) để tạo ra một chu kỳ đầy đủ theo một hướng trên một PC tiêu chuẩn trong một số ít năm CPU. Với điều này, kích thước chu kỳ cần phải nhỏ hơn $2^{60}$. Nhưng việc tìm kiếm mối quan hệ giữa hai giá trị mục tiêu bất kỳ sẽ không khả thi trong 50 năm tới. Tìm kiếm nó cho một số kết hợp là tốt, thậm chí còn tốt nếu có. Theo như tôi biết về $2^{100}$ các bước tính toán là một ranh giới phù hợp cho việc này.
• một bước tính toán có nghĩa là bất kỳ loại thao tác cơ bản nào (+-*/^) được áp dụng ở hai giá trị $<N$
• các thành viên cấu trúc đó có thể là bất kỳ thứ gì như số, vectơ, chuỗi, ma trận, thậm chí cả ảnh nghệ thuật ascii cũng được. Chỉ cần có một số hàm để tạo giá trị giả ngẫu nhiên mà không làm rò rỉ thông tin liên quan đến bảo mật. Tạo nhiều trong số chúng sẽ không tiết lộ bất kỳ thông tin nào về mối quan hệ giữa chúng. Vì vậy, một cái gì đó như $g^r$ với một máy phát điện $g$ và $r$ giá trị ngẫu nhiên sẽ không hoạt động. Tạo chúng không cần phải nhanh như vậy, $<20$giây trên PC tiêu chuẩn là đủ.
• trong trường hợp sử dụng mục tiêu, các thành viên này sẽ đóng vai trò là hạt giống cho RNG. Cấu trúc của những thành viên đó như một sự sắp xếp cho những hạt giống đó.Một số chuỗi số ngẫu nhiên được tạo bởi các RNG đó sẽ tốt hơn các chuỗi khác. Nếu một trong số chúng được tìm thấy rất tốt, thì việc kết nối chúng càng khó càng tốt (= tính toán cái này với cái kia).
• các đối thủ sẽ bình đẳng với người dùng bình thường. Anh ta có quyền truy cập vào tất cả mã nguồn, biến thời gian chạy, khóa, biến, v.v. Khi độ dài chu kỳ mục tiêu $C$ là khá nhỏ, chúng ta cũng có thể coi nó đã được đối thủ biết đến.
• một số kỹ thuật đã được thử nghiệm thêm: máy tự động di động (không nghịch đảo), tessname (không xác định hoặc quá dễ giải), mã hóa đồng hình (không tràn/chu kỳ, không hoạt động nếu tất cả ở PC đối phương).

Cập nhật: Liên quan đến nhận xét của fgrieu:

Chúng ta muốn có một đồ thị liên thông vô hướng gồm N nút [?với biểu diễn đỉnh n là bộ ba tọa độ (tọa độ có phải là số nguyên không?)?]

Có, nhưng những tọa độ đó không có nguồn gốc toàn cầu. Nếu chúng ta muốn tìm một đường đi từ $n_1$ đến $n_2$ chúng tôi bắt đầu tại $n_1$ và tính toán nó là vùng lân cận. Những người có tọa độ liên quan đến $n_1$. Ví dụ. $(0,1,0)$ có thể có nghĩa là chúng tôi bắt đầu tại $n_1$ và áp dụng tiến trình cho chiều thứ 2 một lần.
Các nút bù ở giữa $n_1$ và $n_2$ đối xứng và bất biến với mọi $n_i$ chúng tôi đang bắt đầu từ.
Vì chúng tuần hoàn theo từng chiều nên phần bù chỉ có thể là $+/-$ một nửa kích thước chu kỳ (trong không gian euclide) cho mỗi tọa độ.
Số nguyên là không cần thiết. Các số thực cũng hoạt động miễn là máy tính có thể ước tính chúng đủ tốt để phân biệt giữa các nút khác nhau.
Lưới nằm ở một 3-hình xuyến vì vậy chúng ta có thể hiểu độ lệch cũng là độ lệch góc.

Để rõ ràng, việc chỉ tạo tọa độ ngẫu nhiên không hiệu quả. Chúng luôn cần phải gần với những thứ đã được tạo. Ngoại lệ duy nhất là nút bắt đầu. Những cần phải được tạo ra một cách ngẫu nhiên. Với hai nút bắt đầu như vậy (và tất cả các biến nội bộ), sẽ không có gợi ý nào về hướng phát triển tốt nhất.

Cần có một số quy trình để di chuyển từ nút này sang nút khác dọc theo các cạnh của biểu đồ, khi lặp đi lặp lại sẽ dẫn đến chu kỳ độ dài $C_n$ khi bắt đầu từ n

Bắt đầu tại $n$ và (chủ yếu) di chuyển về phía trước theo một hướng (và ví dụ: không quay lại nhiều lần) chúng ta có thể đạt được $n$ một lần nữa sau $C_n$ các bước. Điều này cần có thể thực hiện được đối với ít nhất 2 hướng trực giao và không quá 3 (tiến và lùi mỗi hướng).

Với hai đỉnh ngẫu nhiên, thật khó để tìm một đường đi giữa hai đỉnh, đòi hỏi nỗ lực điều chỉnh $\Omega(\sqrt[3]{N^2})$

Nó cũng có thể khó hơn nhưng tôi nghĩ điều này là không thể trong các cấu trúc mật mã bình thường với vùng lân cận cố định. Nói chung, nó có thể khó hơn. Vấn đề chính là tìm thứ gì đó không thể rút gọn thành vấn đề kích thước một chiều $C$ vì giá trị mục tiêu quá nhỏ cho điều đó. Điều đó cũng có nghĩa là $C$ được đối thủ biết đến (vì nó có thể được kiểm tra nhanh chóng).
Nhưng nếu tôi không trộn lẫn ký hiệu thì nó phải là $o(C^2+C)$ (đối với vùng lân cận cố định, giao điểm của mặt phẳng luôn có thể) và $\Omega(\sqrt{N})$ và $\Omega(C^{1,5})$ (số bước trung bình) khác $N,C$ cần phải quá lớn.

$C_n$ cần phải theo giai điệu của $O(\sqrt[3]{N})$ [nhưng đó là giới hạn trên hay giới hạn dưới cho Cn?].

Cả hai. Không giống như phương pháp được hiển thị bằng EC ở đâu $N\xấp xỉ C_n$ và không giống như phương pháp sử dụng hai AES trong đó $C_n$ có thể là $1$.
có thể có một cái gì đó như $O(\sqrt[3]{N}\cdot f(\log(N)))$. Mục tiêu chính là để có được một $\max(C_n) < 2^{65}$ (và $\min(C_n) \ge 2^{50}$ (khác để dễ dàng afaik)) với $N<2^{200}$ và tìm kiếm từ ngẫu nhiên $n_1$ đến $n_2$ nên lấy (trong hầu hết các trường hợp) ít nhất $2^{100}$ các bước tiến triển (nhưng có thể, lên đến $\xấp xỉ 10$ tập con là Ok).

bình luận của JAAAY có liên quan:

địa phương euclide hoặc mặt phẳng hyberbolic

Nói cách khác, sự phát triển của khu phố không thể quá nhanh.
Với (rất nhiều thời gian rảnh), chúng ta có thể vẽ cấu trúc lân cận lên các tờ giấy (= mặt phẳng euclide).
Chúng ta có thể đo khoảng cách (euclidean) giữa các nút bằng thước kẻ. Bất kể có bao nhiêu hàng xóm của hàng xóm, chúng ta rút ra khoảng cách trung bình ở giữa các nút sẽ giữ nguyên (khoảng) bằng nhau.
Nếu chúng ta dán hai cạnh giấy đối diện lại với nhau, chúng ta có thể mô phỏng thuộc tính chu kỳ cho một hướng. Xem xét tùy chọn này, khoảng cách (tối thiểu) giữa hai nút cụ thể luôn bằng nhau - bất kể chúng tôi đã bắt đầu vẽ cấu trúc này từ đâu. (Sau khi vẽ hết một vòng theo hai chiều ta phải cắt giấy theo kích thước phù hợp. Ở mép giấy ta tiếp tục đo ở mép giấy đối diện).

Một nút chỉ có thể ở trên tối đa 3 trang tính. Nếu nhiều số nằm trên hai trang tính khác nhau (2-tori) thì tất cả chúng nằm trên một dòng (1-hình xuyến) - giống như giao điểm của hai 2-tori.