Hãy xem xét một tình huống mà bạn cần bảo đảm an toàn cho kho tiền ngân hàng. Nó được coi là hoàn toàn bất khả xâm phạm nếu không có chìa khóa mà bạn được trao vào ngày đầu tiên đi làm. Mục tiêu của bạn là lưu trữ khóa một cách an toàn.

Giả sử bạn quyết định luôn giữ chìa khóa bên mình, cung cấp quyền truy cập vào bộ lưu trữ khi cần. Nhưng bạn sẽ nhanh chóng nhận ra rằng giải pháp như vậy không có quy mô tốt trong thực tế, bởi vì sự hiện diện vật lý của bạn là bắt buộc mỗi khi bạn mở kho lưu trữ. Thế còn kỳ nghỉ mà bạn đã hứa thì sao? Ngoài ra, câu hỏi còn đáng sợ hơn: nếu bạn đánh mất chiếc chìa khóa duy nhất của mình thì sao?

Nghĩ đến kỳ nghỉ của mình, bạn quyết định tạo một bản sao của chìa khóa và giao nó cho một nhân viên khác. Tuy nhiên, bạn hiểu rằng điều này cũng không lý tưởng. Bằng cách nhân đôi số lượng chìa khóa, bạn cũng tăng gấp đôi khả năng bị đánh cắp chìa khóa.

Trong cơn tuyệt vọng, bạn phá hủy bản sao và quyết định chia đôi khóa gốc. Bây giờ, bạn sẽ nghĩ rằng hai người đáng tin cậy với những mảnh chìa khóa sẽ phải có mặt để lấy chìa khóa và mở kho tiền. Điều này có nghĩa là kẻ trộm cần đánh cắp hai chiếc, việc này khó gấp đôi việc lấy trộm một chiếc chìa khóa. Tuy nhiên, bạn sớm nhận ra rằng phương án này cũng chẳng khá hơn là chỉ một chìa khóa, vì nếu ai đó làm mất một nửa chìa khóa thì toàn bộ chìa khóa sẽ không thể lấy lại được.

Vấn đề có thể được giải quyết bằng một loạt chìa khóa và ổ khóa bổ sung, nhưng phương pháp này sẽ nhanh chóng yêu cầu много chìa khóa và ổ khóa. Bạn quyết định rằng thiết kế lý tưởng sẽ là chia sẻ khóa để việc bảo mật không phụ thuộc hoàn toàn vào một người. Bạn cũng kết luận rằng phải có một ngưỡng nào đó cho số lượng mảnh để nếu một mảnh bị mất (hoặc nếu một người đi nghỉ), toàn bộ khóa vẫn hoạt động.

Cách chia sẻ bí mật

Kiểu sơ đồ quản lý khóa này đã được Adi Shamir nghĩ đến vào năm 1979 khi ông xuất bản tác phẩm của mình. "Cách chia sẻ bí mật". Bài viết giải thích ngắn gọn về cái gọi là Sơ đồ ngưỡng để phân chia hiệu quả một giá trị bí mật (chẳng hạn như khóa mật mã) thành các bộ phận. Khi đó, khi và chỉ khi ít nhất của các bộ phận được lắp ráp, bạn có thể dễ dàng khôi phục bí mật .

Từ quan điểm bảo mật, một đặc tính quan trọng của sơ đồ này là kẻ tấn công không nên biết hoàn toàn bất cứ điều gì trừ khi anh ta có ít nhất các bộ phận. Ngay cả sự hiện diện các bộ phận không được cung cấp bất kỳ thông tin nào. Chúng tôi gọi đây là tài sản bảo mật ngữ nghĩa.

Nội suy đa thức

Sơ đồ ngưỡng Shamir được xây dựng xung quanh khái niệm nội suy đa thức. Nếu bạn chưa quen với khái niệm này thì nó thực sự khá đơn giản. Trên thực tế, nếu bạn đã từng vẽ các điểm trên biểu đồ và sau đó kết nối chúng bằng các đường thẳng hoặc đường cong thì bạn đã sử dụng được nó rồi!

Thông qua hai điểm, bạn có thể vẽ vô số đa thức bậc 2. Để chọn một đa thức duy nhất trong số đó, bạn cần có điểm thứ ba. Hình minh họa: Wikipedia

Xét đa thức bậc một, . Nếu muốn vẽ hàm số này trên đồ thị thì bạn cần bao nhiêu điểm? Vâng, chúng ta biết rằng đây là một hàm tuyến tính tạo thành một đường thẳng và do đó nó cần ít nhất hai điểm. Tiếp theo, hãy xem xét hàm đa thức bậc hai, . Đây là một hàm bậc hai nên cần ít nhất ba điểm để vẽ đồ thị. Thế còn một đa thức có bậc ba thì sao? Ít nhất bốn điểm. Vân vân và vân vân.

