Thuật toán rsa của hệ thống mã hóa khóa công khai. Hệ thống mật mã RSA. Chữ ký số và khóa công khai

Cơ chế phân phối quyền trong các hệ điều hành, được phát triển từ những năm 70 của thế kỷ trước, hóa ra đã thành công đến mức nó vẫn được sử dụng trong các hệ thống UNIX, tức là trong hơn bốn mươi năm.

Quyền 777 - nó là gì?

Nguyên tắc cơ bản của phương pháp phân phối quyền truy cập bao gồm sự tồn tại của các thuộc tính bắt buộc, chẳng hạn như tên của người dùng hệ thống cũng như nhóm của họ. Gần như hiển nhiên là trong Linux mỗi người dùng chỉ có thể có một tên, tên này phải là duy nhất trong hệ thống này. Sử dụng biệt danh, người dùng đăng nhập vào hệ thống, nghĩa là trải qua quá trình ủy quyền. Ngoài ra, hệ điều hành còn chứa một số lượng hữu hạn các nhóm người dùng. Mỗi người trong số họ có thể là một phần của một hoặc nhiều nhóm. Superuser - root - có thể chỉnh sửa thuộc tính, tạo và xóa nhóm. Thành viên của các nhóm khác nhau có quyền hoạt động khác nhau trong hệ thống. Ví dụ: quản trị viên có nhiều quyền hơn khách.

Inode (mà mọi tệp đều có) chứa thông tin đăng nhập của chủ sở hữu và tên của nhóm người dùng có quyền đối với tệp.

Khi một tệp được tạo, chủ sở hữu của nó sẽ trở thành người dùng thay mặt cho quá trình đang chạy. Nhóm của tệp mới được tạo cũng được xác định bằng cách sử dụng mã định danh nhóm của quy trình hiện tại. Trong quá trình làm việc tiếp theo, tất cả các giá trị này có thể được thay đổi bằng lệnh console, điều này sẽ được thảo luận sau.

Cách thay đổi quyền

Lệnh chmod có thể thay đổi chế độ truy cập của người dùng vào tệp. Chỉ chủ sở hữu hoặc siêu người dùng của nó mới được phép thay đổi các quyền này dưới bất kỳ hình thức nào. Trong các hệ thống Unix, mã thường được chỉ định dưới dạng số ở dạng bát phân hoặc sử dụng các dấu hiệu ghi nhớ đặc biệt (chữ cái). Sử dụng mỗi phương pháp đều có ưu điểm và nhược điểm. Vì vậy, với sự trợ giúp của chỉ báo kỹ thuật số về quyền truy cập, quản trị viên hệ thống sẽ có thể nhanh chóng định cấu hình loại quyền truy cập mong muốn và với sự trợ giúp của mã ghi nhớ, anh ta sẽ có thể thực hiện việc này chính xác hơn - ví dụ: thêm hoặc loại bỏ quyền ghi hoặc từ chối quyền đọc.

Đối số đầu tiên của lệnh chmod console là thông số kỹ thuật về quyền của người dùng và đây là ký hiệu ghi nhớ hoặc số bát phân. Đối số thứ hai và tiếp theo là tên của các tệp mà chúng tôi đang cố gắng thay đổi quyền truy cập. Khi thiết lập quyền dưới dạng ba số, chữ số đầu tiên xác định quyền cho chủ sở hữu, chữ số thứ 2 cho nhóm và chữ số thứ ba cho tất cả người dùng khác.

Quyền truy cập ghi nhớ

Quyền truy cập vào các tệp trong hệ thống quyền có các biến thể sau:

r - quyền truy cập để đọc tệp;
w - quyền chỉnh sửa dữ liệu (nhưng không được xóa);
x - khả năng khởi chạy một tệp để thực thi.

Hệ thống quyền sau đây áp dụng cho các thư mục:

r - người dùng có thể đọc bất kỳ tập tin nào trong thư mục;
w - với các quyền này, bạn có thể tạo và xóa các tệp trong một thư mục, ngay cả khi một số tệp trong thư mục đó thuộc về người dùng khác;
x - cho biết quyền vào thư mục. Nếu bạn có quyền đối với thư mục con nhưng không có quyền đối với thư mục ở cấp cao hơn thì bạn sẽ không thể truy cập vào thư mục của mình.

Có thể có tổng cộng 8 cách kết hợp khác nhau, được thể hiện trong hình bên dưới.

Sử dụng bảng bên dưới, bạn có thể hiểu cách triển khai các phép gán quyền phức tạp, cũng như cách đặt quyền 777 bằng cách sử dụng đặc tả chmod ghi nhớ.

Cách đặt quyền thành 777 qua SSH

Dưới đây là một số ví dụ về cách sử dụng lệnh chmod:

chmod 711 file_name.txt.

Sử dụng kịch bản phân phối tệp này sẽ dẫn đến việc chủ sở hữu có toàn quyền đối với tệp và tất cả các nhóm người dùng khác chỉ có thể thực thi nó.

Khi sử dụng mã 775, chúng tôi sẽ cung cấp cho chủ sở hữu và toàn bộ nhóm của anh ta danh sách đầy đủ các quyền. Những người dùng khác sẽ không thể thực hiện thay đổi đối với tệp. Phải nói rằng để chỉ định một tập tin chỉ bằng tên riêng của nó thì nó phải nằm trong thư mục chứa tập tin này. Nếu không, bạn có thể di chuyển đến thư mục này bằng lệnh cd folder_name/subdirectory_name hoặc sử dụng cấu trúc sau:

chmod 775 /var/bin/file_name.txt.

Để thay đổi đệ quy quyền của tất cả các tệp trong một thư mục và tất cả các thư mục con, bạn cần thêm khóa chuyển -R vào lệnh chmod. Lệnh kết quả sẽ trông như thế này:

chmod -R 711 file_name.

