1. Mối đe dọa của Máy tính Lượng tử đối với Mã hóa Hiện tại [0]

thumbnail
  1. Hành vi thu thập dữ liệu: Một số cá nhân và quốc gia đang lưu trữ dữ liệu được mã hóa.
    1. Dữ liệu này bao gồm mật khẩu, thông tin ngân hàng và số an sinh xã hội [0].
    2. Họ không thể mở các tập tin này ngay bây giờ [0].
  2. Kỳ vọng về Máy tính Lượng tử: Họ tin rằng trong 10 đến 20 năm tới, máy tính lượng tử sẽ phá vỡ mọi mã hóa [1].
  3. Quy trình "Lưu trữ trước, Giải mã sau": Dữ liệu được lưu trữ để giải mã trong tương lai [1].
    1. Thông tin như nghiên cứu công nghiệp và tình báo chính phủ vẫn có giá trị lâu dài [2].
  4. Đánh giá của NSA: Cơ quan An ninh Quốc gia Mỹ dự đoán khả năng phá vỡ mã hóa khóa công khai trong 5 đến 10 năm [4].
  5. Mối đe dọa hiện tại: Máy tính lượng tử mạnh vẫn còn nhiều năm, nhưng mối đe dọa đã tồn tại do quy trình lưu trữ trước [6].
  6. Hành động lập pháp: Quốc hội Hoa Kỳ đã thông qua luật yêu cầu chuyển đổi sang mã hóa mới chống lại máy tính lượng tử [7].

2. Cơ chế Mã hóa Khóa Đối xứng và RSA [8]

thumbnail

2.1. Mã hóa Khóa Đối xứng Truyền thống [8]

  1. Mã hóa thành công: Các thuật toán mã hóa hiện tại đã hoạt động hiệu quả hơn 40 năm [8].
  2. Chia sẻ khóa bí mật: Trao đổi thông tin cá nhân yêu cầu gặp mặt trực tiếp để chia sẻ khóa bí mật [9].
  3. Khóa đối xứng trên Internet: Khóa tương tự được dùng để mã hóa/giải mã tin nhắn trên Internet [10].
  4. Bảo mật: Tin nhắn an toàn miễn là khóa không bị lộ [11].

2.2. Sự ra đời của Mã hóa Khóa Bất đối xứng (RSA) [12]

  1. Vấn đề chia sẻ khóa: Chia sẻ khóa qua kênh không bảo mật (điện thoại, thư) là không thể [12].
  2. Đột phá năm 1977: Rivest, Shamir và Adleman đã tạo ra bước đột phá về mã hóa [14].
  3. Thuật toán RSA: Mỗi người có hai số nguyên tố lớn bí mật [15].
    1. Nhân hai số này để tạo ra một số công khai (người khác thấy được) [15].
  4. Mã hóa tin nhắn: Người gửi dùng số công khai của người nhận để cắt xén tin nhắn [16].
  5. Giải mã: Người nhận dùng khóa bí mật để giải mã dễ dàng [18].
    1. Người khác không thể giải mã trừ khi tìm được hai thừa số nguyên tố bí mật [18].

3. Phân tích Thừa số Nguyên tố trên Máy tính Cổ điển và Lượng tử [19]

thumbnail
  1. Thử phân tích cổ điển: Siêu máy tính dùng thuật toán general number field sieve [19].
  2. Độ khó: Mật mã hiện đại dùng số nguyên tố dài khoảng chữ số [19].
  3. Thời gian cổ điển: Việc phân tích tích hai số nguyên tố lớn này mất khoảng 16 triệu năm [20].
  4. Sự khác biệt: Máy tính lượng tử có thể làm điều này nhanh hơn nhiều [20].

4. Nguyên lý Hoạt động của Máy tính Lượng tử (Qubit và Chồng chất) [21]

thumbnail

