Tiêu chuẩn quốc gia TCVN 12214-2:2018 (ISO/IEC 14888-2:2008 và đính chính kỹ thuật 1:2015) về Công nghệ thông tin - Các kỹ thuật an toàn - Chữ ký số kèm phụ lục - Phần 2: Các cơ chế dựa trên phân tích số nguyên

TIÊU CHUẨN QUỐC GIA

TCVN 12214-2:2018
ISO/IEC 14888-2:2008 VÀ ĐÍNH CHÍNH KỸ THUẬT 1:2015

CÔNG NGHỆ THÔNG TIN - CÁC KỸ THUẬT AN TOÀN - CHỮ KÝ SỐ KÈM PHỤ LỤC - PHẦN 2: CÁC CƠ CHẾ DỰA TRÊN PHÂN TÍCH SỐ NGUYÊN

Information technology - Security techniques - Digital signatures with appendix - Part 2: Integer factorization based mechanisms

Mục Lục

Lời nói đầu

1  Phạm vi áp dụng

2  Tài liệu viện dẫn

3  Thuật ngữ và định nghĩa

4  Ký hiệu và chữ viết tắt

5  Tổng quan

5.1  Các yêu cầu an toàn

5.2  Khóa kiểm tra

5.3  Kỹ thuật CRT

5.4  Biến đổi giữa xâu bit, số nguyên và chuỗi octet

6  Lược đồ RSA và RW

6.1  Yêu cầu các thành phần dữ liệu để ký/kiểm tra

6.2  Cơ chế ký

6.3  Cơ chế kiểm tra

6.4  Cơ chế định dạng

7  Lược đồ GQ1 (lược đồ dựa trên định danh)

7.1  Tập hợp các thành phần dữ liệu cần để ký/kiểm tra

7.2  Cơ chế ký

7.3  Cơ chế kiểm tra

7.4  Cơ chế định dạng

8  Lược đồ GQ2

8.1  Tập hợp các thành phần dữ liệu cần để ký/kiểm tra

8.2  Cơ chế ký

8.3  Cơ chế kiểm tra

9  Lược đồ GPS1

9.1  Tập hợp các thành phần dữ liệu cần để ký/kiểm tra

9.2  Cơ chế ký

9.2.1  Giới thiệu chung

9.2.2  Số ngẫu nhiên

9.2.3  Tạo coupon

9.2.4  Sử dụng coupon

9.3  Cơ chế kiểm tra

10  Lược đồ GPS2

10.1  Tập hợp các thành phần dữ liệu cần để ký/kiểm tra

10.2  Cơ chế ký

10.2.1  Giới thiệu chung

10.2.2  Số ngẫu nhiên

10.2.3  Tạo coupon

10.2.4  Sử dụng coupon

10.3  Cơ chế kiểm tra

11  Lược đồ ESIGN

11.1  Tập hợp các thành phần dữ liệu cần để ký/kiểm tra

11.2  Cơ chế ký

11.3  Cơ chế kiểm tra

11.4  Cơ chế định dạng

Phụ lục A  (Quy định) Định danh đối tượng

Phụ lục B  (Tham khảo) Hướng dẫn lựa chọn tham số và so sánh các lược đồ chữ ký

Phụ Lục C  (Tham khảo) Các ví dụ

Phụ lục D  (Tham khảo) Hai cơ chế định dạng khác nhau cho các lược đồ RSA/RW

Phụ lục E  (Tham khảo) Cho phép khôi phục lại thông điệp đối với các cơ chế kiểm tra RSA/RW

Phụ lục F  (Tham khảo) Cho phép xác thực hai lần đối với các lược đồ GQ/GPS

Thư mục tài liệu tham khảo

Lời nói đầu

TCVN 12214-2 : 2018 hoàn toàn tương đương với ISO/IEC 14888- 2:2008 và đính chính kỹ thuật 1:2015.

TCVN 12214-2 : 2018 do Cục Quản lý mật mã dân sự và Kiểm định sản phẩm mật mã biên soạn, Ban Cơ yếu Chính phủ đề nghị, Tổng cục Tiêu chuẩn Đo lường Chất lượng thẩm định, Bộ Khoa học và Công nghệ công bố.

Bộ tiêu chuẩn TCVN 12214 (ISO/IEC 14888) Công nghệ thông tin - Các kỹ thuật an toàn - Chữ ký số kèm phụ lục gồm các tiêu chuẩn sau:

- TCVN 12214-1 : 2018 (ISO/IEC 14888-1:2008) Phần 1: Tổng quan

- TCVN 12214-2 : 2018 (ISO/IEC 14888-2:2008) Phần 2: Các cơ chế dựa trên phân tích số nguyên

- TCVN 12214-3 : 2018 (ISO/IEC 14888-3:2016) Phần 3: Các cơ chế dựa trên logarit rời rạc

CÔNG NGHỆ THÔNG TIN - CÁC KỸ THUẬT AN TOÀN - CHỮ KÝ SỐ KÈM PHỤ LỤC - PHẦN 2: CÁC CƠ CHẾ DỰA TRÊN PHÂN TÍCH SỐ NGUYÊN

Information technology - Security techniques - Digital signatures with appendix - Part 2: Integer factorization based mechanisms

1  Phạm vi áp dụng

Tiêu chuẩn này quy định chữ ký số kèm phụ lục với độ an toàn dựa trên độ khó của phân tích số theo mô-đun. Với mỗi lược đồ chữ ký, quy định:

a) Mối quan hệ và ràng buộc giữa tất cả các thành phần dữ liệu được yêu cầu để ký và kiểm tra;

b) Cơ chế ký, tức là cách để tạo ra chữ ký của một thông điệp với các thành phần dữ liệu được yêu cầu để ký;

c) Cơ chế kiểm tra, tức là cách để kiểm tra chữ ký của một thông điệp với các thành phần dữ liệu được yêu cầu để kiểm tra.

Việc tạo các cặp khóa yêu cầu bit ngẫu nhiên và số nguyên tố. Quá trình tạo chữ ký thường yêu cầu bit ngẫu nhiên. Các kỹ thuật sinh các bit ngẫu nhiên và các số nguyên tố nằm ngoài phạm vi tiêu chuẩn này. Để biết thêm thông tin, xem ISO/IEC 18031 [33] và ISO/IEC 18032 [34].

Có nhiều cách khác nhau để có được một bản sao tin cậy của khóa kiểm tra công khai, ví dụ: một chứng thư khóa công khai. Kỹ thuật quản lý khóa và chứng thư nằm ngoài phạm vi tiêu chuẩn này. Để biết thêm thông tin, xem ISO/IEC 9594-8 [27], ISO/IEC 11770 [31] và ISO/IEC 15945 [32].

2  Tài liệu viện dẫn

Các tài liệu viện dẫn sau rất cần thiết cho việc áp dụng tiêu chuẩn này. Đối với các tài liệu viện dẫn ghi năm công bố thì áp dụng phiên bản được nêu. Đối với các tài liệu viện dẫn không ghi năm công bố thì áp dụng phiên bản mới nhất, bao gồm cả các sửa đổi, bổ sung (nếu có).

TCVN 11816 (ISO/IEC 10118) (Tất cả các phần), Công nghệ thông tin - Các kỹ thuật an toàn - Hàm băm.

TCVN 12214-1 (ISO/IEC 14888-1), Công nghệ thông tin - Kỹ thuật an toàn - Chữ ký số kèm phụ lục - Phần 1: Tổng quan.

3  Thuật ngữ và định nghĩa

Với mục đích của tiêu chuẩn này, các thuật ngữ và định nghĩa trong phần 1 tiêu chuẩn này và dưới đây được áp dụng:

3.1

Mô-đun (modulus)

Số nguyên với phân tích số được giữ bí mật và không thể tính toán được các thừa số nguyên tố của số đó.

3.2

Giá trị đặc trưng (representative)

Xâu bit được tạo ra bằng một cơ chế định dạng.

3.3

Salt (salt)

Xâu bit tùy chọn để tạo ra một giá trị đặc trưng.

3.4

Số mũ ký (signature exponent)

Số mũ bí mật để tạo chữ ký.

3.5

Trailer (trailer)

Xâu bit tùy chọn nằm bên phải của một giá trị đặc trưng.

3.6

Số mũ kiểm tra (verification exponent)

Số mũ công khai để kiểm tra thông điệp được ký và cũng có khi được dùng để tạo ra chữ ký.

4  Ký hiệu và chữ viết tắt

Trong tiêu chuẩn này áp dụng các ký hiệu và chữ viết tắt dưới đây:

5  Tổng quan

5.1  Các yêu cầu an toàn