Do đó, cách đặt quyền truy cập thành 777 cho một tệp hoặc thư mục sẽ không thành vấn đề - bạn chỉ cần đăng nhập vào máy chủ web của mình qua SSH và chạy lệnh:

tên tệp chmod 777.

Cách đặt quyền truy cập thành 777 trong bảng điều khiển máy chủ

Bạn cũng có thể thực hiện quy trình tương tự thông qua giao diện trực quan của ứng dụng khách FileZilla FTP hoặc ứng dụng khách WinSCP SFTP. Để thực hiện việc này, bạn sẽ cần cấp quyền cho máy chủ của mình đối với một trong các chương trình này, chọn tệp hoặc thư mục của bạn trong giao diện trực quan, sau đó nhấp chuột phải và chọn các hộp bên cạnh các quyền được yêu cầu.

Đôi khi, trong trường hợp cần gấp, bạn có thể không có quyền truy cập vào máy khách Windows, vì vậy bạn có thể thay đổi quyền truy cập thông qua bảng điều khiển máy chủ web. Để thực hiện việc này, hãy sử dụng trình quản lý tệp của bảng điều khiển, chọn các tệp cần thiết và nhấp vào nút Thay đổi quyền. Tiếp theo, bạn cũng sẽ cần phải kiểm tra tất cả các hộp và bây giờ câu hỏi về cách đặt quyền truy cập 777 vào một thư mục sẽ không còn khó khăn với bạn nữa.

Thuật toán mã hóa khóa công khai RSA là một trong những đề xuất đầu tiên vào cuối những năm 70 của thế kỷ XX. Tên của nó được tạo thành từ các chữ cái đầu tiên trong họ của các tác giả: R. Rivest, A. Shamir và L. Adleman. Thuật toán RSA có lẽ là thuật toán phổ biến và được sử dụng rộng rãi nhất thuật toán bất đối xứng trong các hệ thống mật mã.

Thuật toán dựa trên thực tế là vấn đề phân tích một số lớn thành thừa số nguyên tố là rất khó. Hệ thống mật mã RSA dựa trên hai sự thật sau đây từ lý thuyết số:

nhiệm vụ kiểm tra tính nguyên tố của một số là tương đối dễ dàng;
bài toán phân tích số có dạng n = pq (p và q là số nguyên tố); Việc phân tích nhân tử là rất khó khăn nếu chúng ta chỉ biết n, p và q là những số lớn (đây gọi là bài toán phân tích nhân tử, để biết thêm chi tiết, xem phần “Cơ sở lý thuyết số dùng trong mật mã khóa công khai”).

Thuật toán RSA là thuật toán mã hóa khối trong đó dữ liệu được mã hóa và không được mã hóa phải được biểu diễn dưới dạng số nguyên từ 0 đến n -1 đối với một số n.

Mã hóa

Vì vậy, chúng ta hãy nhìn vào chính thuật toán. Cho thuê bao A muốn gửi một tin nhắn mã hóa đến thuê bao B. Trong trường hợp này, thuê bao B phải chuẩn bị một cặp (khóa chung; khóa riêng) và gửi khóa chung của mình cho người dùng A.

Bước đầu tiên là tạo khóa chung và khóa riêng. Để làm điều này, trước tiên hãy chọn hai số nguyên tố lớn P và Q. Khi đó sản phẩm N được tính:

Sau đó, số phụ f được xác định:

f = (P - l)(Q - 1).

Khi đó số d được chọn ngẫu nhiên< f и взаимно простое с f .

Các số d và N sẽ là khóa chung của người dùng và giá trị e sẽ là khóa riêng.

Vì vậy, tại thời điểm này người dùng sẽ có thông tin được liệt kê trong bảng sau:

Vì người dùng B muốn nhận tin nhắn được mã hóa từ người dùng A nên người dùng B phải gửi khóa chung (d, N) của mình cho người dùng A. Các số P và Q không còn cần thiết nữa nhưng chúng không thể chia sẻ với bất kỳ ai; Tốt nhất là hãy quên chúng hoàn toàn.

Tại thời điểm này, giai đoạn chuẩn bị khóa đã hoàn tất và giao thức RSA chính có thể được sử dụng để mã hóa dữ liệu.

Giai đoạn thứ hai - mã hóa dữ liệu. Nếu thuê bao A muốn gửi một số dữ liệu đến thuê bao B thì anh ta phải thể hiện tin nhắn của mình dưới dạng số và chia nó thành các khối m 1, m 2, m 3, ..., nơi m tôi< N . Tin nhắn được mã hóa sẽ bao gồm các khối có i .

Thuê bao A mã hóa từng khối tin nhắn của mình bằng công thức

c tôi = m tôi d mod N

sử dụng thông số công khai người dùng B và gửi tin nhắn được mã hóa C=(c 1, c 2, c 3, ...) qua một đường dây mở.

Thuê bao B nhận được tin nhắn mã hóa sẽ giải mã tất cả các khối của tin nhắn nhận được bằng công thức

Tất cả các khối được giải mã sẽ giống hệt như các khối đến từ người dùng A.

Kẻ tấn công chặn tất cả tin nhắn và biết tất cả thông tin công khai sẽ không thể tìm thấy tin nhắn gốc với giá trị lớn của P và Q.

Ví dụ về tính toán thuật toán

Cho phép người dùng A muốn gửi tin nhắn cho người dùng B. Trong trường hợp này, người dùng B trước tiên phải chuẩn bị khóa chung và khóa riêng. Ví dụ: hãy để họ chọn các tham số sau:

P = 3, Q = 11, N = 3x11 = 33.

Sau đó f = (P - l)(Q - 1) = (3-1)(11-1) = 20.

Sau đó, người dùng B chọn bất kỳ số d nào không có ước chung với f (điều này là cần thiết để sau đó tin nhắn được mã hóa có thể được khôi phục duy nhất). Đặt d = 13. Con số này sẽ là một trong những thành phần của khóa công khai.

