Điểm:-1

Tràn trong lược đồ chia sẻ bí mật Shamir cổ điển

lá cờ co

Tôi đã triển khai Lược đồ chia sẻ bí mật Shamir cổ điển giống như sau:

  • lấy mật khẩu làm đầu vào (độ dài bất kỳ)
  • chuyển đổi văn bản mật khẩu thành số nguyên lớn
  • tạo hệ số đa thức (an ... a1)
  • tạo các phần tách - cặp (xi, yi) với ngưỡng đã cho

Nó hoạt động rất tốt và đây là cách tạo ra nhiều lượt chia sẻ bí mật hơn:

  • nhận cổ phần và ngưỡng làm đầu vào
  • tìm coeff với gauss (vì vậy tôi biết đa thức ban đầu)
  • tìm giá trị bí mật <- đây là vấn đề
  • tạo thêm lượt chia sẻ - sử dụng dấu thời gian là xi

Mọi thứ đều hoạt động tốt nhưng khi tôi sử dụng mật khẩu dài (10 ký tự trở lên) khi xây dựng lại giá trị bí mật thì có thể không thành công do mất độ chính xác cho các số cao.

Vậy làm thế nào để vượt qua cách tiếp cận cổ điển này? Điều gì nên được thay đổi trong lược đồ mà nó không nhạy cảm với độ tin cậy của văn bản bí mật?

kelalaka avatar
lá cờ in
https://math.stackexchange.com/q/4329986/338051 và điều này trở thành vấn đề về tham số và mã hóa có thể phù hợp hơn với [so].
Vadym Fedyukovych avatar
lá cờ in
Bạn đã sử dụng một số trường hữu hạn để thể hiện mật khẩu của mình chưa?
Macko avatar
lá cờ co
@VadymFedyukovych chưa, vui lòng đưa ra một số tùy chọn về cách thực hiện việc này phải không? Cách mã hóa mật khẩu trong trường hữu hạn mẫu
Điểm:1
lá cờ my

Điều gì nên được thay đổi trong lược đồ mà nó không nhạy cảm với độ tin cậy của văn bản bí mật?

Chà, Vadym đã đề cập rằng Chia sẻ Bí mật Shamir nên được thực hiện trong Trường hữu hạn; tuy nhiên nó không giải quyết câu hỏi của bạn.

Với Lược đồ của Shamir, một phiên bản đơn lẻ có thể chia sẻ bất kỳ giá trị nào giữa $0$$p^k - 1$ (ở đâu $p^k$ là kích thước của trường hữu hạn mà bạn sử dụng [1]). Và, với Shamir, không có sự khác biệt về bảo mật giữa các trường hữu hạn khác nhau, do đó chúng ta có thể chọn một trường dựa trên các mối quan tâm thực tế (ví dụ: số lượng bí mật bạn muốn có thể phát hành, kích thước của bí mật, mức độ dễ dàng thực hiện các phép toán trường hữu hạn khác nhau).

Tuy nhiên, những gì bạn muốn làm là chia sẻ mật khẩu làm bí mật; mật khẩu đó khá dài và có độ dài thay đổi. Vâng, có hai lựa chọn thay thế rõ ràng:

  • Chọn một $p^k$ (hoặc nguyên tố $p$ nếu bạn đi với $k-1$) đủ lớn để chứa bất kỳ mật khẩu nào bạn muốn chia sẻ; ví dụ: nếu bạn sử dụng $p=2^{521}-1$ (là số nguyên tố), bạn có thể chia sẻ mật khẩu có độ dài tối đa 65 ký tự. Điều này hoạt động, tuy nhiên, nhược điểm là các giá trị lớn như vậy sẽ cần được xử lý bằng thư viện bignum. Nếu bạn đang sử dụng một ngôn ngữ có tích hợp thư viện bignum (ví dụ: Python), thì đây không phải là vấn đề - nếu không, có lẽ sẽ dễ dàng hơn với ý tưởng thứ hai.

Với ý tưởng này, nếu chúng ta có mật khẩu 'letmein' (0x6c 0x65 0x74 0x6d 0x65 0x69 0x6e trong ASCII), chúng ta có thể mã hóa nó thành số nguyên 0x6c65746d65696e = 30510848210725230.

  • Chia nhỏ mật khẩu thành nhiều bí mật và chia sẻ riêng từng bí mật. Ví dụ: đối với mật khẩu gồm 14 ký tự, chúng tôi có thể chia mật khẩu đó thành 14 bí mật riêng biệt (với mỗi bí mật là một ký tự từ mật khẩu) và chia sẻ từng ký tự bằng cách sử dụng $p=257$$k=1$ (vì vậy mỗi bên sẽ nhận được tổng cộng 14 lượt chia sẻ, một lượt chia sẻ cho mỗi trong số 14 ký tự). Với ý tưởng này, sẽ an toàn khi sử dụng cùng một mã định danh cho tất cả các cổ phần mà một bên nhận được; tuy nhiên, điều quan trọng là mỗi bí mật được tạo bằng cách sử dụng tính ngẫu nhiên độc lập (nghĩa là mỗi trong số 14 đa thức ngẫu nhiên được tạo riêng).