Cơ chế chữ ký sử dụng một tập các thành phần dữ liệu bắt buộc để ký. Tập hợp này bao gồm khóa ký riêng của người ký, được gọi đơn giản là “khóa ký” trong tiêu chuẩn này của bộ tiêu chuẩn. Một số thành phần dữ liệu của khóa ký phải được giữ bí mật (ít nhất phải giữ bí mật một thành phần dữ liệu).

CHÚ THÍCH Mọi thành phần dữ liệu bí mật phải được lưu trong một thiết bị phần cứng hoặc phần mềm dưới sự kiểm soát của người ký tránh kẻ tấn công có thể lấy cắp được. Các thẻ mạch điện tử tích hợp [24] có thể sử dụng để tạo chữ ký. Cấu hình bảo vệ cho các thiết bị tạo chữ ký nằm ngoài phạm vi tiêu chuẩn này của bộ tiêu chuẩn này.

Quá trình tạo chữ ký RSA và RW chỉ mang tính xác suất khi và chỉ khi mọi chữ ký yêu cầu một giá trị salt mới. Quá trình tạo chữ ký GQ1, GQ2, GPS1, GPS2 và ESIGN hoàn toàn mang tính xác suất. Khi quá trình tạo chữ ký mang tính xác suất, thì mọi người ký phải có phương pháp để chọn các bit ngẫu nhiên.

Cơ chế kiểm tra sử dụng một tập hợp các thành phần dữ liệu bắt buộc để kiểm tra, tất cả dữ liệu này phải được công khai trên miền.

• Mọi thành phần dữ liệu công khai dùng chung cho tất cả người ký được gọi là tham số miền.

• Mọi thành phần dữ liệu công khai đặc trưng cho một người ký duy nhất là một phần của khóa kiểm tra công khai của người ký, được gọi đơn giản là “khóa kiểm tra” trong tiêu chuẩn này của bộ tiêu chuẩn này.

Với một tên miền đã cho, mọi người kiểm tra đều biết được tập hợp các tham số miền và nhận được một bản sao tin cậy của khóa kiểm tra của người ký.

Người ký và người kiểm tra phải đảm bảo đầy đủ rằng tập hợp các tham số miền là hợp lệ, tức là nó thỏa mãn các ràng buộc cụ thể trong lược đồ. Ngược lại, sẽ không có đảm bảo nào về độ an toàn ngay cả khi thông điệp đã ký được chấp nhận. Sự đảm bảo này có được bằng nhiều cách, bao gồm một hoặc nhiều cách sau:

a) Lựa chọn một tập hợp các giá trị từ một nguồn công khai tin cậy, ví dụ: một tiêu chuẩn quốc tế;

b) Tạo ra một tập hợp các giá trị bởi bên thứ ba tin cậy, ví dụ: một tổ chức cung cấp chứng thư số [27];

c) Xác nhận một tập hợp các giá trị bởi bên thứ ba tin cậy, ví dụ: một tổ chức cung cấp chứng thư số [27];

d) Đối với người ký, tạo ra một tập hợp các giá trị bởi một hệ thống tin cậy;

e) Đối với người ký và người kiểm tra, xác nhận một tập hợp các giá trị.

Người ký và người kiểm tra phải đảm bảo đầy đủ rằng khóa kiểm tra là hợp lệ, tức là nó thỏa mãn các ràng buộc cụ thể trong lược đồ. Sự đảm bảo này có được bằng nhiều cách, bao gồm một hoặc nhiều cách sau:

a) Truy cập tới một thư mục hoặc kiểm tra một chứng thư;

b) Một giao thức kiểm tra khóa hoạt động với khóa kiểm tra và có thể là các thông tin khác liên quan đến sự tương tác với phần cứng hoặc phần mềm tạo chữ ký;

c) Tin tưởng vào lời khẳng định của bên thứ ba về việc đảm bảo rằng khóa kiểm tra là hợp lệ;

d) Tin tưởng rằng quá trình tạo khóa được thực hiện hoàn toàn chính xác.

Các giao thức và phương pháp kiểm tra khóa cụ thể để thu thập và chuyển tải sự đảm bảo tính hợp lệ của khóa nằm ngoài phạm vi tiêu chuẩn này của bộ tiêu chuẩn này.

Độ an toàn của mọi lược đồ chữ ký được quy định trong tiêu chuẩn này phụ thuộc vào một số mô-đun và một hàm băm.

• Số mô-đun là an toàn (tức là kháng phân tích số) khi giá trị phân tích số không bị lộ. Khi sử dụng lược đồ, không có chủ thể nào có khả năng phân tích số mô-đun đang được sử dụng.

• Hàm băm sử dụng là một trong những hàm băm được quy định trong TCVN 11816:2017 (ISO/IEC 10118); Nó có khả năng kháng va chạm.

5.2  Khóa kiểm tra

Bảng 1 tổng hợp các khóa kiểm tra (xem 6.1, 7.1, 8.1, 9.1, 10.1 và 11.1).

Bảng 1 - Các khóa kiểm tra

Mọi lược đồ chữ ký được đặc tả trong tiêu chuẩn này sử dụng một mô-đun, ký hiệu là n.

• Trong lược đồ RSA, RW, GQ2, GPS2 và ESIGN, khóa kiểm tra bao gồm n.

• Trong lược đồ GQ1 và GPS1, các tham số miền hoặc khóa kiểm tra bao gồm n.

CHÚ THÍCH Thời hạn sử dụng một giá trị mô-đun cho trước thường bị giới hạn trong một khoảng thời gian nhất định trong một miền nhất định.

Để quy định độ lớn bit của mô-đun được sử dụng, các tham số miền hoặc khóa kiểm tra sẽ bao gồm một thành phần dữ liệu, ký hiệu là α. Nếu không quy định về α, thì giá trị mặc định của α được thiết lập bằng độ lớn bit của mô-đun được sử dụng (nghĩa là không quy định về kích thước mô-đun).

Trong lược đồ GPS1, khóa kiểm tra bao gồm một số công khai được sử dụng, ký hiệu là G.

Để tương thích với cơ sở hạ tầng khóa công khai đã được triển khai, ngay cả khi tất cả những người ký sử dụng cùng một giá trị trong miền, khóa kiểm tra có thể bao gồm:

- Số mũ kiểm tra được dùng, ký hiệu là v trong lược đồ RSA, RW, GQ1, GPS2 và ESIGN;

- Số mô-đun được dùng, ký hiệu là n trong lược đồ GQ1 và GPS1.

Mọi lược đồ chữ ký quy định trong tiêu chuẩn này sử dụng hàm băm, ký hiệu là h.

• Trong lược đồ RSA, RW và ESIGN, một cơ chế định dạng sử dụng hàm h để chuyển đổi thông điệp thành giá trị đặc trưng và kiểm tra giá trị đặc trưng sau khi được khôi phục lại.

• Trong lược đồ GQ1, một cơ chế định dạng sử dụng hàm h để chuyển đổi những chuỗi dữ liệu định danh thành các số công khai và một biến thể băm sử dụng hàm h để tạo ra các xâu bit.

• Trong lược đồ GQ2, GPS1 và GPS2, một biến thể băm sử dụng hàm h để tạo ra các xâu bit.

Để xác định hàm băm đang được sử dụng, các tham số miền hoặc khóa kiểm tra sẽ bao gồm một thành phần dữ liệu, ký hiệu là Indic(h).

Tiêu chuẩn này đặc tả ba cơ chế định dạng (PSS trong mục 6.4, 7.4 và 11.4; D1 và D2 trong phụ lục D). Mỗi cơ chế định dạng sử dụng hai tham số, ký hiệu là ɛ và t. Nhận giá trị 0,64 hoặc |H|, ε cho biết độ dài bit của giá trị salt. Nhận giá trị 0,8 hoặc 16, t cho biết độ dài bit của giá trị trailer.

Tiêu chuẩn này đặc tả bốn biến thể băm, trong đó W ký hiệu một xâu bit và M là một thông điệp.

Để xác định cơ chế định dạng đang được sử dụng, cùng với những giá trị tùy chọn ε và t đang dùng, và/hoặc biến thể băm đang sử dụng, các tham số miền hoặc khóa kiểm tra có thể bao gồm một hoặc hai thành phần dữ liệu, ký hiệu là Indic(format, ε, t) và Indic(variant) nếu cần.

Khóa ưu tiên - Khi các tham số miền và khóa kiểm tra bao gồm thành phần dữ liệu tương tự nhau với những giá trị khác nhau, thì khóa kiểm tra có quyền ưu tiên hơn.

CHÚ THÍCH Trong một miền nhất định, do có khóa ưu tiên, những người ký khác nhau có thể sử dụng các hàm băm khác nhau và/hoặc các kích thước mô-đun khác nhau.

5.3  Kỹ thuật CRT

