Monday, July 14, 2014

Từ đại số đến Bitcoin: 26, Fermat và tôi

26 là một trong những con số mà tôi yêu thích nhất: nó là số tự nhiên duy nhất nằm kẹp giữa một số bình phương (25) và một số lập phương (27).

Đây là một trong những phát hiện của Fermat, nhà toán học vĩ đại người Pháp sống vào thế kỷ 17. Fermat viết bên lề cuốn Arithmetica của Diophantus rằng nghiệm nguyên duy nhất của phương trình $latex y^2 = x^3 - 2$ là $latex (3, \pm 5)$, nhưng ông không công bố bất kỳ chứng minh cụ thể nào cả (nghe quen không?!). Fermat còn thách thức các nhà toán học người Anh cùng thời chứng minh nó, nhưng ai cũng bó tay. Bẵng đi 80 năm sau, Euler công bố một chứng minh, nhưng ngặt nỗi, chứng minh của Euler sai. Bạn có thể tin được không? Euler vĩ đại đưa ra một chứng minh sai! Cho đến tận thế kỷ 19, gần 150 năm sau thời đại của Fermat, con người mới có đủ tri thức để chứng minh rằng Fermat đã đúng. Số 26 đúng là con số duy nhất nằm giữa một số bình phương và một số lập phương.

Chuyện này có liên quan gì đến tôi?

Tôi vô tình thấy bài toán này một vài năm trước và kể từ đó lâu lâu lại mất ăn mất ngủ vài buổi, vì chứng minh mãi không được. Tìm trên Internet cũng có vài chứng minh, nhưng mà chúng sử dụng kiến thức toán tôi không hiểu được. Tôi hầu như đã bỏ cuộc rồi, cho đến khi tôi bắt đầu học thêm toán vì muốn làm mật mã. Ai dè cái mớ toán mà tôi học lại có dây mơ rễ má với bài toán này.

Những kiến thức toán mà tôi sắp trình bày chẳng phải cao siêu gì, tôi nhớ không lầm thì chương trình năm nhất đại học của tôi có dạy hết, nhưng mà hồi xưa tôi không có chịu học, vì không có biết nó hay thế này :-).

Chứng minh của Euler

Đầu tiên Euler chuyển phương trình thành $latex x^3 = y^2 + 2$ (1). Ý tưởng chủ đạo là: a) phân tích vế phải của (1) thành tích hai thừa số nguyên tố cùng nhau; b) vế trái là một số luỹ thừa bậc ba, cho nên cả hai thừa số của vế phải đều là lũy thừa bậc ba; c) từ đó tìm ra nghiệm của phương trình.

Bài tập 1: cho $latex a, b, c \in \mathbf{Z}$ chứng minh rằng $latex a = x^3, b = y^3$ với $latex x, y \in \mathbf{Z}$ nếu như $latex c^3 = {ab}$ và $latex \gcd{(a, b)} = 1$, trong đó $latex \gcd{(a, b)}$ là ước số chung lớn nhất của $latex a$ và $latex b$.

Rõ ràng nếu chỉ xét trên $latex \mathbf{Z}$ thì không có cách nào phân tích được vế phải của (1) thành nhân tử cả. Nhưng toán học là trò chơi mà ở đó các nhà toán học đặt ra các luật chơi, càng ít càng tốt, rồi tự hỏi: cái thế giới mà chúng ta xây dựng từ những luật chơi này có gì hay ho và hữu dụng không? Khi mà nhóm luật chơi ban đầu không còn đem lại những kết quả thú vị nữa thì người ta sẽ thêm vào những luật chơi mới và lại đặt lại câu hỏi ở trên.

Tương tự như thế, để giải quyết những bài toán khó người ta thường thêm vào những luật chơi để tạo ra một thế giới mới, mạnh mẽ hơn, phổ quát hơn nhưng vẫn tương thích với thế giới cũ, rồi dùng những kết quả trong thế giới mới để giải quyết các bài toán trong thế giới cũ. Để giải quyết bài toán của Fermat, Euler thêm vào một luật chơi mới: tồn tại một số $latex \delta$ sao cho $latex \delta^2 = -2$. Nếu chúng ta chấp nhận luật chơi này thì vế phải của (1) sẽ phân tích được thành nhân tử với $latex x^3 = (y - \sqrt{-2}) (y + \sqrt{-2})$ (2).