Bên dưới phần cắt là các ví dụ về việc chọn tham số mật mã RSA “xấu”.

“Cần nhấn mạnh rằng phải cẩn thận khi lựa chọn mô-đun RSA (số N) cho mỗi phóng viên mạng. Về vấn đề này, có thể nói như sau. Người đọc có thể xác minh một cách độc lập rằng việc biết một trong ba đại lượng P, q hoặc φ(n), bạn có thể dễ dàng tìm thấy khóa riêng RSA...".

Hãy thêm vào văn bản này. Nếu việc lựa chọn mô-đun mật mã RSA không thành công, như đã được thực hiện trong ví dụ về hướng dẫn bên dưới, bạn có thể giải mã văn bản mà không cần có khóa bí mật, tức là. mà không biết bất kỳ đại lượng nào trong ba đại lượng được nêu tên.

Để làm điều này, chỉ cần có văn bản mã hóa được chỉ định bởi mô-đun mật mã là đủ N, khóa công khai e mật mã và chỉ thực hiện ba bước của một cuộc tấn công đọc không cần chìa khóa. Sau bước tấn công thứ tư, người ta xác định rằng văn bản nguồn đã được lấy ở bước trước và có thể đọc được. Hãy cho thấy nó dễ dàng như thế nào để làm.

Trước tiên, hãy đưa ra ví dụ từ trang 313-315 trong sách hướng dẫn nói trên.

Ví dụ

Mã hóa tin nhắn văn bản ban đầu ngắn: RSA.
Người nhận đặt mật mã với các đặc điểm n=pq=527, Ở đâu p=17, q=31 Và φ(n)=(р –1)(q – 1)=480. Là khóa công khai e một số được chọn là số nguyên tố cùng nhau φ(n), e=7. Các số nguyên được tìm thấy cho số này bằng thuật toán Euclide mở rộng bạn Và v, thỏa mãn mối quan hệ e∙u+φ(n)∙v=1:

480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
v=2, u=–137.

Bởi vì –137≡343(mod480), Cái đó d=343.

Bài kiểm tra: 7∙343=2401≡1(mod480).

Tin nhắn văn bản được trình bày dưới dạng một dãy số chứa trong khoảng . Thư cho việc này R, S Và MỘTđược mã hóa dưới dạng số nhị phân 5 bit. Số sê-ri của các chữ cái này trong bảng chữ cái tiếng Anh được sử dụng dưới dạng nhị phân:

R=18 10 =(10010) 2, S=19 10 =(10011) 2,
A=1 10 =(00001) 2.

Sau đó RSA=(100101001100001) 2. Việc chia văn bản thành các khối có độ dài giới hạn sẽ tạo ra bản trình bày gồm hai khối: RSA=(100101001), (100001)=(M 1 =297, M 2 =33).

Các khối văn bản nguồn được mã hóa tuần tự M1 =297, M2 =33:
y 1 =E k (M 1)=M 1 e ≡297 7 (mod527)=474.

Ở đây chúng tôi đã sử dụng thực tế rằng:

297 7 =((297 2) 3)297≡(mod527)=(200 3 (mod527)297)(mod527)=474,
y 2 =E k (M 2)=M 2 e ≡33 7 (mod527)=407.

Bản mã, giống như bản gốc, thu được ở dạng hai khối: y 1 =474; y 2 =407.

Giải mã dường như là một chuỗi hành động D k (y i)=(y i) d =(y i) 343 (mod 527), tôi = 1,2.

Tính lũy thừa d sẽ thuận tiện hơn khi thực hiện bằng cách trước tiên biểu diễn số mũ dưới dạng tổng lũy thừa của số 2 , cụ thể là: 343=256+64+16+4+2+1 .

Sử dụng biểu diễn số mũ này d=343, chúng tôi nhận được:

474 2 ≡174(mod527),
474 4 ≡237(mod527),
474 8 ≡307(mod527),
474 16 ≡443(mod527),
474 32 ≡205(mod527),
474 64 ≡392(mod527),
474 128 ≡307(mod527),
474 256 ≡443(mod527),
và cuối cùng 474 343 (mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297.

Giá trị được tính tương tự 407 343 (mod527)=33.

Chuyển sang cách thể hiện theo nghĩa đen của tin nhắn được giải mã sẽ mang lại: RSA.

Sau khi xem ví dụ, sổ tay thảo luận về độ bền của hệ thống RSA. Cần nhấn mạnh sự cần thiết phải thận trọng khi chọn mô-đun mật mã RSA (các số). N) cho mỗi phóng viên mạng. Nó được chỉ ra rằng không thể chấp nhận được việc bỏ qua các yêu cầu đối với các đặc điểm đã chọn của hệ thống mã hóa. Thật không may, trong số các yêu cầu này, việc vi phạm được minh họa bằng ví dụ đã cho không được chỉ ra.

Tấn công vào mật mã RSA

Hãy xem một ví dụ về tấn công vào mật mã RSA. Hãy sử dụng dữ liệu từ ví dụ được đưa ra ở trang 313-315 trong sách giáo khoa “Cơ bản về mật mã” của A.P. Alferov, A.Yu. Zubov, A.S. Kuzmin, A.V. Cheremushkin, Mátxcơva. "Helios ARV", 2001.

Lỗi (không thể chấp nhận) của các tham số hệ thống đã chọn trong ví dụ này được thể hiện dễ dàng bằng các phép tính thực hiện tấn công vào việc đọc văn bản nguồn không cần phím. Bản chất của một cuộc tấn công như sau. Khóa chung của mật mã RSA được chỉ định ( e=7, n=527) và bản mã. Trong ví dụ, bản mã được biểu diễn thành hai khối
y=(y 1 =474, y 2 =407).

Mỗi khối mã hóa được tấn công riêng lẻ, đầu tiên chúng tôi tấn công y 1 =474, sau khi giải mã xong, chúng ta tấn công một khối khác y 2 =407.