Xem xét hai số nguyên x₁ và x₂ là hai số nguyên tố cùng nhau, nhưng không cần là số nguyên tố. Theo định nghĩa, hệ số CRT của x₁ và x₂, ký hiệu là Cr là một số nguyên dương duy nhất, nhỏ hơn x₁, sao cho Cr x x₂ - 1 là bội số của x₁.

Số nguyên bất kỳ X thuộc {0,1... x₁ × x₂ - 1} có thể được phân tích thành cặp duy nhất các thành phần X₁ = X mod x₁ nhận giá trị từ {0,1... x₁ - 1} và X₂ = X mod x₂ nhận giá trị từ {0,1... x₂ -1}.

Hợp số CRT là giá trị nghịch đảo của phân tích ở trên. Sử dụng ba số nguyên x₁,x₂ và Cr để biến đổi hai thành phần X₁ nhận giá trị từ {0,1... x₁ - 1} và X₂ nhận giá trị từ {0,1... x₂ - 1} thành số nguyên duy nhất X nhận giá trị từ {0,1... x₁ x x₂ - 1} sao cho X₁ = X mod x₁ và X₂ = X mod x₂.

Y = X₁ - X₂ mod x₁; Z = Y x Cr mod x₁; X = Z x x₂ + X₂

Lần lượt biến đổi ba thành phần X₁ từ {0,1... x₁ - 1}, X₂ từ {0,1... x₂ - 1} và X₃ từ {0,1... x₃ - 1}, trong đó x₁, x₂ và x₃ nguyên tố cùng nhau từng đôi một, thành số nguyên duy nhất X nhận giá trị từ {0,1... x₁ x x₂ x x₃ - 1} thỏa mãn X₁ = X mod x₁, X₂ = X mod x₂ và X₃ = X mod x₃, hợp số CRT được sử dụng hai lần:

1) để tính toán T nhận giá trị từ {0,1... x₁ x x₂ - 1} sao cho X₁ = T mod x₁ và X₂ = T mod x₂;

2) để tính toán X nhận giá trị từ {0,1... x₁ x x₂ x x₃ - 1} sao cho T = X mod x₁ x x₂ và X₃ = X mod x₃.

Khi biết các thừa số nguyên tố của n (xem mục 6.2, 7.1, 8.1, 8.2, 9.1, 9.2.2 và 10.2.2), kỹ thuật CRT làm giảm độ phức tạp của tính toán số học mod n (xem B.2.3). Thay vì tính toán trực tiếp kết quả cuối cùng nhận giá trị từ {0,1 ...n - 1}, sẽ tính toán một tập hợp các thành phần sau đó biến đổi thành kết quả cuối cùng.

CHÚ THÍCH Hiệu quả của kỹ thuật CRT sẽ tăng theo số lượng các thừa số nguyên tố khác nhau.

5.4  Biến đổi giữa xâu bit, số nguyên và chuỗi octet

Một xâu bit, ký hiệu là D, bao gồm |D| bit trong đó giá trị của mỗi bit là 0 hoặc 1; các bit được đánh số theo thứ tự từ bit trái nhất, ký hiệu là d₁, đến bit phải nhất, ký hiệu là d_|D|.

D = d₁d₂d₃ ... d_|D|-1 d_|D|

Để chuyển đổi D thành một số nguyên, ký hiệu là A, bit trái nhất, ký hiệu là d₁, là bit có trọng số cao nhất và bit phải nhất, ký hiệu là d_|D| là bit có trọng số thấp nhất.

A = 2^|D|-1 x d₁ + 2^|D|-2 x d₂ +...+ 2² x d_|D|-2 + 2 x d_|D|-1 + d_|D|

Độ lớn bit của số nguyên A, ký hiệu là |A| (nghĩa là 2^|A|-1 ≤ A ≤ 2^|A| nếu A > 0, do đó 0 ≤ A < 2^|D|), bằng |D| nếu d₁ = 1, hoặc nhỏ hơn |D| nếu d_{1 =} 0. Biểu diễn nhị phân của số nguyên A bằng một xâu bit có độ dài lớn hơn |A| là xâu bit duy nhất mà khi biến đổi thành số nguyên thì cho giá trị bằng A.

Khi độ dài bit của một xâu là bội số của 8, xâu bit có thể dễ dàng biểu diễn bằng một xâu octet trong đó mỗi octet có giá trị từ “00” đến “FF” trong ký hiệu hệ tập lục phân. Trong một xâu octet, octet được đánh số thứ tự từ octet trái nhất đến octet phải nhất. Để biến đổi một xâu octet thành một số nguyên, octet trái nhất là octet có trọng số cao nhất và octet phải nhất là octet có trọng số thấp nhất.

6  Lược đồ RSA và RW

6.1  Yêu cầu các thành phần dữ liệu để ký/kiểm tra

Các quan hệ và ràng buộc chuỗi được áp dụng cho các thành phần dữ liệu sau:

• Số mũ kiểm tra;

• Tập hợp các thừa số nguyên tố khác nhau;

• Số mô-đun;

• Số mũ ký;

• Tập hợp các số mũ ký CRT.

Số mũ kiểm tra ký hiệu là v. Các giá trị v = 0 và v = 1 không được sử dụng.

CHÚ THÍCH Các giá trị v = 2,3 và 655537(= 2¹⁶ + 1) có những ưu điểm trong thực nghiệm.

Tập hợp các thừa số nguyên tố khác nhau ký hiệu là p_1,p₂ ...p_f được sắp xếp theo thứ tự tăng dần (f > 1).

Lược đồ RSA sử dụng số mũ kiểm tra lẻ. Có thể có nhiều hơn hai thừa số nguyên tố (f ≥ 2). Với i từ 1 đến f, v sẽ nguyên tố cùng nhau với p_i - 1, tức là gcd(v,p_i - 1) = 1.

Lược đồ RW sử dụng số mũ kiểm tra chẵn. Tiêu chuẩn này quy định giá trị v = 2, với chỉ hai thừa số nguyên tố (f = 2), cả hai đều đồng dư với 3 mod 4, nhưng không đồng dư với nhau mod 8.

Số mô-đun, ký hiệu là n là tích của các thừa số nguyên tố (n = p₁ x ... x p_f). Bộ lớn của nó là α bit.

Số mũ ký được ký hiệu là s, là số nguyên dương bất kỳ (thường sử dụng số nhỏ nhất) sao cho v x s - 1 là bội số của lcm(p₁ - 1,...,p_f - 1) nếu v là số lẻ, hoặc là bội số của lcm(p₁ - 1, p₂ - 1)/2 nếu v = 2.

Tập hợp các số mũ ký CRT ký hiệu là s₁ đến s_f. Với i từ 1 đến f, s_i là số nguyên dương bất kỳ (thường sử dụng số nhỏ nhất) sao cho v x s_i -1 là bội số của p_i - 1 nếu v là số lẻ, hoặc là bội số của (p_i - 1)/2 nếu v = 2.

CHÚ THÍCH Trong lược đồ RW, có một thừa số nguyên tố đồng dư với 3 mod 8 và một số khác đồng dư với 7 mod 8, n = 5 mod 8, , s₁ = (p₁ + 1) và s₂ = (p₂ + 1)/4.

Quá trình ký yêu cầu một hàm băm (xem mục 5.1), một cơ chế định dạng và một khóa ký. Khuyến nghị sử dụng cơ chế định dạng được quy định trong 6.4; nó sử dụng hai tham số, ký hiệu là ε và t. Khóa ký có hai dạng sau:

• Với CRT: p₁ đến p_f,f -1 hệ số CRT (xem mục 5.3) và s₁ đến s_f.

• Không có CRT: n và s (n công khai).

CHÚ THÍCH Cơ chế định dạng quy định trong mục 6.4 được tin tưởng là an toàn. Hai cơ chế định dạng quy định trong phụ lục D có giới hạn an toàn nhỏ hơn.

Quá trình kiểm tra yêu cầu một tập hợp các tham số miền và một khóa kiểm tra. Các tham số miền hoặc khóa kiểm tra sẽ bao gồm v và Indic(h), và có thể gồm cả α (mặc định α = |n|) và Indic(format, ε, t) (mặc định theo mục 6.4 với các giá trị tùy chọn ε = |H| và t = 8). Khóa kiểm tra bao gồm n.

6.2  Cơ chế ký

Cơ chế ký được minh họa trong hình 1 sử dụng một hàm băm, một cơ chế định dạng và một khóa ký để ký một thông điệp (một xâu bit, ký hiệu là M), nghĩa là tạo ra một chữ ký của M (một xâu bit, ký hiệu là S).

Hình 1 - Ký với RSA hoặc RW