Không đưa ra một chứng minh cụ thể, Euler chỉ lập luận rằng do $latex y - \sqrt{-2}$ và $latex y + \sqrt{-2}$ nguyên tố cùng nhau (Euler cũng không giải thích tại sao) nên mỗi thừa số phải là một lũy thừa bậc ba. Nghĩa là $latex \exists a, b, c, d \in \mathbf{Z}$ sao cho:
$latex y - \sqrt{-2} = (a + b\sqrt{-2})^3 = (a^3 - 6ab^2) + (3a^2b - 2b^3)\sqrt{-2} $ (3)
$latex y + \sqrt{-2} = (c + d\sqrt{-2})^3 = (c^3 - 6cd^2) + (3c^2d - 2d^3)\sqrt{-2}$ (4)

Vì $latex \sqrt{-2} \notin \mathbf{Z}$, nên từ (3) ta có $latex 3a^2b - 2b^3 = b(3a^2 - 2b^2) = -1$. Nghiệm của phương trình này là $latex a = \pm 1$ và $latex b = -1$. Tương tự như thế ta suy ra nghiệm của phương trình (4) là $latex c = \pm 1$ và $latex d = 1$. Từ đó tính được $latex y = \pm 5$. Do đó $latex (3, \pm 5)$ là nghiệm nguyên duy nhất của phương trình (1).

Để thấy thiếu sót trong lập luận của Euler, chúng ta hãy thử dùng phương pháp này để giải phương trình $latex x^2 = y^2 + 5$. Theo Euler thì $latex \exists a, b, c, d \in \mathbf{Z}$ sao cho:
$latex y - \sqrt{-5} = (a + b\sqrt{-5})^2 = (a^2 - 5b^2) + (2ab)\sqrt{-2} $ (3)
$latex y + \sqrt{-5} = (c + d\sqrt{-5})^2 = (c^2 - 5c^2) + (2cd)\sqrt{-2}$ (4)

Suy ra $latex 2ab = -1$ và $latex 2cd = 1$ (vô lý). Do đó theo Euler phương trình $latex x^2 = y^2 + 5$ không có nghiệm nguyên, nhưng có thể thấy rằng $latex (3, 2)$ là một nghiệm.

Vậy Euler sai ở chỗ nào? Để hiểu chỗ sai của Euler, chúng ta cần phải hiểu chuyện gì xảy ra khi luật chơi mới được thêm vào.

Đại số trừu tượng

Trước khi tìm hiểu luật chơi mới, chúng ta cần phải nhìn lại những luật chơi đã có. Do đề bài là tìm nghiệm nguyên, luật chơi mà chúng ta quan tâm là những luật chi phối các số nguyên và các phép toán giữa chúng. Xét phép toán cộng trên tập $latex \mathbf{Z}$ chúng ta có thể thấy những luật chơi sau đây:
Nhóm phép cộng trên $latex \mathbf{Z}$
i) Đóng: $latex a + b \in \mathbf{Z}, \ \forall a, b \in \mathbf{Z}$
ii) Kết hợp: $latex a + (b + c) = (a + b) + c , \ \forall a, b, c \in \mathbf{Z}$
iii) Giao hoán: $latex a + b = b + a, \ \forall a, b \in \mathbf{Z}$
iv) Phần tử identity [1]: tồn tại một phần tử identity, ký hiệu là $latex 0_{\mathbf{Z}}$ thỏa điều kiện $latex a +  0_{\mathbf{Z}} = a, \ \forall a \in \mathbf{Z}$. Dễ dàng thấy rằng đối với phép cộng trên $latex \mathbf{Z}$ thì $latex  0_{\mathbf{Z}}$ chính là số 0.
v) Phần tử nghịch đảo: $latex \forall a \in \mathbf{Z}, \ \exists b \in \mathbf{Z}: a + b =  0_{\mathbf{Z}}$. Đối với phép cộng trên $latex \mathbf{Z}$ thì phần tử nghịch đảo của $latex a$ chính là $latex -a$.