Tiếp theo, một chuỗi các giá trị số được hình thành bằng cách mã hóa lặp đi lặp lại, lưu trữ kết quả của hai bước liên tiếp của thuật toán tấn công và sử dụng khóa chung. ừ tôi, y 1 = y bản mã có sẵn.

Trong thuật toán tấn công bản mã, số bước sau được xác định: j, mà y i e j (mod n)=(y i e j–1 (mod n)) e (mod n)=y i, tôi>1. Từ mối quan hệ cuối cùng chúng ta thấy rằng khi được nâng lên quyền lực e giá trị (y i e j–1 (mod n)) bản mã ban đầu thu được y tôi = y 1.

Nhưng điều này có nghĩa là bản rõ đã được mã hóa ở bước này. Bằng cách tính toán trực tiếp (có rất ít trong số đó) bằng máy tính trên màn hình, chúng tôi tìm thấy giá trị đó j, tại đó chu kỳ mã hóa kết thúc với giá trị năm 1, từ đó chu kỳ bắt đầu.

Tấn công vào khối đầu tiên y 1 =474 mật mã.
Bước 1: 474 7 (mod527)=382;
Bước 2: 382 7 (mod527)=423;
Bước 3: 423 7 (mod527)=297;
Bước 4: ở bước này, văn bản nguồn đã tìm thấy sẽ được mã hóa nhưng việc này phải được thực hiện vì kẻ tấn công không biết văn bản nguồn. Dấu hiệu hoàn thành cuộc tấn công là sự trùng khớp của giá trị bản mã ban đầu ( 474 ) và kết quả của bước mã hóa thứ 4. Đây chính xác là sự trùng hợp ngẫu nhiên xảy ra.

297 7 (mod527)=474đã nhận được khối văn bản mã hóa đầu tiên (đầu tiên). Cuộc tấn công vào khối đầu tiên đã hoàn thành thành công y 1 =474. Kết quả trước đó của bước 3 bằng bản rõ M1 =297.

n=527 r=297 modulo n=527. Nó được viết như thế này y tôi =у 1 =297. Hình thành dư lượng điện
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 =297.

Tấn công vào khối thứ hai y 2 =407 mật mã.
Bước 1: 407 7 (mod527)=16;
Bước 2: 16 7 (mod527)=101;
Bước 3: 101 7 (mod527)=33;
Bước 4: 33 7 (mod527)=407.

Một lần nữa, ở bước thứ ba, đã thu được một khối văn bản nguồn ( M2 =33), nhưng kẻ tấn công không biết điều này và anh ta thực hiện bước tiếp theo (bước thứ tư), kết quả là ( 407 ) khớp với bản mã ban đầu y 2 =407.

Về cơ bản nằm trong vòng dư lượng modulo n=527 một chu trình xử lý khấu trừ ngắn đã được triển khai r=33 modulo n=527. Nó được viết như thế này y tôi =y 2 =33.
Hình thành dư lượng năng lượng ((33 7 (mod527)) 7 (mod527)) 7 (mod527)=33.

Kết quả của cuộc tấn công (văn bản nguồn M1 =297, M2 =33) thu được bằng cách mã hóa bản mã đã cho ba lần. Thật khó để tưởng tượng một kẻ tấn công bản mã có thể đạt được thành công lớn hơn.

Tiếp tục thảo luận về việc lựa chọn mô-đun và các tham số mật mã khác, chúng ta có thể thêm mô-đun mật mã ( n=527) một số văn bản nguồn không thể được mã hóa. Trong trường hợp này, việc lựa chọn giá trị của khóa chung không đóng vai trò lớn. Có các giá trị văn bản nguồn thường không thể mã hóa bằng mật mã đã chọn bằng mô-đun n=527.

Không ai trong số những cái nhất định có thể mã hóa văn bản nguồn được biểu thị bằng số
187 , 341 , 154 Và 373 .

Ví dụ (không có khả năng mã hóa giá trị của một số văn bản nguồn)

Hãy để các văn bản nguồn được đại diện bởi bốn khối y=(y 1 =154, y 2 =187, y 3 =341, y 4 =373). Nhà triển lãm e khóa chung của mật mã có thể là bất kỳ số nguyên tố cùng nhau nào có hàm Euler φ(n)=φ(527)=480. Tuy nhiên, đối với trường hợp đang xem xét, khóa công khai e có thể được thiết lập tùy ý. Thật vậy, hãy e=2, 4, 7, 9, 17, 111 Sau đó:

154 2 (mod527)=1;
154 4 (mod527)=1;
154 7 (mod527)=154;
154 9 (mod527)=154;
154 17 (mod527)=154;
154 111 (mod527)=154;
187 2 (mod527)=187;
187 4 (mod527)=187;
187 7 (mod527)=187;
187 9 (mod527)=187;
187 17 (mod527)=187;
187 111 (mod527)=187;
341 2 (mod527)=341;
341 4 (mod527)=1;
341 7 (mod527)=341;
341 9 (mod527)=341;
341 17 (mod527)=341;
341 111 (mod527)=341;
373 2 (mod527)=1;
373 4 (mod527)=373;
373 7 (mod527)=373;
373 9 (mod527)=373;
373 17 (mod527)=373;
373 111 (mod527)=373.

Một kết luận đơn giản được rút ra từ ví dụ đã xem xét. Thật vậy, việc lựa chọn các tham số cho quá trình mã hóa phải được tiếp cận rất cẩn thận và phải tiến hành phân tích sơ bộ kỹ lưỡng các tham số đó. Làm thế nào để thực hiện điều này là một vấn đề riêng biệt và không được xem xét trong phạm vi công việc này.

Bên dưới phần cắt là các ví dụ về việc chọn tham số mật mã RSA “xấu”.

Trước tiên, hãy đưa ra ví dụ từ trang 313-315 trong sách hướng dẫn nói trên.