Bước 1 - Chuyển đổi thông điệp M thành một giá trị đặc trưng γ = |n| bit, ký hiệu là F, theo cơ chế định dạng đang sử dụng. Xâu bit F biểu diễn một số, chia hết cho 4, cũng ký hiệu là F (0 < F < n).

Bước 2 - Tạo ra một số ký hiệu là G (0 < G < n).

• Nếu v là số lẻ thì G = F.

• Nếu v = 2, tính toán ký hiệu Jacobi (F|n) và biến đổi ký hiệu Jacobi (G|n) về +1.

○ Nếu (F|n) = +1, thì G = F.

○ Nếu (F|n) = -1, thi G = F/2.

○ Nếu (F|n) = 0 (trường hợp rất hiếm gặp), thì quá trình tạo số thất bại.

Tạo ra một số, ký hiệu là S bằng một trong hai cách sau:

• Với CRT, với i từ 1 đến f, tính G_i = G mod p_i và S_i = mod p_i. Số S là hợp số CRT (xem mục 5.3) S₁ đến S_f.

• Không sử dụng CRT, tính toán S - G^smod n.

Nếu v = 2, thì số S được thay thế bằng n - S.

Chữ ký là một xâu bit bất kỳ đại diện cho S, thường là một xâu gồm |n| bit và cũng ký hiệu là S.

6.3  Cơ chế kiểm tra

Cơ chế kiểm tra được minh họa trong hình 2 sử dụng một tập hợp của các tham số miền và một khóa kiểm tra (xem bảng 1), với khóa ưu tiên (xem mục 5.2) để kiểm tra một thông điệp và một chữ ký của thông điệp đó, tức là hai xâu bit, ký hiệu M và S.

Bước 0 - Loại bỏ nếu |n| ≠ α, hoặc nếu v = 0 hoặc 1, hoặc nếu n không đồng dư với 5 mod 8 khi v = 2.

Bước 1 - Xâu bit S biểu diễn một số, cũng ký hiệu là S. Loại bỏ nếu S = 0 hoặc 1, hoặc nếu S ≥ n - 1. Tính toán G* = S^vmod n.

Hình 2 - Kiểm tra với RSA hoặc RW

Bước 2 - Khôi phục lại giá trị đặc trưng, ký hiệu là F^*.

• Nếu v là một số lẻ, thì F^* là một xâu có độ dài |n| bit biểu diễn của G*.

• Nếu v = 2, F^* là một chuỗi có độ dài |n| bit biểu diễn:

○ G^* nếu G^* đồng dư với 4 mod 8,

○ n - G^* nếu G^* đồng dư với 1 mod 8;

○ 2G^* nếu G^* đồng dư với 6 mod 8;

○ 2(n - G^*) nếu G^* đồng dư với 7 mod 8.

○ Loại bỏ trong các trường hợp còn lại (Không biểu diễn được giá trị trailer).

Bước 3 - Kiểm tra giá trị đặc trưng F^* đã được khôi phục lại theo cơ chế định dạng sử dụng.

6.4  Cơ chế định dạng

Quá trình chuyển đổi thông điệp M sử dụng hai tham số (ε biểu thị độ dài của giá trị salt và t biểu thị độ dài giá trị trailer) thành một giá trị đặc trưng gồm γ bit, ký hiệu là F. Hình 3 minh họa cho cơ chế này.

Hình 3 - Tạo giá trị đặc trưng

1) Các tùy chọn như sau.

• Tùy chọn ε = 0. Giá trị salt là một xâu rỗng và quá trình tạo chữ ký là quá trình tất định.

• Tùy chọn ε = |H|. Giá trị salt, ký hiệu là E là một xâu gồm |H| bit ngẫu nhiên.

○ Nếu giá trị salt là giá trị cố định cho nhiều chữ ký, thì quá trình tạo chữ ký là quá trình tất định.

○ Nếu giá trị salt là một giá trị mới cho từng chữ ký, thì quá trình tạo chữ ký mang tính xác suất.

• Tùy chọn t = 8. Giá trị trailer là một octet đơn, đặt bằng “BC”.

• Tùy chọn t = 16. Giá trị trailer là hai octet liên tiếp: octet phải nhất được đặt bằng “CC”; octect trái nhất xác định hàm băm sử dụng. Octet trái nhất được biểu diễn như sau.

○ Giá trị từ “00” đến “7F” dành cho tiêu chuẩn ISO/IEC JTC 1 SC 27; ISO/IEC 10118 quy định một định danh duy nhất trong dãy giá trị đó cho từng hàm băm tiêu chuẩn, ví dụ: “31” đại diện cho hàm đầu tiên trong Phần 3, có tên gọi là RIPEMD-160 và “33” đại diện cho hàm thứ ba trong Phần 3, có tên gọi là SHA-1.

○ Giá trị từ “80” đến “FF” được dành cho trường hợp đặc biệt.

Trailer- Định danh hàm băm || “CC”.

CHÚ THÍCH Một số nghiên cứu [12] đặt câu hỏi về ưu điểm khi sử dụng định danh như trên trong giá trị trailer.

2) Băm M thành một xâu bit, ký hiệu là H. Từ trái sang phải, nối 8 octet có giá trị “00”, H và E. Băm chuỗi vừa nối thành một xâu bit, ký hiệu là HH.

3) Tạo ra một chuỗi gồm ít nhất γ - t - |H| bit từ HH theo các bước sau sử dụng hai biến: một xâu có độ dài tùy ý, ký hiệu là String, và một xâu 32 bit, ký hiệu là Counter.

a) Đặt String bằng một xâu rỗng.

b) Đặt Counter bằng 0.

c) Thay String bằng String||/h(HH||Counter).

d) Thay Counter bằng Counter + 1.

e) Nếu |H| x Counter < γ - t - |H|, thì quay lại bước c.

Tạo ra một giá trị mặt nạ với γ - t - |H| bit trái nhất của String trong đó bit trái nhất có giá trị bắt buộc bằng 0.

4) Tạo ra một xâu trung gian gồm γ - t - |H| bit được nối từ trái sang phải theo thứ tự như sau:

- γ - t - |H| - 1 - ε bit 0;

- Một bit giới hạn bằng 1;

- Giá trị salt E.

5) Áp dụng mặt nạ cho xâu trung gian, để tạo ra một xâu mặt nạ bằng cách thực hiện phép XOR.

6) Tạo ra F bằng cách nối xâu bit đã được tạo mặt nạ, HH và trailer theo thứ tự từ trái sang phải. Trả về F.

F = Xâu bit được tạo mặt nạ || HH || Trailer

Kiểm tra giá trị đặc trưng đã được khôi phục lại gồm γ bit, ký hiệu là F^* tương ứng với thông điệp M và sử dụng hai giá trị tùy chọn ε và t (được cho bởi khóa kiểm tra hoặc các tham số miền, hoặc là giá trị mặc định).

1) Kiểm tra giá trị trailer như sau.

- Nếu octet phải nhất của F^* có giá trị bằng “BC”, thì tùy chọn được khôi phục lại là t^* = 8.

- Nếu octet phải nhất của F^* có giá trị bằng “CC” và nếu octet bên trái của “CC” xác định hàm băm sử dụng, thì tùy chọn được khôi phục lại là t^* = 16.

- Loại bỏ trong các trường hợp còn lại (Không thể biểu diễn giá trị trailer) và khi t^* và t  khác nhau.

2) Chia γ - t  bit trái nhất của F^* thành hai phần: một xâu đã được tạo mặt nạ gồm γ - t - |H| bit nằm ở bên trái và xâu gồm |H| bit, ký hiệu là HH^* nằm ở bên phải.

3) Tạo mặt nạ gồm |n| - t - |H| bit từ HH^* giống bước 3 ở trên.

4) Áp dụng mặt nạ vào xâu đã được tạo mặt nạ, để khôi phục lại một xâu trung gian bằng cách Thực hiện phép XOR, trong đó bit giới hạn là bit đầu tiên có giá trị bằng 1 tính từ trái sang.

- Nếu còn lại ε bit ở bên phải của bit giới hạn trong xâu trung gian đã được khôi phục lại, thì tạo ra một xâu bit, ký hiệu là E^*.

- Ngược lại, thì loại bỏ.

5) Băm M thành một xâu bit, ký hiệu là H. Từ trái sang phải, nối 8 octet có giá trị “00”, H và E^*. Băm chuỗi vừa nối thành một xâu bit, ký hiệu là HH.

6) Chấp nhận hoặc loại bỏ tùy thuộc vào HH và HH* giống nhau hay khác nhau.

7  Lược đồ GQ1 (lược đồ dựa trên định danh)

7.1  Tập hợp các thành phần dữ liệu cần để ký/kiểm tra