Những luật chơi này chẳng có gì đặc biệt, nếu không muốn nói là hết sức tầm thường, nhưng tôi muốn nhấn mạnh: sự tầm thường của chúng chẳng qua là do chúng ta quá quen thuộc với phép cộng trên tập số nguyên. Bạn sẽ thấy 5 luật chơi này sâu sắc hơn nhiều, nếu biết rằng chúng vẫn đúng nếu chúng ta xét phép cộng hai điểm trên đường cong elliptic định nghĩa trên một trường hữu hạn - phép toán mà từ đó người ta xây dựng một thuật toán rất quan trọng trong Bitcoin.

Phép cộng trên $latex \mathbf{Z}$ chỉ là một ví dụ cụ thể của một cấu trúc đại số (algebraic structure) sâu sắc và tổng quát hơn nhiều, mà các nhà toán học gọi là nhóm Abel (Abelian group). Nếu phép toán trên một tập hợp không có tính giao hoán, nhưng vẫn thỏa đầy đủ các điều kiện còn lại (ví dụ như phép nhân hai ma trận) cấu trúc đại số được tạo ra vẫn được xem làm một nhóm, nhưng chúng ta chỉ xem xét nhóm Abel trong phạm vi bài viết này. Trừ khi có ghi chú cụ thể, từ đây về sau tôi sẽ dùng từ nhóm để chỉ nhóm Abel.

Một cách tổng quát, phép toán, ký hiệu là $latex +_{\mathbf{G}}$, trên tập $latex \mathbf{G}$ sẽ tạo thành một nhóm, nếu thỏa những điều kiện sau đây:
Định nghĩa nhóm 
i) Đóng: $latex a +_{\mathbf{G}} b \in \mathbf{G}, \ \forall a, b \in \mathbf{G}$
ii) Kết hợp: $latex a +_{\mathbf{G}}(b +_{\mathbf{G}} c) = (a +_{\mathbf{G}} b) +_{\mathbf{G}} c , \ \forall a, b, c \in \mathbf{G}$
iii) Giao hoán: $latex a +_{\mathbf{G}} b = b +_{\mathbf{G}} a, \ \forall a, b \in \mathbf{G}$
iv) Phần tử identity: tồn tại một phần tử identity, ký hiệu $latex 0_{\mathbf{G}}$ thỏa điều kiện $latex a +_{\mathbf{G}} 0_{\mathbf{G}} = a, \ \forall a \in \mathbf{G}$.
v) Phần tử nghịch đảo: $latex \forall a \in \mathbf{G}, \ \exists b \in \mathbf{G}: a +_{\mathbf{G}} b = 0_{\mathbf{G}}$.
Lưu ý: tôi dùng ký hiệu $latex +_{\mathbf{G}}$ để chỉ phép toán trên nhóm, nhưng không có nghĩa phép toán đó tương tự như phép cộng hai số nguyên.

Bài tập 2: cho $latex \mathbf{G}$ là một nhóm, chứng minh rằng:
a) $latex \mathbf{G}$ chỉ có duy nhất một phần tử identity.
b) Mọi phần tử của $latex \mathbf{G}$ chỉ có duy nhất một nghịch đảo.
c) $latex a +_{\mathbf{G}} b = a +_{\mathbf{G}} c \Longleftrightarrow b = c, \ \forall a,b,c \in \mathbf{G}$.

Trên tập $latex \mathbf{Z}$ thì những thuộc tính trong bài tập ở trên được mặc nhiên thừa nhận như là một phần của luật chơi, nhưng bây giờ chúng ta thấy rằng có thể chứng minh được chúng. Nói cách khác nhóm luật chơi mà chúng ta chọn ra đã bao gồm luôn những thuộc tính này. Do đó chọn lựa những luật chơi nào để tổng quát hóa lên là một vấn đề quan trọng. Nếu chọn thiếu thì chúng ta không thể xây dựng được những kết quả hữu ích, còn chọn thừa thì chúng ta lại sẽ không nhìn thấy được bức tranh toàn cảnh. Tại sao những luật chơi ở trên được chọn? Câu trả lời đơn giản là vì người ta thấy chúng vừa đủ.

Nhóm xuất hiện ở khắp nơi. Những thuật toán mã hóa khóa công khai phổ biến nhất được xây dựng dựa trên nhóm. Hàng xóm của tôi làm machine learning, tập trung vào nhận dạng giọng nói, một lĩnh vực tưởng chừng như chẳng liên quan gì đến nhóm hay đại số, nhưng một lần tôi thấy anh ấy đọc sách đại số, hỏi ra thì mới biết có một nhánh nghiên cứu mới trong ngành của anh ấy sử dụng các công cụ và tri thức của đại số trừu tượng (abstract algebra), tức là nhóm và các cấu trúc đại số khác, để giải quyết các vấn đề của machine learning.

