Nếu kỷ nguyên điện toán lượng tử đến, liệu Bitcoin của chúng ta có an toàn không?

Đọc bài viết này mất 25 phút

Tác động của điện toán lượng tử đối với hoạt động khai thác là vấn đề kinh tế của việc nâng cấp chip hơn là vấn đề bảo mật.

Tiêu đề gốc: "Nếu kỷ nguyên điện toán lượng tử đến, liệu Bitcoin của chúng ta có an toàn không?" 》

Tác giả gốc: Li Hua, Guo Yu

Nguồn gốc: ChainNews

Điện toán lượng tử Tác động về khai thác thiên về tính kinh tế của việc nâng cấp chip hơn là vấn đề bảo mật.

Mỗi khi có tin tức về điện toán lượng tử, mọi người lại lo lắng về Bitcoin. Lý do rất đơn giản, Bitcoin dựa trên mật mã và lý do tại sao mật mã có thể được thiết lập là dựa trên khả năng tính toán nhất định. Nếu điện toán lượng tử làm cho các phép tính mà ban đầu không thể hoặc khó thực hiện được có thể tính toán được thì phương pháp mã hóa này sẽ thất bại.

Nhưng sự lo lắng này là không cần thiết. Lý do cũng đơn giản không kém: chừng nào chúng ta còn có những phép tính không thể hoàn thành ngay cả với điện toán lượng tử thì chưa đủ sao? Phương pháp mã hóa (mật mã bảo mật lượng tử) dựa trên tính toán này không thể bị bẻ khóa bằng điện toán lượng tử và khi đó Bitcoin có thể được nâng cấp lên phương pháp mã hóa này.

"Bài toán độ khó mạng" là một đại diện điển hình. Ngay cả đối với điện toán lượng tử, nó vẫn không thể tính toán được. Dựa trên sự “vô minh” của con người, chúng ta luôn có thể tìm cách sống dưới sự bảo vệ của mật mã ở mức độ lớn.

Các thuật toán mã hóa trong Bitcoin

Chúng tôi biết rằng địa chỉ ví Bitcoin tương ứng với khóa chung và khóa riêng. Chỉ với khóa riêng thì Bitcoin trong ví mới có thể được sử dụng, nhưng khóa riêng thì an toàn và không thể truy cập được qua ví địa chỉ hoặc khóa công khai. Khóa được tính toán.

Làm thế nào để đạt được điều này? Hãy bắt đầu với phòng bi-a.

Bạn vào phòng bida chơi bida, đặt bi vào một vị trí phía dưới bàn bida, gọi là điểm A, Sau đó bạn đánh bóng, giả sử bạn đánh bóng rất mạnh thì quả bóng bắt đầu từ điểm A sẽ luôn chạm vào một điểm ở một bên của bàn bi-a, rồi nảy từ điểm đó sang một bên khác của bàn bi-a. điểm ở bên cạnh... Nó có thể đã nảy lên như thế này B lần (ví dụ mười nghìn lần), và cuối cùng dừng lại ở một điểm ở một phía nào đó của bàn bida, gọi là điểm C.

Bạn của bạn đến vào lúc này. Anh ta có thể nhìn thấy vị trí của quả bóng bi-a tại điểm C. Bạn cho anh ta biết vị trí ban đầu của quả bóng A. Chỉ và góc của quả bóng, hỏi anh ta quả bóng nảy lên bao nhiêu lần, tức là B là bao nhiêu? Bạn của bạn có thể sẽ không thể trả lời trong một thời gian.

Đây là một thuật toán tạo khóa công khai và riêng tư đơn giản. C (vị trí) là khóa chung và B (số lần) là khóa riêng. . Nếu biết điểm A và số lần nảy B thì có thể tính được điểm C; nhưng nếu chỉ biết điểm A và điểm C thì khó tính được số lần nảy B.

Trong mật mã thực, các cạnh của bàn bi-a được thay thế bằng các đường cong elip và A là một đường cong elip (thực ra là một nhóm elip ) trên một điểm cố định, nó tự chạm vào (quả bóng được đánh từ vị trí tiếp tuyến của điểm), quả bóng va chạm xung quanh trong nhóm hình elip B nhiều lần, và cuối cùng rơi xuống một điểm trong nhóm hình elip, Điểm này cần được ánh xạ lại và có một điểm C trên nhóm hình elip. C là khóa chung và B là khóa riêng.