Ví dụ

480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
v=2, u=–137.

Bởi vì –137≡343(mod480), Cái đó d=343.

Bài kiểm tra: 7∙343=2401≡1(mod480).

R=18 10 =(10010) 2, S=19 10 =(10011) 2,
A=1 10 =(00001) 2.

Các khối văn bản nguồn được mã hóa tuần tự M1 =297, M2 =33:
y 1 =E k (M 1)=M 1 e ≡297 7 (mod527)=474.

Ở đây chúng tôi đã sử dụng thực tế rằng:

297 7 =((297 2) 3)297≡(mod527)=(200 3 (mod527)297)(mod527)=474,
y 2 =E k (M 2)=M 2 e ≡33 7 (mod527)=407.

Bản mã, giống như bản gốc, thu được ở dạng hai khối: y 1 =474; y 2 =407.

Giải mã dường như là một chuỗi hành động D k (y i)=(y i) d =(y i) 343 (mod 527), tôi = 1,2.

Sử dụng biểu diễn số mũ này d=343, chúng tôi nhận được:

Giá trị được tính tương tự 407 343 (mod527)=33.

Chuyển sang cách thể hiện theo nghĩa đen của tin nhắn được giải mã sẽ mang lại: RSA.

Tấn công vào mật mã RSA

Mỗi khối mã hóa được tấn công riêng lẻ, đầu tiên chúng tôi tấn công y 1 =474, sau khi giải mã xong, chúng ta tấn công một khối khác y 2 =407.

n=527 r=297 modulo n=527. Nó được viết như thế này y tôi =у 1 =297. Hình thành dư lượng điện
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 =297.

Không ai trong số những cái nhất định có thể mã hóa văn bản nguồn được biểu thị bằng số
187 , 341 , 154 Và 373 .

Ví dụ (không có khả năng mã hóa giá trị của một số văn bản nguồn)

Cuối cùng, đã đến lúc bắt đầu mô tả hệ thống mật mã RSA. Ngoài việc giải thích cách thức hoạt động của nó, chúng ta phải thảo luận chi tiết về độ an toàn của nó; nói cách khác, tại sao việc phá vỡ một tin nhắn được mã hóa bằng hệ thống mật mã RSA lại khó đến vậy?

§ 12.1. Về sự khởi đầu và kết thúc

Để triển khai hệ thống mã hóa RSA một người dùng, bạn phải chọn hai số nguyên tố p và q khác nhau và tính tích của chúng. Các số nguyên tố p và q được giữ bí mật trong khi số đó trở thành một phần của khóa chung. Trong § 12.5, chúng tôi thảo luận chi tiết về phương pháp chọn các số nguyên tố chính và lựa chọn này liên quan như thế nào đến độ tin cậy của hệ thống.

Một tin nhắn (có thể được coi là một số nguyên) được mã hóa bằng cách nâng nó lên một modulo lũy thừa nào đó. Do đó, trước tiên chúng ta phải tìm cách biểu diễn văn bản của tin nhắn dưới dạng danh sách các lớp modulo. quá trình mã hóa, nhưng chỉ chuẩn bị tin nhắn để nó có thể được mã hóa.

Để đơn giản, giả sử rằng nội dung tin nhắn chỉ chứa các từ được viết bằng chữ in hoa. Vì vậy, tin nhắn cuối cùng là một chuỗi các chữ cái và dấu cách. Bước đầu tiên là thay thế từng chữ cái trong tin nhắn bằng một số được chọn từ bảng sau:

(xem bản quét)

Khoảng cách giữa các từ được thay thế bằng số 99. Thực hiện thủ tục này, chúng ta sẽ nhận được một số, có thể rất lớn nếu tin nhắn dài. Tuy nhiên, đây không phải là con số cuối cùng mà chúng ta đang hướng tới mà chỉ là một tập hợp các lớp modulo. Và bây giờ chúng ta cần chia cách biểu diễn số của thông điệp thành từng phần, mỗi phần là một số tự nhiên không vượt quá. Những phần này thường được gọi là. khối tin nhắn.

Ví dụ: biểu diễn bằng số của phương châm “BIẾT BẢN THÂN” trông như thế này:

Bằng cách chọn những cái đơn giản, chúng ta sẽ có được sản phẩm. Do đó, biểu diễn số của thông điệp được viết ở trên phải được chia thành các khối nhỏ hơn 23.393.

Tất nhiên, việc lựa chọn các khối không phải là rõ ràng, nhưng cũng không hoàn toàn tùy tiện. Ví dụ, để tránh sự mơ hồ ở giai đoạn

việc giải mã không được làm nổi bật các khối bắt đầu bằng 0.

Khi giải mã tin nhắn được mã hóa bằng hệ thống mã hóa RSA, sẽ thu được một chuỗi các khối. Sau đó chúng được kết nối với nhau để tạo ra một biểu diễn số của thông điệp. Và chỉ sau khi thay số bằng chữ cái theo bảng trên thì mới đọc được tin nhắn gốc.

Xin lưu ý rằng mỗi chữ cái trong bảng được mã hóa bằng một số có hai chữ số. Điều này được thực hiện để ngăn chặn sự nhầm lẫn. Giả sử chúng ta đánh số các chữ cái theo thứ tự, bắt đầu bằng 1, tức là A tương ứng với 1, B tương ứng với 2, v.v. Trong trường hợp này, chúng ta sẽ không thể nói chắc chắn liệu khối 12 đại diện cho một cặp chữ cái hay chỉ một chữ cái, chữ cái thứ mười hai trong bảng chữ cái. Tất nhiên, để biểu diễn tin nhắn bằng số, bạn có thể sử dụng bất kỳ sự tương ứng một-một nào giữa các chữ cái và số, chẳng hạn như -mã hóa, trong đó việc dịch tin nhắn sang dạng kỹ thuật số được máy tính tự động thực hiện.