CHÚ THÍCH Tập hợp các thừa số nguyên tố là giá trị bí mật của thực thể với số mô-đun công khai; Số mô-đun là tham số miền, hoặc một phần của khóa kiểm tra. Do đó, lược đồ có thể thực hiện bằng một trong hai cách sau.

1) Nếu số mô-đun là một tham số miền, thì thực thể tạo ra số mô-đun công khai là một tổ chức tin cậy cung cấp chứng thư số cung cấp cho mỗi người ký một số bí mật riêng, do đó đảm bảo chuỗi dữ liệu định danh của người ký. Ví dụ, nhà sản xuất thẻ điện tử tích hợp [24] có một số mô-đun.

• Đối với thẻ cá nhân, một chủ thể được ủy quyền sử dụng giá trị bí mật của nhà sản xuất để ký các chuỗi dữ liệu định danh; Trong mỗi thẻ, nó lưu trữ một chuỗi dữ liệu định danh và một số bí mật.

• Trong thời hạn sử dụng, thẻ điện tử sử dụng số bí mật theo kỹ thuật tri thức không.

2) Nếu số mô-đun là một phần của khóa kiểm tra, thì với mỗi phiên (session), người ký được cung cấp một số bí mật, do đó bảo đảm chuỗi dữ liệu định danh phiên. Trong một mạng cục bộ, một tổ chức cung cấp chứng thư số giám sát từng thao tác đăng nhập và quản lý một thư mục trong đó mỗi bên kiểm tra có thể nhận được một bản sao tin cậy của số mô-đun cho mọi chủ thể.

• Khi một máy tính kết nối tới mạng cục bộ, tức là, trong một thao tác đăng nhập, nó sử dụng giá trị bí mật của chủ thể tương ứng để tạo ra một số bí mật bằng cách đăng nhập một lần đối với một chuỗi dữ liệu định danh phiên.

• Trong phiên liên lạc, máy tính không thể sử dụng giá trị bí mật của chủ thể (một giá trị bí mật dài hạn) vì không biết gì về giá trị đó; nó sử dụng số bí mật theo kỹ thuật tri thức không, số bí mật (một giá trị bí mật ngắn hạn) chỉ có giá trị trong một vài giờ; nó mất giá trị sau phiên liên lạc.

Các quan hệ và ràng buộc chuỗi được áp dụng cho các thành phần dữ liệu sau:

• Số mũ kiểm tra và một tham số độ dài chữ ký;

• Tập hợp các thừa số nguyên tố khác nhau;

• Số mô-đun;

• Chuỗi dữ liệu định danh;

• Số công khai;

• Số bí mật.

Số mũ kiểm tra, ký hiệu là v là một số nguyên tố. Tham số độ dài chữ ký được ký hiệu là t. Tích (|v| - 1) x t nhỏ hơn hoặc bằng |H|.

CHÚ THÍCH Với (|v| - 1) x t = 80, các giá trị thường gặp của v và t là (2⁸⁰ +13,1), (2⁴⁰ + 15,2), (2²⁰ + 7,4), (2¹⁶ + 1,5).

Tập hợp các thừa số nguyên tố khác nhau ký hiệu là p₁,p₂ ...p_f được sắp xếp theo thứ tự tăng dần (f > 1)

Với i từ 1 đến f, v không chia hết cho p_i -1.

Số mô-đun, ký hiệu là n, là tích của các thừa số nguyên tố (n = p₁ x ... x p_f). Độ lớn của nó là α bit.

Quá trình tạo của mỗi người ký tuân thủ theo ba bước sau.

Bước 1 - Lựa chọn một chuỗi dữ liệu định danh, ký hiệu là Id. Nó là một xâu bit, xác định người ký duy nhất và hợp lệ theo một thỏa thuận có sẵn ở cấp độ miền.

CHÚ THÍCH Chuỗi dữ liệu định danh bao gồm một số tài khoản, số seri, ngày giờ hết hạn, các quyền của một định danh. Bắt buộc phải tuân theo thời hạn theo ngày và giờ hết hạn trong chuỗi; số seri giúp đơn giản hóa quá trình thu hồi.

Bước 2 - Chuyển đổi Id thành một giá trị đặc trưng gồm γ = |n| bit theo cơ chế định dạng sử dụng. Nó đại diện cho số công khai, ký hiệu là G (1 < G < n).

Bước 3 - Tạo ra số bí mật, ký hiệu là Q bằng một trong hai cách sau.

• Với CRT, với i từ 1 đến f, tính một số, ký hiệu là s_i là số nguyên dương nhỏ nhất sao cho v x s_i - 1 là bội số của p_i - 1, do đó u_i = p_i - 1 - s_i, G_i = G mod p_i và Q_i = mod p_i. Số Q là hợp số CRT (xem mục 5.3) của Q₁ đến Q_f.

• Không có CRT, tính một số, ký hiệu s là số nguyên dương nhỏ nhất sao cho v x s - 1 là bội số của lcm(p₁ - 1,..., p_f - 1), thì u = lcm(p₁ - 1, ...,p_f - 1) - s và Q = G^u mod n.

CHÚ THÍCH Số Q là số nghịch đảo mod n của chữ ký được định nghĩa trong 6.1. Cặp G và Q thỏa mãn G x Q^v mod n = 1.

Quá trình ký yêu cầu một hàm băm (xem mục 5.1), một biến thể băm, một cơ chế định dạng và một khóa ký. Khuyến nghị sử dụng cơ chế định dạng quy định trong 7.4. Khóa ký bao gồm t,v,n và Q (t, v, n công khai).

Quá trình kiểm tra yêu cầu một tập hợp các tham số miền, một khóa kiểm tra và Id. Các tham số miền có thể bao gồm t (mặc định t = 1). Các tham số miền hoặc khóa kiểm tra bao gồm v,n và Indic(h) và có thể gồm α (mặc định α = |n|), Indic(variant) (mặc định sử dụng biến thể đầu tiên) và Indic(format, ε, t) (mặc định trong 7.4).

7.2  Cơ chế ký

Cơ chế ký được minh họa trong hình 4 sử dụng một hàm băm, một biến thể băm và một khóa ký để ký một thông điệp (một xâu bit, ký hiệu M), tức là tạo ra một chữ ký của M (hai xâu bit, ký hiệu là R và S).

Hình 4 - Ký với GQ1

Bước 1 - Lựa chọn t xâu gồm |n| bit ngẫu nhiên.

Biểu diễn các số ngẫu nhiên (giữ bí mật), ký hiệu là r₁ đến r_t (ký hiệu là r trong hình 1).

CHÚ THÍCH Xác suất để một xâu gồm |n| bit ngẫu nhiên có giá trị bằng 0 hoặc một bội số của một thửa số nguyên tố của n là không đáng kể.

Bước 2 - Với i từ 1 đến t, tính toán mod n và biểu diễn giá trị đó bằng một xâu gồm |n| bit, ký hiệu là W_i.

Tạo một xâu gồm |n| x t bit, ký hiệu là W gồm W₁ II W₂ II ... II W_t.

Bước 3 - Tạo ra một xâu bit, ký hiệu là H theo biến thể băm sử dụng.

H = h(W II M) trong biến thể đầu tiên

h(W II h(M)) trong biến thể thứ hai

h(h(W) II M) trong biến thể thứ ba

h(h(W) II h(M)) trong biến thể thứ tư

Tạo ra phần đầu tiên của chữ ký, ký hiệu là R gồm (|v| -1) x t bit trái nhất của H.

Bước 4 - Tách R thành t xâu gồm |v| - 1 bit, cụ thể gồm R₁ II R₂ II ... II R_t. Mỗi xâu bit R_i biểu diễn một số, cũng ký hiệu là R_i (nhỏ hơn 2^|v|-1 do đó nhỏ hơn v).

Với i từ 1 đến t, tính toán r_i x Q^Ri mod n và biểu diễn bằng một xâu gồm |n| bit, ký hiệu là S_i.

Tạo ra phần thứ hai của chữ ký, ký hiệu là S, gồm S₁ II S₂ II ... Il S_t (|n| x t bit).

7.3  Cơ chế kiểm tra

Cơ chế kiểm tra minh họa trong hình 5 sử dụng một tập hợp các tham số miền, một khóa kiểm tra (xem bảng 1) với khóa ưu tiên (xem 5.2) và một chuỗi dữ liệu định danh (một xâu bit, ký hiệu là Id), để kiểm tra một thông điệp và chữ ký của thông điệp đó, tức là ba xâu bit, ký hiệu là M, R và S.

Bước 0 - Loại bỏ nếu |n| ≠ α, hoặc nếu v không là số nguyên tố lẻ, hoặc nếu |R| ≠ (|v| - 1) x t, hoặc nếu |S| ≠ |n| x t, hoặc nếu Id hết hạn hoặc bị thu hồi.