Đây là thuật toán đường cong elip nổi tiếng, được sử dụng để tạo khóa chung và khóa riêng. Đây là thuật toán đầu tiên trong hệ thống Bitcoin các phương pháp mật mã.

Thuật toán đường cong elip khó bẻ khóa (dựa trên "bài toán độ khó logarit rời rạc"), nhưng không phải là không thể bẻ khóa Một lượng tử đủ mạnh Thuật toán đa thức có thể được tìm thấy thông qua phép tính và B có thể được tính thông qua A và C, tức là khóa riêng có thể được tính thông qua khóa chung. Vì vậy, nếu chúng ta thực sự bước vào kỷ nguyên điện toán lượng tử, thuật toán đường cong elip cần được thay thế bằng thuật toán mới có khả năng chống lại tính toán lượng tử.

Thuật toán đường cong Elliptic và tính toán lượng tử

Độ bảo mật của thuật toán chữ ký số đường cong elip được Bitcoin sử dụng là 2^128 (secp256-k1. Thứ tự của nhóm đường cong gần bằng 2^256 và độ phức tạp của cuộc tấn công đường cong elip thuật toán xấp xỉ O(sqrt(N)), lấy căn bậc hai của 2^256 và nhận 2^128). Đây là một con số thiên văn.

Trong trường hợp điện toán lượng tử, sử dụng thuật toán Shor do Peter Shor đề xuất, độ phức tạp của việc tấn công các đường cong elip là khoảng O(log (N)^3), đối với Bitcoin, cường độ tính toán theo lý thuyết là 128^3 lần.

Nghiên cứu trên giấy có liên quan cho thấy việc xây dựng một máy tính lượng tử tấn công đường cong secp256-k1, giả sử rằng máy tính có thể giảm tỷ lệ lỗi bit đến 10 ^-4 thì hy vọng rằng việc tính toán có thể hoàn thành trong vòng 7 ngày bằng cách sử dụng 1,7 triệu qubit.

Trong hệ thống Bitcoin, có một phương thức mã hóa khác là hàm băm SHA-256, được sử dụng để tạo địa chỉ ví tương ứng đến khóa công khai. Thuật toán này rất dễ hiểu, nó chuyển đổi đầu vào thành đầu ra theo cách không thể đảo ngược, có tính chất một chiều rất mạnh, không thể tính toán đầu vào thông qua đầu ra.

Do đó, hàm băm chỉ có thể bị bẻ khóa thông qua vũ lực, nghĩa là thay đổi giá trị đầu vào và thử đi thử lại cho đến khi có thể sử dụng giá trị nhất định. Tính giá trị đầu ra mục tiêu từ các giá trị đầu vào.

So với máy tính cổ điển, máy tính lượng tử có lợi thế đáng kể trong tìm kiếm vũ phu, nhưng nó vẫn là tối ưu hóa hiệu suất ở cấp độ đa thức, chúng tôi có thể duy trì bảo mật bằng cách nhân đôi số bit bảo mật, chẳng hạn như sử dụng SHA-512.

Địa chỉ ví Bitcoin có được bằng cách băm khóa chung hai lần, một lần với SHA-256 và một lần với RIPEMD-160 (một hàm băm khác function), điện toán lượng tử khó có thể vượt qua được hai cổng băm và “đập” khóa công khai qua địa chỉ ví.

Điện toán lượng tử và SHA-256

Thuật toán lượng tử hiện tại có thể tăng tốc tính toán SHA-256 là thuật toán Grover do Lov Grover đề xuất vào năm 1996, có thể tăng hiệu suất tìm kiếm vũ phu theo hệ số bình phương. Giả sử chúng ta muốn tìm một cái kim trong một hình vuông khổng lồ N × N. Một máy tính cổ điển cần tìm kiếm từng ô một, và trong trường hợp xấu nhất, nó cần tìm kiếm N. Nó chỉ cần tìm kiếm N lần.

Tóm lại: có hai thuật toán mã hóa cơ bản trong Bitcoin, một là thuật toán đường cong elip và hai là hàm băm SHA -256 . Hiện tại, có thể tìm ra một phương pháp tính toán lượng tử hiệu quả cho cái trước và đạt được sự bẻ khóa; nhưng không có phương pháp tính toán lượng tử hiệu quả cho cái sau. Tất nhiên, điều kiện tiên quyết để bẻ khóa là điện toán lượng tử thực sự đủ mạnh, bạn biết đấy, chip lượng tử mới nhất của Google chỉ có 54 qubit.