§ 12.2. Mã hóa và giải mã

Một thông báo được chuẩn bị để mã hóa bằng phương pháp § 12.1 bao gồm một chuỗi các khối, mỗi khối có số lượng nhỏ hơn một số. Bây giờ hãy thảo luận về cách mỗi khối được mã hóa. Để làm điều này, chúng ta cần một số bằng tích của các số nguyên tố và một số tự nhiên, modulo khả nghịch, tức là số thỏa mãn điều kiện

Chúng ta hãy nhớ lại rằng từ p và q đã biết, số này có thể được tính toán dễ dàng. Thật sự,

Cặp này được gọi là khóa công khai hoặc khóa mã hóa của hệ thống mật mã RSA mà chúng tôi đang mô tả. Đặt khối tin nhắn, tức là một số nguyên thỏa mãn bất đẳng thức. Chúng ta sẽ dùng ký hiệu để biểu thị khối tin nhắn được mã hóa tương ứng với nó được tính theo quy tắc sau:

Lưu ý rằng mỗi khối tin nhắn được mã hóa riêng biệt. Do đó, một tin nhắn được mã hóa thực sự bao gồm các khối được mã hóa riêng biệt. Hơn nữa, chúng tôi không thể kết hợp các khối này thành một số lớn, vì điều này sẽ khiến tin nhắn không thể giải mã được. Chúng ta sẽ sớm thấy lý do cho việc này.

Hãy quay lại ví dụ mà chúng ta đã bắt đầu xem xét trong đoạn đầu tiên. Chúng tôi đã sửa để Bây giờ chúng tôi cần chọn một số Hãy nhớ lại rằng nó phải nguyên tố cùng nhau Số nguyên tố nhỏ nhất không chia hết 23088 bằng 5. Hãy đặt Để mã hóa khối tin nhắn đầu tiên từ § 12.1, chúng tôi có để xác định phép trừ của số 25245 modulo 23393. Bằng cách sử dụng chương trình tính toán ký hiệu (hoặc máy tính, nếu bạn đủ kiên nhẫn), chúng ta sẽ nhận được rằng số khấu trừ cần thiết là 22.752. Vì vậy, tin nhắn được mã hóa được biểu thị bằng chuỗi khối sau đây. :

Hãy xem cách giải mã các khối tin nhắn được mã hóa. Để bắt đầu giải mã, chúng ta cần biết phần tử nghịch đảo của modulo. Phần tử cuối cùng trong số chúng là một số tự nhiên, chúng ta sẽ biểu thị bằng Cặp được gọi là khóa bí mật hoặc khóa giải mã của hệ thống mã hóa RSA. Nếu a là một khối tin nhắn được mã hóa thì việc giải mã tương ứng của nó

Kết quả của hoạt động là:

Trước khi quay lại ví dụ, cần có một số nhận xét. Thứ nhất, rất dễ tính toán nếu bạn biết Thật vậy, khóa bí mật được xác định bằng thuật toán Euclide mở rộng. Thứ hai, nếu khối đó là tin nhắn gốc thì chúng ta có quyền mong đợi sự bình đẳng. Nói cách khác, khi giải mã một khối tin nhắn được mã hóa, chúng ta hy vọng tìm ra khối tương ứng của tin nhắn gốc. Thực tế là trường hợp này không diễn ra trực tiếp từ thuật toán được mô tả ở trên, nhưng chúng ta sẽ thảo luận chi tiết mọi thứ trong đoạn tiếp theo.

Cuối cùng, như chúng tôi đã lập luận trong phần giới thiệu và xuyên suốt cuốn sách, để phá vỡ một hệ thống mật mã RSA, bạn cần phân tích nó thành nhân tử vì bạn cần biết cách giải mã thông điệp. Tuy nhiên, một khi hoạt động của hệ thống được mô tả chi tiết, rõ ràng là như vậy. tuyên bố sau không hoàn toàn chính xác. Để đọc mã hóa, ngoài chính phần tử đó, bạn chỉ cần biết nghịch đảo modulo của phần tử. Do đó, để hack hệ thống, việc tính toán với đã biết là đủ. Hóa ra phép tính này tương đương với việc phân tích một số. , như chúng ta sẽ thấy trong § 12.4.

Trong ví dụ đang thảo luận, chúng tôi áp dụng thuật toán Euclide mở rộng cho các số và 5 để xác định.

(xem bản quét)

Do đó, nghịch đảo của 5 modulo sẽ là -9235 và

Số tự nhiên nhỏ nhất có thể so sánh với -9235 modulo Vì vậy, để giải mã một khối tin nhắn được mã hóa, chúng ta phải nâng nó lên lũy thừa 13,853 modulo 23,393. Trong ví dụ của chúng ta, khối được mã hóa đầu tiên là 22,752. Tính toán trừ của số 22. 75213853 modulo 23,393 , chúng tôi nhận được Lưu ý rằng ngay cả với những con số nhỏ như vậy, yêu cầu để vận hành hệ thống mật mã RSA vẫn vượt quá khả năng của hầu hết các máy tính bỏ túi.

§ 12.3. Tại sao nó hoạt động?

Như chúng tôi đã lưu ý trước đó, các bước được mô tả ở trên dẫn đến một hệ thống mật mã hoạt động chỉ khi sau khi giải mã từng khối của thông điệp được mã hóa, khối tương ứng của khối ban đầu được khôi phục. Giả sử rằng chúng ta đang xử lý một hệ thống RSA có khóa chung và khóa riêng. Sử dụng ký hiệu của § 12.2, chúng ta cần chỉ ra rằng đối với bất kỳ số nguyên nào thỏa mãn bất đẳng thức thì danh tính đúng.

Thực tế chỉ cần chứng minh điều đó là đủ

