Cấu trúc môđun của tập điểm có bậc hữu hạn trên đường cong elliptic và ứng dụng trong mật mã

Journal of Science – 2015, Vol. 8 (4), 10 – 21<br /> <br /> Part D: Natural Sciences, Technology and Environment<br /> <br /> CẤU TRÚC MÔĐUN CỦA TẬP ĐIỂM CÓ BẬC HỮU HẠN TRÊN ĐƯỜNG CONG<br /> ELLIPTIC VÀ ỨNG DỤNG TRONG MẬT MÃ<br /> Võ Anh Tuấn1<br /> 1<br /> <br /> ThS. Trường Đại học An Giang<br /> Thông tin chung:<br /> Ngày nhận bài: 30/12/14<br /> Ngày nhận kết quả bình duyệt:<br /> 15/02/15<br /> Ngày chấp nhận đăng: 12/15<br /> <br /> ABSTRACT<br /> <br /> Title:<br /> Module structure of the set of<br /> points having finite order on<br /> elliptic curve and application in<br /> cryptography<br /> <br /> Weierstrass form over<br /> <br /> Từ khóa:<br /> Đường cong elliptic không kỳ<br /> dị, điểm có bậc hữu hạn, cấu<br /> trúc module, mật mã<br /> Keywords:<br /> Nonsingular elliptic curve, the<br /> point has finite order, the<br /> module structure, cryptography<br /> <br /> The main aim of this article is describing module structure of the set of the points<br /> P on elliptic curve which satisfy nP=O. In this set, P is the point having finite<br /> order on nonsingular elliptic curve E. The elliptic’s equation is given by<br /> <br /> p<br /> <br /> field (p is a prime number greater than 3) and O is<br /> <br /> the point at infinity. The set of the points which satisfy this condition is a subgroup<br /> and its structure is a<br /> <br />  n  module. Beside this new  n  module structure,<br /> <br /> this article also describes a new encryption method based on this structure by<br /> maple 13.0 software.<br /> <br /> TÓM TẮT<br /> Mục đích chính của bài báo này là mô tả cấu trúc môđun của tập hợp những điểm<br /> P nằm trên đường cong elliptic thỏa mãn điều kiện nP=O. Trong đó, P là điểm<br /> có bậc hữu hạn trên đường cong elliptic E không kỳ dị, phương trình của đường<br /> cong elliptic E được cho bởi dạng Weierstrass trên trường  p (là số nguyên tố<br /> lớn hơn 3), O là điểm tại vô cùng. Tập hợp những điểm mà nó thỏa mãn điều kiện<br /> này là một nhóm con và cấu trúc của nó là  n  môđun. Bên cạnh cấu trúc<br /> môđun mới này, bài báo còn mô tả một phương pháp mã hóa dựa trên cấu trúc<br /> này bằng phần mềm maple 13.0.<br /> <br />  p n là nhóm con của<br /> <br /> 1. GIỚI THIỆU<br /> <br /> nP=O thì khi đó E <br /> <br /> Ta ký hiệu tập điểm của đường cong elliptic E trên<br /> <br />  p  và cấu trúc của nhóm con này là một<br /> <br /> trường  p (p là số nguyên tố lớn hơn 3) là<br /> <br /> E <br /> <br />  p  . Để tập điểm này trở thành nhóm aben ta<br /> <br /> E <br /> <br />  n  module. Trong trường hợp n là một số<br /> <br /> bổ sung vào điểm tại vô cùng O và quy tắc cộng<br /> điểm. Một điểm P trên đường cong elliptic E được<br /> gọi là có bậc n nếu nP  O, mP  O với mọi<br /> <br /> nguyên tố ta sẽ có được một phương pháp mã hóa<br /> dựa vào cấu trúc môđun của nhóm con này.<br /> Trong suốt bài báo này phương trình của đường<br /> cong elliptic E được cho bởi dạng Weierstrass:<br /> <br />  p n là tập<br /> <br /> số nguyên 1  m  n . Nếu gọi E <br /> <br /> 2<br /> <br /> 3<br /> <br /> y  x  ax  b<br /> <br /> hợp những điểm trên đường cong elliptic thỏa mãn<br /> <br /> 3<br /> <br /> 2<br /> <br /> 4a  27b  0.<br /> 10<br /> <br /> thỏa<br /> <br /> mãn<br /> <br /> điêu<br /> <br /> kiện<br /> <br /> Journal of Science – 2015, Vol. 8 (4), 10 – 21<br /> <br /> Part D: Natural Sciences, Technology and Environment<br /> <br /> 2. CẤU TRÚC MÔĐUN CỦA TẬP ĐIỂM CÓ BẬC HỮU HẠN TRÊN ĐƯỜNG CONG ELLPTIC<br /> 2.1 Định nghĩa<br /> Điểm P trên đường cong elliptic được gọi là điểm có bậc n nếu nP = O , mP  O, với mọi số nguyên<br /> <br /> 1  m  n và ký hiệu bậc của P là deg(P).<br /> 2.2 Mệnh đề<br /> Cho P là điểm có bậc n trên đường cong elliptic E không kỳ dị. Khi đó, với mọi số nguyên k   thì điểm<br /> kP  mP . Trong đó m là số dư trong phép chia k cho n. Hay nói cách khác với mọi<br /> <br /> k  m   n , P  E  p  thì kP  mP .<br /> n<br /> <br /> Chứng minh. Với k  m   n thì tồn tại số nguyên a   sao cho k  m  an . Khi đó với mọi<br /> <br /> P  E  p  ta có kP  m  an  P . Bằng phương pháp quy nạp ta chứng minh kP  mP .<br /> n<br /> <br /> Thật vậy, với a  0  kP  mP hiển nhiên đúng.<br /> <br /> <br /> <br /> <br /> <br /> + Với a  1  kP  m  n P  mP  nP do cấu trúc   môđun và vì nP=O nên<br /> <br /> kP  mP .<br /> <br /> <br /> <br /> <br /> <br /> + Với a  2  kP  m  2n P lý luận tương tự như trên ta được kP  mP .<br /> <br /> <br /> <br />  <br /> <br /> <br /> <br /> + Giử sử đúng a  l  1 ta chứng minh đúng với a  l . Nghĩa là kP  m  l  1 n P  mP<br /> <br /> <br /> <br /> <br /> <br /> ta chứng minh kP  m  ln P  mP . Thật vậy,<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> kP  m  l  1  1 n P  kP  m  l  1 n  n P  m  l  1 n P  nP<br /> <br /> <br /> <br /> <br /> <br />  <br /> <br /> Do giả thuyết quy nạp m  l  1 n P  mP<br /> <br />  kP  mP  nP<br /> Vì nP  O nên ta thu được kP  mP .<br /> <br />  n . □<br /> <br /> Dễ dàng chứng minh được điểm mP  E  p<br /> 2.3 Mệnh đề<br /> <br /> Cho đường cong Elliptic E xác định trên trường  p (p> 3) thỏa mãn điều kiện không kỳ dị. Khi đó,<br /> <br />  <br /> <br /> E p<br /> <br /> n<br /> <br /> là một   môđun.<br /> n<br /> <br /> Chứng minh.<br /> <br />  <br /> <br /> i. Trước tiên ta chứng minh E  p<br /> <br />  <br /> <br /> + E p<br /> <br /> n<br /> <br />  <br /> <br /> n<br /> <br />  <br /> <br /> là nhóm con của E  p .<br /> <br />  <br /> <br />  E  p , điểm O  E  p<br /> <br /> n<br /> <br />  <br /> <br /> do đó E  p<br /> <br /> 11<br /> <br /> n<br /> <br />  .<br /> <br /> Journal of Science – 2015, Vol. 8 (4), 10 – 21<br /> <br />  <br /> <br /> + P , Q  E  p<br /> <br /> n<br /> <br /> Part D: Natural Sciences, Technology and Environment<br /> <br />  .<br /> <br /> ta chứng minh P  Q  E  p<br /> <br /> n<br /> <br /> Thật vậy, ta xét điểm n(P  Q )  nP  nQ do tính chất của một   môđun.<br /> <br />  <br /> <br /> Mà P , Q  E  p<br /> <br /> n<br /> <br /> nên nP  O, nQ  O  nP  nQ  O  n (P  Q )  O<br /> <br />  <br /> <br />  P Q  E p<br /> <br /> n<br /> <br /> + Ta xét phần tử đối của P, giả sử Q là phần tử đối của P. Khi đó, ta có:<br /> <br /> P  Q  O  n(P  Q )  O<br /> Mặt khác, n(P  Q )  nP  nQ  nP  nQ  O , mà nP  O , do đó: nQ  O . Từ đây<br /> <br />  <br /> <br /> ta có được Q  E  p<br /> <br />  <br /> <br /> Như vậy, E  p<br /> <br /> n<br /> <br /> n<br /> <br /> .<br /> <br />  <br /> <br /> bảo toàn phép toán cộng do đó nó là nhóm con của E  p .<br /> <br /> ii. Tiếp theo ta xây dựng phép nhân ngoài.<br /> <br />  <br /> <br /> n  E  p<br /> <br /> n<br /> <br /> (m, P )<br /> <br />  <br /> <br />  E p<br /> <br /> n<br /> <br />  mP<br /> <br />   . Ta có: k (lP )  k (lP )<br /> <br /> a. Tính chất kết hợp: k , l   n , P  E  p<br /> <br /> n<br /> <br />  k (lP )  k (lP )  k (lP )  (kl )P  k (lP )  (kl )P  k (lP )  (kl )P .<br /> <br />   . Ta có:<br /> <br /> b. Tính chất phân phối: k , l   n , P , Q  E  p<br /> <br /> n<br /> <br /> + (k  l )P  (k  l )P  (k  l )P  (k  l )P  (k  l )P  (k  l )P<br /> <br />  (k  l )P  kP  lP  (k  l )P  kP  lP .<br /> + k (P  Q )  k (P  Q )  k (P  Q )  kP  kQ  k (P  Q )  kP  kQ .<br /> c. Tính chất Unita. Ta có: 1P  1P  P .<br /> Rõ ràng đây là một   môđun.<br /> n<br /> <br /> 3. ỨNG DỤNG<br /> Ví dụ 1. Sử dụng giao thức trao đổi chìa khóa của Diffie-Hellman vào phương pháp mã hóa sử dụng điểm<br /> có bậc hữu hạn. Giả sử T cần gởi văn bản mật cho C là:<br /> “Mathematics is my favorite subject”.<br /> <br /> 12<br /> <br /> Journal of Science – 2015, Vol. 8 (4), 10 – 21<br /> <br /> Giả sử khóa bí mật của T là<br /> trong<br /> <br /> <br /> <br /> ví dụ<br /> <br /> Part D: Natural Sciences, Technology and Environment<br /> <br /> k1  2 , khóa bí mật của B là k2  3 và u là phần tử được chọn ngẫu nhiên<br /> <br /> u  7 . Khi đó: Khóa công khai của T là KSCKT  7k1  49 . Khóa công khai của<br /> <br /> C là KSCKC  7<br /> <br /> k2<br /> <br />  343 .<br /> <br /> * Tiến trình mã hóa: T muốn gởi văn bản cho C tiến hành như sau: T đặt tương ứng văn bản rõ với một<br /> điểm P có bậc là một số nguyên tố n thuộc đường cong E và tính khóa bí mật cho phiên làm việc này là<br /> k<br /> <br /> K  (KSCKC ) 1  117649 . T tiến hành mã hóa bằng cách tính điểm nhân K .P  Q và gởi cho<br /> C điểm Q.<br /> * Tiến trình giải mã: C nhận được điểm Q tiến hành giải mã như sau:<br /> k<br /> <br /> C tính khóa của phiên làm việc này là M  (KSCKT ) 2 và tìm bậc của Q.<br /> C tìm<br /> <br /> m   n , tính nghịch đảo m<br /> <br /> 1<br /> <br /> 1<br /> <br /> và giải mã bằng cách tính điểm m Q .<br /> <br /> Chứng minh.<br /> Vì n là một số nguyên tố. Khi đó,  n là một trường. Với mọi m   n , m  0 luôn tồn tại m<br /> sao cho m.m<br /> <br /> 1<br /> <br /> 1<br /> <br />  n<br /> <br />  1 mà 1P  1P  P .<br /> <br /> Như vậy, với một số nguyên k bất kỳ được chọn làm khóa thì luôn tồn tại m   n sao cho<br /> <br /> k  m  m  n   kP  mP  Q .<br /> 1<br /> <br /> 1<br /> <br /> 1<br /> <br /> Để khôi phục lại được dữ liệu, ta lấy m Q  m (mP )  (m m )P  1P .<br /> Mà 1P  1P  P . Kết luận: Dữ liệu được khôi phục.<br /> 4. MÔ TẢ PHƯƠNG PHÁP BẰNG PHẦN MỀM MAPLE 13.0<br /> Bảng tương ứng số - ký tự - điểm.<br /> <br /> Tương ứng hệ<br /> thập phân<br /> 0<br /> <br /> Đồ hoạ<br /> (Hiển thị ra<br /> được)<br /> Khoảng<br /> trống (␠)<br /> <br /> Tương ứng với<br /> điểm trên<br /> đường cong E<br /> <br /> Tương ứng hệ<br /> thập phân<br /> <br /> Đồ hoạ<br /> (Hiển thị ra<br /> được)<br /> <br /> Tương ứng với<br /> điểm trên<br /> đường cong E<br /> <br /> [19,67]<br /> <br /> 49<br /> <br /> w<br /> <br /> [116,160]<br /> <br /> 1<br /> <br /> A<br /> <br /> [22,91]<br /> <br /> 50<br /> <br /> x<br /> <br /> [120,93]<br /> <br /> 2<br /> <br /> B<br /> <br /> [23,99]<br /> <br /> 51<br /> <br /> y<br /> <br /> [124,190]<br /> <br /> 3<br /> <br /> C<br /> <br /> [26,100]<br /> <br /> 52<br /> <br /> z<br /> <br /> [125,40]<br /> <br /> 4<br /> <br /> D<br /> <br /> [27,67]<br /> <br /> 53<br /> <br /> !<br /> <br /> [126,195]<br /> <br /> 5<br /> <br /> E<br /> <br /> [28,194]<br /> <br /> 54<br /> <br /> #<br /> <br /> [135,60]<br /> <br /> 6<br /> <br /> F<br /> <br /> [30,135]<br /> <br /> 55<br /> <br /> $<br /> <br /> [138,139]<br /> <br /> 7<br /> <br /> G<br /> <br /> [33,52]<br /> <br /> 56<br /> <br /> %<br /> <br /> [140,142]<br /> <br /> 8<br /> <br /> H<br /> <br /> [34,154]<br /> <br /> 57<br /> <br /> &<br /> <br /> [142,198]<br /> <br /> 13<br /> <br /> Journal of Science – 2015, Vol. 8 (4), 10 – 21<br /> <br /> Part D: Natural Sciences, Technology and Environment<br /> <br /> Tương ứng hệ<br /> thập phân<br /> <br /> Đồ hoạ<br /> (Hiển thị ra<br /> được)<br /> <br /> Tương ứng với<br /> điểm trên<br /> đường cong E<br /> <br /> Tương ứng hệ<br /> thập phân<br /> <br /> Đồ hoạ<br /> (Hiển thị ra<br /> được)<br /> <br /> Tương ứng với<br /> điểm trên<br /> đường cong E<br /> <br /> 9<br /> <br /> I<br /> <br /> [35,45]<br /> <br /> 58<br /> <br /> '<br /> <br /> [143,26]<br /> <br /> 10<br /> <br /> J<br /> <br /> [37,132]<br /> <br /> 59<br /> <br /> (<br /> <br /> [144,48]<br /> <br /> 11<br /> <br /> K<br /> <br /> [38,191]<br /> <br /> 60<br /> <br /> )<br /> <br /> [145,80]<br /> <br /> 12<br /> <br /> L<br /> <br /> [40,52]<br /> <br /> 61<br /> <br /> *<br /> <br /> [146,124]<br /> <br /> 13<br /> <br /> M<br /> <br /> [41,85]<br /> <br /> 62<br /> <br /> +<br /> <br /> [147,155]<br /> <br /> 14<br /> <br /> N<br /> <br /> [43,13]<br /> <br /> 63<br /> <br /> ,<br /> <br /> [148,59]<br /> <br /> 15<br /> <br /> O<br /> <br /> [45,42]<br /> <br /> 64<br /> <br /> -<br /> <br /> [150,87]<br /> <br /> 16<br /> <br /> P<br /> <br /> [46,93]<br /> <br /> 65<br /> <br /> .<br /> <br /> [155,19]<br /> <br /> 17<br /> <br /> Q<br /> <br /> [47,170]<br /> <br /> 66<br /> <br /> /<br /> <br /> [157,4]<br /> <br /> 18<br /> <br /> R<br /> <br /> [49,32]<br /> <br /> 67<br /> <br /> 0<br /> <br /> [161,109]<br /> <br /> 19<br /> <br /> S<br /> <br /> [50,147]<br /> <br /> 68<br /> <br /> 1<br /> <br /> [164,88]<br /> <br /> 20<br /> <br /> T<br /> <br /> [53,101]<br /> <br /> 69<br /> <br /> 2<br /> <br /> [167,189]<br /> <br /> 21<br /> <br /> U<br /> <br /> [54,194]<br /> <br /> 70<br /> <br /> 3<br /> <br /> [168,15]<br /> <br /> 22<br /> <br /> V<br /> <br /> [55,189]<br /> <br /> 71<br /> <br /> 4<br /> <br /> [173,51]<br /> <br /> 23<br /> <br /> W<br /> <br /> [56,177]<br /> <br /> 72<br /> <br /> 5<br /> <br /> [179,189]<br /> <br /> 24<br /> <br /> X<br /> <br /> [57,178]<br /> <br /> 73<br /> <br /> 6<br /> <br /> [181,140]<br /> <br /> 25<br /> <br /> Y<br /> <br /> [58,200]<br /> <br /> 74<br /> <br /> 7<br /> <br /> [183,47]<br /> <br /> 26<br /> <br /> Z<br /> <br /> [61,36]<br /> <br /> 75<br /> <br /> 8<br /> <br /> [189,84]<br /> <br /> 27<br /> <br /> a<br /> <br /> [62,68]<br /> <br /> 76<br /> <br /> 9<br /> <br /> [190,158]<br /> <br /> 28<br /> <br /> b<br /> <br /> [64,72]<br /> <br /> 77<br /> <br /> :<br /> <br /> [191,199]<br /> <br /> 29<br /> <br /> c<br /> <br /> [65,35]<br /> <br /> 78<br /> <br /> ;<br /> <br /> [195,14]<br /> <br /> 30<br /> <br /> d<br /> <br /> [69,101]<br /> <br /> 79<br /> <br /> <<br /> <br /> [196,184]<br /> <br /> 31<br /> <br /> e<br /> <br /> [70,141]<br /> <br /> 80<br /> <br /> =<br /> <br /> [197,11]<br /> <br /> 32<br /> <br /> f<br /> <br /> [77,17]<br /> <br /> 81<br /> <br /> ><br /> <br /> [198,7]<br /> <br /> 33<br /> <br /> g<br /> <br /> [80,45]<br /> <br /> 82<br /> <br /> ?<br /> <br /> [202,83]<br /> <br /> 34<br /> <br /> h<br /> <br /> [86,145]<br /> <br /> 83<br /> <br /> @<br /> <br /> [205,74]<br /> <br /> 35<br /> <br /> i<br /> <br /> [90,127]<br /> <br /> 84<br /> <br /> [<br /> <br /> [206,84]<br /> <br /> 36<br /> <br /> j<br /> <br /> [92,117]<br /> <br /> 85<br /> <br /> ]<br /> <br /> [212,14]<br /> <br /> 37<br /> <br /> k<br /> <br /> [94,25]<br /> <br /> 86<br /> <br /> {<br /> <br /> [213,23]<br /> <br /> 38<br /> <br /> l<br /> <br /> [95,175]<br /> <br /> 87<br /> <br /> }<br /> <br /> [215,116]<br /> <br /> 39<br /> <br /> m<br /> <br /> [97,46]<br /> <br /> 88<br /> <br /> ^<br /> <br /> [219,89]<br /> <br /> 40<br /> <br /> n<br /> <br /> [98,42]<br /> <br /> 89<br /> <br /> _<br /> <br /> [220,22]<br /> <br /> 41<br /> <br /> o<br /> <br /> [99,49]<br /> <br /> 90<br /> <br /> `<br /> <br /> [222,53]<br /> <br /> 42<br /> <br /> p<br /> <br /> [101,148]<br /> <br /> 91<br /> <br /> |<br /> <br /> [224,6]<br /> <br /> 43<br /> <br /> q<br /> <br /> [104,135]<br /> <br /> 92<br /> <br /> ~<br /> <br /> [234,53]<br /> <br /> 44<br /> <br /> r<br /> <br /> [106,13]<br /> <br /> 93<br /> <br /> Ñ<br /> <br /> [238,82]<br /> <br /> 14<br /> <br />