4.1. So sánh Bit Cổ điển và Qubit [21]

  1. Bit cổ điển: Tại một thời điểm, bit chỉ có một trạng thái (0 hoặc 1) [21].
  2. Hai bit: Có thể ở một trong bốn trạng thái (00, 01, 10, 11) [22].
  3. Phép tính cổ điển: Phép tính chỉ thực hiện trên một trạng thái tại một thời điểm (ví dụ: ) [23].

4.2. Sức mạnh của Qubit và Chồng chất [25]

  1. Qubit: Cũng có trạng thái 0 hoặc 1, nhưng không bị giới hạn ở một trạng thái [25].
  2. Chồng chất: Qubit có thể là sự kết hợp tùy ý của 0 và 1 [26].
  3. Hai qubit: Có thể tồn tại đồng thời ở trạng thái chồng chất của 0, 1, 2, và 3 [27].
  4. Phép tính song song: Máy tính lượng tử thực hiện phép tính cho tất cả các số cùng lúc [28].
    1. Kết quả là sự chồng chất của các câu trả lời khác nhau (1, 7, 49, 343) [28].
  5. Mở rộng: Thêm một qubit nhân đôi số trạng thái có thể có [29].
    1. Ba qubit biểu diễn tám trạng thái, thực hiện tám phép tính đồng thời [30].
    2. 20 qubit có thể biểu diễn hơn 1 triệu trạng thái đồng thời [31].
    3. 300 qubit biểu diễn nhiều trạng thái hơn số hạt trong vũ trụ quan sát được [32].

4.3. Thách thức của Đo lường và Giải pháp Lượng tử [33]

  1. Nhược điểm lớn: Tất cả câu trả lời được nhúng trong sự chồng chất của các trạng thái [33].
  2. Đo lường: Khi đo, chỉ nhận được một giá trị ngẫu nhiên và thông tin khác bị mất [34].
  3. Nhiệm vụ khó khăn: Cần cách thông minh để chuyển đổi chồng chất thành trạng thái chỉ chứa thông tin mong muốn [35].
  4. Ứng dụng: Máy tính lượng tử vô dụng cho hầu hết ứng dụng hiện tại [36].
  5. May mắn: Các vấn đề có thể giải quyết được lại chính là nền tảng của hầu hết mật mã khóa công khai [37].

5. Thuật toán Shor và Phép biến đổi Fourier Lượng tử [39]

thumbnail
  1. Phép biến đổi Fourier Lượng tử (QFT): Được Shaw và Coppersmith tìm ra năm 1994 [39].
  2. Chức năng QFT: Giống QFT thông thường, nó áp dụng cho tín hiệu tuần hoàn và trả về các tần số [39].
  3. Ứng dụng vào Lượng tử: Nếu sự chồng chất có các kỳ hạn phân tách đều đặn (tuần hoàn), QFT trích xuất được tần số [40].
  4. Mục tiêu: QFT cho phép trích xuất thông tin tần số từ sự chồng chất tuần hoàn [41].
  5. Giải thích: Giải thích cách máy tính lượng tử tìm thừa số nhanh hơn bằng cách so sánh ví dụ đơn giản và áp dụng lượng tử [42].

6. Ví dụ Phân tích Thừa số Cổ điển (n=77) [43]

thumbnail

6.1. Tìm Chu kỳ (Số mũ ) [43]

  1. Thiết lập ví dụ: Đặt (tích của hai số nguyên tố và ) [43].
  2. Chọn cơ số $g$: Chọn số không có thừa số chung với (ví dụ: ) [46].
  3. Tính chất: Nhân với chính nó nhiều lần sẽ luôn đạt bội số của [47].
    1. Tồn tại số mũ sao cho là bội số của [48].
  4. Tính toán số dư: Lặp lại phép tính và quan tâm đến số dư [53].
  5. Tìm thấy chu kỳ: Với và , ta tìm thấy là bội số của (tức là 78) [57].