Thật vậy, cả số nguyên 6 và số nguyên không âm đều nhỏ hơn. Do đó, chúng có thể so sánh được về giá trị tuyệt đối khi và chỉ khi chúng bằng nhau. Đặc biệt, điều này giải thích lý do tại sao chúng tôi chia cách biểu diễn số của thông báo thành các khối nhỏ hơn. Hơn nữa, có thể thấy từ điều này là khối.

Thông điệp được mã hóa phải được viết riêng: nếu không lý luận của chúng ta sẽ không hiệu quả.

Từ công thức mã hóa và giải mã, nó suy ra rằng

Vì các phần tử nghịch đảo nhau về mô đun nên tồn tại một k tự nhiên sao cho hơn nữa, theo điều kiện, các số này lớn hơn. Do đó, thay thế tích trong phương trình (3.1), ta thu được.

Bây giờ chúng ta hãy sử dụng định lý Euler, trong đó phát biểu rằng Do đó, tức là

và lẽ ra chúng ta đã hoàn toàn có được bằng chứng nếu không có một sai sót nhỏ nào lọt vào đó.

Nếu bạn cẩn thận xem lại lập luận của chúng tôi một lần nữa, bạn sẽ nhận thấy rằng chúng tôi đã không tính đến các điều kiện của định lý Euler. Trên thực tế, trước khi áp dụng định lý, cần phải đảm bảo rằng các số là nguyên tố chung. Điều này có vẻ như cần phải được theo dõi khi chuẩn bị một thông điệp để mã hóa, tức là. Khi chia biểu diễn số của một thông báo thành các khối, bạn cần đảm bảo rằng tất cả các khối kết quả là nguyên tố cùng nhau. May mắn thay, điều này là không cần thiết, vì trên thực tế, việc so sánh được thực hiện cho bất kỳ khối nào. Và lỗi không nằm ở kết quả mà chúng ta muốn chứng minh mà chỉ nằm ở chính chứng minh đó. Cách tiếp cận đúng dựa trên cơ sở lập luận được sử dụng để chứng minh định lý Corcelt trong Chương 7.

Hãy nhớ lại rằng các số nguyên tố khác nhau ở đâu. Hãy xác định phần dư của một số modulo Vì

các phép tính cho cả hai số nguyên tố đều giống nhau, chúng ta sẽ chỉ giải quyết trường hợp này một cách chi tiết.

đối với một số nguyên Do đó,

Bây giờ chúng ta muốn áp dụng định lý Fermat, nhưng chúng ta chỉ có quyền làm điều này nếu nó không chia. Hãy để yêu cầu này được thỏa mãn. Sau đó, chúng tôi nhận được điều đó

Bằng cách thay thế định lý Fermat bằng định lý Euler, chúng ta đã không giải quyết được vấn đề nảy sinh: phép so sánh chỉ đúng với một số khối chứ không phải cho tất cả các khối. Tuy nhiên, bây giờ các khối mà lý luận không hoạt động phải được chia cho Xa hơn, nếu nó chia thì cả 6 và có thể so sánh với 0 về mô đun và do đó có thể so sánh được với nhau. Vì vậy, sự so sánh được chứng minh cũng có giá trị trong trường hợp này. Do đó, phép so sánh đúng với mọi số nguyên. Lưu ý rằng chúng tôi không đúng. lẽ ra có thể sử dụng cách suy luận tương tự khi áp dụng định lý Euler vào Thực tế, bất đẳng thức không có nghĩa là so sánh vì số này là hợp số.

Vì vậy, chúng ta đã chứng minh rằng So sánh cũng được chứng minh tương tự. Nói cách khác, chia cả cho và Nhưng là các số nguyên tố khác nhau, do đó, bổ đề từ § 3.6 đảm bảo cho chúng ta rằng A chia hết vì chúng ta có với bất kỳ số nguyên nào. Nói cách khác, As chúng ta đã lưu ý ở đầu đoạn văn, điều này đủ để chứng minh đẳng thức vì cả hai phần của nó đều là những số nguyên không âm nhỏ hơn. Tóm lại, chúng ta có thể nói rằng

thuật toán của đoạn trước dẫn đến một hệ thống mật mã thực tế. Bây giờ bạn cần chắc chắn rằng nó đáng tin cậy.

§ 12.4. Tại sao hệ thống lại đáng tin cậy?

Hãy nhớ lại rằng RSA là một hệ thống mã hóa có khóa chung bao gồm tích của nhiều số nguyên tố khác nhau và một số tự nhiên khả nghịch theo modulo. Chúng ta hãy xem xét kỹ những gì có thể làm để bẻ khóa RSA nếu tất cả những gì được biết chỉ là một cặp.

Để giải mã một khối được mã hóa bằng RSA, chúng ta phải biết nghịch đảo của modulo k. Vấn đề là hầu như cách duy nhất được biết để làm điều này là dựa trên việc áp dụng thuật toán Euclide mở rộng. Tuy nhiên, để tính toán bằng công thức từ § 9.4, chúng ta cần biết điều gì xác nhận tuyên bố ban đầu: Phá vỡ RSA yêu cầu nhân tố hóa. Và vì những khó khăn trong việc phân rã là cơ bản nên hệ thống RSA an toàn.

Tất nhiên, người ta có thể cho rằng một ngày nào đó ai đó sẽ khám phá ra một thuật toán tính toán mà không cần thông tin về các thừa số của một số, chẳng hạn, điều gì sẽ xảy ra nếu ai đó nghĩ ra một cách hiệu quả để xác định trực tiếp bằng thực tế, đây chỉ là. một phương pháp mở rộng trá hình Chính xác hơn là, nếu

đã biết thì chúng ta có thể dễ dàng tính được.

vậy tổng các ước số nguyên tố cần tìm đã biết. Hơn nữa,

do đó sự khác biệt cũng được biết đến. Bây giờ, bằng cách giải một hệ phương trình tuyến tính đơn giản, chúng ta có thể dễ dàng tìm ra hệ số hóa.