Đây chính là sức mạnh của đại số trừu tượng. Chúng ta có thể quên đi bản chất của những phần tử và phép toán giữa chúng, mà chỉ cần tìm hiểu những tính chất của một nhóm tổng quát, suy ra từ tập luật chơi ban đầu, nhưng những tính chất này sẽ đúng trên tất cả các nhóm. Ví dụ như các định lý ở bài tập số 2 đúng với nhóm phép cộng trên $latex \mathbf{Z}$, nhóm phép nhân của trường hữu hạn $latex \mathbf{F}_p$ (sẽ nói đến sau), hay nhóm các điểm trên đường cong elliptic trên một trường hữu hạn, v.v. Nói cách khác, chúng ta chỉ cần tìm hiểu một lần và có thể dùng đi dùng lại tri thức về nhóm cho các ứng dụng rất khác nhau.

Ngoài phép cộng ra trên tập $latex \mathbf{Z}$ còn có phép nhân thỏa mãn các luật chơi sau đây:
Tính chất của phép nhân trên $latex \mathbf{Z}$
i) Đóng: $latex ab \in \mathbf{Z}, \ \forall a, b \in \mathbf{Z}$
ii) Kết hợp: $latex a(bc) = (ab)c, \ \forall a, b \in \mathbf{Z}$.
iii) Giao hoán: $latex ab = ba, \ \forall a, b \in \mathbf{Z}$.
iv) Phần tử identity: tồn tại phần tử identity, ký hiệu là $latex  1_{\mathbf{Z}}$, thỏa điều kiện $latex a1_{\mathbf{Z}} = a, \ \forall a \in \mathbf{Z}$. Dễ dàng thấy rằng đối với phép nhân trên $latex \mathbf{Z}$ thì $latex 1_{\mathbf{Z}}$ chính là số 1.
v) Phân phối trên phép cộng: $latex a(b + c) = ab + ac, \ \forall a, b, c \in \mathbf{Z}$.
Lưu ý rằng không có phần tử nào của $latex \mathbf{Z}$, ngoại trừ $latex \pm{1}$, có phần tử nghịch đảo theo phép nhân.

Một tập hợp với hai phép toán thỏa mãn các tính chất tương tự như phép cộng và nhân trên $latex \mathbf{Z}$ được gọi là vành (ring). $latex \mathbf{Z}$ là vành số nguyên. Tập hợp các số hữu tỉ $latex \mathbf{Q}$ với các tính chất thông thường của phép cộng và phép nhân tạo thành một vành. Tập hợp các số hữu tỉ $latex \mathbf{R}$ với các tính chất thông thường của phép cộng và phép nhân tạo thành một vành.

Lưu ý: tương tự như nhóm, tồn tại những vành mà phép nhân không có tính giao hoán. Cũng có vành mà phần tử identity của phép nhân không tồn tại. Do đó nói một cách chính xác vành mà chúng ta xét ở đây là vành giao hoán với phần tử identity của phép nhân, nhưng do tất cả các vành mà chúng ta quan tâm đều ở dạng này cho nên từ đây về sau tôi chỉ gọi chúng là vành.

Quay trở lại chứng minh của Euler. Nhắc lại, Euler thêm vào một luật chơi mới: tồn tại phần tử $latex \delta$ sao cho $latex \delta^2 = -2$. Xét tập $latex \mathbf{Z}[\sqrt{-2}] = \{a + b\delta: \ a, b \in \mathbf{Z}\}$.

Cho $latex x = a + b\delta, \ x' = a' + b'\delta$, tổng và tích của $latex x$ và $latex x'$ được định nghĩa như sau:
Phép cộng và nhân trên $latex \mathbf{Z}[\sqrt{-2}] $
$latex x + y = (a + a') + (b + b')\delta$
$latex xy =  (aa' - bb') + (ab' + a'b)\delta$
Bài tập 3: Chứng minh rằng tập $latex \mathbf{Z}[\sqrt{-2}]$ với hai phép toán định nghĩa như trên tạo thành một vành.

