Chao xìn mọi người lại là mình đây Nhabachoc KAD.
Vì mình không có nhiều thời gian để có thể làm được một Blog hoàn chỉnh nên các bạn thông cảm nha. Hãy vào link sau để đọc được chi tiết bài viết vì ở dưới bị lỗi các công thức:
https://kadpkt.notion.site/Elliptic-394f892d81334998b90919c2c75b1a19Bài viết này có dành cho bạn?
Là 1 người muốn hiểu sâu hơn là chỉ biết áp dụng
Hay thắc mắc vì sao Ví Điện Tử có thể bảo mật
Học toán như không học
Hành trang cần chuẩn bị:
Tư duy logic để hiểu về toán học
Nới lỏng các cơ mặt, thả lỏng cơ não
Cùng tắt đèn bật ý tưởng, gét go 🪄
Hệ mật trên đường cong Elliptic (Elliptic Curve Cryptography, gọi tắt là ECC) là một trong những loại mật mã mạnh nhất hiện nay. Trong thế giới, ECC được áp dụng nhiều nhất trong mật mã bởi độ an toàn cực kỳ cao. Để đạt được độ an toàn nhưng tính toán lại nhanh, các nhà khoa học về bảo mật đã áp dụng CÁI LỜ 🤨🤨🤨 ơ này, đang học tập nha gì CL ở đây, bậy thế? Khônggggggg chính là cái lờ thật đó các bạn thử tìm trong GG xem
Cái Lờ là cái lồng hình trụ được đan bằng tre có hai cửa ở hai đáy , hai cửa này là loại cửa một chiều: cá chui vào được nhưng không thể chui ra.
Công cụ bắt cá này vào dễ - ra khó chính là những gì các nhà khoa học hay tìm kiếm. Để tạo ra được một hệ thống bảo mật hoàn hảo thì chúng ta cũng cần các yếu tố: Ngon - Dễ hiểu, Bổ - Bảo mật tốt, Rẻ - Tính toán nhanh và vào dễ - ra khó hay còn gọi là hàm bẫy rất phù hợp với tiêu chí này và elliptic còn có thêm được yếu tố nhanh nên quá là oki luôn.
Từ nãy tới giờ mình hơi vòng vo, nào bây giờ chính là đường cong elliptic:
$$ y^2 = x^3 + Ax + B $$
Với điều kiện $4A^3 + 27B^2 \not = 0$
Đường cong Elliptic trong không gian 3 chiều
1 mặt cắt của đường cong elliptic
Tính chất
Chúng ta sẽ cùng mổ xẻ và phân tích (không phải mõm nha) dựa trên toán học. Điểm độc đáo:
Tính đối xứng qua trục hoành ( trục x )
Bất kỳ đường không thẳng đứng nào cũng sẽ cắt đường cong ở nhiều nhất là ba điểm.
Chính nhờ 2 điểm này đã hình thành nên phép cộng trên đường cong mà ta sẽ nói ngay sau đây.
Phép toán nhóm trên EC trong trường số thực R:
Trước hết nếu chưa biết nhóm trong đại số là gì hãy đọc qua ở đây: Toán học cơ bản
Ở đây chúng ta đang và chỉ nói về nhóm cộng <không có phép trừ, nhân, chia điểm với điểm> trên EC và vì là 1 nhóm nên phải thoả mãn các tính chất của 1 nhóm. Với điểm P, Q thuộc EC thì theo tính chất đóng ⇒ điểm R là tổng của 2 điểm P, Q cũng thuộc EC mà “Bất kỳ đường không thẳng đứng nào cũng sẽ cắt đường cong ở nhiều nhất là ba điểm” rất phù hợp theo tính chất này.
Phép cộng 2 điểm
Nhìn trên hình các bạn có thể hình dung ra ngay cách mà phép cộng này hoạt động:
Khi P $\not =$ Q: Nối điểm P và Q cắt EC ở đâu, lấy đối xứng điểm đó là tổng 2 điểm
Khi P trùng Q: Vẽ đường tiếp tuyến tại P cắt EC ở đâu, lấy đối xứng điểm đó là tổng 2 điểm
Hừm tại sao lại là đối xứng nhỉ, các bạn có cùng thắc mắc với mình không 🤔 sao không lấy luôn điểm cắt làm tổng 2 điểm. Cái gì cũng có lý do của nó ????
Phép nhân vô hướng: Không có phép nhân 2 điểm trong EC nhưng phép nhân vô hướng thì khác, 1 điểm có toạ độ (x, y) nhân vô hướng với n thì điểm mới không phải (xn, yn) đâu nha 🤣 mà thực ra nó là n phép cộng. VD: nP = P + P + P + … + P và ta sẽ thực hiện từng phép tính:
P + P = 2P
2P + P = 3P
…
Phép nhân vô hướng
Nhóm con vòng (cyclic):
Trước hết nếu chưa biết nhóm cyclic số là gì hãy đọc qua ở đây: Toán học cơ bản
Bài toán Logarit rời rạc trên EC (ECDLP - Elliptic Curve Discrete Logarit Problem)
Trước hết nếu chưa biết Logarit rời rạc là gì hãy đọc qua ở đây: Toán học cơ bản
Bài toán: Cho E là một đường cong Elliptic và điểm P (có cấp n) thuộc E. Cho điểm Q $\in$ E, tìm số nguyên dương m ( $2 \leqslant m \leqslant n-2$ ) sao cho Q = mP
Chưa có thuật toán hiệu quả nào để giải quyết bài toán này. Muốn giải ta cần kiểm tra tất cả các giá trị $m \in [2...n-2]$, nếu điểm P được lựa chọn cẩn thận với n rất lớn thì việc giải bài toán ECDLP xem như không khả thi.
Vậy tóm lại nó làm gì ?
Sau khi đọc qua lý thuyết hãy cùng xem ví dụ nha chứ không u đầu quá rồi 😵💫 Ta muốn tính 215*A ( n=215 ) cần dừng lại và phân tích một chút:
Nếu ta biến thành A + A + A + … + A tổng 215 lần thì không có gì bàn cãi, rất đơn giản và dễ hiểu 👍 nhưng nếu con số n rất lớn vậy thì hỏng rồi, máy tính sẽ cần rất lâu để thực hiện cừng đấy phép tính và nếu vẫn cố chấp tính theo thì ta giả sử A + A mất 1s để tính thì tổng cần mất 214s để xong. OK
Nếu ta động não hơn một chút: 215 = $12^7 + 12^6 + 02^5 + 12^4 + 02^3 + 12^2 + 12^1 + 12^0$. Chỗ này khá dễ để phân tích nhỉ nhưng hồi trước mình cũng không biết tính đâu nên mình vẫn sẽ nói qua 1 chút:
B1: Bạn mặc định toàn bộ bạn này sẽ được quy đổi và tính theo hàm có hệ số là mũ 2.
B2: Chọn 1 con số $2^x$ gần số cần tìm ở đây là $2^7$ = 128 gần 215 nhất. Nếu $2^8$ = 256 sẽ vượt quá con số cần tìm và nhân với $i \in {\{0, 1\}}$ ở đây và 1 vì $2^7$ hợp lệ.
B3: Tính hiệu còn lại sau khi đã tìm được 215 - $2^7$ = 87
B3: Lần lượt như thế x từ số (bắt đầu - 1) đến 0 sẽ đc thay = 6→5→4→3→2→1→0. Ta thấy $2^6$ hợp lệ và tính hiệu chỉ còn lại 23 nhưng $2^5$ = 32 thì không vì nó lớn hơn hiệu còn lại là 23 …
Để ý thêm 1 chút ta sẽ nhận ra:
$$ 215A = 2^7A + 2^6A + 2^4A + 2^2A + 2^1A + 2^0*A $$
Và điều này vô hình chung rất thích hợp để tính toán:
Điểm $2^0*A = A$ có sẵn
Điểm $2^1*A = 2A = A + A$
Điểm $2^2*A = 4A = 2A + 2A$
Điểm $2^3*A = 8A = 4A + 4A$
…
Điểm $2^7*A = 128A = 64A + 64A$
Phép tính phía trước sẽ là bước tiến để phép tính phía sau thực hiện, các phép tính tăng lên theo cấp số nhân nên sẽ rất nhanh để có thể tiến được đến con số n 🚀 Các bạn hiểu tại sao tính theo hàm hệ số là mũ 2 chưa. Tính theo cách này chúng ta chỉ cần 8s để tính các điểm $2^0$ ⇒ $2^7$ và 7s để cộng các điểm đó lại với nhau. Tổng 15s <<< siêu nhỏ so với 214s 🥰 nếu n siêu to thì con số này còn kinh khủng hơn nữa.
Ngược lại, nếu chúng ta biết điểm đầu A và điểm cuối R là điểm cuối tính toán được yêu cầu tính n (bước tính) chính là bài toán ECDLP thì theo như phân tích bên trên nếu bạn không biết được n thì không thể tính ra dãy số để giúp phép tính nhanh hơn đồng nghĩa với việc bạn phải thử từng bước một.
🕵️ 🤟 Đây chính là điều làm nên sự kì diệu giúp nó đứng lên top đầu trong mật mã: tính toán nhanh mà an toàn.