Sunday, June 8, 2014

Google End-To-End

Hôm kia nhóm của tôi phát hành mã nguồn của End-To-End, chương trình mã hóa email mà bọn tôi làm từ hơn một năm nay. Còn rất nhiều việc phải làm trước khi bọn tôi có một phiên bản chính thức, nhưng đi được bước đầu rồi cũng thấy nhẹ nhõm phần nào. Sáng nay đồng nghiệp báo là phần mềm của bọn tôi được nhắc đến trong một bài báo ở trang nhất của tờ New York Times. Trước đó Edward Snowden cũng có nhắc đến. Woohoo!

Đây là phần mềm lớn nhất mà tôi từng tham gia viết. Tôi chịu trách nhiệm thư viện các thuật toán mã hóa. Phần này nhỏ, nhưng mà để viết được tôi cũng phải đọc nhiều sách vở và các bài báo nghiên cứu. Tôi thích những dự án như thế này, vì làm xong thì mình "lời" được một mớ kiến thức mới.

Mặc dù tôi tự tin thư viện của mình sẽ "nâng giá gạo", nhưng mà tôi cũng thấy rất hồi hộp trước ngày phát hành, không chỉ cho phần của tôi mà còn toàn bộ chương trình. Trước giờ tôi toàn đi chọc ngoáy phần mềm của người khác, đây là lần đầu tôi đưa phần mềm của mình ra cho người khác coi. Cũng may là cho đến nay, cũng gần một tuần rồi, nhưng vẫn chưa có ai tìm được lỗ hổng nào cả.

Mới đầu tôi viết cái thư viện một mình, về sau thì tôi thuyết phục được một đồng nghiệp tham gia viết cùng tôi. Ở Google người ta đánh giá cao khả năng lãnh đạo và muốn chứng minh được khả năng này thì cách tốt nhất là thuyết phục được người khác tham gia dự án của mình. Nghĩa là nếu tự mình thiết kế rồi tự mình viết luôn thì không được đánh giá cao bằng mình thiết kế xong rồi để cho người khác làm.

Anh đồng nghiệp tốt nghiệp Stanford hồi tôi còn chưa được sinh ra. Hơn ba chục năm kinh nghiệm. Trên danh nghĩa thì tôi lãnh đạo phần này, nhưng mà tôi thấy mình học được nhiều điều từ anh ấy hơn là ngược lại. Rốt cuộc trong cái thư viện này chỗ nào tâm tối mịt mờ là do tôi viết, còn lại tất cả những ý tưởng hay ho là của ảnh. Tôi nghĩ nếu mà ảnh viết từ đầu chắc có khi còn hay hơn. Hỏi ra mới biết anh ấy là một thành viên trong nhóm cùng với James Gosling tạo ra Java.

Thư viện của bọn tôi triển khai các hệ mật mã dựa trên đường cong elliptic (elliptic curve crypto). Kiến thức toán của tôi ở đây cực kỳ hạn chế. Tôi chỉ biết rằng từ vài chục năm nay elliptic curve là một lĩnh vực nghiên cứu quan trọng bậc nhất của ngành lý thuyết số. Andrew Wiles chứng minh định lý cuối cùng của Fermat bằng cách chứng minh một định lý về các đường cong này. Trong thập niên 80 của thế kỷ trước người ta phát hiện ra hai ứng dụng khác của elliptic curve: phân tích nhân tử số lớn và xây dựng các hệ mã khóa công khai.

Các hệ mã khóa công khai xây dựng trên lý thuyết số đều dựa vào độ khó của hai bài toán: phân tích nhân tử số lớn và tính logarithm rời rạc trên nhóm Abel hữu hạn (discrete log problem). Hệ mã RSA lừng danh dựa trên bài toán thứ nhất, nhưng cho đến nay người ta đã tìm ra các thuật toán cận mũ (sub-exponential, không biết dịch vậy có đúng không?) để giải quyết bài toán này. Do đó nếu muốn an toàn khi sử dụng RSA thì bắt buộc phải sử dụng các bộ khóa có chiều dài cỡ 3000 bit. Vấn đề là muốn tạo ra các bộ khóa như thế thì phải tìm được các số nguyên tố có chiều dài cỡ 1500 bit, nghĩa là có khoảng 450 chữ số. Khi bọn tôi cài đặt thử một thuật toán dựa trên Miller-Rabin thì thấy muốn tìm được chúng phải mất vài chục giây. Bọn tôi không muốn người sử dụng phải chờ lâu như thế.

Cách đây tầm ba mươi năm hai nhà toán học là Miller và Koblitz cùng phát hiện ra rằng các điểm trên đường cong elliptic định nghĩa trên một trường hữu hạn tạo thành một nhóm Abel hữu hạn và do đó có thể dùng chúng để xây dựng các hệ mật mã khóa công khai. Điều lý thú là thuật toán tốt nhất để giải bài toán discrete log trên các nhóm này vẫn có thời gian chạy lũy thừa. Nói cách khác khi sử dụng elliptic curve crypto thì chiều dài khóa sẽ ngắn hơn. Ngoài ra việc tạo ra các bộ khóa trong các hệ mật mã này cũng rất đơn giản: khóa bí mật chỉ là một số ngẫu nhiên còn khóa công khai thì được tạo ra bằng một phép tính đơn giản.

Khi nào có hứng thú tôi sẽ viết chi tiết về các hệ mật mã này. Ai muốn tìm hiểu thì có thể xem qua các cuốn sách sau đây:

* Introduction Mathematical Cryptography Undergraduate Mathematics: cuốn này rất cơ bản, thích hợp cho người mới bắt đầu. Tôi rất thích cuốn này.