Dễ dàng thấy rằng $latex \mathbf{Z} \subset \mathbf{Z}[\sqrt{m}]$, trong đó $latex m < 0$. Người ta gọi $latex \mathbf{Z}$ là một vành con của $latex \mathbf{Z}[\sqrt{m}]$. Đây là điểm mấu chốt để thấy được chỗ sai trong lập luận của Euler: vì $latex \mathbf{Z}$ là vành con của $latex \mathbf{Z}[\sqrt{m}]$, một số tính chất của $latex \mathbf{Z}$ có thể không còn đúng trên $latex \mathbf{Z}[\sqrt{m}]$.

Sự khác biệt đó là: mọi số nguyên trên vành $latex \mathbf{Z}$ có thể được phân tích thành tích của các số nguyên tố và sự phân tích này là duy nhất. Đây là định lý cơ bản của số học. Định lý này có vẻ hiển nhiên, nhưng lưu ý rằng nó không thuộc vào tập luật chơi ban đầu trong định nghĩa của một vành. Nói cách khác, từ tập luật chơi này, với một số vành nhất định, ta có thể chứng minh hoặc phủ định tính chất phân tích nhân tử duy nhất (unique factorization).

Trong phần sau chúng ta sẽ tìm hiểu tính chất phân tích nhân tử duy nhất và chứng minh rằng nó đúng trên $latex \mathbf{Z}$ và $latex \mathbf{Z}[\sqrt{-2}]$, nhưng lại sai trên $latex \mathbf{Z}[\sqrt{-5}]$.

[1] Tôi không biết nên dịch identity element ra tiếng Việt sao cho hay. Ai biết chỉ giùm.

Wednesday, June 18, 2014

Why Javascript Crypto Is Useful

Update: Nate Lawson published a thoughtful comment on this article.

Update: A few more thoughts from Brad Hill of PayPal and W3C.

Update: why it's hard to maintain large codebases written in Javascript or other dynamic languages.

It's approximately a year ago when I wrote my first Javascript crypto library for a production system at Google - it's a thin wrapper on top a library that has been released as End-To-End. Since then I've designed and written many such wrappers - eight of which have been deployed in popular products and services. I think Javascript crypto is a very useful tool that could help solve a wide range of problems, some of which I'm going to discuss below.

Some people have strong feelings about Javascript crypto, for good reason. At the end of the day Javascript is the language of the Web, so like it or not Javascript crypto won't go away. As somebody who likes crypto and security the only thing that I figure I could do is to study to understand the problems and fix them.

Writing crypto code in Javascript is indeed difficult, because of the lack of types and the permissive nature of the run-times. It's always easy to shoot yourself in the foot if you don't know what you're doing in any languages, but in Javascript you don't even hear the shot: the run-times usually don't complain, but they just silently give you an incorrect result.

For example, if you have an array x of 10 elements, accessing x[10] or x[11] won't throw an out of bound exception, but return undefined. This behavior is very hostile to crypto code, as demonstrated in this super neat exploit discovered by Bleichenbacher, the grandfather of many crypto attacks:
* Visit http://people.eku.edu/styere/Encrypt/JS-AES.html. This is a Javascript implementation of AES.
* Encrypt this string: ưưưưưưưưưưưưưưưư as ASCII.
* Decrypt the ciphertext.
* XOR each character of the decryption with 0x52.
* And the result is the key.

So what happened? The program expects ASCII inputs, but we give it Unicode. The function that causes the vulnerability is SubBytes

// do S-Box substitution
function SubBytes(state, Sbox)
{
   var i;

   for( i=0; i<16; i++ )
      state[i] = Sbox[ state[i] ];

   return state;
}

The state variable holds the input. If state[i] >= 256, state[i] would become undefined because Sbox is defined as an array of only 256 elements. Apparently this problem doesn't just apply to that particular library - there are plenty of others. There's a few ways to take care of it.

The first thing you can do is to extensively check the inputs and limit the number of places where you have to convert types. If you want a byte array, you should always check that it's an array and each element is a byte. The type of parameters in public interfaces should be consistent. You don't want to accept strings in one place, and big integers or byte arrays in others. There's still a few places in the End-To-End's library that could be more consistent, and we're going on that.