Bitcoin của chúng tôi có an toàn không?

Nếu bước vào kỷ nguyên điện toán lượng tử, chúng ta chỉ cần sử dụng thuật toán mã hóa kháng điện toán lượng tử để tạo khóa chung, khóa riêng và địa chỉ ví. Vậy là xong. Nhưng nếu người dùng không nâng cấp khóa chung và khóa riêng, liệu bitcoin trong ví của họ có bị đánh cắp không? câu trả lời là phủ định.

Có những trường hợp đại khái sau:

1. Nếu Bitcoin trong địa chỉ ví chưa bao giờ được sử dụng thì khóa công khai của địa chỉ đó sẽ không được biết và những người khác chỉ biết địa chỉ ví (chỉ khi chúng tôi tiêu Bitcoin vào một địa chỉ nhất định. Khóa công khai chỉ cần đưa ra, nhưng ngay cả khi chỉ sử dụng một lần, khóa chung sẽ được phát trên toàn mạng).

Như đã đề cập trước đó, SHA-256 rất khó bị bẻ khóa bằng điện toán lượng tử, điều đó có nghĩa là người khác không thể tính toán được thông qua địa chỉ ví Khóa công khai. Do đó, ngay cả khi khóa riêng có thể được tính từ khóa chung, những địa chỉ ví chưa lộ khóa chung vẫn được an toàn.

2. Nếu bạn có thói quen sử dụng Bitcoin tốt và chỉ sử dụng địa chỉ ví một lần, thì cũng theo cách tương tự, khóa chung của địa chỉ mới Cũng không xác định, số Bitcoin trong địa chỉ mới vẫn an toàn.

3. Nếu người dùng sử dụng lại địa chỉ ví, khóa công khai tương ứng với địa chỉ đó sẽ bị lộ; nếu điện toán lượng tử bị bẻ khóa Elliptic Thuật toán đường cong thì Bitcoin ở địa chỉ này có nguy cơ bị đánh cắp.

Theo thống kê, gần 5 triệu Bitcoin được lưu trữ trong các địa chỉ có khóa công khai bị lộ. Ngoài ra, có gần 1,77 triệu Bitcoin được sử dụng Địa chỉ P2PK, là định dạng tài khoản Bitcoin sớm nhất và khóa công khai là công khai, bao gồm cả các tài khoản được cho là Satoshi Nakamoto. Nếu những Bitcoin này không thay đổi địa chỉ, chúng sẽ nằm trong phạm vi của một cuộc tấn công điện toán lượng tử. (Nguồn dữ liệu: Ambi Labs)

Ngoài địa chỉ ví, còn có một vị trí quan trọng khác trong hệ thống Bitcoin nơi SHA được sử dụng - 256, đó là khai thác mỏ. Khai thác là quá trình bẻ khóa mạnh mẽ của hàm băm, bằng cách điều chỉnh giá trị đầu vào để "đạt" giá trị đầu ra nằm trong phạm vi mục tiêu.

Như đã đề cập ở trên, về mặt lý thuyết, chip máy tính lượng tử có thể "nghiền nát" chip máy tính cổ điển trong quá trình tìm kiếm vũ phu, nhưng chúng ta cũng cần phải tính đến trình độ phát triển công nghệ và quy trình sản xuất chip. Ngoài ra, chip liên tục được nâng cấp cùng với sự phát triển của công nghệ, tác động của điện toán lượng tử đến việc khai thác là vấn đề kinh tế của việc nâng cấp chip hơn là vấn đề bảo mật.

Bảo mật trong điện toán lượng tử: mật khẩu mạng

Trong khi điện toán lượng tử đang phát triển thì mật mã bảo mật lượng tử cũng đang phát triển nhanh chóng. Tiêu biểu nhất là "mật mã dựa trên mạng", tức là hệ thống mật mã dựa trên mạng tinh thể).

"Grid" là một không gian vectơ có các hệ số nguyên. Nó có thể được hiểu là một không gian nhiều chiều. Nó có hai cơ bản: "Bài toán độ khó mạng" là bài toán vectơ ngắn nhất và là bài toán vectơ gần nhất. Việc giải loại bài toán này đòi hỏi độ phức tạp về thời gian theo cấp số nhân. Khi đó, nếu các thừa số là đa thức thì không có thuật toán thời gian đa thức cho loại bài toán này. Điều này cũng đúng với tính toán lượng tử.Một khả năng tính toán không thể thực hiện được.

