Luận án Nghiên cứu một số giải pháp đảm bảo an toàn và hiệu quả cho lược đồ chữ ký số kiểu EC-Schnorr

thì 𝑓(�̅�, �̅�) = 𝑓(𝑘, 𝑎). Nếu 𝑎, 𝑘 > 𝑞 2 , khi đó ta có: 𝑓(�̅�, �̅�) = 𝑎 − 𝑞 + 𝐴(𝑘 − 𝑞) + 𝐵 = 𝑎 + 𝐴𝑘 + 𝐵 − 𝑞 − 𝐴𝑞 = 𝑎 + 𝐴𝑘 + 𝐵 = 0 𝑚𝑜𝑑 𝑞. Tương tự, cho các trường hợp (𝑎 > 𝑞 2 , 𝑘 ≤ 𝑞 2 ) hoặc (𝑎 ≤ 𝑞 2 , 𝑘 > 𝑞 2 ). Xét các đa thức 𝑓1(𝑥, 𝑦) = 𝑞, 𝑓2(𝑥, 𝑦) = 𝑞𝑥 và 𝑓3(𝑥, 𝑦) = 𝑓(𝑥, 𝑦). Dễ thấy rằng: 𝑓𝑖(�̅�, �̅�) = 0 mod 𝑞 (với 𝑖 = 1,2,3). Ta xây dựng lưới 𝐿 được căng bởi các véctơ hàng của ma trận 𝐼 được định nghĩa như sau (các hàng của ma trận 𝐼 lần lượt là hệ số của đa thức 𝑓1(𝑥𝑋, 𝑦𝑌) = 𝑞, 𝑓2(𝑥𝑋, 𝑦𝑌) = 𝑞𝑋𝑥 và 𝑓3(𝑥𝑋, 𝑦𝑌) = 𝑌𝑦 + 𝐴𝑋𝑥 + 𝐵. 𝐼 = ( 𝑞 0 0 0 𝑞𝑋 0 𝐵 𝐴𝑋 𝑌 ) Do các hàng của 𝐼 là ℝ-độc lập tuyến tính nên lưới 𝐿 có số chiều là 𝑛 = 3. Áp dụng thuật toán rút gọn lưới LLL ta thu được một cơ sở mới 𝑏1 = (𝐶0, 𝐶1, 𝐶2), 𝑏2 = (𝐶3, 𝐶4, 𝐶5) và 𝑏3 = (𝐶6, 𝐶7, 𝐶8). ( 𝑞 0 0 0 𝑞𝑋 0 𝐵 𝐴𝑋 𝑌 ) 𝐿𝐿𝐿 → ( 𝐶0 𝐶1 𝐶2 𝐶3 𝐶4 𝐶5 𝐶6 𝐶7 𝐶8 ) 87 Theo định nghĩa, ta có định thức của lưới: det(𝐿) = |det(𝐼)| = 𝑞2𝑋𝑌. Đặt 𝛾0 = 𝐶0, 𝛾1 = 𝐶1 𝑋 , 𝛾2 = 𝐶2 𝑌 , 𝛾3 = 𝐶3, 𝛾4 = 𝐶4 𝑋 và 𝛾5 = 𝐶5 𝑌 . Khi đó, ta có: 𝑏1 = (𝛾0, 𝛾1𝑋, 𝛾2𝑌), 𝑏2 = (𝛾3, 𝛾4𝑋, 𝛾5𝑌). Tiếp theo ta đặt 𝑔1(𝑥, 𝑦) = 𝛾0 + 𝛾1𝑥 + 𝛾2𝑦 và 𝑔2(𝑥, 𝑦) = 𝛾3 + 𝛾4𝑥 + 𝛾5𝑦. Do 𝑔1(𝑥𝑋, 𝑦𝑌) và 𝑔2(𝑥𝑋, 𝑦𝑌) là các tổ hợp tuyến tính nguyên của 𝑓𝑖(𝑥𝑋, 𝑦𝑌) (với 𝑖 = 1,2,3) nên các đa thức 𝑔1(𝑥, 𝑦) và 𝑔2(𝑥, 𝑦) nhận (�̅�, �̅�) là nghiệm theo modulo 𝑞. Do đó, các đa thức 𝑔1(𝑥, 𝑦), 𝑔2(𝑥, 𝑦) thỏa mãn điều kiện thứ nhất của Bổ đề 3.13, tức là: 𝑔1(�̅�, �̅�) = 0 mod 𝑞 và 𝑔2(�̅�, �̅�) = 0 mod 𝑞 (3.7) Hơn nữa, ta có 𝑏1 = ‖𝑔1(𝑥𝑋, 𝑦𝑌)‖. Do đó, theo Mệnh đề 3.4, ta có: ‖𝑏1‖ < 2 3−1 4 (det(𝐿)) 1 3 = √2(𝑞2𝑋𝑌) 1 3. Mặt khác, theo giả thiết, ta có 𝑋𝑌 < 𝑞 6√6 . Suy ra ‖𝑔1(𝑥𝑋, 𝑦𝑌)‖ < 𝑞 √3 (3.8) Theo Bổ đề 3.13 và từ (3.7), (3.8), ta suy ra 𝑔1(�̅�, �̅�) = 0 trên vành số nguyên. Tương tự, ta có ‖𝑏2‖ = ‖𝑔2(𝑥𝑋, 𝑦𝑌)‖. Cũng theo Mệnh đề 3.4, ta có: ‖𝑏2‖ ≤ 2 1 4 ( det(𝐿) ‖𝑏1‖ ) 1 2 . Theo giả thiết, ta có ‖𝑏1‖ > 3√2𝑋𝑌. Suy ra: ‖𝑏2‖ ≤ 2 1 4 ( det(𝐿) ‖𝑏1‖ ) 1 2 < 2 1 4 ( 𝑞2𝑋𝑌 3√2𝑋𝑌 ) 1 2 = 𝑞 √3 . Khi đó, ta suy ra 𝑔2(�̅�, �̅�) = 0 trên vành số nguyên. Tiếp theo, ta giải hệ 2 phương trình 2 ẩn 𝑔1(𝑥, 𝑦) = 0 và 𝑔2(𝑥, 𝑦) = 0. Khi đó, nếu tồn tại 𝑦 sao cho 𝑦𝑃 = 𝑄 thì �̅� = �̅� .Từ �̅� ta có thể tìm được khóa bí mật dài hạn 𝑎.■ Từ Mệnh đề 3.15, ta xây dựng thuật toán tìm khóa bí mật dài hạn của lược đồ chữ ký số EC-Schnorr như sau: 88 Đầu vào: Các giá trị (𝑟, 𝑠) của lược đồ chữ ký số EC-Schnorr. Đầu ra: Khóa bí mật dài hạn 𝑎 hoặc tấn công không thực hiện được. Bước 1: Tính 𝐴 = −𝑟−1mod 𝑞 và 𝐵 = 𝑠𝑟−1mod 𝑞 Bước 2: Xây dựng lưới 𝐿 được sinh từ (𝑞, 0,0), (0, 𝑞𝑋, 0) và (𝐵, 𝐴𝑋, 𝑌). Sử dụng thuật toán LLL, tìm cơ sở LLL-rút gọn của lưới 𝐿. ( 𝑞 0 0 0 𝑞𝑋 0 𝐵 𝐴𝑋 𝑌 ) 𝐿𝐿𝐿 → ( 𝐶0 𝐶1 𝐶2 𝐶3 𝐶4 𝐶5 𝐶6 𝐶7 𝐶8 ) Bước 3.Tính 𝛾0 = 𝐶0, 𝛾1 = 𝐶1 𝑋 , 𝛾2 = 𝐶2 𝑌 , 𝛾3 = 𝐶3, 𝛾4 = 𝐶4 𝑋 và 𝛾5 = 𝐶5 𝑌 . Bước 4. Xây dựng đa thức 𝑔1(𝑥, 𝑦), 𝑔2(𝑥, 𝑦) tương ứng là véctơ đầu tiên và véctơ thứ hai của cơ sở LLL-rút gọn. Cụ thể, 𝑔1(𝑥, 𝑦) = 𝛾0 + 𝛾1𝑥 + 𝛾2𝑦 và 𝑔2(𝑥, 𝑦) = 𝛾3 + 𝛾4𝑥 + 𝛾5𝑦. Bước 5. Giải hệ phương trình { 𝑔1(𝑥, 𝑦) = 0 𝑔2(𝑥, 𝑦) = 0 Bước 6. Nếu tồn tại 𝑦 sao cho 𝑦𝑃 = 𝑄 thì trả về đầu ra là �̅� = 𝑦, còn không thì trả về “Tấn công không thực hiện được”. Nhận xét 3.16. Đặt 𝑋 = 2𝛼 , 𝑌 = 2𝛽, khi đó điều kiện 𝑋𝑌 < 𝑞/6√6 tương đương 2𝛼+𝛽 < 𝑞/6√6 hay 𝛼 + 𝛽 < log2(𝑞/6√6). Theo Mệnh đề 3.15, ta có thể khôi phục được khóa bí mật khi: |�̅�| < 𝑋 = 2𝛼 , |�̅�| < 𝑌 = 2𝛽 và 𝑋𝑌 < 𝑞/6√6 Do đó, để tránh tấn công thì ta cần chọn: |�̅�| > 𝑋 = 2𝛼 , |�̅�| > 𝑌 = 2𝛽 và 𝑋𝑌 > 𝑞/6√6. Khi đó 2𝛼+𝛽 > 𝑞/6√6 hay 𝛼 + 𝛽 > log2(𝑞/6√6). Vì vậy, ta chọn: 𝛼 > log2( 𝑞 6√6 ) 2 và 𝛽 > log2( 𝑞 6√6 ) 2 89 Khi đó, điều kiện |�̅�| > 𝑋 = 2𝛼 tương đương |�̅�| > 2 log2( 𝑞 6√6 ) 2 = ( 𝑞 6√6 )1/2. Tương tự, |�̅�| > 𝑌 = 2𝛽 tương đương |�̅�| > 2 log2( 𝑞 6√6 ) 2 = ( 𝑞 6√6 )1/2. Do (6√6) 1/2 nhỏ hơn rất nhiều so với 𝑞1/2 ( 𝑞1/2 = 2128 bit nếu 𝑞 = 2256 ) nên để tránh tấn công này, ta có thể chọn |�̅�| > 𝑞1/2 và |�̅�| > 𝑞1/2 tương đương 𝑞1/2 < 𝑎, 𝑘 < 𝑞 − 𝑞1/2. Thật vậy, với mọi 𝑞 > 4, ta có 𝑞1/2 < 𝑞/2. Khi đó, theo định nghĩa của �̅�, nếu 𝑎 ≤ 𝑞/2 thì �̅� = 𝑎, do đó điều kiện |�̅�| > 𝑞1/2 suy ra 𝑎 > 𝑞1/2. Ngược lại, nếu 𝑎 > 𝑞/2 thì �̅� = 𝑎 − 𝑞, do đó điều kiện |�̅�| > 𝑞1/2 suy ra −(𝑎 − 𝑞) > 𝑞1/2 hay 𝑎 𝑞1/2 tương đương 𝑞1/2 𝑞1/2, ta suy ra 𝑞1/2 < 𝑘 < 𝑞 − 𝑞1/2. Tấn công Poulakis lên lược đồ chữ ký số EC-Schnorr Tấn công này dựa trên một cách giải của các phương trình Conic có dạng 𝑟(𝑥, 𝑦) = 𝐷𝑥𝑦 + 𝐴𝑥 + 𝐵, trong đó 𝐷, 𝐴, 𝐵 ∈ ℤ. Vì vậy, ta có thể xây dựng tấn công chỉ cần một đa thức từ véctơ đầu tiên của cơ sở LLL-rút gọn. Cụ thể, thuật toán giải phương trình 𝑟(𝑥, 𝑦) là như sau: Đầu vào: Phương trình 𝑟(𝑥, 𝑦) = 𝐷𝑥𝑦 + 𝐴𝑥 + 𝐵 = 0 trong ℤ và phân tích ra thừa số nguyên tố của 𝐵. Đầu ra: Cặp (𝑥, 𝑦) ∈ ℤ2thỏa mãn 𝑟(𝑥, 𝑦) = 0. Bước 1. Tính tập 𝐷(𝐵) gồm tất cả các ước của số nguyên B. Bước 2. Với mỗi 𝑥 ∈ 𝐷(𝐵) tính 𝑦 = −(𝐵/𝑥 + 𝐴)/𝐷. Bước 3. Nếu 𝑦 ∈ ℤ thì trả về cặp (x,y), còn không thì trả về “không tìm được nghiệm”. Chứng minh tính đúng đắn: Giả sử (𝑥, 𝑦) ∈ ℤ2 là nghiệm của 𝑟(𝑥, 𝑦) = 0. Khi đó, 𝑥(𝐷𝑦 + 𝐴) = −𝐵. Suy ra 𝑥|𝐵 hay 𝐵 = 𝑥𝛽, trong đó 𝛽 ∈ ℤ. Đơn giản hóa phương trình, ta thu được 𝐷𝑦 + 𝐴 + 𝛽 = 0. Do đó, 90 𝑦 = −(𝛽 + 𝐴)/𝐷 = −(𝐵/𝑥 + 𝐴)/𝐷. Nếu 𝑦 ∈ ℤ thì ta có (𝑥, 𝑦) là nghiệm của 𝑟(𝑥, 𝑦) = 0. Mệnh đề 3.17. Đối với lược đồ chữ ký số EC-Schnorr, giả sử tồn tại các số nguyên dương 𝑋, 𝑌 sao cho |𝑘−1̅̅ ̅̅ ̅| < 𝑋, |�̅�| < 𝑌 và 𝑋2𝑌 < 𝑞/(6√6) thì có thể tìm được khóa bí mật dài hạn 𝑎 của lược đồ chữ ký trong thời gian đa thức. Chứng minh: Nhân cả hai vế của (3.6) với 𝑘−1 và 𝑟−1, ta có 𝑘−1𝑎 + (𝑠𝑟−1)𝑘−1 − 𝑟−1 = 0 mod 𝑞 Đặt 𝐴 = 𝑠𝑟−1mod 𝑞 và 𝐵 = −𝑟−1mod 𝑞. Khi đó, cặp (𝑘−1̅̅ ̅̅ ̅, �̅�) là nghiệm của phương trình đồng dư 𝑓(𝑥, 𝑦) = 𝑥𝑦 + 𝐴𝑥 + 𝐵 = 0 mod 𝑞. Xét các đa thức 𝑓1(𝑥, 𝑦) = 𝑞, 𝑓2(𝑥, 𝑦) = 𝑞𝑥 và 𝑓3(𝑥, 𝑦) = 𝑓(𝑥, 𝑦). Dễ thấy các đa thức này cũng nhận (𝑘−1̅̅ ̅̅ ̅, �̅�) là nghiệm trên modulo 𝑞. Xây dựng lưới 𝐿 được căng các véctơ hàng của ma trận 𝐽, ở đó 𝐽 có các hàng lần lượt là hệ số của các đa thức 𝑓1(𝑥𝑋, 𝑦𝑌) = 𝑞, 𝑓2(𝑥𝑋, 𝑦𝑌) = 𝑞𝑋𝑥 và 𝑓3(𝑥𝑋, 𝑦𝑌) = 𝑋𝑌𝑥𝑦 + 𝐴𝑋𝑥 + 𝐵. 𝐽 = ( 𝑞 0 0 0 𝑞𝑋 0 𝐵 𝐴𝑋 𝑋𝑌 ) Do các hàng của 𝐽 là ℝ-độc lập tuyến tính nên lưới có số chiều bằng 𝑛 = 3. Áp dụng thuật toán LLL vào lưới 𝐿 ta thu được một cơ sở mới như sau. ( 𝑞 0 0 0 𝑞𝑋 0 𝐵 𝐴𝑋 𝑋𝑌 ) 𝐿𝐿𝐿 → ( 𝐶0 𝐶1 𝐶2 𝐶3 𝐶4 𝐶5 𝐶6 𝐶7 𝐶8 ) Ta có det(𝐿) = |det(𝐼)| = 𝑞2𝑋2𝑌. Đặt 𝛾0 = 𝐶0, 𝛾1 = 𝐶1/𝑋, 𝛾2 = 𝐶2/𝑋𝑌 . Ta có 𝑏1 = (𝛾0, 𝛾1𝑋, 𝛾2𝑋𝑌). Đặt 𝑔1(𝑥, 𝑦) = 𝛾0 + 𝛾1𝑥 + 𝛾2𝑥𝑦. Do 𝑔1(𝑥𝑋, 𝑦𝑌) là các tổ hợp tuyến tính nguyên của 𝑓𝑖(𝑥𝑋, 𝑦𝑌) với 𝑖 = 1,2,3 nên 𝑔1(𝑘−1̅̅ ̅̅ ̅, �̅�) = 0 mod 𝑞. Do vậy đa thức 𝑔1(𝑥, 𝑦) thỏa mãn điều kiện trong Bổ đề 3.13. Bây giờ ta cần xác minh điều kiện để các đa thức 𝑔1(𝑥, 𝑦) thỏa mãn điều kiện của Bổ đề 3.13. Theo Mệnh đề 3.4, 91 ‖𝑏1‖ ≤ 2 3−1 4 (det(𝐿)) 1 3 = √2(𝑞2𝑋2𝑌) 1 3 Do đó, để 𝑔1(𝑥, 𝑦) thỏa mãn điều kiện của Bổ đề 3.13, ta cần √2(𝑞2𝑋2𝑌) 1 3 < 𝑞 √3 Nói cách khác, ta cần 𝑋2𝑌 < 𝑞 6√6 . Khi đó, ta có ‖𝑏1‖ = ‖𝑔1(𝑥𝑋, 𝑦𝑌)‖ < 𝑞 √3 . Thật vậy, nếu 𝛾2 = 0 thì 𝛾0 = 𝑞𝑡0, 𝛾1 = 𝑞𝑋𝑡1, với 𝑡0, 𝑡1 ∈ ℤ và 𝑞√2 < ‖𝑏1‖ < 𝑞/√3 (vô lý). Suy ra, 𝛾2 ≠ 0 và ‖𝑏1‖ = ‖𝑔1(𝑥𝑋, 𝑦𝑌)‖ < 𝑞 √3 . Theo Bổ đề 3.13, ta có 𝑔1(𝑘−1̅̅ ̅̅ ̅, �̅�) = 0 trên vành số nguyên. Áp dụng thuật toán giải phương trình cho 𝑔1(𝑥, 𝑦) ta thu được �̅� và 𝑘−1̅̅ ̅̅ ̅. Ta có thuật toán tìm khóa bí mật dài hạn của lược đồ EC-Schnorr theo Mệnh đề 3.17 như sau: Đầu vào: Các giá trị (𝑟, 𝑠) của EC-Schnorr. Đầu ra: Khóa 𝑎 hoặc “Tấn công không thực hiện được”. Bước 1. Tính 𝐴 = 𝑠𝑟−1 mod 𝑞 và 𝐵 = −𝑟−1mod 𝑞. Bước 2. Xây dựng lưới 𝐿 được sinh từ (𝑞, 0,0), (0, 𝑞𝑋, 0) và (𝐵, 𝐴𝑋, 𝑋𝑌). Sử dụng thuật toán LLL, tìm cơ sở LLL-rút gọn của lưới 𝐿. ( 𝑞 0 0 0 𝑞𝑋 0 𝐵 𝐴𝑋 𝑋𝑌 ) 𝐿𝐿𝐿 → ( 𝐶0 𝐶1 𝐶2 𝐶3 𝐶4 𝐶5 𝐶6 𝐶7 𝐶8 ) Bước 3. Tính: 𝛾0 = 𝐶0, 𝛾1 = 𝐶1/𝑋, 𝛾2 = 𝐶2/𝑋𝑌 . Bước 4. Xây dựng đa thức 𝑔1(𝑥, 𝑦) từ véctơ đầu tiên của cơ sở LLL- rút gọn. Cụ thể 𝑔1(𝑥, 𝑦) = 𝛾0 + 𝛾1𝑥 + 𝛾2𝑥𝑦. Bước 5. Sử dụng Thuật toán 3.3 giải phương trình Conic để tính tập 𝑆 gồm các nghiệm (𝑥, 𝑦) của đa thức 𝑔1(𝑥, 𝑦) = 0. Bước 6. Nếu tồn tại (𝑥0, 𝑦0) ∈ 𝑆 và 𝑦0𝑃 = 𝑄 thì trả về �̅� = 𝑦0, còn không trả về “Tấn công không thực hiện được”. 92 Nhận xét 3.18. Đặt 𝑋 = 2𝛼 , 𝑌 = 2𝛽, khi đó điều kiện 𝑋2𝑌 < 𝑞/6√6 tương đương 22𝛼+𝛽 < 𝑞/6√6 hay 2𝛼 + 𝛽 < log2(𝑞/6√6). Theo Mệnh đề 3.17, ta có thể khôi phục được khóa bí mật khi: |𝑘−1̅̅ ̅̅ ̅| < 𝑋, |�̅�| < 𝑌 và 𝑋2𝑌 < 𝑞 6√6 . Do đó, để tránh tấn công thì ta cần chọn: |𝑘−1̅̅ ̅̅ ̅| > 𝑋 = 2𝛼 , |�̅�| > 𝑌 = 2𝛽 và 𝑋2𝑌 > 𝑞/6√6. Khi đó 22𝛼+𝛽 > 𝑞/6√6 hay 2𝛼 + 𝛽 > log2(𝑞/6√6). Vì vậy, ta chọn 𝛼 > log2( 𝑞 6√6 ) 3 và 𝛽 > log2( 𝑞 6√6 ) 3 Khi đó, điều kiện |𝑘−1̅̅ ̅̅ ̅| > 𝑋 = 2𝛼 tương đương |𝑘−1̅̅ ̅̅ ̅| > 2 log2( 𝑞 6√6 ) 3 = ( 𝑞 6√6 )1/3. Tương tự, điều kiện, |�̅�| > 𝑌 = 2𝛽 tương đương |�̅�| > 2 log2( 𝑞 6√6 ) 3 = ( 𝑞 6√6 )1/3. Do (6√6) 1/3 nhỏ hơn rất nhiều so với 𝑞1/3 (𝑞1/3 ≈ 285 bit nếu 𝑞 = 2256) nên để tránh tấn công này, ta có thể chọn |𝑘−1̅̅ ̅̅ ̅| > 𝑞1/3, |�̅�| > 𝑞1/3, tương đương, 𝑞1/3 < 𝑎, 𝑘−1 < 𝑞 − 𝑞1/3. Nhận xét 3.19. Ngoài điều kiện liên quan đến 𝑎 và 𝑘−1, ta cũng có thể áp dụng tấn công có các điều kiện liên quan đến 𝑎−1 và 𝑘. Cụ thể, ta thực hiện biến đổi như sau. Nhân cả hai vế của phương trình (3.6) với 𝑎−1, ta có: 𝑎−1𝑘 − 𝑠𝑎−1 − 𝑟 = 0  mod 𝑞 Đặt 𝐴 = −𝑠 mod 𝑞 và 𝐵 = −𝑟 mod 𝑞. Khi đó, cặp (𝑎−1̅̅ ̅̅ ̅, �̅�) là nghiệm của phương trình đồng dư 𝑓(𝑥, 𝑦) = 𝑥𝑦 + 𝐴𝑥 + 𝐵 = 0 mod 𝑞. Áp dụng tấn công tương tự như đã được trình bày như trên, ta cũng có thể khôi phục được khóa bí mật dài hạn 𝑎 và khóa bí mật tức thời 𝑘 nếu |𝑎−1̅̅ ̅̅ ̅| < 𝑋, |�̅�| < 𝑌, trong đó 𝑋 = 2𝛼 , 𝑌 = 2𝛽 và 2𝛼 + 𝛽 < log2(𝑞/6√6). Vì vậy, để tránh tấn công trong trường hợp này ta có thể chọn 𝑞1/3 < 𝑎−1, 𝑘 < 𝑞 − 𝑞1/3. 93 Nhận xét 3.20. Trong lược đồ chữ số EC-Schnorr-M, khóa bí mật tức thời 𝑘𝑀 = 𝐻(𝑘||𝑚), trong đó 𝑘 ∈𝑅 [1, 𝑞 − 1]. Do đó, nếu các khóa bí mật dài hạn a và khóa bí mật tức thời 𝑘𝑀 của lược đồ chữ ký số EC-Schnorr-M thỏa mãn các điều kiện như trong lược đồ chữ ký số EC-Schnorr thì ta có thể khôi phục được khóa bí mật dài hạn và tức thời của lược đồ. Các kết quả thực nghiệm NCS đã cài đặt các Thuật toán 3.2 và 3.4 để tìm khóa bí mật của lược đồ chữ ký số EC-Schnorr và EC-Schnorr-M sử dụng phần mềm tính toán đại số Magma được cài đặt trên máy tính CPU Intel Core i7-6700 3.4 Ghz, 8Gb RAM, sử dụng bộ tham số NIST P-256 [40] có dạng 𝑦2 = 𝑥3 + 𝐴𝑥 + 𝐵 trường hữu hạn 𝔽𝑝 với các tham số cụ thể như trong Bảng 3.1 ở phần trên. Trong từng tấn công, các lược đồ EC-Schnorr-M, EC-Schnorr cùng sử dụng các khóa bí mật dài hạn 𝑎 và tức thời 𝑘 có các kích thước như sau: Tấn công q (bit) |�̅�|(bit) |𝑘−1̅̅ ̅̅ ̅|(bit) |�̅�|(bit) Thời gian (giây) Blake 256 126 256 126 0,01 Poulakis 256 80 80 256 1,36 Trong mỗi tấn công lên từng lược đồ chữ ký số, NCS thực nghiệm mô phỏng tấn công 100 lần. Chi tiết tỉ lệ thành công và thời gian trung bình được trình bày trong bảng sau: Lược đồ EC-Schnorr Lược đồ EC-Schnorr-M Tấn công Tỉ lệ thành công Thời gian trung bình Tỉ lệ thành công Thời gian trung bình Blake 72% 0,04 giây 71% 0,05 giây Poulakis 100% 1,6 giây 100% 1,7 giây 94 3.2.4. Đề xuất tiêu chuẩn cho khóa bí mật của lược đồ kiểu EC-Schnorr Nhận xét 3.21. Qua kết quả thực nghiệm, ta thấy rằng các tấn công có thể tìm được các khóa bí mật trong thời gian rất nhanh. Cụ thể, đối với lược đồ chữ ký số kiểu EC-Schnorr sử dụng cấp nhóm q có kích thước 256 bit, ta có thể khôi phục các khóa bí mật dưới 2 giây nếu thỏa mãn các điều kiện sau đây: - Theo tấn công của Blake: 𝑎, 𝑘 ∉ [𝑞1 2⁄ , 𝑞 − 𝑞1 2⁄ ] - Theo tấn công của Poulakis: 𝑎, 𝑘−1, 𝑎−1, 𝑘 ∉ [𝑞1 3⁄ , 𝑞 − 𝑞1 3⁄ ] Luận án đã dựa trên các tấn công tìm khóa bí mật trên lược đồ chữ ký số ECDSA để xây dựng các phiên bản tấn công tương tự lên lược đồ chữ ký số kiểu EC-Schnorr. Các kết quả lý thuyết và thực nghiệm cho thấy, trong lược đồ chữ ký số kiểu EC-Schnorr, khi các khóa ký thỏa mãn điều kiện tấn công thì phương pháp của Blake và Poulakis có thể tìm được các khóa ký trong thời gian rất nhanh. Do đó, để đảm bảo an toàn khi sử dụng các lược đồ chữ ký số trong thực tế ta cần phải lựa chọn các khóa ký và nghịch đảo của chúng một cách cẩn thận và chính xác nhằm tránh các tấn công như vậy. Tiêu chuẩn 3.3. Các khóa ký tức thời và khóa ký dài hạn trong lược đồ chữ ký kiểu EC-Schnorr phải thỏa mãn điều kiện sau để tránh các tấn công kiểu Blake và Poulakis: 𝑞1 2⁄ < 𝑎, 𝑎−1, 𝑘, 𝑘−1 < 𝑞 − 𝑞1 2⁄ . 3.2.5. Đánh giá về bộ nhớ và hiệu năng của EC-Schnorr-M khi áp dụng Tiêu chuẩn 3.3 Tiêu chuẩn 3.3 yêu cầu phải kiểm tra các tham số khóa bí mật dài hạn (𝑎, 𝑎−1) và tham số khóa bí mật tức thời 𝑘, 𝑘−1 nằm trong khoảng (𝑞1 2⁄ 𝑞 − 𝑞1 2⁄ ). Đối với việc kiểm tra 𝑎, 𝑎−1 ∈ (𝑞, 𝑞 − 𝑞1/2 ) không ảnh hưởng đến hiệu năng của lược đồ EC-Schnorr-M vì việc này chỉ phải thực hiện một lần và có thể đưa vào trong quá trình sinh tham số bí mật dài hạn của hệ mật. Việc kiểm tra khóa bí mật tức thời 𝑘, 𝑘−1 ∈ (𝑞, 𝑞 − 𝑞1/2 ) sẽ yêu cầu một phép tính nghịch đảo modulo (giá trị 𝑞 − 𝑞1/2 sẽ được tính toán trước bên 95 ngoài thuật toán chính của EC-Schnorr-M). Bộ nhớ tăng lên một khai báo biến 𝑘−1 𝑚𝑜𝑑 𝑛 với kích thước theo tiêu chuẩn an toàn tối thiểu cỡ 256-bit và một b; một biến dùng để lưu trữ giá trị 𝑞 − 𝑞1/2 với kích thước tối thiểu cỡ 256-bit. Như vậy bộ nhớ tăng thêm khoảng 02-byte (kết quả hiệu năng được đưa ra cụ thể ở mục 3.5). 3.3. Ý nghĩa của việc nghiên cứu và đề xuất tiêu chuẩn tăng cường an toàn cho khóa bí mật của lược đồ chữ ký số EC-Schnorr-M 3.3.1. Ý nghĩa của tiêu chuẩn về khóa bí mật Như đã trình bày ở mục 3.2, tất cả các chuẩn đối với hệ mật Elliptic hoặc lược đồ chữ ký số dựa trên đường cong elliptic đưa ra đều có các điểm chung về điều kiện cấp của đường cong và cấp của nhóm điểm (cấp của đường cong phải có ước nguyên tố lớn 𝑛 và độ lớn theo bit của 𝑛 đảm bảo tính khó giải của bài toán ECDLP. Điểm chung tiếp theo là tiêu chuẩn để chống lại những tấn công hiệu quả, phổ quát đối với hệ mật Elliptic, bao gồm tấn công MOV, tấn công kiểu đường cong bất quy tắc và siêu kỳ dị. Qua khảo sát, chỉ có duy nhất 2 chuẩn trên thế giới (ISO và SEC1v2 của Certicom) có tiêu chuẩn liên quan đến khóa bí mật, đó là yêu cầu về phân rã 𝑛 = ±1 của cấp nhóm. Bản chất ở đây liên quan đến kiểu tấn công đối với khóa bí mật dựa trên giả thuyết Diffie-Hellman mạnh, cái mà phụ thuộc vào phân rã của 𝑛 ± 1. Tiêu chuẩn này được khuyến cáo chỉ áp dụng được với các lược đồ mật mã mà tạo ra một bộ tiên đoán có thể trả về lũy thừa khóa bí mật của nó với một đầu vào bất kỳ [10], chẳng hạn như lược đồ chữ ký mù BLS và lược đồ mã hóa ElGamal nguyên thủy. Cách tiếp cận của NCS trong luận án này, một phần cũng giống như của ISO và Certicom, tập trung vào nghiên cứu các tấn công liên quan đến khóa bí mật của lược đồ để đưa ra tiêu chuẩn nhằm tránh tấn công trực tiếp khám phá khóa bí mật, một trong những kiểu tấn công mang tính thực tế. Các 96 Tiêu chuẩn 3.1, 3.2 và Tiêu chuẩn 3.3 mà NCS đưa ra mặc dù không xuất phát từ các công trình do NCS tự nghiên cứu, tuy nhiên NCS thấy rằng đây là một vấn đề cần được quan tâm, đặc biệt là đối với những người làm về kỹ thuật mật mã. Như vậy, với yêu cầu đảm bảo cho khóa bí mật luôn được đặt lên hàng đầu nên việc nghiên cứu, đề xuất tiêu chuẩn để đảm bảo an toàn hơn cho khóa bí mật là một việc làm có ý nghĩa khoa học và thực tiễn. 3.3.2. Ý nghĩa của lược đồ EC-Schnorr-M trong việc chống lại tấn công lặp khóa bí mật a) Mô tả tấn công Rowhammer Tấn công Rowhammer là một kỹ thuật tấn công cho phép kẻ tấn công sửa đổi dữ liệu trong bộ nhớ mà không cần truy cập đến nó. Bản chất của tấn công Rowhammer là sử dụng mã phần mềm để tạo ra lỗi vào phần cứng theo cách có thể kiểm soát được. Cụ thể là gây ra việc "lật bit" bằng cách truy cập nhanh và liên tục vào dữ liệu trong một hàng bộ nhớ trên chip RAM để tạo ra điện tích làm thay đổi dữ liệu được lưu trữ ở các địa chỉ khác trong "hàng bộ nhớ". Các hàng bộ nhớ tấn công được gọi là "hàng xâm lược" và hàng nơi xảy ra lật bit được gọi là "hàng nạn nhân". Trong công trình “Flipping Bits in Memory Without Accessing Them: An Experimental Study of DRAM Disturbance Errors” của nhóm tác giả Yoongu Kim đã chứng minh rằng, bằng cách liên tục truy cập vào hai vị trí bộ nhớ “hàng xâm lược” trong không gian địa chỉ ảo của một tiến trình, có thể gây ra sự thay đổi bit ở vị trí “hàng nạn nhân” thứ ba. Điều này có thể thực hiện được vì các tế bào DRAM ngày càng nhỏ và sát nhau hơn, làm cho việc ngăn chặn các tế bào DRAM tương tác điện với nhau trở nên khó khăn hơn. Do đó, việc truy cập vào một vị trí trong bộ nhớ có thể làm xáo trộn các vị trí 97 lân cận, khiến điện tích bị rò rỉ vào hoặc ra khỏi các ô nhớ lân cận, điều này có thể thay đổi giá trị của ô từ 1 thành 0 hoặc ngược lại. Hiện tượng lật bit được tạo ra bằng cách sử dụng đoạn mã nhỏ sau đây: code1a: mov (X),% eax // Đọc từ địa chỉ X mov (Y),% ebx // Đọc từ địa chỉ Y clflush (X) // Xóa bộ nhớ cache cho địa chỉ X clflush (Y) // Xóa bộ nhớ cache cho địa chỉ Y jmp code1a Quy trình gây ra hiện tượng lật bit được giải thích gồm hai công đoạn sau đây: - Lựa chọn địa chỉ: Để code1a gây ra hiện tượng lật bit, địa chỉ X và Y phải ánh xạ tới các hàng DRAM khác nhau trong cùng một khối. Mỗi chip DRAM chứa nhiều hàng ô. Truy cập một byte trong bộ nhớ bao gồm việc chuyển dữ liệu từ hàng vào “bộ đệm hàng” của chip (xả các ô của hàng trong quá trình này), đọc hoặc ghi nội dung của bộ đệm hàng, sau đó sao chép nội dung của bộ đệm hàng trở lại các ô của hàng ban đầu (sạc lại các tế bào). Chính quá trình “kích hoạt” một hàng (xả và sạc lại) có thể làm xáo trộn các hàng liền kề. Nếu điều này được thực hiện đủ số lần, giữa các lần tự động làm mới các hàng liền kề (thường xảy ra sau mỗi 64ms), điều này có thể gây ra hiện tượng lật bit trong các hàng liền kề. Bộ đệm hàng hoạt động như một bộ đệm, vì vậy nếu địa chỉ X và Y trỏ đến cùng một hàng, thì code1a sẽ chỉ đọc từ bộ đệm hàng mà không kích hoạt hàng liên tục. Hơn nữa, mỗi khối DRAM có khái niệm riêng về “hàng hiện đang được kích hoạt”. Vì vậy, nếu địa chỉ X và Y trỏ đến các khối khác nhau, code1a sẽ chỉ đọc từ bộ đệm hàng của các khối đó mà không kích hoạt các hàng liên tục. Tuy nhiên, nếu X và Y trỏ đến các hàng khác nhau trong cùng một giàn, code1a sẽ khiến các hàng của X và Y được kích hoạt nhiều lần. Đây được gọi là "Rowhammer". 98 - Bỏ qua bộ đệm: Không có lệnh CLFLUSH của code1a , các lần đọc bộ nhớ (MOV) sẽ được phân phát từ bộ đệm của CPU. Việc xóa bộ nhớ cache bằng CLFLUSH buộc các truy cập bộ nhớ được gửi đến DRAM bên dưới, điều này cần thiết để làm cho các hàng được kích hoạt nhiều lần. Trong nhiều năm kể từ khi cuộc tấn công Rowhammer đầu tiên được phát hiện, các nhà nghiên cứu đã chứng minh nhiều cách sử dụng kỹ thuật này để thay đổi dữ liệu được lưu trữ trên thẻ RAM, bao gồm cả thế hệ DDR3 và DDR4. Mặc dù ban đầu giới hạn trong các tình huống mà kẻ tấn công có quyền truy cập vật lý vào mục tiêu, các nhà nghiên cứu cuối cùng cho thấy một cuộc tấn công Rowhammer có thể được thực hiện từ xa thông qua web và sử dụng kỹ thuật này để giành quyền kiểm soát máy ảo Linux trên đám mây. Như các nhà nghiên cứu của Google Project Zero đã giải thích vào năm 2015, tấn công Rowhammer ngày càng khả thi và hiệu quả vì các tế bào DRAM đang dần trở nên nhỏ và sát nhau hơn. Việc thu nhỏ và khả năng đóng gói nhiều dung lượng bộ nhớ hơn đã làm cho việc ngăn chặn các tế bào DRAM tương tác điện với nhau trở nên khó khăn hơn. "Rowhammer là một hiện tượng ghép điện trong silicon của chính nó, cho phép bỏ qua tiềm năng của các chính sách bảo vệ phần cứng và bộ nhớ phần mềm. Điều này có thể cho phép thực thi các đoạn mã không tin cậy để thoát ra khỏi sandbox của nó và nắm quyền kiểm soát toàn bộ hệ thống" phát biểu từ nhóm nghiên cứu của Google (Yoongu Kim và các cộng sự). Yoongu Kim hiện là kỹ sư phần mềm tại Google, là một trong những nhà nghiên cứu đã báo cáo lỗ hổng Rowhammer đầu tiên. Tấn công này còn được mở rộng thành “Half-Double”, có thể gây ra các cú lộn bit ở khoảng cách của một hàng DRAM. Half-Double hiển thị các “hàng kẻ xâm lược” có thể gây ra hiện tượng lộn xộn trên các “hàng nạn nhân” ở xa nhau hơn. Nhóm nghiên cứu lưu ý rằng "Với Half-Double, chúng tôi đã quan sát thấy hiệu ứng Rowhammer 99 lan truyền đến các hàng bên ngoài các hàng liền kề, mặc dù sức mạnh bị giảm. Với ba hàng A, B và C liên tiếp, chúng tôi có thể tấn công C bằng cách hướng một số lượng rất lớn các quyền truy cập đến A, cùng với chỉ một số ít lượng quyền truy cập đến B. Dựa trên các thử nghiệm của chúng tôi, các quyền truy cập vào B có một hiệu ứng phi tuyến tính, trong khi đó chúng dường như vận chuyển hiệu ứng Rowhammer của A lên C". b) Đối với một số bộ sinh số ngẫu nhiên tồi Các bộ tạo số ngẫu nhiên có thể chia làm 2 loại chính: các bộ tạo số giả ngẫu nhiên (pseudo-random number generator -PRNG) và các bộ tạo số ngẫu nhiên thực sự (true-random number generator - TRNG). TRNGs là các cơ chế không tất định và có thể chia làm 2 loại dựa trên nguồn nhiễu mà nó sử dụng: TRNG vật lý và TRNG phi-vật lý. TRNG vật lý sử dụng các nguồn nhiễu vật lý cho bởi phần cứng chuyên dụng, chẳng hạn như đi-ốt nhiễu, dao động tự do, phân rã phóng xạ, hiệu ứng photon lượng tử, Trong khi, TRNG phi-vật lý sử dụng các nguồn nhiễu phi-vật lý chẳng hạn như dữ liệu hệ thống như các đầu ra của các hàm API, dữ liệu RAM hoặc thời gian hệ thống, hoặc thao tác bàn phím, di chuyển chuột, chạm màn hình. PRNGs là các cơ chế tất định tạo ra một chuỗi các số “có dạng ngẫu nhiên”. Tuy nhiên, với cùng một đầu vào cho trước thì một PRNG sẽ luôn tạo ra cùng một đầu ra. Một số PRNG an toàn đã được chuẩn hoá bởi NIST và ISO là Hash-DRBG, CTR-DRBG, HMAC-DRBG [8]. Ngoài ra còn có một số bộ tạo số giả ngẫu nhiên khác, như bộ tạo đồng dư tuyến tính; bộ tạo đồng dư bậc 2, bậc 3; bộ tạo luỹ thừa modular; bộ tạo Blum-Blum-Shub; bộ tạo Micali-Schnorr. Mặc dù nhiều bộ tạo số giả ngẫu nhiên đã được chứng minh an toàn về mặt lý thuyết, nhưng trong thực tế vẫn xuất hiện các tấn công lên các bộ tạo 100 này và dẫn đến phá vỡ các hệ mật sử dụng bộ tạo đó. Đa phần các tấn công thực tế là do lỗi cài đặt hoặc do kẻ tấn công cố tình gây lỗi lên bộ tạo. Đối với các lỗi cài đặt, việc thử nghiệm và đánh giá chặt chẽ có thể phát hiện được các lỗi này. Tuy nhiên, với các lỗi do kẻ tấn công cố tình gây lỗi (ví dụ các tấn công kênh kề lên các mạch phần cứng) lên thiết bị thì người thiết kế rất khó kiểm soát do sự phát triển nhanh chóng về năng lực tính toán. Do đó, vấn đề dùng lặp lại khóa bí mật tức thời, hoặc nhiều khóa bí mật tức thời có tính chất đặc biệt là chứa các dãy bit lặp lại giống nhau do bộ tạo số giả ngẫu nhiên là hoàn toàn có thể xảy ra. Để thấy được ý nghĩa thực tiễn của việc nghiên cứu đề xuất lược đồ chữ ký số EC-Schnorr-M trong việc chống lại tấn công sử dụng khóa bí mật bị lặp lại, chúng ta xem xét một số tấn công thực tế sau đây đối với các bộ sinh số ngẫu nhiên mà phá vỡ độ an toàn của hệ mật được sử dụng. • Bộ sinh số ngẫu nhiên trong thư viện mật mã OpenSSL Năm 2008, Bello đã khám phá ra rằng bộ sinh số ngẫu nhiên trong OpenSSL trên hệ điều hành Debian là có thể dự đoán. Lỗ hổng này là do một gói dữ liệu được cập nhật năm 2006 bởi một nhà thiết kế của Debian. Nhà thiết kế đó đã bỏ đi một phần code được sử dụng trong quá trình sinh mầm của bộ tạo số ngẫu nhiên. Bello sau đó đã phát hiện ra rằng phần code mà người lập trình đã bỏ đi là quan trọng đối với độ an toàn của hệ mật bởi vì nó chịu trách nhiệm xáo trộn dữ liệu ngẫu nhiên vào mầm. Điều này dẫn đến mầm sinh ngẫu nhiên trong OpenSSL là duy nhất dựa trên ID của quá trình đang xử lý, mà có tối đa 32768 khả năng mặc định bởi nền tảng Linux. Với chỉ 32768 mầm có thể, có nghĩa là mầm có thể dự đoán dễ dàng hơn và một cấu trúc OpenSSL bất kỳ mà sử dụng bộ sinh số ngẫu nhiên này sẽ trở nên dễ bị tổn thương bởi các tấn công. 101 • Khoá yếu trong các thiết bị mạng Năm 2012, một lỗ hổng nghiêm trọng trong việc sinh ngẫu nhiên trên hệ điều hành Linux đã dẫn đến một số lượng lớn các chứng chỉ TLS và các khoá SSH trở nên dễ dàng phân tích và do đó chúng bị thoả hiệp. Các nhà nghiên cứu chỉ ra rằng một số khoá bí mật của RSA có thể khôi phục được do các vấn đề về entropy thấp. • Lỗ hổng trong hệ thống chức thực số công dân Đài Loan Trong hội nghị Asiacrypt 2013, Bernstein cùng đồng sự đã chỉ ra rằng các thẻ căn cước thông minh được cấp bởi chính phủ Đài Loan có lỗ hổng. Nghiên cứu cũng liên quan đến các khoá bí mật có độ an toàn entropy thấp. Các nhà nghiên cứu đã đánh giá 2 triệu khoá RSA 1024-bit từ cơ sở dữ liệu “chứng minh nhân dân số” của Đài Loan và thấy rằng 184 các khoá trong đó bị phân tích dễ dàng trong vài giờ. Họ cho rằng các khoá RSA yếu đó là do một lỗ hổng nghiệm trọng trong bộ sinh số ngẫu nhiên phần cứng. Tính ngẫu nhiên được sử dụng cho việc sinh khoá RSA chứa không đủ entropy và đã tạo ra các mẫu có thể dự đoán và các số nguyên tố RSA chung có thể dự đoán. Các thẻ thông minh bị tấn công theo cách này trên một phạm vi lớn đã có một tác động mạnh lên xã hội Đài Loan thời điểm đó. • Lỗi sinh số ngẫu nhiên đối với ví Bitcoin trên Android Năm 2013, một mối nguy hiểm đã được phát hiện trong thư viện Java java.security, trong lớp SecureRandom. Lỗ hổng này là do SecureRandom có các giá trị va chạm, và dẫn đến nó có thể tạo ra cùng một đầu ra 2 lần (hiện tượng lặp khóa). Điều này có nghĩa là SecureRandom có một lỗ hổng entropy lớn vì đầu ra trở nên có thể dự đoán. Vì điều này, các thuật toán dựa trên SecureRandom để tạo khoá hoặc các thành phần ngẫu nhiên mật mã khác cũng bị thoả hiệp. 102 Một trong các thuật toán phụ thuộc đó là ví Bitcoin Android. Ví Bitcoin Android sử dụng thuật toán ký số ECDSA để ký các giao dịch Bitcoin, thuật toán này sử dụng lớp SecureRandom Java trên các thiết bị Android để tạo một số ngẫu nhiên cho mỗi chữ ký. Vì lỗ hổng này, cùng một số ngẫu nhiên có thể được tạo ra để dùng cho 2 chữ ký khác nhau. Khi đó, kẻ tấn công có thể dễ dàng khôi phục khoá bí mật của lược đồ. Sử dụng khoá bí mật đó, một kẻ tấn công có thể ký một giao dịch bất kỳ và do đó đánh cắp Bitcoin từ ví Bitcoin bị ảnh hưởng. Mối nguy hiểm này có một tác động lớn bởi vì tất cả các người dùng Android với Bitcoin được lưu trữ trên thiết bị Android sẽ gặp rủi ro trong việc bị đánh cắp Bitcoin bởi các kẻ tấn công khai thác lỗ hổng này. Sau khi mối nguy hiểm này được phát hiện, Google và Bitcoin đã cập nhật bản vá an toàn để chữa lỗi này. Sau khi sửa chữa, cài đặt ví Bitcoin Android sử dụng /dev/urandom để sinh trực tiếp số ngẫu nhiên cho các chữ ký của chúng, thay vì sử dụng lớp SecureRandom của Java. • NSA cài đặt backdoor trong chuẩn sinh số ngẫu nhiên Năm 2013, bộ sinh số ngẫu tất định dựa trên đường cong elliptic Dual_EC_DRBG mà được chấp nhận là một tiêu chuẩn quốc gia NIST SP 800-90A do ảnh hưởng của NSA, đã bị cộng đồng mật mã phản đối vì phát hiện tồn tại một điểm yếu cố ý trong thuật toán cũng như các đường cong elliptic được NIST đề nghị. Dựa trên các tài liệu rò rỉ từ Edward Snowden, bộ sinh số ngẫu nhiên Dual_EC_DRBG trong chuẩn SP 800-90A chính xác là "một bẫy bí mật của NSA", cũng như về sự an toàn của các đường cong elliptic do NIST đề nghị trong chuẩn của NIST. Chẳng hạn: - NIST P-256: Có đường cong xoắn là hơi yếu, độ an toàn 2121. - NIST P-256: Có đường cong xoắn rất yếu, độ an toàn chỉ là 259. Hơn nữa, có thể tồn tại các đường cong yếu mà ta chưa biết trong số các chuẩn do NIST đề xuất, một vài đường cong yếu ở dạng 𝑦2 = 𝑥3 − 3𝑥 + 𝑏. 103 3.4. So sánh kết quả đạt được của luận án 3.4.1. So sánh về lý thuyết Giải pháp đề xuất (EC-Schnorr-M) Lược đồ gốc (EC-Schnorr) Ghi chú An toàn chứng minh được Đã đưa ra chứng minh an toàn chi tiết, rõ ràng dựa trên phương pháp chứng minh an toàn của lược đồ Schnorr gốc Chưa có (chỉ mới có chứng minh an toàn cho lược đồ Schnorr gốc; việc áp dụng sang không là hiển nhiên) Luận án áp dụng lại phương pháp chứng minh an toàn của lược đồ Schnorr trên trường hữu hạn để chứng minh cho EC-Schnorr; sau đó chỉ ra sự tương đương về mặt an toàn chứng minh được giữa lược đồ này và phiên bản đề xuất; đây là cách tiếp cận mới và cần có sự hiểu biết sâu sắc về nguyên lý chứng minh dựa trên mô hình bộ tiên tri ngẫu nhiên ROM và Bổ đề Forking Chống tấn công lặp khóa Có Không Hiệu quả Thêm một phép tính hàm băm so với EC- Schnorr gốc Một phép tính hàm băm trong môi trường tính toán hạn chế (kích thước thông điệp nhỏ/trung bình) sẽ ảnh hưởng không đáng kể về hiệu năng so với lược đồ gốc Tiêu chuẩn 3.1 (yêu cầu khóa bí mật không Áp dụng cho khóa bí mật dài hạn Áp dụng cho khóa bí mật dài hạn và khóa bí mật tức thời - Do sử dụng thêm phép tính hàm băm đối với khóa bí mật tức thời nên thuật toán 104 có liên tiếp hai khối t-bit với 𝑡 ≥ 7) EC-Schnorr-M do NCS đề xuất không cần áp dụng cho khóa bí mật tức thời - Việc áp dụng cho khóa bí mật dài hạn chỉ cần kiểm tra một lần trong quá trình sinh tham số - Khi áp dụng tiêu chuẩn này cho khóa bí mật tức thời sẽ làm cho hiệu năng của thuật toán giảm đi Tiêu chuẩn 3.2 (yêu cầu khóa bí mật không có liên tiếp 3 khối t-bit với 3 ≤ 𝑡 ≤ 6) Áp dụng cho khóa bí mật dài hạn Áp dụng cho khóa bí mật dài hạn và khóa bí mật tức thời Do sử dụng thêm phép tính hàm băm đối với khóa bí mật tức thời nên thuật toán EC-Schnorr-M do NCS đề xuất không cần áp dụng cho khóa bí mật tức thời Tiêu chuẩn 3.3 (an toàn cho khóa bí mật) Áp dụng cho khóa bí mật dài hạn Áp dụng cho khóa bí mật dài hạn và khóa bí mật tức thời 3.4.2. So sánh về thực hành NCS đã thực nghiệm các thuật toán sinh khóa, ký và kiểm tra chữ ký của lược đồ chữ ký số EC-Schnorr và EC-Schnorr-M. Kết quả thực nghiệm được thực hiện trên phần mềm mã nguồn mở Sagemath trên máy tính với năng lực tính toán CPU Intel Core i7-6700 3.4 Ghz, 8Gb RAM. NCS sử dụng các tham số NIST với 𝑞 có kích thước 256 bit cùng với đường cong elliptic 𝐸: 𝑦2 = 𝑥3 + 𝑎𝑥 + 𝑏 được định nghĩa trên trường hữu hạn 𝔽𝑝: 105 𝑝:= 1157920892103562487626974469494075735300861434152903141 95533631308867097853951 𝑎 ≔ -3 𝑏 ≔ 4105836372515214212932612978004726840911444101599372555 4835256314039467401291 𝑞:= 1157920892103562487626974469494075735299969552241357603 42422259061068512044369 Trên mỗi thông điệp, NCS thực hiện 100 lần tính chữ ký sau đó lấy kết quả thời gian thực hiện trung bình nhằm đánh giá chính xác nhất thời gian thực hiện của các thuật toán. Do NCS sử dụng thuật toán ký ngẫu nhiên nên cùng một thông điệp khi ta thực hiện ký 100 lần thì sẽ sinh ra 100 chữ ký khác nhau. Hàm băm được sử dụng là hàm băm SHA256 được hỗ trợ trong thư viện Python. Lược đồ chữ ký số Kích thước văn bản Thuật toán sinh khóa (giây) Thuật toán sinh khóa + kiểm tra điều kiện khóa bí mật dài hạn (giây) Thuật toán ký (giây) Thuật toán ký+kiểm tra điều kiện khóa bí mật tức thời (giây) Thuật toán kiểm tra chữ ký (giây) EC-Schnorr 0,65 M 0.01372 0.01420 0.01500 0.01668 0.03006 1,3 MB 0.01400 0.01499 0.01741 0.01818 0.03214 3,04 MB 0.01491 0.01467 0.02175 0.02267 0.03686 7,6 MB 0.01465 0.01488 0.03231 0.03370 0.04701 10,5 MB 0.01421 0.01432 0.03860 0.03944 0.05574 19,2 MB 0.01438 0.01483 0.06145 0.06281 0.07644 EC- Schnorr-M 0,65 M 0.01400 0.01412 0.01912 0.01949 0.03060 1,3 MB 0.01423 0.01434 0.02144 0.02172 0.03138 3,04 MB 0.01432 0.01485 0.03021 0.03064 0.03686 7,6 MB 0.01429 0.01438 0.05142 0.05282 0.04872 10,5 MB 0.01410 0.01431 0.06650 0.06942 0.05687 19,2 MB 0.01450 0.01475 0.10563 0.10851 0.07563 106 Qua kết quả thực nghiệm, ta có thể thấy rằng: 1. Thuật toán sinh khóa của lược đồ chữ ký số EC-Schnorr và EC- Schnorr-M có thời gian thực hiện xấp xỉ nhau và không phụ thuộc vào kích thước thông điệp. Sai số giữa các lần thực hiện (0,001 giây) là phép sai số thực hiện trên máy tính. 2. Việc thêm các điều kiện kiểm tra khóa bí mật dài hạn và khóa bí mật tức thời hầu như không ảnh hưởng đến tốc độ thực thi của thuật toán sinh khóa và ký. 3. Thuật toán ký của lược đồ chữ ký số EC-Schnorr và EC-Schnorr-M có thời gian thực hiện phụ thuộc vào kích thước thông điệp. Với các văn bản có kích thước nhỏ thì hai thuật toán ký của hai lược đồ có thời gian sấp xỉ nhau. Khi kích thước văn bản lớn hơn thì thời gian chênh lệch tăng lên. Điều này là do trong thuật toán ký của lược đồ chữ ký số EC-Schnorr-M sử dụng thêm một phép tính hàm băm so với thuật toán ký của lược đồ chữ ký EC-Schnoor. 4. Thuật toán kiểm tra chữ ký của lược đồ chữ ký EC-Schnorr và EC- Schnorr-M có thời gian thực hiện xấp xỉ nhau và phụ thuộc vào kích thước thông điệp. Cụ thể, kích thước thông điệp nhỏ thì ta có thời gian kiểm tra chữ ký nhanh hơn và ngược lại. Tuy nhiên, với kích thước văn bản khoảng 19,2MB thì thời gian kiểm tra chữ ký của hai thuật toán vẫn rất nhanh (xấp xỉ 0,085 giây) 3.5. Kết luận Chương 3 Các kết quả chính trong chương này bao gồm: - Phân tích, đánh giá, tổng quát hóa tấn công khôi phục khóa ký dài hạn trong lược đồ chữ ký số kiểu EC-Schnorr và đề xuất tiêu chuẩn đối với thuật toán sinh khóa của lược đồ chữ ký số kiểu EC-Schnorr. (Khẳng định 3.6, Thuật toán 3.1, Khẳng định 3.11, Tiêu chuẩn 3.1, Tiêu chuẩn 3.2). 107 - Phân tích các tấn công và đề xuất tiêu chuẩn cho khóa bí mật tức thời, khóa bí mật dài hạn của lược đồ kiểu EC-Schnorr (Mệnh đề 3.15, Thuật toán 3.2, Mệnh đề 3.17, Thuật toán 3.4, Tiêu chuẩn 3.3). - Phân tích làm rõ ý nghĩa khoa học và thực tiễn của việc nghiên cứu, đề xuất lược đồ chữ ký số EC-Schnorr-M và các tiêu chuẩn an toàn cho khóa bí mật (mục 3.3 và mục 3.4). Nội dung của chương này liên quan đến các bài báo số [3], [4] (Danh mục các công trình khoa học đã công bố). 108 Lược đồ chữ ký số đóng vai trò quan trọng trong bảo mật và an toàn thông tin phục vụ phát triển Chính phủ điện tử. Việc ứng dụng các lược đồ chữ ký số dựa trên đường cong elliptic một cách an toàn và hiệu quả là một lựa chọn phù hợp cho thế hệ Internet kết nối vạn vật, cho cuộc cách mạng công nghiệp lần thứ 4. Với mục tiêu như vậy, luận án đã có những đóng góp cụ thể như sau: A. Các kết quả đạt được của luận án: - Phân tích độ an toàn và đánh giá một số yêu cầu về hàm băm được sử dụng để đảm bảo độ an toàn cho lược đồ chữ ký số EC-Schnorr. - Phân tích tính hiệu quả và khả năng ứng dụng của lược đồ chữ ký số EC-Schnorr. - Phân tích tấn công với việc sử dụng lặp lại khóa bí mật tức thời và đánh giá các giải pháp đã có để chống tấn công này (Kết quả 2.1, Kết quả 2.2, Kết quả 2.3, Mệnh đề 2.1). - Đề xuất lược đồ chữ ký số EC-Schnorr-M dựa trên lược đồ EC- Schnorr gốc (bổ sung thêm một phép tính hàm băm giữa khóa bí mật tức thời và thông điệp) cùng các phân tích, đánh giá và chứng minh an toàn trong mô hình bộ tiên tri ngẫu nhiên (Thuật toán 2.5, Mệnh đề 2.2, Hệ quả 2.4, Bổ đề 2.9, Bổ đề 2.10, Mệnh đề 2.11, Hệ quả 2.12). - Phân tích, đánh giá, tổng quát hóa tấn công khôi phục khóa ký dài hạn trong lược đồ chữ ký số kiểu EC-Schnorr và đề xuất tiêu chuẩn đối với thuật toán sinh khóa của lược đồ chữ ký số kiểu EC-Schnorr, trong đó có EC- Schnorr-M (Khẳng định 3.6, Thuật toán 3.1, Khẳng định 3.11, Tiêu chuẩn 3.1, Tiêu chuẩn 3.2). 109 - Phân tích các tấn công và đề xuất tiêu chuẩn cho khóa bí mật tức thời, khóa bí mật dài hạn của lược đồ chữ ký số EC-Schnorr-M (Mệnh đề 3.15, Thuật toán 3.2, Mệnh đề 3.17, Thuật toán 3.4, Tiêu chuẩn 3.3). - Phân tích làm rõ ý nghĩa khoa học và thực tiễn của việc nghiên cứu, đề xuất lược đồ chữ ký số EC-Schnorr-M và các tiêu chuẩn an toàn cho khóa bí mật dài hạn và tức thời. B. Những đóng góp mới của luận án: 1) Phân tích chỉ ra điểm yếu của giải pháp sử dụng 2 khóa bí mật tức thời nhằm ngăn chặn sử dụng trùng khóa trong quá trình tạo chữ ký. 2) Đề xuất một lược đồ chữ ký số EC-Schnorr-M dựa trên lược đồ EC- Schnorr gốc nhằm giảm thiểu việc sử dụng trùng lặp khóa bí mật tức thời, với các phân tích, đánh giá và chứng minh an toàn trong mô hình bộ tiên tri ngẫu nhiên. 3) Đề xuất tiêu chuẩn đối với thuật toán sinh khóa của lược đồ chữ ký số kiểu EC-Schnorr, trong đó có EC-Schnorr-M nhằm tránh bị tấn công khi khóa bí mật tức thời có các khoảng bit lặp. 4) Đề xuất tiêu chuẩn cho khóa bí mật tức thời, khóa bí mật dài hạn của lược đồ chữ ký số EC-Schnorr-M nhằm chống tấn công kiểu Blake và Poulakis. C. Hướng nghiên cứu tiếp theo: - Nghiên cứu, đánh giá về khả năng ảnh hưởng của khóa bí mật dài hạn (về không gian, về các tấn công đối với hàm băm) của lược đồ chữ ký số EC- Schnorr-M. - Nghiên cứu, đánh giá về lý thuyết và thực nghiệm các tấn công cài đặt đối với lược đồ chữ ký số EC-Schnorr-M trong các thiết bị IoT. 110 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ [1]. Triệu Quang Phong, Nguyễn Quốc Toàn, Nguyễn Tiến Xuân, “Phân tích về hai lỗi của ECDSA và các biến thể so với GOST R 34.10- 2012”, Chuyên san Nghiên cứu khoa học và công nghệ trong lĩnh vực ATTT, Ban Cơ yếu Chính phủ, số 3.CS(04)-2016. [2]. Đặng Minh Tuấn, Nguyễn Văn Căn, Nguyễn Ánh Việt, Nguyễn Tiến Xuân, “Đề xuất chữ ký số ủy nhiệm và ứng dụng cho ủy nhiệm chi trong hệ thống Bítcoin”, Kỷ yếu Hội nghị Khoa học công nghệ Quốc gia lần thứ X: Nghiên cứu cơ bản và ứng dụng Công Nghệ thông tin (FAIR); Đà Nẵng, ngày 17-18/8/2017, trang 131-137. [3]. Nguyễn Tiến Xuân, Khúc Xuân Thành, Nguyễn Quốc Toàn, “Nghiên cứu về độ an toàn của khóa bí mật trong lược đồ chữ ký số EC- Schnorr”, Hội thảo quốc gia lần thứ XXI: Một số vấn đề chọn lọc của công nghệ thông tin và truyền thông; Thanh Hóa, ngày 27-28 tháng 7 năm 2018, trang 256-261. [4]. Nguyễn Tiến Xuân, Khúc Xuân Thành và Nguyễn Quốc Toàn, “Về độ an toàn của lược đồ chữ ký số EC-Schnorr khi khóa bí mật tức thời có các khoảng bit lặp lại”, HNUE JOURNAL OF SCIENCE, Natural Sciences, 2018, Volume 63, Issue 11A, trang 3-16. [5]. Nguyễn Tiến Xuân, Nguyễn Quốc Toàn, “Về một giải pháp đảm bảo an toàn khóa bí mật tức thời trong các lược đồ chữ ký số dựa trên ECDLP”, Tạp chí Nghiên cứu khoa học và Công nghệ quân sự, Số Đặc san, tháng 8 năm 2019, trang 52-61. 111 Tài liệu tham khảo tiếng Việt [1]. Nguyễn Quốc Toàn, “Nghiên cứu xây dựng các tham số an toàn cho hệ mật Elliptic và ứng dụng”, Luận án TS, Viện KH&CN quân sự, 2012. [2]. Nguyễn Quốc Toàn và nhóm đề tài, “Xây dựng thuật toán và chương trình sinh tham số an toàn cho lược đồ chữ ký số GOST R 34.10- 2012”, Ban Cơ yếu Chính phủ, Hà Nội, 2016. [3]. Võ Tùng Linh và nhóm đề tài, “Nghiên cứu cơ sở lý thuyết và xây dựng chương trình chứng minh tính nguyên tố dựa trên đường cong elliptic và ứng dụng”, Ban Cơ yếu Chính phủ, Hà Nội, 2012. Tài liệu tham khảo tiếng Anh [4]. A Statistical Test Suite for the Validation of Random Number Generators and Pseudorandom Number Generators for Cryptographic Applications, NIST Special Publication 800-22rev1a, April 2010. [5]. Amos Fiat and Adi Shamir, “How to prove yourself: Practical solutions to identification and signature problems”, In Andrew M. Odlyzko, editor, CRYPTO 1986. [6]. Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász,“Factoring polynomials with rational coefficients”, Mathematische Annalen, Vol. 261, No. 4, pp. 515–534. [7]. Arjen Klaas Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung, and Christophe Wachter. Public keys. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO, volume 7417 of Lecture Notes in Computer Science, pages 626-642. Springer, 2012. [8]. Barker, E. and J. Kelsey, NIST special publication 800-90A: Recommendation for random number generation using deterministic random bit generators, 2012. 112 [9]. Brown, Daniel RL. "Sec 2: Recommended elliptic curve domain parameters." Standars for Efficient Cryptography (2010). [10]. Cheon J., Security Analysis of the Strong Diffie-Hellman Problem, Annual International Conference on the Theory and Applications of Cryptographic Techniques, In: Eurocrypt 2006. [11]. Claus-Peter Schnorr, “Efficient identification and signatures for smart cards”, CRYPTO’89, volume 435, Springer-Verlag, 1990. [12]. Daniel R. L. Brown, SEC1v2: Elliptic Curve Cryptography, Standards for Efficient Cryptography, 2009. [13]. Daniel J. Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange, and Nicko van Someren. Factoring RSA keys from certified smart cards: Coppersmith in the wild. Cryptology ePrint Archive, Report 2013/599, 2013. [14]. David Pointcheval and Jacques Stern,“Security arguments for digital signatures and blind signatures”, Journal of Cryptology, 13(3):361- 396, 2000. [15]. David Brumley and Dan Boneh. Remote timing attacks are practical. Computer Networks, 48(5):701–716, 2005. [16]. Don Johnson, Alfred Menezes, and Scott Vanstone, “The Elliptic Curve Digital Signature Algorithm (ECDSA)”, 2001. [17]. Dolmatov, A. Degtyarev, “GOST R 34.10-2012: Digital Signature Algorithm”, https://tools.ietf.org/html/rfc7091. [18]. D. Boneh and G. Durfee, “Cryptanalysis of RSA with private key d less than N/sup 0.292”, IEEE trans. on Info. Theory, 46(4):1339– 1349, 2000. [19]. D. Pointcheval and J. Stern, “Security Proofs for Signature Schemes”, Eurocrypt '96, LNCS1070, Springer-Verlag, Berlin, 1996. 113 [20]. D. Poddebniak, et al, “Attacking deterministic signature schemes using fault attacks”, (EuroS&P), IEEE, 2018. [21]. D. Poulakis, “Some lattice attacks on DSA and ECDSA”, Applicable Algebra in Engineering, Comm. and Comp, 2011. [22]. Ernest F. Brickell, David Pointcheval, Serge Vaudenay, and Moti Yung, “Design validations for discrete logarithm based signature schemes”, In Hideki Imai and Yuliang Zheng, editors, PKC 2000, volume 1751 of LNCS, pages 276-292. Springer-Verlag, 2000. [23]. G. Sarath, D. C. Jinwala, and S. Patel, “A Survey on Elliptic Curve Digital Signature Algorithm and Its Variants”, CSE, DBDM, CCNET, AIFL, SCOM, CICS, 121-136, 2014. [24]. G. Neven, Nigel P. Smart, and B. Warinschi, “Hash function requirements for Schnorr signatures”, Journal of Mathematical Cryptology 3.1, 69-87, 2009. [25]. Hakim Khali and Ahcene Farah, “DSA and ECDSA-based MultiSignature Schemes”, IJCSNS International Journal of Computer Science and Network Security, 2007. [26]. H.Z. Liao, Hung-Zih, and Y.Y. Shen, “On the Elliptic curve digital signature algorithm”, Tunghai Science 8: 109-126, 2006. [27]. ISO/IEC 14888-3-2006/Amd 1-2010, “Elliptic Curve Russian Digital Signature Algorithm, Schnorr Digital Signature Algorithm, Elliptic Curve Schnorr Digital Signature Algorithm, and Elliptic Curve Full Schnorr Digital Signature Algorithm”, 2010. [28]. ISO/IEC 11770-3:2008, “Information Technology-Security Techniques-Key Management-Part 3: Mechanisms Using Asymmetric Techniques”, 2008. [29]. ISO/IEC 15946-5:2017, Information technology - Security techniques - Cryptographic techniques based on elliptic curves - Part 5: Elliptic curve generation, 2017. 114 [30]. I.F. Blake, and T. Garefalakis. “On the security of the digital signature algorithm”. Designs, Codes and Cryptography, 2002. [31]. J. Malone-Lee and N. P. Smart, “Modifications of ECDSA”. In Proceedings of Selected Areas in Cryptography - SAC’02, 2002. [32]. Kai Michaelis, Christopher Meyer, and J¨org Schwenk. Randomly failed! the state of randomness in current java implementations. In Ed Dawson, editor, CT-RSA, volume 7779 of Lecture Notes in Computer Science, pages 129- 144. Springer, 2013. [33]. K. A. Draziotis, “DSA lattice attacks based on Coppersmith’s method”, Information Processing Letters, 116(8):541–545, 2016. [34]. Kan. W, Analysis of Underlying Assumptions in NIST DRBGs, IACR Cryptol ePrint Arch, 2007. [35]. L. Lamport, Constructing digital signatures from a one-way function, Technical Report CSL98, SRI International, 1979. [36]. Mihir Bellare, Zvika Brakerski, Moni Naor, Thomas Ristenpart, Gil Segev, Hovav Shacham, and Scott Yilek. Hedged public-key encryption: How to protect against bad randomness. In Mitsuru Matsui, editor, ASIACRYPT, volume 5912 of Lecture Notes in Computer Science, pages 232-249. Springer, 2009. [37]. Murray R Bremner, “Lattice basis reduction: an introduction to the LLL algorithm and its applications”, CRC Press, 2002. [38]. Nadia Heninger, Zakir Durumeric, Eric Wustrow, and J. Alex Halderman. Mining your Ps and Qs: Detection of widespread weak keys in network devices. In Proceedings of the 21st USENIX Security Symposium, August 2012. [39]. Nicolas Gama and Phong Nguyen, “Predicting lattice reduction”. Advances in Cryptology, Eurocrypt’08, pp. 31–51, 2008. 115 [40]. NIST FIPS 186-4:2013, FIPS 186-5:2019 (draft), “Digital signature standard (dss)”, 2019. [41]. N. Fleischhacker, T. Jager, and D. Schröder. “On tight security proofs for Schnorr signatures”. International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2014. [42]. Paul Kocher, Joshua Jaffe, and Benjamin Jun. Differential power analysis. In Advances in cryptology—CRYPTO’99, pages 789–789. Springer, 1999 [43]. Paul C Kocher. Timing attacks on implementations of Diffie- Hellman, RSA, DSS, and other systems. In Annual International Cryptology Conference, pages 104–113. Springer, 1996. [44]. Peter James Leadbítter, Dan Page, and Nigel P Smart, “Attacking DSA under a repeated bits assumption”, In CHES, Vol. 3156, pp. 428–440, 2004. [45]. Phillip Rogaway. Nonce-based symmetric encryption. In Roy and Meier [32], pages 348-359. [46]. Phillip Rogaway and Thomas Shrimpton. A provable-security treatment of the key-wrap problem. In Vaudenay [33], pages 373-390. [47]. Phong Q Nguyen and Igor E Shparlinski, “The insecurity of the Elliptic curve digital signature algorithm with partially known nonces”. Designs, codes and cryptography, pp. 201–217, 2003. [48]. R.C. Merkle, A certified digital signature based on a conventional function, in: Advances in Cryptology––Crypto87, LNCS, 293, 1987, pp. 369–378. [49]. Savu, Laura, “Signcryption Scheme based on Schnorr Digital Signature”, 2012. 116 [50]. Scott Yilek. Resettable public-key encryption: How to encrypt on a virtual machine. In Josef Pieprzyk, editor, CT-RSA, volume 5985 of Lecture Notes in Computer Science, pages 41-56. Springer, 2010. [51]. Seny Kamara and Jonathan Katz. How to encrypt with a malicious random number generator. In Kaisa Nyberg, editor, FSE, volume 5086 of Lecture Notes in Computer Science, pages 303-315. Springer, 2008. [52]. Seurin, Yannick, “On the exact Security of Schnorr-Type Signatures in the Random Oracle Model”, Cryptology ePrint Archive 2012. [53]. SP 800-57 Part 1 Rev. 5 Recommendation for Key Management: Part 1 – General. [54]. Technical Guideline TR-03111 Elliptic Curve Cryptography Version 2.0, Bundesamt fur Sicherheit in der Informationstechnik, Germany, [55]. Thomas Ristenpart and Scott Yilek. When good randomness goes bad: Virtual machine reset vulnerabilities and hedging deployed cryptography. In NDSS. The Internet Society, 2010. [56]. T. Pornin, “RFC 6979: Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)”, August 2013. [57]. T. Q. Phong, N. Q. Toàn, “Some Security Comparisonsof GOST R 34.10-2012 and ECDSA Signature Schemes”, 6th Workshop on Current Trends in Cryptology (CTCrypt 2017), June 5-7, 2017, Saint Petersburg, Repino, Russia. Pre-proceedings, p 140-158. [58]. Y. Chen and Phong Q Nguyen, “BKZ 2.0: Better lattice security estimates”, In Inter. Conference on the Theory and Application of Cryptology and Infor. Security, pp. 1–20, 2011. 117 [59]. Yevgeniy Dodis, David Pointcheval, Sylvain Ruhault, Damien Vergnaud, and Daniel Wichs. Security analysis of pseudo-random number generators with input: /dev/random is not robust. [60]. Zvi Gutterman, Benny Pinkas, and Tzachy Reinman, Analysis of the linux random number generator, IEEE Computer Society, 2006.