Hình 5 - Kiểm tra với GQ1

Bước 1 - Biến đổi Id thành một giá trị đặc trưng gồm γ = |n| bit theo cơ chế định dạng sử dụng.

Xâu bit này biểu diễn một số công khai G(0 < G < n).

CHÚ THÍCH Số G trong mỗi lần tạo có thể được lưu trong bộ nhớ cache để tiếp tục sử dụng.

Bước 2 - Chia R thành t xâu gồm |v| - 1 bit là R₁ Il R₂ II ... II R_t và S thành t xâu gồm |n| bit là S₁ II S₂ II ... II S_t. Mỗi xâu R_i hoặc S_i biểu diễn một số, cũng ký hiệu là R_i hoặc S_i. Loại bỏ nếu S_i = 0 hoặc ≥ n.

Với i từ 1 đến t, tính toán mod n và biểu diễn bằng một xâu gồm |n| bit, ký hiệu là .

Tạo ra một xâu gồm |n| x t bit, ký hiệu là W* với .

Bước 3 - Tạo ra một xâu bit, ký hiệu là H* theo biến thể băm sử dụng.

H^* = h(W^* II M) trong biến thể đầu tiên

h(W^* II h(M)) trong biến thể thứ hai

h(h(W*) II M) trong biến thể thứ ba

h(h(W*) II h(M)) trong biến thể thứ tư

Tạo ra một xâu bit, ký hiệu là R^*, gồm (|v| - 1) x t bit trái nhất của H^*.

Bước 4 - Chấp nhận hoặc loại bỏ phụ thuộc vào R và R^* giống nhau hay khác nhau.

7.4  Cơ chế định dạng

Biến đổi một chuỗi dữ liệu định dạng Id thành một giá trị đặc trưng gồm γ bit, ký hiệu là F.

1) Băm ld thành một xâu bit, ký hiệu là H. Nối 8 octet có giá trị bằng “00” vào bên trái xâu bit H. Băm chuỗi vừa nối thành một xâu bit, ký hiệu là HH.

2) Tạo ra một xâu gồm ít nhất γ - |H| bit từ HH theo các bước sau sử dụng hai biến: một xâu có độ dài tùy ý, ký hiệu là String và một xâu 32 bit, ký hiệu là Counter.

a) Đặt String bằng một xâu rỗng.

b) Đặt Counter bằng 0.

c) Thay thế String bằng String || h(HH || Counter).

d) Thay thế Counter bằng Counter + 1.

e) Nếu |H| x Counter < γ - |H|, thì quay lại bước c.

Tạo ra một xâu có mặt nạ với γ - |H| bit trái nhất của String trong đó bit trái nhất được đặt bằng 0 và nghịch đảo bit phải nhất.

3) Tạo ra F bằng cách nối xâu vừa được tạo mặt nạ vào bên trái của HH.

F = Xâu bit được tạo mặt nạ || HH

4) Nếu tất cả γ - 1 bit trái nhất của F bằng 0 (trường hợp rất hiếm gặp), thì quá trình thất bại (xâu bit Id không phù hợp). Ngược lại trả về giá trị F.

8  Lược đồ GQ2

8.1  Tập hợp các thành phần dữ liệu cần để ký/klểm tra

Các quan hệ và ràng buộc chuỗi được áp dụng cho các thành phần dữ liệu sau:

• Tham số an toàn, số các số cơ sở và tham số độ dài chữ ký;

• Tập hợp các số cơ sở;

• Tập hợp các thừa số nguyên tố khác nhau;

• Số mô-đun;

• Tham số thay thế;

• Tập hợp các số mũ bí mật;

• Tập hợp các số bí mật.

Tham số an toàn ký hiệu là k. Số các số cơ sở ký hiệu là m. Tham số độ dài chữ ký ký hiệu là t. Tích của k x m x t sẽ nhỏ hơn hoặc bằng |H|.

CHÚ THÍCH Với k x m x t = 80, các giá trị thường gặp của k, m và t là (80,1,1), (20,4,1), (16,5,1)(10,8,1) và (8,10,1).

Tập hợp các số cơ sở được ký hiệu là g₁, g₂,...,g_m được sắp xếp theo thứ tự tăng dần. Đây chính là m số nguyên tố khác nhau nhỏ hơn 256.

Tập hợp các thừa số nguyên tố khác nhau ký hiệu là p_1, p₂,..., p_f được sắp xếp theo thứ tự tăng dần (f > 1). Mỗi thừa số nguyên tố p_j có công thức như sau p_j = 1 + q_j x trong đó q_j là số lẻ (tức là p_j - 1 chia hết cho , nhưng không chia hết cho ).

Có ít nhất một số cơ sở g_i và hai thừa số nguyên tố p_j và p_{j j} có ký hiệu Legendre như sau:

• Nếu h_j = h_jj, thì (g_i|p_j) = -(g_i|p_jj)

• Nếu h_j > h_jj, thì (g_i|p_j) = -1

CHÚ THÍCH Quá trình sinh khóa theo một trong hai cách sau:

• Cho trước một tập hợp các số cơ sở, ví dụ: các số nguyên tố đầu tiên 2, 3, 5, 7, 11, 13, 17, 19..., lựa chọn một tập hợp các thừa số nguyên tố.

• Cho trước một tập hợp các thừa số nguyên tố, ví dụ các thừa số nguyên tố của mô-đun RSA hoặc RW, lựa chọn một tập hợp các số cơ sở.

Số mô-đun, ký hiệu là n, là tích của các thừa số nguyên tố (n = p₁ x ... x p_f). Độ lớn của nó bằng α bit.

Tham số thay thế, ký hiệu là b, là số lớn nhất từ f số h₁ đến h_f.

Tập hợp các phần tử bí mật ký hiệu là Q_1,1 đến Q_m,f. Với mỗi thừa số nguyên tố p_j,m phần tử bí mật (mỗi phần tử tương ứng với một số cơ sở g_i) được tính toán như sau:

; u_j = q_j - s_j;

Tập hợp các số bí mật ký hiệu là Q₁ đến Q_m. Với i từ 1 đến m, số Q_i là hợp số CRT (xem mục 5.3) của Q_i,1 đến Q_i,f.

CHÚ THÍCH 1 q = lcm(q₁,...q_r); ; u = q - s;

CHÚ THÍCH 2 Với v = 2^b+k và G_i = , mọi cặp G_i và Q_i kiểm tra .

CHÚ THÍCH 3 Nếu mod n ≠ 1, thì với b là bình phương mod n của X_i, số lượng phần tử đơn vị trước đó là một căn bậc hai mod n của phần tử đơn vị, ký hiệu là ω_i, là nghiệm tầm thường (ω_i = n -1) hoặc không tầm thường (1 < ω_i < n-1). Nếu g_i kiểm tra ràng buộc trên các ký hiệu Legendre, thì ω_i là không tầm thường, tức là n chia hết , nhưng không chia hết ω_i - 1 hoặc ω_i + 1, do đó biết được phân tích không tầm thường n = gcd(n,ω_i -1 ) x gcd(n,ω_i  + 1).