A Computational Introduction to Number Theory and Algebra: cuốn này dành cho những ai muốn tìm hiểu sâu hơn về số học và đại số. Tôi bắt đầu đọc cuốn này cách đây bốn năm, đến giờ vẫn chưa đọc hết. Nghĩ đến thấy buồn quá :-(.

Guide to Elliptic Curve Crypto: cuốn này dành cho những ai muốn viết một thư viện như của bọn tôi, cung cấp kiến thức cơ bản và rất nhiều thông tin về cách triển khai các thuật toán và các hệ mã.

Elliptic Curves: Number Theory and Cryptography: cuốn này đi sâu hơn nữa về elliptic curve, hứa hẹn là sẽ giải thích chứng minh của Andrew Wiles! Tôi đang "cày" cuốn này và chỉ mới đọc được đến chương hai vì không hiểu, phải quay lại cuốn NTB ở trên để đọc lại về nhóm, vành và trường.

Tóm lại cho cái bài hết sức lan man này: mọi con đường đều dẫn về toán. Một phần mềm tưởng chẳng có dây mơ rễ má gì nhưng nhìn kỹ mới thấy toàn toán là toán. Không hiểu toán là không làm được. Thế mà hồi đi học đại học tôi cứ thắc mắc tại sao phải học toán? Chắc là do không thấy được ứng dụng của chúng. Tôi nghĩ cách dạy toán tốt chắc hẳn phải là song song giữa lý thuyết và ứng dụng. Cuốn NTB làm rất tốt điều này. Một hai chương lý thuyết xen kẽ với một hai chương ứng dụng.

Tự học toán rất khó, nhưng mà không học toán thì làm gì cũng khó.

Cập nhật: bạn Tho Tung có còm rằng thật ra Miller và Koblitz không phải là người đầu tiên chỉ ra nhóm các điểm trên đường cong elliptic định nghĩa trên một trường hữu hạn tạo thành một nhóm Abel hữu hạn. Tôi đọc paper của Miller thì thấy đúng là như thế thật. Như vậy đóng góp của Miller và Koblitz là ở chỗ chỉ ra rằng bài toán logarithm rời rạc trên nhóm này là khó và do đó có thể sử dụng chúng để làm mật mã.

Cập nhật: anh Duong-Hieu Phan chỉ ra rằng ngoài còn có rất nhiều hệ mã dựa trên mã sửa sai và đặc biệt là Lattice-based Crypto với tấn công và tính an toàn sử dụng rất nhiều lý thuyết Geometry of Numbers từ Minkowski.

9 comments:

Root said...

Nhắc đến toán mới nhớ :D Không biết anh đã học hết bộ The Art of Computer Programming chưa nhỉ ? Và anh nghĩ thế nào về bộ sách này ?

Thai Duong said...

Root: tôi mua cuốn II, vì cần tham khảo một thuật toán trong đó cho End-To-End.

Tôi nghĩ thế nào về bộ sách đó chắc không quan trọng đâu :-).

teng teng said...

haiza.. sao ko dùng từ chúng tôi mà dùng từ bọn tôi thế nhở :D

Minh Hoàng said...
This comment has been removed by the author.
One_thought said...

Chào anh Thái.

Nhắc đến bảo mật, anh nghĩ thế nào về Unseen.is giúp bảo mật mail và chat nhóm hay hội thoại

Huan Truong said...

Chúc mừng anh Thái và bộ end-to-end. Đây là một bước tiến mới cho việc bảo mật ở đầu cuối, và hy vọng chúng ta sẽ có email mã hóa đầu cuối trong một ngày không xa.

Xin được phỏng vấn anh Thái một câu, nếu như email được mã hóa đầu cuối thì Google/các anh có nghĩ đến việc tìm kiếm email, vốn là một chức năng vô cùng tiện lợi của Gmail, sẽ được giải quyết như thế nào không?

- Bi.

Tho Tung said...

Em biết blog của anh qua blog của GS Châu. Đây là lần đầu tiên em comment ở đây.

Em nghĩ người ta đã biết các điểm trên đường cong Elliptic định nghĩa trên trường hữu hạn lập thành một nhóm Abel từ khá lâu rồi. Có lẽ Koblitz và Miller áp dụng điều này để xây dựng các hệ mật mã chứ họ không phải là những người đầu tiên phát hiện ra điều trên :).

GS Benedict Gross ở Harvard có loạt bài giảng về Đại số đại cương (Abstract Algebra) ở trang
http://www.extension.harvard.edu/open-learning-initiative/abstract-algebra

Em thấy đây là loạt bài giảng rất hay và dễ hiểu. Em xin giới thiệu cùng mọi người luôn.

Thai Duong said...

Huan Truong: tìm kiếm trên dữ liệu được mã hóa là một vấn đề có thể giải quyết được.

Tho Tung: oh cảm ơn bạn. Tôi không biết cái này. Tôi đã cập nhật lại bài viết.

Tuấn Anh said...

Chào anh Thái, hồi học đại học em cũng gặp vấn đề như anh đề cập "không biết tại sao phải học toán vì không thấy ứng dụng của nó". Bây giờ nhiều khi gặp 1 vấn đề khó, có tài liệu mà kiến thức toán không đủ để đọc. Em đang chuẩn bị học cao học ngành an toàn thông tin, anh Thái có thể chỉ em nên đọc sách nào và học toán ra sao không. Cảm ơn anh nhiều (blog của anh tạo nhiều cảm xúc và động lực cho em để học hành tử tế hơn :D)