6.2. Sử dụng Số mũ để Tìm Thừa số [58]

  1. Sắp xếp lại phương trình: [58].
  2. Phân tích: là bội số của (nếu chẵn) [59].
  3. Liên hệ với thừa số: và phải nằm ở vế trái của phương trình [61].
  4. Tính toán: Với , hai số hạng là và [62].
  5. Kết quả: Hai số này có thể có chung thừa số với [64].

6.3. Thuật toán Euclid để Tìm Ước chung Lớn nhất (GCD) [65]

  1. Bước cuối: Sử dụng thuật toán Euclid để tìm ước chung lớn nhất (GCD) [65].
  2. Quy trình Euclid: Chia số lớn hơn cho số nhỏ hơn, lấy số dư, rồi lặp lại [66].
    1. Ví dụ: GCD(32769, 77) dư 44 [67].
    2. Tiếp theo: GCD(77, 44) dư 33 [69].
    3. Tiếp theo: GCD(44, 33) dư 11 [70].
    4. Khi phần dư bằng 0, số chia trước đó là GCD [70].
  3. Kết quả: GCD là 11, là một thừa số của 77 [71].
  4. Thừa số còn lại: Chia được 7 [73].
  5. Tóm tắt các bước: Đoán , tìm số mũ , tính hai số mới, dùng Euclid tìm và [74].

7. Tăng tốc bằng Máy tính Lượng tử (Bước 2) [75]

thumbnail
  1. Bước tăng tốc: Máy tính lượng tử tăng tốc ở bước hai: tìm số mũ [76].
  2. Quan sát chu kỳ số dư: Tiếp tục tính cho thấy số dư lặp lại theo chu kỳ 10 [78].
    1. Số mũ có phần dư 1 là 10, số mũ tiếp theo là 20, 30, 40... [80].
    2. Khoảng cách giữa các lần xuất hiện số dư giống nhau là bội số của chu kỳ (10) [81].
  3. Nguyên tắc: Tìm số mũ bằng cách quan sát khoảng cách của bất kỳ số dư nào [83].
  4. Áp dụng Lượng tử: Máy tính lượng tử sử dụng sự chồng chất để tìm chu kỳ [88].
    1. Bộ cubit 1: Chuẩn bị chồng chất của các số mũ lên đến (cần ~4100 cubit hoàn hảo) [90].
    2. Bộ cubit 2: Khởi tạo ở trạng thái không (~250 cubit) [92].
  5. Tính toán vướng víu: Nâng lên lũy thừa của bộ cubit 1, chia cho , lưu số dư vào bộ cubit 2 [93].
  6. Đo lường thông minh: Đo phần số dư, không phải toàn bộ chồng chất [95].
    1. Nếu đo được số dư , ta còn lại chồng chất của các số mũ có cùng số dư [97].
    2. Các số mũ này cách nhau một lượng (chính là chu kỳ cần tìm) [98].
  7. Trích xuất $R$: Áp dụng Phép biến đổi Fourier Lượng tử lên sự chồng chất tuần hoàn này [100].
    1. Kết quả còn lại là các trạng thái chứa [100].
    2. Đo lường để tìm [100].
  8. Hoàn tất giải mã: Với (số mũ ), ta có thể dùng thuật toán Euclid để tìm và [101].

8. Số lượng Qubit Cần thiết và Sự phát triển [102]

thumbnail
  1. Cubit không hoàn hảo: Cubit thực tế không hoàn hảo, cần thêm cubit làm thông tin dư thừa [102].
  2. Ước tính số lượng cubit vật lý:
    1. 2012: Ước tính cần 1 tỷ cubit để phá mã RSA [103].
    2. 5 năm sau: Con số giảm xuống còn 230 triệu cubit [103].
    3. 2019: Ước tính giảm mạnh xuống chỉ còn 20 triệu cubit vật lý [103].
  3. Tình hình hiện tại: IBM chưa đạt được số lượng cubit ước tính này [104].
  4. Tiến độ: Sự tiến bộ dường như đang diễn ra theo cấp số nhân [104].
  5. Kết luận: Vấn đề hiện tại là khi nào đường cong này sẽ va chạm trước khi mã hóa bị phá vỡ [105].

