Bài giảng Mật mã ứng dụng: Bài toán logarit rời rạc và Diffie-Hellman - Đại học Bách khoa Hà Nội

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:50

Thêm vào BST

Báo xấu

25
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Mật mã ứng dụng: Bài toán logarit rời rạc và Diffie-Hellman" trình bày các nội dung chính sau đây: Định nghĩa Nhóm; Cấp của một phần tử trong nhóm; Hàm logarit rời rạc và hàm mũ; Bài toán Logarit rời rạc;... Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Mật mã ứng dụng: Bài toán logarit rời rạc và Diffie-Hellman - Đại học Bách khoa Hà Nội

Mật mã ứng dụng Bài toán logarit rời rạc và Diffie-Hellman
Nội dung • Bài toán Logarit rời rạc • Bài toán Diffie-Hellman
Định nghĩa Nhóm Một nhóm Abel (",⋅) thoả mãn các tính chất sau: 1. Có phần tử đơn vị: 1 ∈ # thoả mãn ∀% ∈ #, % ⋅ 1 = 1 ⋅ % = % 2. Mọi phần tử đều khả nghịch: ∀% ∈ #, ∃* ∈ # thoả mãn % ⋅ * = 1 3. Kết hợp: ∀%, *, + ∈ # ta có % ⋅ (* ⋅ +) = (% ⋅ *) ⋅ + 4. Giao hoán: ∀%, * ∈ # ta có % ⋅ * = * ⋅ %
Cấp của một phần tử trong nhóm • Cấp của phần tử !, ký hiệu ord(a), là số " > 0 nhỏ nhất thoả mãn !! = 1 ∈ (. • Định lý Lagrange: Trong nhóm hữu hạn ( với lực lượng ), ta có ∀! ∈ (, ord(!) ∣ ). • Hệ quả: Trong nhóm hữu hạn ( với lực lượng ), ta có ∀! ∈ (, !" = 1. • Ký hiệu: ⟨!⟩ = {!# ∣ 2 ≥ 0} là nhóm con sinh bởi !.
Nhóm vòng • Ký hiệu ⟨"⟩ = {"! ∣ ' ≥ 0} là nhóm con sinh bởi ". • Nếu ⟨"⟩ = + thì " là một phần tử sinh của +. • Khẳng định: |⟨"⟩| = ord("). • Định nghĩa: G là nhóm vòng nếu có g thoả mãn ⟨/⟩ = +
Hàm logarit rời rạc và hàm mũ • Khẳng định: Nếu + là nhóm vòng cấp 0 và / là phần tử sinh, thì quan hệ 1 ↔ /" là 1-to-1 giữa {0,1, … , 0 − 1} và +. • Hàm mũ x à gx • Hàm logarit rời rạc gx à x
Tính ngẫu nhiên của lũy thừa 627x (mod 941)
Bài toán Logarit rời rạc • Xét / là một phần tử sinh của ℤ∗ và ℎ ∈ ℤ∗ . # # • Bài toán Logarit rời rạc (DLP) là bài toán tìm một số mũ 1 thỏa mãn / " ≡ ℎ mod ;. • Số 1 được gọi là logarit rời rạc cơ sở / của ℎ và ký hiệu Dlog% (ℎ).
Bài tập Hãy tính các logarit rời rạc sau. 1. Dlog& (13) trong modun nguyên tố 23 2. Dlog'( (22) trong modun nguyên tố ; = 47. 3. Dlog)&* (608) trong modun nguyên tố ; = 941.
Tính Logarit rời rạc • Xét số nguyên tố ; = 56509, và ta có thể kiểm tra / = 2 là một căn nguyên thủy modun ;. • Làm thế nào để tính log& (38679)? • Một phương pháp là tính 2( , 2' , 2& , 2+ , ⋯ mod 56509 cho đến khi được lũy thừa bằng 38679. • Bạn có thể kiểm tra rằng 2''&+, ≡ 38679 mod 56509.
Nội dung • Bài toán Logarit rời rạc • Bài toán Diffie-Hellman
Bài tập ∗ Hãy tính hai giá trị sau trong ℤ'+ . • DH* (10,5) • DH& (12,9) biết rằng ⟨2⟩ = {1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7} ⟨7⟩ = {1, 7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2} DHg(ga, gb) = gab (mod p)
Nhắc lại: Giao thức Diffie-Hellman (1977) Xét nhóm vòng G (e.g G = (Zp)* ) với cấp n Lấy một phần tử sinh g thuộc G (i.e. G = {1, g, g2, g3, … , gn-1 } ) Alice Bob Chọn ngẫu nhiên a in {1,…,n} Chọn ngẫu nhiên b trong {1,…,n} A = ga B = gb Ba (g b)a ab (g a)b = Ab = = kAB =g =
Bài tập • Alice và Bob dùng số nguyên tố ; = 1373 và cơ sở / = 2 để trao đổi khóa. • Alice gửi Bob giá trị F = 974. • Bob chọn số bí mật G = 871. • Bob nên gửi cho Alice giá trị gì, và khóa bí mật họ chia sẻ là gì? • Bạn có thể đoán được số bí mật " của Alice không?
Một câu hỏi mở • Nếu ta có thể giải bài toán Logarit rời rạc, vậy ta có thể giải bài toán Diffie-Hellman. Tại sao? • Nhưng nếu ta có thể giải được bài toán Diffie-Hellman, vậy liệu ta có thể giải được bài toán logarit rời rạc không?
Một số nhóm hay được dùng • Nhóm ℤ∗ = {1, … , 1 − 1} với 1 nguyên tố ! • Nhóm thặng dư bình phương ℚ! = {%# ∣ % ∈ ℤ∗ } ! • Nhóm ℤ∗ = {% ∈ {1, … , 6 − 1} ∣ gcd(%, 6) = 1}. $ Hệ RSA sử dụng ℤ!% với 1, 7 là các số nguyên tố ngẫu nhiên lớn. • Nhóm ℚ$ = {%# ∣ % ∈ ℤ∗ } $ • Nhóm điểm trên đường cong Elliptic
Mật mã ứng dụng Hệ mật mã dựa trên đường cong Elliptic
Nội dung 1. Đường cong Elliptic (Elliptic Curve, EC) 2. Bài toán Logarit rời rạc trên EC 3. Giao thức trao đổi khoá Diffie-Hellman trên EC
gniﬁcantly smaller, yet still twice as long as symmetric ciphers with the sam ryptographic strength. Vấn đề: Tìm hệ mật với tham số ngắn hơn able 6.1 Bit lengths of public-key algorithms for different security levels Algorithm Family Cryptosystems Security Level (bit) 80 128 192 256 Integer factorization RSA 1024 bit 3072 bit 7680 bit 15360 bit Discrete logarithm DH, DSA, Elgamal 1024 bit 3072 bit 7680 bit 15360 bit Elliptic curves ECDH, ECDSA 160 bit 256 bit 384 bit 512 bit Symmetric-key AES, 3DES 80 bit 128 bit 192 bit 256 bit Kích thước theo bit của các hệ mật mã khoá công khai ở mức an toàn khác nhau You may want to compare this table with the one given in Sect. 1.3.2, whi rovides information about the security estimations of symmetric-key algorithms.
elliptic curve equation and plotting it over the set of real numb Example 9.3. In Figure 9.3 the elliptic curve y2 = x3 − 3x + 3 Đường cong Elliptic numbers. y Đường cong Elliptic trên K là tập mọi cặp (x,y) ∈ K thoả mãn phương trình y2 = x3 + a·x + b cùng với một điểm vô cực O, x trong đó a, b ∈ K và thoả mãn 4·a3 +27·b2 ≠ 0. Fig. 9.3 y2 = x3 − 3x + 3 over R y2 = x3 −3x+3 trên R Đường cong không điểm kỳ dị