CHÚ THÍCH 4 Nếu ký hiệu Jacobi bằng (±g_i|n) = -1 (có nghĩa là n ≡ 1 mod 4, thì ω_i là không tầm thường.

Quá trình ký yêu cầu một hàm băm (xem mục 5.1), một biến thể băm và một khóa ký. Khóa ký có một trong hai dạng sau:

• Với CRT: k, t, b, p₁ đến p_f, f - 1 hệ số CRT (xem mục 5.3) và Q_1,1 đến Q_m,f (k, t, b công khai).

• Không có CRT: k, t, b, n và Q₁ đến Q_m (k, t, b, n công khai).

Quá trình kiểm tra yêu cầu một tập hợp các tham số miền và một khóa kiểm tra. Các tham số miền bao gồm k và có thể có m (mặc định, m = 1) và t (mặc định, t = 1). Các tham số miền hoặc khóa kiểm tra sẽ bao gồm Indic(h), và có thể bao gồm g₁,g₂…g_m (mặc định, m số nguyên tố đầu tiên, tức là 2,3,5,7,11...), α (mặc định, α = |n|) và Indic(variant) (mặc định, là biến thể đầu tiên). Khóa kiểm tra bao gồm n và có thể có b (mặc định, b = 1).

8.2  Cơ chế ký

Cơ chế ký được minh họa trong hình 6, sử dụng một hàm băm, một biến thể băm và một khóa ký để ký một thông điệp (một xâu bit, ký hiệu M), tức là tạo ra chữ ký của M (hai xâu bit, ký hiệu là R và S).

Hình 6 - Ký với GQ2

Bước 1 - Tạo ra các số ngẫu nhiên (thường ký hiệu là r trong hình 1) bằng một trong hai cách sau:

• Với CRT, với j từ 1 đến f, chọn t xâu gồm |p_j| bit ngẫu nhiên. Biểu diễn các số và giữ bí mật, ký hiệu là r_1,1 đến r_t,f.

CHÚ THÍCH Xác suất để một xâu gồm |p_j| bit ngẫu nhiên bằng 0 hoặc p_i là không đáng kể.

• Không có CRT, chọn t xâu gồm |n| bit ngẫu nhiên. Biểu diễn các số và giữ bí mật, ký hiệu là r₁ đến r_t.

CHÚ THÍCH Xác suất để một xâu gồm |n| bit ngẫu nhiên bằng 0 hoặc bội của một thừa số nguyên tố bất kỳ của n là không đáng kể.

Bước 2 - Tạo ra các xâu bit, ký hiệu là W₁ đến W_t bằng một trong hai cách sau.

• Với CRT, với i từ 1 đến t và j từ 1 đến f, tính toán . Với i từ 1 đến t, biểu diễn hợp số CRT (xem mục 5.3) của W_i,1 đến W_i,f bằng một xâu gồm |n| bit, ký hiệu là W_i.

• Không có CRT, với i từ 1 đến t, tính toán mod n và biểu diễn nó bằng một xâu gồm |n| bit, ký hiệu là W_i.

Tạo ra một xâu bit, ký hiệu là W, với W₁ II W₂ II ... Il W_t (|n| x t bit).

Bước 3 - Tạo ra một xâu bit, ký hiệu là H theo biến thể băm sử dụng.

H = h(W II M) trong biến thể đầu tiên

h(W II h(M)) trong biến thể thứ hai

h(h(W) II M) trong biến thể thứ ba

h(h(W) II h(M))trong biến thể thứ tư

Tạo ra phần đầu tiên của chữ ký, ký hiệu là R gồm k x m x t bit trái nhất của H.

Bước 4 - Tách R thành t xâu gồm k x m bit, cụ thể gồm R₁ Il R₂ II ... II R_t. Tách mỗi R_i thành m xâu gồm k bit như sau R_i,1 II R_i,2 II ... II R_i,m. Mỗi xâu R_i,j gồm k bit, từ bit trái nhất ký hiệu là R_i,j,1 đến bit phải nhất ký hiệu là R_i,j,k. Mỗi xâu R_i,j biểu diễn một số_, cũng ký hiệu là R_i,j (< 2^k).

Tạo ra các số, ký hiệu S₁ đến S_t bằng một trong hai cách sau.

• Với CRT, với i từ 1 đến t và j từ 1 đến f, tính toán. Với i từ 1 đến t, số S_i là hợp số CRT (xem mục 5.3) của S_i,1 đến S_i,f.

• Không có CRT, với i từ 1 đến t, tính toán

Số S_i bất kỳ có thể được thay thế bằng n - S_i.

Biểu diễn từng số S_i bằng một xâu gồm |n| bit, cũng ký hiệu là S_i.

Tạo ra phần thứ hai của chữ ký, ký hiệu là S, với S₁ || S₂ || ... || S_t (gồm |n| x t bit).

8.3  Cơ chế kiểm tra

Cơ chế kiểm tra được minh họa trong hình 7 sử dụng một tập hợp các tham số miền và một khóa kiểm tra (xem bảng 1), với khóa ưu tiên (xem mục 5.2) để kiểm tra một thông điệp và chữ ký của thông điệp đó, tức là có ba xâu bit, ký hiệu là M, R và S.

Bước 0 - Loại bỏ nếu |n| ≠ a, hoặc nếu |R| ≠ k x m x t, hoặc nếu |S| ≠ |n| x t, hoặc nếu m các số cơ sở không phải là các số nguyên tố khác nhau nhỏ hơn 256.

Hình 7 - Kiểm tra với GQ2

Bước 1 - Tách S thành t xâu gồm |n| bit như sau S₁ II S₂ II ... II S_t. Mỗi xâu bit S_i biểu diễn một số, cũng ký hiệu là S_i. Loại bỏ nếu bất kỳ S_i = 0 hoặc ≥ n.

Tách R thành t xâu gồm k x m bit như sau R₁ II R₂ II ... II R_t. Tách mỗi R_i thành m xâu gồm k bit như sau R_i,1 II R_i,2 II ... II R_i,m. Mỗi xâu R_i,j gồm k bit, từ bit trái nhất ký hiệu là R_i,j,1 đến bit phải nhất ký hiệu là R_i,j,k. Mỗi xâu R_i,j biểu diễn một số, cũng ký hiệu là R_i,j (< 2^k).

Với i từ 1 đến t, tính toán và biểu diễn bằng một xâu gồm |n| bit, ký hiệu là .

CHÚ THÍCH Bắt đầu từ một tập giá trị bằng phép nhân của S, k được xen kẽ với b + k phép bình phương. Sau giá trị bình phương thứ l là phép nhân thứ l: với j từ 1 đến m, bit tương ứng (ký hiệu là R_i,j,l ở vị trí mà giá trị hiện thời là bội số của g_j (bit được đặt bằng 1) hoặc không là bội số của g_j) (bit được đặt bằng 0). Giá trị cuối cùng sau bình phương thứ b + k là W^*.

Tạo ra một xâu bit, ký hiệu là W* với W^*₁ II W^*₂ Il ... II W^*_t (gồm |n| x t bit).

Bước 2 - Tạo ra một xâu bit, ký hiệu là H* theo biến thể băm sử dụng.

H^* = h(W II M) trong biến thể đầu tiên

h(W^* II h(M)) trong biến thể thứ hai

h(h(W *) II M) trong biến thể thứ ba

h(h(W^*) II h(M)) trong biến thể thứ tư

Tạo ra một xâu bit, ký hiệu là R^*, gồm k x m x t bit trái nhất của H^*.

Bước 3 - Chấp nhận hoặc loại bỏ phụ thuộc vào R và R^* giống nhau hay khác nhau.

9  Lược đồ GPS1

9.1  Tập hợp các thành phần dữ liệu cần để ký/kiểm tra

Các quan hệ và ràng buộc chuỗi được áp dụng cho các thành phần dữ liệu sau:

• Số mô-đun;

• Tập hợp các thừa số nguyên tố;

• Số bí mật;

• Số cơ sở;

• Số công khai.

Số mô-đun ký hiệu là n. Độ lớn của nó bằng α bit. Không thể biết được phân tích của số mô-đun thành các thừa số nguyên tố.

Tập hợp các thừa số nguyên tố ký hiệu là p₁, p₂ ... p_f được sắp xếp theo thứ tự tăng dần (f > 1).

Số bí mật, ký hiệu là Q, được biểu diễn bởi một xâu gồm |H| bit ngẫu nhiên.

Số cơ sở ký hiệu là g. Cấm sử dụng giá trị g = 0 và g = 1.

CHÚ THÍCH Giá trị g = 2 có nhiều ưu điểm trong thực tế ứng dụng.

Số công khai, ký hiệu là G được tạo ra bằng một trong hai cách sau :

• Với CRT, với i từ 1 đến f, tính toán Q_i = Q mod (p_i - 1) và G_i = g^Qi mod p_i. Số G là hợp số CRT (xem mục 5.3) của G₁ đến G_f.

• Không có CRT, tính toán G = g^Q mod n.

Quá trình ký yêu cầu một hàm băm (xem mục 5.1), một biến thể băm và một khóa ký. Khóa ký được tạo ra bằng một trong hai cách sau :

• Với CRT: P₁ đến P_f, f - 1 hệ số CRT (xem mục 5.3), g và Q (g công khai);

• Không có CRT: n, g và Q (n, g công khai).

Quá trình kiểm tra yêu cầu một tập hợp các tham số miền và một khóa kiểm tra. Các tham số miền hoặc khóa kiểm tra bao gồm n và Indic(h), và có thể gồm g (mặc định, g = 2), α (mặc định, α = |n|) và Indic(variant) (mặc định, biến thể thứ ba). Khóa kiểm tra bao gồm G.

9.2  Cơ chế ký

9.2.1  Giới thiệu chung

Cơ chế ký được minh họa bằng hình 8 sử dụng một hàm băm, một biến thể băm và một khóa ký để ký một thông điệp (một xâu bit, ký hiệu là M), tức là tạo ra một chữ ký của M (hai xâu bit, ký hiệu là R và S)

Mỗi người ký được cung cấp một hoặc nhiều coupon. Theo định nghĩa, một coupon là một xâu bit, độc lập với thông điệp, tiền tính toán từ một xâu các bit ngẫu nhiên, phải giữ bí mật và chỉ sử dụng một lần.

Hình 8 - Ký với GPS1

9.2.2  Số ngẫu nhiên

Bước 1 - Lựa chọn một xâu của 2|H| + 80 bit ngẫu nhiên.

Nó biểu diễn một số ngẫu nhiên, cần phải giữ bí mật, ký hiệu là r.

Quá trình tạo số ngẫu nhiên liên quan đến quá trình tạo coupon hoặc sử dụng coupon.

• Bước 2 sử dụng r và n hoặc p₁ đến p_f.

• Bước 4 sử dụng r và Q.

CHÚ THÍCH Nếu thiết bị tạo chữ ký tạo ra các xâu bit giả ngẫu nhiên bằng một hàm tất định của các chỉ số coupon, thì nó lưu trữ chỉ số của coupon được tạo ra cuối cùng và chỉ số của coupon được sử dụng cuối cùng. Ngược lại, nó lưu trữ các xâu bit cho đến khi sử dụng các coupon.

9.2.3  Tạo coupon

Bước 2 - Tạo ra một xâu bit, ký hiệu là W bằng một trong hai cách sau.

• Với CRT, với i từ 1 đến f, tính toán r_i = r mod(p_i - 1) và . Biểu diễn hợp số CRT (xem mục 5.3) của W₁ đến W_f bằng một xâu gồm |n| bit, ký hiệu là W.

• Không có CRT, tính toán g^r mod n và biểu diễn nó bằng một xâu gồm |n| bit, ký hiệu là W.

Coupon, ký hiệu là T được đặt bằng mã băm h(W).

9.2.4  Sử dụng coupon

Bước 3 - Tạo ra phần đầu tiên của chữ ký, ký hiệu là R theo biến thể băm sử dụng.

R = h(T||M), tức là = h(h(W)||M) trong biến thể thứ ba

h(T||h(M)), tức là = h(h(W))||h(M)) trong biến thể thứ tư.

