Đường cong elip c ++
|
đường cong. "secp192r1" => y^2 = x^3 + 6277101735386680763835789423207666416083908700390324961276x + 2455155546008943817740293915197451784769108058161191238065 (mod 6277101735386680763835789423207666416083908700390324961279) 1 * G = (602046282375688656758213480587526111916698976636884684818, 174050332293622031404857552280219410364023488927386650641) 2 * G = (5369744403678710563432458361254544170966096384586764429448, 5429234379789071039750654906915254128254326554272718558123) 3 * G = (2915109630280678890720206779706963455590627465886103135194, 2946626711558792003980654088990112021985937607003425539581) 4 * G = (1305994880430903997305943738697779408316929565234787837114, 3981863977451150342116987835776121688410789618551673306674) 5 * G = (410283251116784874018993562136566870110676706936762660240, 1206654674899825246688205669651974202006189255452737318561) 6 * G = (4008504146453526025173196900303594155799995627910231899946, 3263759301305176906990806636587838100022690095020155627760) 7 * G = (3473339081378406123852871299395262476289672479707038350589, 2152713176906603604200842901176476029776544337891569565621) 8 * G = (1167950611014894512313033362696697441497340081390841490910, 4002177906111215127148483369584652296488769677804145538752) 9 * G = (3176317450453705650283775811228493626776489433309636475023, 44601893774669384766793803854980115179612118075017062201) # Khái niệm cơ bản về thực thi mật mã đường cong elip trên pythonimportcollectionsdefinv (n, q). "" "Div on pn modulo a/b mod % q == 1 "" "foriinrange (q). nếu (n*i) % q == 1. returnipassassertFalse," not used "passdefsqrt (n, q). " "" Nếu không tồn tại >>> khẳng định (sqrt (n, q) [0] ** 2) % q == n >>> khẳng định (sqrt (n, q) [1] ** 2) . """div trên PN modulo a/b mod q dưới dạng * inv(b, q) mod q >>> khẳng định n * inv(n, q) % q == 1 """foriinrange(q). nếu (n*i) %q==1. returnipassassertSai, "chưa đạt"passdefsqrt(n, q). """sqrt trên PN modulo. trả về hai số hoặc ngoại lệ nếu không tồn tại >>> khẳng định (sqrt(n, q)[0] ** 2) % q == n >>> khẳng định (sqrt(n, q)[1] ** 2) %Để hiểu động lực của mật mã đường cong elip, trước tiên chúng ta phải hiểu toàn bộ mục đích của mật mã khóa công khai. Để làm điều này, chúng tôi đưa ra một tình huống giả định liên quan đến hai người bạn cũ của những nhà mật mã ở khắp mọi nơi, Alice và Bob. ví dụ 1. 1. (Alice và Bob) Giả sử Alice và Bob muốn truyền đạt thông điệp bí mật cho nhau. Vấn đề duy nhất là, mọi người đều biết rằng một kẻ nghe trộm xấu xa (có tên thích hợp là Eve) có quyền truy cập vào tất cả các thông tin liên lạc giữa Alice và Bob. Làm thế nào họ có thể kể bí mật của mình mà Eve không nghe thấy (hoặc ít nhất là Eve không nghe thấy bất cứ điều gì quan trọng), và ngăn cô ấy làm xáo trộn thông tin trên đường truyền từ người này sang người khác? Đây là lúc ý tưởng về khóa công khai xuất hiện. Alice và Bob mỗi người có một khóa, một số hoặc quy trình toán học có thể được áp dụng cho các tin nhắn, bao gồm một phần công khai và một phần riêng tư. Các phần riêng tư của các khóa này không bao giờ được truyền đi, trong khi các phần công khai thì mọi người đều có thể truy cập được, kể cả Eve. Khi Alice muốn gửi một tin nhắn cho Bob, cô ấy sử dụng phần khóa công khai của Bob để mã hóa thông tin và gửi nó mà không cần lo lắng về việc ai sẽ nhìn thấy nó. Sau đó, Bob sử dụng phần bí mật trong khóa của mình để giải mã thông tin. Bởi vì Bob là người duy nhất có phần bí mật trong khóa của mình nên anh ấy là người duy nhất có thể giải mã nó. Để tăng cường bảo mật, Alice và Bob cũng có thể có chữ ký công khai và riêng tư, hoạt động tương tự như khóa. Nếu Alice muốn Bob biết rằng tin nhắn mà anh ấy nhận được từ cô ấy là xác thực, cô ấy sẽ áp dụng chữ ký riêng cho một số tin nhắn xác thực trước khi gửi nó; . Nếu Eve giả mạo chữ ký, chữ ký sẽ bị cắt xén và Bob sẽ biết nó bị hỏng Nếu khóa công khai và khóa riêng toán học không có ý nghĩa, chỉ cần nghĩ về khóa chung là ổ khóa và khóa riêng là chìa khóa của những ổ khóa đó. Alice và Bob đều phân phát công khai các bản sao và bản sao của từng ổ khóa của họ, nhưng luôn giữ chìa khóa an toàn bên mình Sau đó, để gửi cho Bob một tin nhắn, Alice chỉ cần tìm một trong những ổ khóa của Bob, khóa tin nhắn của cô ấy lại với nó và gửi cho anh ấy. Anh ta có một chìa khóa duy nhất cho tất cả các ổ khóa của mình, vì vậy anh ta là người duy nhất có thể mở nó Lưu ý rằng tính bảo mật của hệ thống này hoàn toàn không phụ thuộc vào việc Alice và Bob tìm ra cách an toàn để truyền thông tin, mà nó phụ thuộc rất nhiều vào Alice và Bob, mỗi người đều có các khóa riêng rất, rất khó truy xuất nếu chỉ sử dụng khóa chung của họ. Eve chỉ có thể bị cản trở nếu thông tin mà cô ấy có thể chặn được là hoàn toàn vô dụng. Điều này đưa chúng ta đến bài toán logarit rời rạc đường cong elip, mà chúng ta sẽ thấy có thể đủ khó để cung cấp cho chúng ta một cặp khóa hữu ích. Đầu tiên chúng ta phải giải thích các đường cong elip
định nghĩa 2. 1. Đường cong elip là một đường cong đại số xạ ảnh không đơn kì trên một trường k nào đó với chi 1 và một điểm xác định O (đây sẽ là “điểm ở vô cực”). Miễn là k không có đặc tính 2 hoặc 3, đây sẽ là một đường cong lập phương phẳng có điểm ở vô cực và chúng ta có thể mô tả đường cong là các điểm thỏa mãn phương trình y2 = x3 + ax + b, với a và b sao cho phân biệt, ∆ = −16(4a3 + 27b2), là khác không (sẽ mang lại tính không kỳ dị mong muốn) Luật nhóm trên đường cong elip. Hoạt động được khai thác để chọn khóa trong mật mã đường cong elip xuất phát từ việc coi đường cong elip là một nhóm abel với các điểm là phần tử. Luật nhóm là cộng điểm; Điểm kết quả, R, sẽ là tổng của P và Q. Với mục đích của phần bổ sung này, hãy lưu ý rằng điểm ở vô cực O nằm trên bất kỳ đường thẳng nào đi qua một điểm và nó ngược chiều. Các thuộc tính chính thức của luật bổ sung được mô tả dưới đây  Định lý 2. 2 Định luật cộng trên đường cong elip C có các tính chất sau (trong đó O = −O là điểm ở vô cực, và nếu P = (x0, y0) thì −P = (x0, −y0)) (i) Đối với điểm P ∈ C, P + O = P , (ii) Với các điểm P, Q ∈ C, P + Q = Q + P (iii) Với điểm P ∈ C, tồn tại điểm −P sao cho P + (−P) = O (iv) Với P, Q, R ∈ C, (P + Q) + R = P + (Q + R) Nói tóm lại, luật bổ sung cho chúng ta các thuộc tính nhóm mà chúng ta mong muốn. Ngoài ra, chúng tôi sẽ lưu ý rằng tập hợp con các điểm trong nhóm này có cả hai tọa độ thuộc về một trường k đã cho, cùng với điểm ở vô cực, sẽ tạo thành một nhóm con của nhóm đường cong C. Điều này sẽ rất quan trọng, bởi vì các đường cong được sử dụng trong mật mã đường cong elip được xác định trên một trường hữu hạn và chúng ta cần đóng tập hợp đó dưới phép cộng điểm Bởi vì mục tiêu của chúng tôi bây giờ không phải là xây dựng mật mã đường cong elliptic, mà là để hiểu cách thức hoạt động của nó, chúng tôi sẽ bỏ qua bằng chứng chính thức, nhưng lưu ý rằng hầu hết các thuộc tính ở trên đều tuân theo trực tiếp từ mô tả hình học của phép cộng điểm
Bây giờ chúng ta đã hiểu các thuộc tính của các đường cong elliptic như các nhóm, chúng ta có thể tiếp cận vấn đề logarit rời rạc của đường elliptic, từ đó các hệ thống mật mã đường cong elliptic rút ra sức mạnh của chúng định nghĩa 3. 1 Bài toán logarit rời rạc đường cong elip (ECDLP) là đây. cho một đường cong elip C được xác định trên Fq và hai điểm P, Q ∈ C, tìm một số nguyên x sao cho Q = xP Có thể hiểu ở cấp độ rất cơ bản tại sao vấn đề này có thể khó giải quyết. Hãy tưởng tượng trải qua nhiều lần lặp lại quy trình cộng điểm được mô tả ở trên trên một đường cong có rất nhiều điểm, sau đó xóa tất cả các bước trung gian. Không rõ ngay lập tức cách tiến hành khi cố gắng tạo lại quy trình bạn vừa ẩn Trên thực tế, không ai biết chính xác vấn đề này khó giải như thế nào, bởi vì không ai nghĩ ra một thuật toán hiệu quả để giải quyết nó. Tuy nhiên, nó được cho là khó giải hơn so với bài toán logarit rời rạc nói chung, và các bài toán phân tích thừa số khác nhau được sử dụng trong các hệ thống mật mã khác (và các phương pháp tốt nhất để bẻ khóa các bài toán này dường như không dễ dàng thích ứng với các bài toán về đường cong elliptic) . Khi xem xét các kích thước khóa cần thiết cho nhiều mức bảo mật nhất định (trong đó “an toàn hơn” có nghĩa là “mất nhiều thời gian hơn để phá vỡ”) của hệ thống mật mã đường cong elip so với các hệ thống mật mã truyền thống khác, kích thước khóa yêu cầu của các hệ thống khác tăng theo cấp số nhân khi độ khó tăng lên, Điều này có nghĩa là nếu chúng ta thiết lập hệ thống mật mã của mình sao cho chúng chỉ có thể bị bẻ khóa bằng cách giải ECDLP, thì thông điệp của Bob và Alice sẽ cực kỳ an toàn
Bởi vì ECDLP cho chúng ta biết rằng đối với Q = xP, x rất khó tìm, chúng ta muốn Q và P là khóa chung trong bất kỳ hệ thống mật mã nào mà chúng ta sử dụng (khóa móc) và x là khóa riêng (khó tìm). . Có nhiều cách để xây dựng các hệ thống mật mã hoạt động theo cách này, vì vậy chúng tôi sẽ cung cấp hai ví dụ. Cả hai đều là dạng tương tự đường cong elip của các hệ thống mật mã có sẵn được tạo ra để sử dụng bài toán logarit rời rạc tổng quát; . Cả hai cũng giả sử một số hệ thống nhúng thông điệp hiện có vào các điểm trên đường cong elip. Có một số cách để thực hiện việc này, không có cách nào được gắn cụ thể vào các hệ thống mật mã đã cho, vì vậy chúng ta chỉ giả sử rằng chúng ta đã chọn một số cách nhúng thông điệp m vào điểm Pm, và cách nhúng này được biết đến công khai (để Bob có thể . Ví dụ đầu tiên của chúng tôi là sự thích ứng của hệ thống mật mã khóa công khai ElGamal Ví dụ 4. 1 (Hệ mật mã đường cong elip ElGamal) Giả sử rằng chúng ta có một số đường cong elip C xác định trên trường hữu hạn Fq trong đó q = pn lớn (và p là số nguyên tố) Giả sử rằng C, q và một điểm G ∈ C được biết đến công khai, cũng như hệ thống nhúng m # → Pm. Khi Alice muốn liên lạc bí mật với Bob, họ tiến hành như vậy
Đây là một hệ thống mật mã thành công vì mọi thao tác mà Alice và Bob phải thực hiện (cộng và trừ trên đường cong) đều tương đối dễ dàng, trong khi thao tác mà Eve phải thực hiện để bẻ khóa hệ thống là cực kỳ khó (hoặc đối với thực tế cuộc sống). . Ví dụ tiếp theo của chúng ta, một dạng tương tự của hệ thống mật mã khóa công khai Massey-Omura, hoạt động trên một loạt các bài toán dễ tới lui tương tự đối với Alice và Bob tạo ra ECDLP cho Eve Ví dụ 4. 2 (Hệ thống mật mã đường cong elip Massey-Omura) Như trước đây, giả sử rằng chúng ta có một số đường cong elip C được xác định trên một trường hữu hạn Fq trong đó q = pn lớn và N =. C. (Chúng tôi không cần số điểm trên C trong ví dụ trước, nhưng thông tin này không bao giờ được coi là bí mật, vì nó có thể được tính toán với hiệu quả tương đối. ) Hệ thống nhúng m # → Pm, cũng như q, C và N, được công khai Khi Alice muốn liên lạc bí mật với Bob, họ tiến hành như vậy
Tuy nhiên, các tính toán của Alice và Bob dễ thực hiện hơn nhiều so với ECDLP của Eve, vì vậy hệ thống mật mã này đã thành công
Các ví dụ mà chúng tôi đã cung cấp ở trên đơn giản về mặt khái niệm, nhưng điều quan trọng cần nhớ là các nhóm mà chúng tôi đang xem xét là rất lớn, các khóa đủ lớn để đo bằng số bit và các thao tác được mô tả là “tương đối dễ dàng” Chúng ta cũng phải nhớ rằng không phải mọi sự lựa chọn về đường cong, trường hữu hạn và điểm đều được tạo ra như nhau. Trong hệ thống ElGamal, Alice và Bob không hoạt động trên toàn bộ đường cong, mà trên nhóm tuần hoàn được tạo bởi G và trong hệ thống Massey-Omura, được tạo bởi Pm Những quyết định này phải được thực hiện tốt và sẽ mất nhiều không gian hơn thế này để giải thích cách thực hiện chúng tốt Tuy nhiên, với những lựa chọn phù hợp, chúng ta sẽ thấy sức mạnh của một thứ khá đơn giản, đó là luật nhóm đường cong elliptic. Một ý tưởng hình học đơn giản như việc kết nối các dấu chấm (mặc dù một dấu chấm phải nằm ở vô cực) mang lại cho chúng ta một hệ thống nhắn tin bí mật vẫn chưa bị bẻ khóa |