9. Chuyển đổi sang Mật mã Hậu Lượng tử (PQC) [107]

thumbnail

9.1. Cuộc thi PQC của NIST [107]

  1. Nhu cầu: Các nhà khoa học tìm kiếm mã hóa mới chống lại cả máy tính cổ điển và lượng tử [107].
  2. Khởi động cuộc thi: Năm 2016, NIST phát động cuộc thi tìm thuật toán mã hóa mới [108].
  3. Kết quả: 82 đề xuất đã được kiểm tra nghiêm ngặt [109].
  4. Lựa chọn: Ngày 5 tháng 7 năm 2022, NIST chọn bốn thuật toán làm tiêu chuẩn PQC [109].
    1. Ba trong số các thuật toán này dựa trên toán học lattice [110].

9.2. Cơ sở Toán học Lattice (Ví dụ 2D) [111]

  1. Khái niệm Lattice: Tạo ra các điểm bằng cách cộng các tổ hợp số nguyên của hai vectơ cơ sở () [111].
  2. Bài toán: Tìm tổ hợp nào của đưa đến điểm lattice gần điểm mục tiêu nhất [112].
  3. Độ khó tăng lên: Nếu thay đổi vectơ cơ sở thành , bài toán trở nên khó hơn nhiều [113].
    1. Với vectơ , mỗi bước đi theo một hướng có thể làm lệch hướng khác [116].
  4. Ví dụ 2D: Cần kết hợp và để tìm điểm gần nhất [117].

9.3. Mở rộng Chiều và Độ khó [118]

  1. Không gian 3D trở lên: Bài toán trở nên khó hơn nhiều trong không gian 3D [118].
  2. Thách thức bổ sung: Bạn chỉ được cung cấp các vectơ tạo nên lattice, không phải tất cả các điểm [119].
  3. Tăng số chiều: Số lượng điểm lưới bên trong hình cầu tăng theo lũy thừa của số chiều [121].
    1. Không gian 3D hoặc 100 chiều vẫn quản lý được [124].
    2. Các sơ đồ PQC đề xuất sử dụng khoảng 1000 chiều [125].
  4. Khó khăn ở chiều cao: Ở nhiều chiều, việc tìm điểm gần nhất cực kỳ khó [126].
    1. Một bước đi đúng hướng có thể bị sai lầm ở 999 chiều còn lại [126].

9.4. Mã hóa bằng Lattice [130]

  1. Mã hóa: Mỗi người giữ bí mật bộ vectơ cơ sở tốt (tạo lattice) [130].
  2. Chia sẻ công khai: Họ chỉ chia sẻ lattice bằng một tập hợp vector khó đoán [130].
  3. Gửi tin nhắn: Người gửi chọn một điểm trên lattice của người nhận (ví dụ: số 3) [131].
    1. Thêm nhiễu ngẫu nhiên để tin nhắn không chính xác tại điểm đó mà ở gần đó [132].
  4. Giải mã: Người nhận tìm điểm lattice gần nhất với tin nhắn trong không gian 1000 chiều [133].
    1. Điều này dễ dàng với người nhận vì họ có bộ vectơ đẹp [134].
    2. Điều này cực kỳ khó với người khác, kể cả máy tính lượng tử [136].

10. Kết luận và Tầm nhìn Tương lai [137]

thumbnail
  1. Vai trò của các nhà nghiên cứu: Các nhà toán học và mật mã đang đảm bảo dữ liệu bí mật được giữ kín [137].
  2. Mục tiêu: Giúp an toàn tiến về phía trước, bảo vệ cơ sở hạ tầng và cho phép cuộc sống bình thường [138].
  3. Xu hướng: Máy tính lượng tử và chatbot AI sẽ đóng vai trò lớn hơn trong tương lai [139].
  4. Lời khuyên: Điều quan trọng là phải tìm hiểu cách chúng hoạt động ngay bây giờ [140].