Với ý tưởng này, chúng tôi sẽ mã hóa mật khẩu 'letmein' thành 8 bí mật độc lập 0x6c 0x65 0x74 0x6d 0x65 0x69 0x6e

Với ý tưởng thứ hai này, nếu bạn không muốn tiết lộ độ dài của bí mật, điều bạn có thể làm là luôn chia sẻ một số lượng bí mật cố định (đó sẽ là độ dài tối đa của mật khẩu bạn có thể chia sẻ, chẳng hạn như 32) và đối với mật khẩu ngắn hơn thế, hãy điền vào các ký tự bí mật bổ sung có giá trị không thể xuất hiện trong mật khẩu thực (ví dụ của tôi về $p=257$, giá trị rõ ràng để sử dụng sẽ là $256$).


[1]: Với mọi số nguyên tố $p$ và bất kỳ số nguyên nào $k$, có một trường kích thước hữu hạn $p^k$. Có lẽ bạn sẽ dễ dàng hơn khi bắt đầu sử dụng một trường có $k=1$$p$ một số nguyên tố có kích thước phù hợp - điều này làm cho các phép toán cộng, trừ và nhân gần hơn rất nhiều với các thuật toán tiêu chuẩn mà bạn quen thuộc (phép chia vẫn còn khó khăn).

Macko avatar
lá cờ co
hmm, ý tưởng thứ hai có vẻ lạ đối với tôi vì mỗi bên nhận (các) chia sẻ không nên có đủ cổ phần để tạo lại mật khẩu được bảo vệ (bí mật). Thứ hai, tôi không hiểu cách chia sẻ các ký tự mật khẩu sau này có thể được xây dựng lại thành mật khẩu có độ dài đầy đủ. Cách tiếp cận này có vẻ linh hoạt hơn.
Macko avatar
lá cờ co
có vẻ như sự chấp thuận đầu tiên là tùy chọn tốt nhưng nó cần một số lần thử và lỗi để tìm ra điểm hấp dẫn của các cấu trúc được sử dụng nội bộ - để tìm thời gian mật khẩu phức tạp hoặc dài vẫn có thể được xử lý bằng thuật toán bằng văn bản.
poncho avatar
lá cờ my
@Macko: nếu bạn không hiểu ý thứ hai, bạn đang suy nghĩ quá nhiều. Với nó, bạn tạo một sơ đồ chia sẻ bí mật cho chữ cái đầu tiên và đưa ra những chia sẻ đó. Đồng thời, bạn tạo ss cho chữ cái thứ hai và chia các cổ phần đó cho cùng một bên và tương tự cho chữ cái thứ ba, thứ tư, v.v. Khi đến lúc kết hợp lại, hãy lấy tất cả các cổ phần mà các bên có và kết hợp chia sẻ đầu tiên của họ với nhau (to gen chữ cái đầu tiên); tương tự với cái thứ hai, v.v. Khi bạn có tất cả các chữ cái, chỉ cần nối chúng lại với nhau là xong.
Macko avatar
lá cờ co
Tôi nghĩ rằng tùy chọn thứ hai là thiết kế quá mức và các bên sẽ kết thúc với quá nhiều cổ phiếu khó quản lý. Bây giờ tôi sẽ gắn bó với tùy chọn cổ điển 1 ...
Điểm:0
lá cờ in

Từ mô tả đã cho, người ta có thể gợi ý rằng các số thập phân và phép toán dấu phẩy động sẽ là một giải pháp đơn giản. Không có tràn và các vấn đề chính xác với các trường hữu hạn.

Vui lòng xem xét số học modulo một số số nguyên tố, xác định lại c ++ tiêu chuẩn cộng, trừ, nhân và chia. Chọn một cuốn sách giáo khoa mà bạn có thể đọc. Đó là một con đường dài. Chúc may mắn.

Macko avatar
lá cờ co
Tất nhiên là bạn đúng nhưng tôi cần thêm chi tiết hoặc xác nhận cách thực hiện đúng: trước tiên mã hóa mật khẩu thành số lớn (trong Java sẽ là BigInteger) hơn là chuyển đổi giá trị này thành số trong một số trường hữu hạn? Từ giờ trở đi, tất cả các phép tính như (tạo hệ số, nội suy) chỉ nên thực hiện trong trường xác định?

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