Điều thực sự thú vị về tính chất này là, với bậc của hàm đa thức và ít nhất điểm, chúng ta có thể rút ra các điểm bổ sung cho hàm đa thức này. Chúng tôi gọi phép ngoại suy của những điểm bổ sung này nội suy đa thức.

Tạo nên một bí mật

Bạn có thể đã nhận ra rằng đây là lúc kế hoạch thông minh của Shamir phát huy tác dụng. Hãy nói bí mật của chúng ta - . Chúng ta có thể biến đến một điểm trên đồ thị và đưa ra hàm đa thức có bậc , thỏa mãn điểm này. Chúng ta hãy nhớ lại điều đó sẽ là ngưỡng của các đoạn được yêu cầu, vì vậy nếu chúng ta đặt ngưỡng thành ba đoạn, chúng ta phải chọn hàm đa thức có bậc hai.

Đa thức của chúng ta sẽ có dạng Đâu и - các số nguyên dương được chọn ngẫu nhiên. Chúng ta chỉ đang xây dựng một đa thức có bậc , trong đó hệ số tự do  - Đây là bí mật của chúng tôi , và với mỗi cái tiếp theo có một hệ số dương được chọn ngẫu nhiên. Nếu chúng ta quay lại ví dụ ban đầu và giả sử rằng , thì ta có hàm .

Tại thời điểm này, chúng ta có thể tạo các đoạn bằng cách kết nối số nguyên duy nhất trong Đâu (vì đó là bí mật của chúng tôi). Trong ví dụ này, chúng tôi muốn phân phối bốn mảnh có ngưỡng là ba, vì vậy chúng tôi tạo điểm ngẫu nhiên và gửi một điểm cho mỗi người trong số bốn người đáng tin cậy, những người giữ chìa khóa. Chúng tôi cũng cho mọi người biết rằng , vì đây được coi là thông tin công khai và cần thiết để phục hồi .

Khôi phục bí mật

Chúng ta đã thảo luận về khái niệm nội suy đa thức và cách nó làm cơ sở cho sơ đồ ngưỡng của Shamir . Khi bất kỳ ba trong số bốn người được ủy thác muốn khôi phục , họ chỉ cần nội suy với những điểm độc đáo riêng. Để làm được điều này, họ có thể xác định quan điểm của mình và tính đa thức nội suy Lagrange bằng công thức sau. Nếu lập trình đối với bạn rõ ràng hơn toán học thì pi về cơ bản là một toán tử for, nhân tất cả các kết quả và sigma là for, cộng lại mọi thứ.

Khi chúng ta có thể giải nó như thế này và trả về hàm đa thức ban đầu:

Kể từ khi chúng tôi biết rằng , sự hồi phục được thực hiện đơn giản:

Sử dụng số học số nguyên không an toàn

Mặc dù chúng ta đã áp dụng thành công ý tưởng cơ bản của Shamir , chúng ta gặp phải một vấn đề mà chúng ta đã bỏ qua cho đến tận bây giờ. Hàm đa thức của chúng tôi sử dụng số học số nguyên không an toàn. Lưu ý rằng với mỗi điểm bổ sung mà kẻ tấn công thu được trên biểu đồ hàm của chúng ta thì khả năng có được các điểm khác sẽ ít hơn. Bạn có thể tận mắt nhìn thấy điều này khi vẽ biểu đồ số điểm ngày càng tăng cho hàm đa thức bằng cách sử dụng số học số nguyên. Điều này phản tác dụng với mục tiêu bảo mật đã nêu của chúng tôi, bởi vì kẻ tấn công hoàn toàn không biết gì cho đến khi họ có ít nhất mảnh vỡ.

Để chứng minh mạch số học số nguyên yếu đến mức nào, hãy xem xét một tình huống trong đó kẻ tấn công đạt được hai điểm và biết thông tin công khai rằng . Từ thông tin này anh ta có thể suy ra , bằng hai và thay các giá trị đã biết vào công thức и .

Kẻ tấn công sau đó có thể tìm thấy , đếm :

Vì chúng ta đã xác định là số nguyên dương được chọn ngẫu nhiên, có một số lượng hạn chế có thể . Sử dụng thông tin này, kẻ tấn công có thể suy ra , vì bất cứ điều gì lớn hơn 5 sẽ làm được tiêu cực. Điều này hóa ra là đúng vì chúng ta đã xác định

Kẻ tấn công sau đó có thể tính toán các giá trị có thể , thay thế в :

Với những lựa chọn hạn chế cho nó trở nên rõ ràng việc lựa chọn và kiểm tra các giá trị dễ dàng như thế nào . Chỉ có năm lựa chọn ở đây.

Giải quyết vấn đề với số học số nguyên không an toàn

Để loại bỏ lỗ hổng này, Shamir đề xuất sử dụng số học mô-đun, thay thế trên Đâu и - tập hợp tất cả các số nguyên tố.

