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
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:
| AǁB
A Å B b Cr CRT |
Xâu bit kết quả của phép ghép hai xâu bit A và B theo thứ tự.
Xâu bit kết quả của phép XOR hai xâu bit A và B có cùng độ dài. Tham số thay thế (adaptation) (GQ2). Hệ số CRT. Định lý phần dư Trung Hoa. |
| |D| | Độ dài bit của D nếu D là một xâu bit, hoặc độ lớn bit của D nếu D là một số (tức là, bằng 0 nếu D = 0, hoặc bằng số nguyên duy nhất i sao cho 2i-1 ≤ D < 2i nếu D > 0. Ví dụ |65537 = 216 + 1| = 17). |
| ëDû
éDù E F f G, Gi g, gi |
Số nguyên lớn nhất nhỏ hơn hoặc bằng D.
Số nguyên nhỏ nhất lớn hơn hoặc bằng D. Salt (RSA, RW, ESIGN). Giá trị đặc trưng của (RSA, RW, GQ1, ESIGN). Số lượng các thừa số nguyên tố. Số công khai. Số cơ sở. |
| (g|n) | Ký hiệu Jacobi của một số nguyên dương g đối với một hợp số lẻ n.
CHÚ THÍCH 1 Theo định nghĩa, ký hiệu Jacobi của g đối với n là tích của ký hiệu Legendre của g đối với mọi thừa số nguyên tố của n (tính lặp lại các ký hiệu Legendre đối với các thừa số nguyên tố lặp lại nhiều lần). Có thể tính ký hiệu Jacobi [13,15] mà không cần biết về các thừa số nguyên tố của n. |
| (g|p) | Ký hiệu Legendre của một số nguyên dương g đối với một số nguyên tố lẻ p.
CHÚ THÍCH 2 Theo định nghĩa, nếu p là số nguyên tố thì (g|p) = g(p-1)/2mod p. Nghĩa là (g|p) bằng 0 nếu g là bội của p, ngược lại bằng +1 hoặc -1 phụ thuộc g có là bình phương theo mô-đun p hay không. |
| gcd(a,b)
H, HH h i mod n Id Indic k lcm(a b) M m n pi Q, Qi Qi,j R r, ri, rij S s, si T t u, ui v W ‘XY’ x, y, z α γ ε t |
Ước chung lớn nhất của hai số nguyên dương a và b.
Mã băm. Hàm băm. Số nguyên duy nhất j từ 0 đến n – 1 sao cho n chia hết cho i – j. Chuỗi dữ liệu định danh (GQ1). Chỉ số của một cơ chế được dùng (hàm băm, cơ chế định dạng, biến thể băm. Tham số an toàn (GQ2). Bội số chung nhỏ nhất của hai số nguyên dương a và b. Thông điệp. Số lượng các số cơ sở (GQ2). Mô-đun. Thừa số nguyên tố. Số bí mật. Số mũ bí mật (GQ2). Phần đầu tiên của chữ ký (GQ1, GQ2, GPS1, GPS2). Số ngẫu nhiên (GQ1, GQ2, GPS1, GPS2, ESIGN). Chữ số (RSA, RW, ESIGN) hoặc phần thứ hai của chữ ký (GQ1, GQ2, GPS1, GPS2). Số mũ chữ ký (RSA, RW, GQ1, GQ2). coupon (GPS1, GPS2). Tham số độ dài chữ ký (GQ1, GQ2). Số mũ (GQ1, GQ2). Số mũ kiểm tra (RSA, RW, GQ1, GPS2, ESIGN). Xâu bit (GQ1, GQ2, GPS1, GPS2). Ký hiệu sử dụng các chữ số hexa ‘0’ tới ‘9’ và ‘A’ tới ‘F’, bằng XY hệ cơ số 16. Các số nguyên. Độ lớn bit của mô-đun. Độ dài bit của các giá trị đặc trưng (RSA, RW, GQ1, ESIGN). Độ dài bit của các giá trị salt (các cơ chế định dạng). Độ dài bit của các giá trị trailer (các cơ chế định dạng). |
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
|
Lược đồ |
Bắc buộc |
Tùy chọn a) |
Tùy chọn b) |
||
|
RSA, RW, ESIGN |
n |
V |
lndic(h) |
α |
Indic(format, ɛ, t) |
|
GQ1 c) |
|
n,v |
lndic(h) |
α |
Indic(variant), Indic(format, ɛ, t) |
|
GQ2 |
n |
|
lndic(h) |
b, (g1,g2…gm),α |
Indic(variant) |
|
GPS1 |
G |
n |
lndic(h) |
g, α |
Indic(variant) |
|
GPS2 |
n |
v |
lndic(h) |
g, α |
Indic(variant) |
| a) Nếu không là thành phần của khóa kiểm tra, thì một thành phần dữ liệu sẽ là một tham số miền.
b) Nếu không phải là một tham số miền, cũng không là thành phần của khóa kiểm tra, thì một thành phần dữ liệu sẽ được coi là một giá trị mặc định. e) Khóa kiểm tra GQ1 có thể là rỗng. |
|||||
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.
| 1) h(WǁM) | 2) h(Wǁh(M)) | 3) h(h(W)ǁM) | 4) h(h(W)ǁh(M)) |
Để 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 x1 và x2 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 x1 và x2, ký hiệu là Cr là một số nguyên dương duy nhất, nhỏ hơn x1, sao cho Cr x x2 – 1 là bội số của x1.
Số nguyên bất kỳ X thuộc {0,1… x1 × x2 – 1} có thể được phân tích thành cặp duy nhất các thành phần X1 = X mod x1 nhận giá trị từ {0,1… x1 – 1} và X2 = X mod x2 nhận giá trị từ {0,1… x2 -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 x1,x2 và Cr để biến đổi hai thành phần X1 nhận giá trị từ {0,1… x1 – 1} và X2 nhận giá trị từ {0,1… x2 – 1} thành số nguyên duy nhất X nhận giá trị từ {0,1… x1 x x2 – 1} sao cho X1 = X mod x1 và X2 = X mod x2.
Y = X1 – X2 mod x1; Z = Y x Cr mod x1; X = Z x x2 + X2
Lần lượt biến đổi ba thành phần X1 từ {0,1… x1 – 1}, X2 từ {0,1… x2 – 1} và X3 từ {0,1… x3 – 1}, trong đó x1, x2 và x3 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… x1 x x2 x x3 – 1} thỏa mãn X1 = X mod x1, X2 = X mod x2 và X3 = X mod x3, hợp số CRT được sử dụng hai lần:
1) để tính toán T nhận giá trị từ {0,1… x1 x x2 – 1} sao cho X1 = T mod x1 và X2 = T mod x2;
2) để tính toán X nhận giá trị từ {0,1… x1 x x2 x x3 – 1} sao cho T = X mod x1 x x2 và X3 = X mod x3.
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à d1, đến bit phải nhất, ký hiệu là d|D|.
D = d1d2d3 … 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à d1, 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 d1 + 2|D|-2 x d2 +…+ 22 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 d1 = 1, hoặc nhỏ hơn |D| nếu d1 = 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(= 216 + 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à p1,p2 …pf đượ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 pi – 1, tức là gcd(v,pi – 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 = p1 x … x pf). 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(p1 – 1,…,pf – 1) nếu v là số lẻ, hoặc là bội số của lcm(p1 – 1, p2 – 1)/2 nếu v = 2.
Tập hợp các số mũ ký CRT ký hiệu là s1 đến sf. Với i từ 1 đến f, si là số nguyên dương bất kỳ (thường sử dụng số nhỏ nhất) sao cho v x si -1 là bội số của pi – 1 nếu v là số lẻ, hoặc là bội số của (pi – 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, 
, s1 = (p1 + 1) và s2 = (p2 + 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: p1 đến pf,f -1 hệ số CRT (xem mục 5.3) và s1 đến sf.
• 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 Gi = G mod pi và Si = 
mod pi. Số S là hợp số CRT (xem mục 5.3) S1 đến Sf.
• Không sử dụng CRT, tính toán S – Gsmod 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* = Svmod 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.
|
H = h(M) |
HH = h((“0000 0000 0000 0000”) ||H|| E) |
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.
|
H = h(M) |
HH = h((“0000 0000 0000 0000”) || H || E*) |
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à (280 +13,1), (240 + 15,2), (220 + 7,4), (216 + 1,5).
Tập hợp các thừa số nguyên tố khác nhau ký hiệu là p1,p2 …pf đượ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 pi -1.
Số mô-đun, ký hiệu là n, là tích của các thừa số nguyên tố (n = p1 x … x pf). Độ 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à si là số nguyên dương nhỏ nhất sao cho v x si – 1 là bội số của pi – 1, do đó ui = pi – 1 – si, Gi = G mod pi và Qi = 
mod pi. Số Q là hợp số CRT (xem mục 5.3) của Q1 đến Qf.
• 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(p1 – 1,…, pf – 1), thì u = lcm(p1 – 1, …,pf – 1) – s và Q = Gu 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 Qv 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à r1 đến rt (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à Wi.
Tạo một xâu gồm |n| x t bit, ký hiệu là W gồm W1 II W2 II … II Wt.
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 R1 II R2 II … II Rt. Mỗi xâu bit Ri biểu diễn một số, cũng ký hiệu là Ri (nhỏ hơn 2|v|-1 do đó nhỏ hơn v).
Với i từ 1 đến t, tính toán ri x QRi mod n và biểu diễn bằng một xâu gồm |n| bit, ký hiệu là Si.
Tạo ra phần thứ hai của chữ ký, ký hiệu là S, gồm S1 II S2 II … Il St (|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à R1 Il R2 II … II Rt và S thành t xâu gồm |n| bit là S1 II S2 II … II St. Mỗi xâu Ri hoặc Si biểu diễn một số, cũng ký hiệu là Ri hoặc Si. Loại bỏ nếu Si = 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.
|
H = h(ld) |
HH = h(‘00000000 00000000’||H) |
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à g1, g2,…,gm đượ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à p1, p2,…, pf được sắp xếp theo thứ tự tăng dần (f > 1). Mỗi thừa số nguyên tố pj có công thức như sau pj = 1 + qj x 
trong đó qj là số lẻ (tức là pj – 1 chia hết cho , nhưng không chia hết cho 
).
Có ít nhất một số cơ sở gi và hai thừa số nguyên tố pj và pj j có ký hiệu Legendre như sau:
• Nếu hj = hjj, thì (gi|pj) = –(gi|pjj)
• Nếu hj > hjj, thì (gi|pj) = -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 = p1 x … x pf). Độ 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ố h1 đến hf.
Tập hợp các phần tử bí mật ký hiệu là Q1,1 đến Qm,f. Với mỗi thừa số nguyên tố pj,m phần tử bí mật (mỗi phần tử tương ứng với một số cơ sở gi) được tính toán như sau:
; uj = qj – sj; 
Tập hợp các số bí mật ký hiệu là Q1 đến Qm. Với i từ 1 đến m, số Qi là hợp số CRT (xem mục 5.3) của Qi,1 đến Qi,f.
CHÚ THÍCH 1 q = lcm(q1,…qr); 
; u = q – s; 
CHÚ THÍCH 2 Với v = 2b+k và Gi = 
, mọi cặp Gi và Qi 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 Xi, 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 gi 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 (±gi|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, p1 đến pf, f – 1 hệ số CRT (xem mục 5.3) và Q1,1 đến Qm,f (k, t, b công khai).
• Không có CRT: k, t, b, n và Q1 đến Qm (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 g1,g2…gm (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 |pj| bit ngẫu nhiên. Biểu diễn các số và giữ bí mật, ký hiệu là r1,1 đến rt,f.
CHÚ THÍCH Xác suất để một xâu gồm |pj| bit ngẫu nhiên bằng 0 hoặc pi 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à r1 đến rt.
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à W1 đến Wt 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 Wi,1 đến Wi,f bằng một xâu gồm |n| bit, ký hiệu là Wi.
• 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à Wi.
Tạo ra một xâu bit, ký hiệu là W, với W1 II W2 II … Il Wt (|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 R1 Il R2 II … II Rt. Tách mỗi Ri thành m xâu gồm k bit như sau Ri,1 II Ri,2 II … II Ri,m. Mỗi xâu Ri,j gồm k bit, từ bit trái nhất ký hiệu là Ri,j,1 đến bit phải nhất ký hiệu là Ri,j,k. Mỗi xâu Ri,j biểu diễn một số, cũng ký hiệu là Ri,j (< 2k).
Tạo ra các số, ký hiệu S1 đến St 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ố Si là hợp số CRT (xem mục 5.3) của Si,1 đến Si,f.
• Không có CRT, với i từ 1 đến t, tính toán 
Số Si bất kỳ có thể được thay thế bằng n – Si.
Biểu diễn từng số Si bằng một xâu gồm |n| bit, cũng ký hiệu là Si.
Tạo ra phần thứ hai của chữ ký, ký hiệu là S, với S1 || S2 || … || St (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 S1 II S2 II … II St. Mỗi xâu bit Si biểu diễn một số, cũng ký hiệu là Si. Loại bỏ nếu bất kỳ Si = 0 hoặc ≥ n.
Tách R thành t xâu gồm k x m bit như sau R1 II R2 II … II Rt. Tách mỗi Ri thành m xâu gồm k bit như sau Ri,1 II Ri,2 II … II Ri,m. Mỗi xâu Ri,j gồm k bit, từ bit trái nhất ký hiệu là Ri,j,1 đến bit phải nhất ký hiệu là Ri,j,k. Mỗi xâu Ri,j biểu diễn một số, cũng ký hiệu là Ri,j (< 2k).
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à Ri,j,l ở vị trí mà giá trị hiện thời là bội số của gj (bit được đặt bằng 1) hoặc không là bội số của gj) (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*1 II W*2 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à p1, p2 … pf đượ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 Qi = Q mod (pi – 1) và Gi = gQi mod pi. Số G là hợp số CRT (xem mục 5.3) của G1 đến Gf.
• Không có CRT, tính toán G = gQ 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: P1 đến Pf, 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 p1 đến pf.
• 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 ri = r mod(pi – 1) và 
. Biểu diễn hợp số CRT (xem mục 5.3) của W1 đến Wf bằng một xâu gồm |n| bit, ký hiệu là W.
• Không có CRT, tính toán gr 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 GR x gS 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 = 2160 + 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à p1, p2 … pf đượ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 pi – 1.
Số mô-đun, ký hiệu là n là tích của các thừa số nguyên tố (n = p1 x … x pf). Độ 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(p1 – 1, …,pf – 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, p1 đến pf, 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 p1 đến pf.
• 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 ri = v x r mod(pi – 1) và 
mod pi. Biểu diễn hợp số CRT (xem mục 5.3) của W1 đến Wf bằng một xâu gồm |n| bit, ký hiệu là W.
• Không có CRT, tính toán gv×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.
10.3 Cơ chế kiểm tra
Cơ chế kiểm tra được minh họa trong hình 11, 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 v không là số nguyên tố lẻ, hoặc nếu g = 0 hoặc 1, hoặc nếu |R| ≠ |H|, hoặc nếu |S| ≠ |n| + |H| + 80.
Hình 11 – Kiểm tra với GPS2
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 gv×S+R 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.
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
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;
• Cặp các thừa số nguyên tố khác nhau;
• Số mô-đun.
Số mũ kiểm tra, ký hiệu là v lớn hơn hoặc bằng 8, nhưng nhỏ hơn 2α–1.
CHÚ THÍCH Giá trị v = 1024 cố nhiều ưu điểm trong thực tế sử dụng.
Cặp các thừa số nguyên tố khác nhau ký hiệu là p1 và p2 được sắp xếp theo thứ tự tăng dần. Độ lớn của mỗi thừa số nguyên tố là α/3 bit (α là một bội số của 3).
CHÚ THÍCH Cho ví dụ, α = 1023 (không bằng 1024), 1536, 2046 hoặc 2049 (không bằng 2048), 2304,
Số mô-đun, ký hiệu là n là tích của 
(sử dụng lại thừa số nguyên tố lớn nhất). Độ lớn của nó là α bit.
• Ước chung lớn nhất của v và n bằng 1, tức là gcd(v,n) = 1.
• Ước chung lớn nhất của v,p1 – 1 và p2 – 1 tối đa bằng α, tức là gcd(v,p1 – 1, p2 – 1) ≤ α.
CHÚ THÍCH Giá trị v bất kỳ nhỏ hơn hoặc bằng α thỏa mãn cả hai ràng buộc trên.
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 quy định trong 11.4. Khóa ký bao gồm v,p1 và p2 (v 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 α (mặc định α = |n|) và Indic(format, ε, t) (mặc định theo mục 11.4). Khóa kiểm tra bao gồm n.
11.2 Cơ chế ký
Cơ chế ký được minh họa trong hình 12, 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), tức là tạo ra một chữ ký của M (một xâu bit, ký hiệu là S).
Hình 12 – Ký với ESIGN
Bước 1 – Lựa chọn một xâu gồm 2|n|/3 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. Số r nhỏ hơn p1 x p2.
CHÚ THÍCH Xác suất để một xâu gồm 2|n|/3 bit ngẫu nhiên bằng 0 hoặc bội số 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ính toán hai số, ký hiệu là y(< n) và z(< p2). Số z cần được giữ bí mật.
y = rv mod n
z = (v x rv–1)–1mod p2
CHÚ THÍCH Công thức z = r x (v x y)–1 mod p2 có nhiều ưu điểm tính toán.
Bước 3 – Biến đổi thông điệp M thành một giá trị đặc trưng gồm γ = |n|/3 bit, ký hiệu là F theo cơ chế định dạng sử dụng. Xâu bit F biểu diễn một số, cũng ký hiệu là F (0 < F < p1).
Bước 4 – Tính toán một số, ký hiệu là S (0 < S < n).
Nếu 
(trường hợp này xảy ra trên 50%), thì quay lại bước 1.
S = r + (w x z mod p2) x p1 x p2mod n
Nếu v là số chẵn, thì số S được thay thế bằng n – S.
Chữ ký, cũng ký hiệu là S là xâu bit bất kỳ biểu diễn số S, thường là một xâu gồm |n| bit.
11.3 Cơ chế kiểm tra
Cơ chế kiểm tra được minh họa trong hình 13, 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à 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ó hai xâu bit, ký hiệu là M và S.
Bước 0 – Loại bỏ nếu α không phải là bội số của 3, hoặc nếu |n| ≠ α, hoặc nếu v < 8, hoặc nếu v ≥ 2α-1.
Hình 13 – Kiểm tra với ESIGN
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 Svmod n và biểu diễn bằng một xâu gồm |n| bit, ký hiệu là G*.
Bước 2 – Khôi phục lại giá trị đặc trưng, ký hiệu là F* chính là γ = |n|/3 bit trái nhất của G*.
Bước 3 – Kiểm tra giá trị đặc trưng đã được khôi phục lại F* theo cơ chế định dạng sử dụng.
11.4 Cơ chế định dạng
Biến đổi thông điệp M thành một giá trị đặc trưng gồm γ bit, ký hiệu là F.
1) Lựa chọn một xâu mới gồm ε = |H| bit ngẫu nhiên. Nó tạo ra một giá trị salt, ký hiệu là E.
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ị bằng “00” vào H và giá trị salt E. Băm chuỗi vừa nối thành một xâu bit, ký hiệu là HH.
|
H = h(M) |
HH = h(“0000 0000 0000 0000″)||H||E) |
3) Tạo ra một chuỗi 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 String bằng String||h(HH||Counter).
d) Thay Counter bằng Counter + 1.
e) Nếu |H| x Counter < γ – |H|, thì quay lại bước c.
Tạo ra một giá trị mặt nạ với γ – |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 γ – |H| bit được nối từ trái sang phải theo thứ tự như sau:
– γ – |H| – ε – 1 bit 0;
– Một bit giới hạn bằng 1;
– Giá trị salt E.
5) Bằng cách thực hiện phép XOR, áp dụng mặt nạ vào xâu trung gian, từ đó tạo ra một xâu bit đã được tạo mặt nạ.
6) Tạo ra F bằng cách nối xâu bit đã đượ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
7) Nếu γ bit của F đều bằng 0 (trường hợp rất hiếm gặp), thì quay lại bước 1 (giá trị salt E không phù hợp). Ngược lại, trả về F.
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.
1) Nếu γ bit của F* đều bằng 0, thì loại bỏ. Ngược lại, tiếp tục.
2) Từ |H| bit phải nhất của F*, ký hiệu là HH*, tạo mặt nạ gồm γ – |H| bit giống bước 3 ở trên.
3) Thực hiện phép XOR, áp dụng mặt nạ tới γ – |H| bit trái nhất của F*, để khôi phục lại một xâu trung gian trong đó bit giới hạn là bit đầu tiên được đặt 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ỏ.
4) 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.
|
H = h(M) |
HH = h((“0000 0000 0000 0000“)||H||E*) |
5) 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.
Thư mục tài liệu tham khảo
[1] M. Bellare and P. Rogaway, The exact security of digital signatures: How to sign with RSA and Rabin, in Proc. Eurocrypt ’96, U. Maurer, Ed., Lecture Notes in Computer Science, Vol. 1070, Advances in Cryptology, pp. 399-416, Berlin, Springer-Verlag, 1996
[2] J.-S. Coron, On the exact security of full domain hashing, in Proc. Crypto 2000, M. Bellare, Ed., Lecture Notes in Computer Science, Vol. 1880, Advances in Cryptology, pp. 229-235, Berlin, Springer-Verlag, 2000
[3] A. Fujioka, T. Okamoto and S. Miyaguchi, ESIGN, an efficient digital signature implementation for smart cards, in Proc. Eurocrypt ’91, D.W. Davies, Ed., Lecture Notes in Computer Science, Vol. 547, Advances in Cryptology, pp. 446-457, Berlin, Springer-Verlag, 1992
[4] M. Gardner, A new kind of cipher that would take millions of years to break, Scientific American, Vol. 237-8, pp. 120-124,1977
[5] M. Girault. Self-certified public keys, in Proc. Eurocrypt ’91, D.W. Davies, Ed., Lecture Notes in Computer Science, Vol. 547, Advances in Cryptology, pp. 490-497, Berlin, Springer-Verlag, 1992
[6] M. Girault and J.C. Paillès. On-line / off-line RSA-like, Workshop on Cryptography and Coding 2003
[7] S. Goldwasser, S. Micali and C. Rackoff, The knowledge complexity ofinteractive proof systems, in SIAM Journal on Computing, Vol. 18, pp. 186-208,1989
[8] S. Goldwasser, S. Micali and R.L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, in SIAM Journal on Computing, Vol. 17-2, pp. 491-531, April 1988
[9] L.C. Guillou and J.-J. Quisquater, A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory, in Proc. Eurocrypt ’88, C.G. Günther, Ed., Lecture Notes in Computer Science, Vol. 330, Advances in Cryptology, pp. 123-128, Berlin, Springer-Verlag, 1988
[10] L.C. Guillou and J.-J. Quisquater, A paradoxical identity-based signature scheme resulting from zeroknowledge, in Proc. Crypto ’88, Sh. Goldwasser, Ed., Lecture Notes in Computer Science, Vol. 403, Advances in Cryptology, pp. 216-231, Berlin, Springer-Verlag, 1988
[11] L.C. Guillou, M. Ugon and J.-J. Quisquater, Cryptographic authentication protocols for smart cards, in Computer Networks Magazine, Vol. 36, pp. 437-451, North Holland Elsevier Publishing, July 2001
[12] B. Kaliski, On hash function firewalls in signature schemes, in Proc. Cryptographers’ Track RSA Conference 2002, B. Preneel, Ed, Lecture Notes in Computer Science, Vol. 2271, pp. 1-16, Berlin, Springer-Verlag, 2002
[13] D.E. Knuth, The Art of Computer Programming. Vol. 2. Addison-Wesley, 3rd edition, 1997
[14] A.K. Lenstra and E.R. Verheul, Selecting cryptographic key sizes, in Journal of Cryptology, Vol. 14-4, pp. 255-293, 2001
[15] A.J. Menezes, P.C. van Oorschot and S.A. Vanstone, Handbook of Applied Cryptography, Boca Raton, CRC Press, 1997
[16] A.M. Odlyzko, The future of integer factorization, in Cryptobytes, Vol. 1-2, pp. 5-12, Summer 1995
[17] G. Poupard and J. Stern, Security analysis of a practical “on the fly” authentication and signature generation, in Proc. Eurocrypt ’98, K. Nyberg, Ed., Lecture Notes in Computer Science, Vol. 1403, Advances in Cryptology, pp. 422-436, Berlin, Springer-Verlag, 1998
[18] M.O. Rabin, Digital signatures and public-key functions as intractable as factorization, Technical Report MIT/LCS/TR-212, MIT Laboratory for Computer Science, January 1979
[19] R.L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, in Communications of the ACM, Vol. 21-2, pp. 120-126, 1978
[20] R. Silverman, A cost-based security analysis of symmetric and asymmetric key lengths, RSA Labs Bulletin, Vol. 13, April 2000 (revised November 2001)
[21] X. Wang and H. Yu, How to break MD5 and other hash-functions, in Proc. Eurocrypt ’05, R. Cramer, Ed., Lecture Notes in Computer Science, Vol. 3494, Advances in Cryptology, pp. 19-35, Berlin, Springer-Verlag, 2005
[22] X. Wang, Y. Yin and H. Yu, Finding collisions in the full SHA-1, in Proc. Crypto ’05, V. Shoup, Ed., Lecture Notes in Computer Science, Vol. 3621, Advances in Cryptology, pp. 17-36, Berlin, SpringerVeriag, 2005
[23] H.C. Williams, Some public-key crypto-functions as intractable as factorization, in Proc. Crypto ’84, G.R. Blakley and D. Chaum, Eds., Lecture Notes in Computer Science, Vol. 196, Advances in Cryptology, pp. 66-70, Berlin, Springer-Verlag, 1985
[24] ISO/IEC 7816 (all parts), Identification cards – Integrated circuit cards
[25] ISO/lEC 8824-1:2002, Information technology – Abstract Syntax Notation One (ASN.1): Specification of basic notation
[26] ISO/IEC 8825-1:2002, Information technology – ASN.1 encoding rules: Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished Encoding Rules (DER)
[27] ISO/IEC 9594-8:2005, Information technology – Open Systems Interconnection – The Directory: Public-key and attribute certificate frameworks
[28] ISO/IEC 9796 (all parts), Information technology – Security techniques – Digital signature schemes giving message recovery
[29] TCVN 11817-3 (ISO/IEC 9798-3), Công nghệ thông tin – Các kỹ thuật an toàn – Xác thực thực thể – Phần 3: Cơ chế sử dụng kỹ thuật chữ ký số.
[30] ISO/IEC 9798-5:2004, Information technology – Security techniques – Entity authentication – Part 5: Mechanisms using zero-knowledge techniques
[31] TCVN 7817 (ISO/IEC 11770) (tất cả các phần), Công nghệ thông tin – Các kỹ thuật an toàn – Quản lý khóa
[32] ISO/IEC 15945:2002, Information technology – Security techniques – Specification of TTP services to support the application of digital signatures
[33] ISO/IEC 18031:2005, Information technology – Security techniques – Random bit generation
[34] ISO/IEC 18032:2005, Information technology – Security techniques – Prime number generation
[35] TCVN 12214-3 (ISO/IEC 14888-3), Công nghệ thông tin – Các kỹ thuật an toàn – Chữ ký số kèm phụ lục – Phần 3: Cơ chế dựa trên logarit rời rạc
| 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 | |||
| Số, ký hiệu văn bản | TCVN12214-2:2018 | Ngày hiệu lực | |
| Loại văn bản | Tiêu chuẩn Việt Nam | Ngày đăng công báo | |
| Lĩnh vực | Ngày ban hành | ||
| Cơ quan ban hành | Tình trạng | Còn hiệu lực | |
Các văn bản liên kết
| Văn bản được hướng dẫn | Văn bản hướng dẫn | ||
| Văn bản được hợp nhất | Văn bản hợp nhất | ||
| Văn bản bị sửa đổi, bổ sung | Văn bản sửa đổi, bổ sung | ||
| Văn bản bị đính chính | Văn bản đính chính | ||
| Văn bản bị thay thế | Văn bản thay thế | ||
| Văn bản được dẫn chiếu | Văn bản căn cứ |