Bước 4 - Xâu bit R biểu diễn một số, cũng ký hiệu là R.

Tính toán S = r - R x Q.

Phần thứ hai của chữ ký, cũng ký hiệu là S là một xâu gồm 2|H| + 80 bit biểu diễn số S.

9.3  Cơ chế kiểm tra

Cơ chế kiểm tra được minh họa bằng hình 9 sử dụng một tập hợp các tham số miền và một khóa kiểm tra (xem bảng 1) với khóa ưu tiên (xem 5.2) để kiểm tra một thông điệp và một chữ ký của thông điệp khác, tức là có ba xâu bit, ký hiệu là M, R và S.

Bước 0 - Loại bỏ nếu |n| ≠ α, hoặc nếu g = 0 hoặc 1, hoặc nếu |R| ≠ |H|, hoặc nếu |S| ≠ 2|H| + 80.

Hình 9 - Kiểm tra với GPS1

Bước 1 - Các xâu bit R và S biểu diễn hai số, cũng ký hiệu là R và S.

Tính toán G^R x g^S mod n và biểu diễn nó bằng một xâu gồm |n| bit, ký hiệu là W^*.

Bước 2 - Tạo ra một xâu bit, ký hiệu là R^* theo biến thể băm sử dụng.

R^* = h(h(W^*) || M) trong biến thể thứ ba

h(h(W^*) || /h(M)) trong biến thể thứ tư

CHÚ THÍCH Mã băm h(W^*) là coupon đã được khôi phục lại.

Bước 3 - Chấp nhận hoặc loại bỏ phụ thuộc vào R và R^* giống nhau hay khác nhau.

10  Lược đồ GPS2

10.1  Tập hợp các thành phần dữ liệu cần để ký/kiểm tra

Các quan hệ và ràng buộc chuỗi được áp dụng cho các thành phần dữ liệu sau:

• Số mũ kiểm tra;

• Tập hợp các thừa số nguyên tố khác nhau;

• Số mô-đun;

• Số bí mật;

• Số cơ sở.

Số mũ kiểm tra, ký hiệu là v là một số nguyên tố do đó |v| = |H| + 1.

CHÚ THÍCH Nếu |H| = 160, thì giá trị v = 2¹⁶⁰ + 7 có nhiều ưu điểm trong thực tế sử dụng.

Tập hợp các thừa số nguyên tố khác nhau được ký hiệu là p₁, p₂ ... p_f được sắp xếp theo thứ tự tăng dần (f > 1).

Với i từ 1 đến f, v không chia hết p_i - 1.

Số mô-đun, ký hiệu là n là tích của các thừa số nguyên tố (n = p₁ x ... x p_f). Độ lớn của nó bằng α bit.

Số bí mật được ký hiệu là Q. Nó là một số nguyên dương bất kỳ (thường sử dụng số nhỏ nhất) do đó v x Q - 1 là bội số của lcm(p₁ - 1, ...,p_f - 1), được biểu diễn bằng một xâu gồm |n| bit.

CHÚ THÍCH Số Q được định nghĩa giống như số mũ ký quy định trong 6.1.

Số cơ sở được ký hiệu là g. Cấm sử dụng giá trị g = 0 và g = 1.

CHÚ THÍCH Giá trị g = 2 có nhiều ưu điểm trong thực tế sử dụng.

Quá trình ký yêu cầu một hàm băm (xem mục 5.3), một biến thể băm và một khóa ký. Khóa ký được tạo ra bằng một trong hai cách sau:

• Với CRT: v, p₁ đến p_f, f - 1 hệ số CRT (xem mục 5.3), Q và g (v,g công khai);

• Không có CRT: v, n, Q và g (v, n, g công khai).

Quá trình kiểm tra yêu cầu một tập hợp các tham số miền và một khóa kiểm tra. Các tham số miền hoặc khóa kiểm tra bao gồm v và Indic(h) và có thể bao gồm g (mặc định g = 2), α (mặc định, α = |n|) và Indic(variant) (mặc định là biến thể thứ ba). Khóa kiểm tra bao gồm n.

10.2  Cơ chế ký

10.2.1  Giới thiệu chung

Cơ chế ký được minh họa bằng hình 10, sử dụng một hàm băm, một biến thể và một khóa ký để ký một thông báo (một xâu bit, ký hiệu là M) tức là tạo ra một chữ ký của M (hai xâu bit, ký hiệu là R và S).

Mỗi người ký được cung cấp một hoặc nhiều coupon. Theo định nghĩa, một coupon là một xâu bit, độc lập với thông điệp, tiền tính toán từ một xâu các bit ngẫu nhiên, được giữ bí mật và chỉ sử dụng một lần.

Hình 10 - Ký với GPS2

10.2.2  Số ngẫu nhiên

Bước 1 - Lựa chọn một xâu gồm |n| + |H| + 80 bit ngẫu nhiên.

Biểu diễn một số ngẫu nhiên cần giữ bí mật, ký hiệu là r.

Quá trình tạo số ngẫu nhiên liên quan đến quá trình tạo coupon hoặc sử dụng coupon.

• Bước 2 sử dụng r, v và n hoặc p₁ đến p_f.

• Bước 4 sử dụng r và Q.

CHÚ THÍCH Nếu thiết bị tạo chữ ký tạo ra các xâu bit giả ngẫu nhiên bằng một hàm tất định của các chỉ số coupon, thì nó lưu trữ chỉ số của coupon được tạo ra cuối cùng và chỉ số của coupon được sử dụng cuối cùng. Ngược lại, nó lưu trữ các xâu bit cho đến khi sử dụng các coupon.

10.2.3  Tạo coupon

Bước 2 - Tạo ra một xâu bit, ký hiệu là W bằng một trong hai cách sau.

• Với CRT, với i từ 1 đến f, tính toán r_i = v x r mod(p_i - 1) và mod p_i. Biểu diễn hợp số CRT (xem mục 5.3) của W₁ đến W_f bằng một xâu gồm |n| bit, ký hiệu là W.

• Không có CRT, tính toán g^v×r mod n và biểu diễn bằng một xâu gồm |n| bit, ký hiệu là W.

Coupon, ký hiệu là T được đặt bằng mã băm h(W).

10.2.4  Sử dụng coupon

Bước 3 - Tạo ra phần thứ nhất của chữ ký, ký hiệu là R theo biến thể băm sử dụng.

R = h(T || M), tức là = h(h(W) || M) trong biến thể thứ ba

h(T || h(M)), tức là = h(h(W) || h(M)) trong biến thể thứ tư.

Bước 4 - Xâu bit R biểu diễn một số, cũng ký hiệu là R.

Tính toán S = r - R x Q.

Phần thứ hai của chữ ký, cũng ký hiệu là S là một xâu gồm |n| + |H| + 80 bit biểu diễn số S.