Điều này có nghĩa là thuật toán tính toán thực sự phân tách số thành các thừa số, do đó, nó rất dễ dàng. Nhưng còn quá sớm để bình tĩnh lại. Bạn có thể đi xa hơn trong tưởng tượng của mình và cho rằng ai đó đã phát minh ra một thuật toán xác định trực tiếp bởi Nhưng vì vậy, nếu chúng ta biết, thì chúng ta biết số đó là bội số của nó. Hóa ra thông tin đó cũng đủ để phân tách. Một thuật toán xác suất dẫn đến sự phân rã như vậy có thể được tìm thấy V . Bài tập 7 trình bày một thuật toán phân rã tương tự (nhưng đơn giản hơn) với giả định rằng hệ thống mật mã Rabin có thể bị phá vỡ. Nó sẽ cho bạn ý tưởng về thuật toán xác suất từ .

Vẫn còn khả năng cuối cùng để hack: nỗ lực khôi phục khối trực tiếp bằng dư lượng modulo. Nếu nó đủ lớn thì việc tìm kiếm có hệ thống tất cả các ứng cử viên có thể cho việc tìm kiếm là lối thoát duy nhất. Chưa có ai nghĩ ra điều gì tốt hơn. Chúng tôi đã liệt kê các lập luận chính giải thích tại sao việc phá vỡ hệ thống mật mã RSA được coi là tương đương với việc phân tích nhân tử, mặc dù chưa có bằng chứng chắc chắn nào cho tuyên bố này.

§ 12.5. Lựa chọn những điều đơn giản

Từ cuộc thảo luận trước đó, để đảm bảo an toàn cho hệ thống mật mã RSA, điều quan trọng là phải chọn đúng số nguyên tố. Đương nhiên, nếu chúng nhỏ thì hệ thống sẽ dễ dàng bị tấn công. Tuy nhiên, chỉ chọn những số lớn là chưa đủ. Thật vậy, ngay cả khi p và q rất lớn nhưng chênh lệch nhỏ thì tích của chúng có thể dễ dàng phân tích thành nhân tử bằng thuật toán Fermat (xem § 3.4).

Đây không phải là cuộc nói chuyện nhàn rỗi. Năm 1995, hai sinh viên tại một trường đại học ở Mỹ đã bẻ khóa một phiên bản RSA công khai. Điều này trở nên khả thi do sự lựa chọn kém các thừa số nguyên tố của hệ thống.

Mặt khác, RSA đã được sử dụng từ lâu và nếu các thừa số nguyên tố được chọn cẩn thận thì hệ thống thực sự trở nên khá đáng tin cậy. Vì vậy, bất kỳ lập trình viên mã hóa RSA nào cũng cần một phương pháp hiệu quả để chọn thành công các số nguyên tố.

Giả sử chúng ta muốn tạo một hệ thống mật mã RSA với khóa chung trong đó số nguyên có khoảng các chữ số. Trước tiên, hãy chọn một số nguyên tố có số ký tự nằm ở giữa, hãy tiến gần đến số đó. Hiện tại, kích thước khóa được khuyến nghị cho mục đích sử dụng cá nhân là 768 bit, tức là. phải dài khoảng 231 chữ số. Để xây dựng một số như vậy, chúng ta cần hai số đơn giản, gồm 104 và 127 chữ số. Xin lưu ý rằng các số nguyên tố được chọn theo cách này khá xa nhau, tức là Sử dụng thuật toán Fermat để phân rã trong tình huống này là không thực tế. Ngoài ra, chúng ta cần đảm bảo rằng không chỉ các thừa số nhỏ mà cả các thừa số lớn đều tham gia phân tích các số thành thừa số nguyên tố. Thật vậy, nếu không thì con số sẽ trở thành con mồi dễ dàng cho một số thuật toán phân rã nổi tiếng (xem). Bây giờ chúng ta hãy xem xét một phương pháp tìm số nguyên tố thỏa mãn các điều kiện đã nêu.

Đầu tiên chúng ta cần một kết quả đơn giản về phân bố của các số nguyên tố. Chúng ta hãy nhớ lại biểu thị số lượng số nguyên tố không vượt quá x. Cho định lý số nguyên tố, ta thấy rằng với x lớn thì số đó xấp xỉ bằng logarit tự nhiên

trên cơ sở (xem § 4.5). Giả sử nó là một số rất lớn, một số dương nào đó. Chúng tôi muốn ước tính số lượng các số nguyên tố nằm giữa và ước tính sự khác biệt Nhờ định lý số nguyên tố và tính chất của logarit, hiệu xấp xỉ bằng.

Giả sử rằng nó rất nhỏ, chúng ta có thể giả sử giá trị bằng 0 và có được ước tính hợp lý về chênh lệch. Vì vậy, số lượng số nguyên tố nằm giữa xấp xỉ bằng nhau. Đương nhiên, ước tính càng chính xác thì x càng lớn. càng nhỏ để biết phần giới thiệu chi tiết hơn về ước tính đó, xem ([D. 10]).

Giả sử chúng ta cần chọn một số nguyên tố lân cận số nguyên x. Để xác định, chúng ta sẽ giả sử rằng x có cấp độ và chúng ta đang tìm một số nguyên tố trong khoảng từ x đến. Sẽ rất hữu ích nếu biết trước có bao nhiêu số nguyên tố trong khoảng này. Để ước tính số lượng số nguyên tố, bạn có thể sử dụng kết quả vừa thu được. Trong ví dụ của chúng tôi, giá trị có độ lớn rất nhỏ: Do đó, sử dụng công thức được viết ở trên, chúng tôi kết luận rằng khoảng cách giữa các điểm xấp xỉ

số nguyên tố. Ở cuối đoạn thứ hai của Chương 11, chúng tôi đã xây dựng một chiến lược được thiết kế để chứng minh tính nguyên tố của một số lẻ cho trước. Nó bao gồm ba bước.