You can also use typed arrays, instead of plain old array of numbers. When you see an Uint8Array you know for sure that each element is a byte, so don't have to perform the expensive check. Unfortunately Internet Explorer < 10 doesn't support typed arrays, so it's a bit ugly to use them right now. For that reason we haven't supported typed arrays in the End-To-End's library, but we're working on that too.

Finally you can use Closure's pseudo types. You can annotate variables with types, and the Closure compiler uses these annotations to type-check your program, which helps catch type mismatch bugs early during the development. End-To-End's library is built on Closure, so we have pseudo types since day one.

After fixing the type problem, Javascript then could only be as bad as other languages when it comes to XOR things together. I've seen broken crypto in C, C++, C#, Java, Ruby, Python, ActionScript, etc. so I don't really buy the argument that Javascript crypto is too bad that we shouldn't even try to do anything with it. The language has its annoying flaws, i.e., numbers are stored as floating point in a 52-bit mantissa, broken bitwise shift left, etc., but they just make the task of programming a crypto library a bit more fun and challenging, not riskier.

Most people consider Javascript crypto harmful after reading this article by Matasano Security (disclaimer: I worked at Matasano before joining Google, and I've always been a huge fan of @tqbf, one of the company's founders.) If you haven't go read it, I'll wait. I don't know when the article was written, but many of its criticisms are outdated. Javascript now has a secure PRNG. WebCrypto is going to provide a lot of native implementation of common crypto primitives, including a secure key storage. Guess what do Stanford, Google, and Microsoft have in common? Each has released an open source Javascript crypto library. No other languages have enjoyed this tremendous support.

That said, I totally agree with its main criticism: if you don't trust the network or the server, doing Javascript crypto, with the code being loaded directly over that network from that server, won't help safeguard your data against active network attackers or the server itself. That's why End-To-End will be released as a Chrome extension. In other words if the server or the network is considered as adversary in your threat model, don't trust Javascript crypto code delivered from them. This threat model doesn't, however, apply to all applications. Below is a few of many such applications that I've seen.

1. Crypto browser apps

Without Javascript crypto you don't have SSH-In-A-Tab, PwdHash, various Bitcoin wallets, etc.

Do you have a Chromecast? If you don't, go buy one. It's an amazing product, and did you know that it uses Javascript crypto to make the out of box setup so easy and yet secure?

We're living in a world dominated by apps, so it's easy to forget that instead of installing an app to do something you can just visit a website on your favorite browser and get the same thing done instantly, thanks to the power of Javascript.

2. Stay out of scope of PCI DSS

Here's how a request is typically processed in a large scale system: Browsers <----> Load Balancers <---> Reverse Proxies <---> Frontends <---> Backends.

If you don't want to make your load balancers, reverse proxies, frontends, etc. fall within the scope of PCI DSS you want to use Javascript crypto to encrypt credit card data on the browsers, and only decrypt them on the backends.

You also want to use Javascript crypto if the user inputs are so sensitive that you don't want them to be accidentally logged on any intermediate components.

3. Avoid leaking data to third-party

When you collect data with Javascript, and pass to server in URL parameters you could leak them to third-parties, e.g., via the Referer header. So you want to encrypt them using a public key encryption scheme, e.g., RSA, in Javascript.

4. Reduce latency

You have a big fat website that takes many seconds to load because it has to load megabytes of Javascript. The Javascript code is changed very frequently so caching doesn't help much. One solution is to cache the base code in localStorage, and just download a small diff next times. But if you do that, you may never recover from a compromise. If the attacker manages to insert a backdoor to the cached code of a user (by exploiting a XSS, for example) he'll forever have access to that user's account (see this talk by my colleague Artur Janc for more details).

So you want to verify the integrity of the cached code, and you can do that by digitally signing the cached code, then using Javascript on browsers to verify the signature. You can trust the Javascript code because it's freshly served by your server.

In general returning signed data and code to browsers, then verifying them with the Javascript code loaded from trusted origins could significantly help reduce latency by cutting the number of requests as well as the size of responses.

Conclusion: Programming crypto in Javascript is hard, but doable. As usual if you don't know much about crypto, you should use good libraries developed and maintained by people in the know. Javascript crypto has received unprecedented support from Stanford, Google, Microsoft and W3C, as it has been proven super useful in many applications.

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.