Chúng ta hãy nhanh chóng nhớ lại cách hoạt động của số học mô-đun. Đồng hồ có kim là một khái niệm quen thuộc. Cô ấy sử dụng một chiếc đồng hồ . Ngay khi kim giờ vượt qua mười hai, nó sẽ trở về một. Một đặc tính thú vị của hệ thống này là chỉ cần nhìn vào đồng hồ, chúng ta không thể suy ra kim giờ đã quay được bao nhiêu vòng. Tuy nhiên, nếu biết kim giờ đã đi qua 12 bốn lần thì chúng ta hoàn toàn có thể xác định được số giờ đã trôi qua bằng một công thức đơn giản Đâu  là ước số của chúng tôi (ở đây ),  là hệ số (số chia đi vào số ban đầu bao nhiêu lần không có số dư, ở đây ) và  là phần còn lại, thường trả về lệnh gọi toán tử modulo (ở đây ). Biết tất cả các giá trị này cho phép chúng ta giải phương trình cho , nhưng nếu bỏ sót hệ số thì chúng ta sẽ không bao giờ lấy lại được giá trị ban đầu.

Chúng ta có thể chứng minh điều này cải thiện tính bảo mật của lược đồ như thế nào bằng cách áp dụng lược đồ này vào ví dụ trước và sử dụng . Hàm đa thức mới của chúng tôi , và những điểm mới . Giờ đây, những người giữ khóa có thể một lần nữa sử dụng phép nội suy đa thức để xây dựng lại hàm của chúng ta, chỉ có điều lần này các phép tính cộng và nhân phải đi kèm với việc giảm modulo (ví dụ ).

Sử dụng ví dụ mới này, giả sử rằng kẻ tấn công đã học được hai trong số những điểm mới này, và thông tin đại chúng . Lần này, kẻ tấn công, dựa trên tất cả thông tin hắn có, đưa ra các hàm sau, trong đó:  là tập hợp tất cả các số nguyên dương và đại diện cho hệ số mô đun .

Bây giờ kẻ tấn công của chúng tôi tìm thấy lại , tính toán :

Sau đó anh ấy thử lại , thay thế в :

Lần này anh ấy gặp phải một vấn đề nghiêm trọng. Công thức thiếu giá trị , и . Vì có vô số sự kết hợp của các biến này nên anh ta không thể thu được bất kỳ thông tin bổ sung nào.

Cân nhắc về Bảo mật

Đề xuất kế hoạch chia sẻ bí mật của Shamir bảo mật từ quan điểm của lý thuyết thông tin. Điều này có nghĩa là toán học có khả năng chống lại ngay cả kẻ tấn công có sức mạnh tính toán vô hạn. Tuy nhiên, mạch vẫn chứa một số vấn đề đã biết.

Ví dụ, sơ đồ Shamir không tạo ra đoạn cần kiểm tra, tức là mọi người có thể tự do đưa ra những mảnh vỡ giả và cản trở việc khôi phục bí mật chính xác. Người giữ mảnh thù địch có đủ thông tin thậm chí có thể tạo ra một mảnh khác bằng cách thay đổi theo ý riêng của bạn. Vấn đề này được giải quyết bằng cách sử dụng kế hoạch chia sẻ bí mật có thể kiểm chứng, chẳng hạn như sơ đồ của Feldman.

Một vấn đề khác là độ dài của bất kỳ đoạn nào cũng bằng độ dài của bí mật tương ứng, do đó độ dài của bí mật rất dễ xác định. Vấn đề này có thể được giải quyết bằng cách tầm thường phần đệm bí mật với các số tùy ý có độ dài cố định.

Cuối cùng, điều quan trọng cần lưu ý là mối lo ngại về bảo mật của chúng tôi có thể vượt ra ngoài bản thân thiết kế. Đối với các ứng dụng mật mã trong thế giới thực, thường có mối đe dọa về các cuộc tấn công kênh bên trong đó kẻ tấn công cố gắng trích xuất thông tin hữu ích từ thời gian thực thi ứng dụng, bộ nhớ đệm, sự cố, v.v. Nếu đây là vấn đề đáng lo ngại, cần cân nhắc cẩn thận trong quá trình phát triển để sử dụng các biện pháp bảo vệ như chức năng và tra cứu theo thời gian liên tục, ngăn chặn việc lưu bộ nhớ vào đĩa và một số cân nhắc khác nằm ngoài phạm vi của bài viết này.

Bản trình diễn

Trên trang này Có một minh họa tương tác về kế hoạch chia sẻ bí mật của Shamir. Trình diễn dựa trên thư viện ssss-js, bản thân nó là một cổng JavaScript của chương trình phổ biến ssss. Lưu ý rằng việc tính giá trị lớn , и Có thể mất một thời gian.

Nguồn: www.habr.com