Nghe có vẻ hơi trừu tượng, có lẽ có thể hiểu như thế này: dùng bút vẽ nhiều chấm đen lên một tờ giấy A4 giấy, Sau đó đổi bút và vẽ một điểm đỏ lên giấy. Việc chúng ta cần làm là tìm điểm đen gần điểm đỏ nhất. Việc này thật dễ dàng, bây giờ từ không gian hai chiều của tờ giấy A4 sang không gian ba chiều không gian chiều, hãy tưởng tượng trôi nổi trong không gian. Có nhiều chấm đen. Bây giờ đặt một chấm đỏ vào, và điều tương tự là tìm chấm đen gần chấm đỏ nhất. Điều này không khó, nhưng so với không gian hai chiều không gian, độ khó không còn ở mức như cũ.

Bây giờ, chúng ta biến không gian ba chiều thành không gian ba chiều. Cho một điểm màu đỏ, hãy tìm điểm đen gần nhất với Nó Chấm, điểm đen này nhất định phải tồn tại, nhưng nghĩ mà xem, chẳng phải gần như không thể tìm thấy nó sao? Đây là vấn đề khó khăn về mạng.

Không gian mạng tương tự như đường cong elip. Trên đường cong elliptic có thể có các công thức toán học (thuật toán đường cong elip) đặt khóa chung và khóa riêng ở hai đầu của phương trình, trong không gian lưới cũng có các công thức toán học (như thuật toán LLL) có thể đặt các chấm đen và chấm đỏ. Đặt mọi thứ vào cả hai vế của phương trình, sau đó chúng ta có thể sử dụng loại công thức này để tạo khóa chung và khóa riêng.

Trong thuật toán đường cong elip, do "bài toán độ khó logarit rời rạc" nên máy tính truyền thống không thể tính toán khóa riêng thông qua khóa chung ; trong thuật toán mã hóa mạng, do "vấn đề về độ khó mạng", máy tính lượng tử không thể tính toán khóa riêng từ khóa chung.

Mật mã mạng đang phát triển nhanh chóng. Dựa trên mạng, chúng ta không chỉ có các khóa công khai và khóa riêng có khả năng chống lại điện toán lượng tử mà còn Một loạt các thuật toán hoặc giao thức mã hóa tương ứng với các khái niệm mã hóa cổ điển, có thể được sử dụng trong chữ ký số, trao đổi khóa, bằng chứng không có kiến thức và các lĩnh vực ứng dụng khác.

"Vũ trụ tin vào mã hóa. Mã hóa thì dễ, giải mã thì khó." Điều này sẽ vẫn như vậy trong tương lai gần. Vì vậy, đừng lo lắng, điều này đúng với Bitcoin và đúng với blockchain.

Tài liệu tham khảo

[1] Arute, Frank, Kunal Arya, Ryan Babbush,Dave Bacon, Joseph C. Bardin , Rami Barends, Rupak Biswas và cộng sự. "Ưu thế lượng tử sử dụng bộ xử lý siêu dẫn có thể lập trình." Nature 574, số 7779 (2019): 505-510.
[2] Andreas M. Antonopoulos trả lời các câu hỏi về điện toán lượng tử:
www.youtube.com/watch?v=eo7mwcsUbdo；www.youtube.com/watch?v=wlzJyp3Qm7s
[3] Gentry, Craig. "Mã hóa đồng cấu hoàn toàn bằng cách sử dụng mạng lý tưởng." Trong Stoc, tập 9, không . 2009, trang 169-178. 2009.
[4] Aggarwal, Divesh, Gavin K. Brennen, Troy Lee, Miklos Santha và Marco Tomamichel. "Các cuộc tấn công lượng tử vào Bitcoin và cách bảo vệ chống lại chúng." arXivpreprint arXiv:1710.10377 (2017).
[5]Stewart, I., D. Ilie, Alexei Zamyatin, Sam Werner, M. F. Torshizi và WilliamJ. Knottenbelt. "Cam kết kháng cự lượng tử: một biện pháp bảo vệ chậm rãi cho Bitcoin chống lại sự nhanh chóng tấn công điện toán lượng tử." Royal Society openscience 5, số 6 (2018): 180410.
[6] Regev,Oded. "Mật mã dựa trên mạng." Trong Hội nghị mật mã quốc tế thường niên, trang 131-141. Springer, Berlin , Heidelberg, 2006.