Bài giảng Cài đặt các giao mật mã dùng đường cong elliptic trên trường hữu hạn

CÀI ĐẶT CÁC GIAO MẬT MÃ DÙNG ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG HỮU HẠNMục tiêuKiến thức cơ bản về đường cong ellipticCài đặt một số giao thức mật mã dùng đường congI. CÁC KIẾN THỨC LIÊN QUANTRƯỜNG HỮU HẠNĐƯỜNG CONG ELLIPTICĐƯỜNG CONG ELLIPTIC TRÊN RĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG FpĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG Fq1.TRƯỜNG HỮU HẠNTrường là tập K với hai phép toán cộng (+) và nhân(*) thỏa:K là nhóm aben với phép toán cộng có phần tử trung hòa (của phép cộng)K\{O} là nhóm aben với phép táon nhân có phần tử đơn vị Với mọi a,b,c thuộc K ta có:c(a+b)=ca+cbVà (a+b)c=ca+cb (luật phân phối)Trường có thể có vô hạn phần tử( VD: R)Một trường được gọi là hữu hạn nếu nó có hữu hạn phần tử. VD:ZP={0,1,,p-2,p-1}	Với p nguyên tố.(Zp với phép cộng theo mod p, phép nhân theo mod p)-->một trườngNếu p ngyên tố thì trường hữu hạn Fp là trừng gồm các phần tử từ 0 đến p-1Nếu q=pr. Thì phần tử của trường Fq thỏa phương trình:Xq-X=0Fq là tập nghiệm của pt này. Phần tử của trường Fq là các đa thứcĐặc số của trường: K trường có phần tử đơn vị 1 với phép toán nhân. Khi đó đặc số của K được định nghĩa là: sốn n nhỏ nhất sao cho:1+1++1=0 (n lần)KÝ HIỆU: char K=nNếu không tồn tại số n như vậy , nghĩa là 1+1+.+1≠ 0 ta cộng thêm “1” bao nhiêu cũng được .=> đặc số bằng 0Bậc của a: Với a thuộc F*q: bậc của a là số k nhỏ nhất không âm thỏa a k=1.Bậc của a luôn là ước của q-1.II GIỚI THIỆU ĐƯỜNG CONG ELLIPTICĐịnh nghĩa: Đường cong elliptic trên trường K là tập hợp các điểm thỏa phương trình: (E):y2+a1xy+a3y=x3+a2x2+a4x+a6 (1)Với một đểm O gọi là điểm tại vô cùng.Phương trình phải thỏa điều kiện không kì dị. Nghĩa là khi viết dưới dạng F(x,y)=0 thì tại mọi điểm (x,y) có ít nhất một trong các đạo hàm riêng khác 0.Điều kiện không kì dị nghĩa là nếu xét tập các điểm trên một đường cong, thì dường cong đó không có điểm bội. Hay nếu biểu diễn y2 như một đa thứ bậc 3 của x thì đa thức không có nghiệm bội.4.ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG SỐTHỰCTrong những trường đặc số khác 2,3 phương trình (1) có thể đưa dạng Weierstrass về:(E):y2=4x3+a4x+a6 Biệt thức: Δ=-16(4a43+27a62)Điều kiện không kì dị(không có điểm bội):4a43+27a62≠0(E):y2=x3+2x+1 (E):y2=x3-3x+2 (E):y2+y=x3-x 	(E): y2=x3+1/4*x+5/45. ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG HỮU HẠNCác điểmcủa đường cong (E) KH: E(Fq) trên trường Fq có q phần tử thỏa mãn phương trình trong Fq:	y2=4x3+a4x+a6Ví dụ:(E): y2=x3+1 (a1=0, a6=1) trên F5Các điểm thuộc đường cong: (0,1),(0,-1),(2,2)(2,-2),(4,0)II. CÁC PHÉP TOÁN1. PHÉP CỘNG 2.PHÉP NHÂN NHANH3. TƯƠNG Ứ NG MỘT SỐ VỚI MỘT ĐIỂM TRÊN CONGĐẾM SỐ ĐIỂM CỦA ĐƯỜNG CONG(Lecture Notes on Computer network Security by Avi Kak)2. PHÉP CỘNGĐường cong elliptic trên trường số thực:Cộng hai điểm P(x1,y1) + Q(x2,y2).=(x3,y3). Ta có công thức:Và phép nhân:Với:Trên Z(2n)(E): y2+xy=x3+ax+bĐiểm –p=(x,-(x+y)Công thức cộng hai điểm P,Q:Với 3.PHÉP NHÂNPhép nhân ta có 2P=P+P:Phép nhân nP ta thực hiện phép cộng P n lầnCộng hai điểm trên trường hữu hạnVí dụ:p=29, a=4, b=20(E): y2=x3+4x+20 trên F29(5,22)+(16,27)=(13,16)2(5,22)=(14,6)Ví dụ:F24 Với a=z3,b=z3+1, f(z)=z4+z+1	(E): y2+xy=x3+z3x2+(x3+1)phần tử trong trường này có dạng: a3z3+a2z2+a1z+a0 được biểu diển là:(a3a2a1a0) Ta có:P(0010,1111), Q(1100,1100) (0010,1111)+(1100,1100)=(0001,0001)2(0010,1111)=(1011,0010)II. CÁC GIAO THỨC MẬT MÃĐỊNH NGHĨA GIAO THỨCMÔ HÌNH TRA ĐỔI CHÌA DIFFIE-HELLMANHỆ MÃ EL GAMAL DÙNG ECTHUẬT TOÁN ECIESCHỮ KÝ ĐIỆN TỬ1. GIAO THỨCĐỊNH NGHĨA: Giao thức là nghi thức giao dịch gồm một số bước hoạt động của hai hay nhiều phía để hàn thành một nhiệm vụ xác định.CÁC TÍNH CHẤT CỦA GIAO THỨC:Người tham gia phải nắm vững các bước của giao thứcMọi người phải chấp hành việc tuân thủ giao thức Giao thức phải mạch lạc rõ ràngGiao thức phải mang tính đầy đủ.GIAO THỨC MẬT MÃ: là giao thức dùng trong lĩnh vực mật mã và được xây dựng trên các công cụ mật mã học.Các công cụ nền tảng của mật mã học là các hệ mã, hàm băm, phương pháp ký điện tử 2. MÔ HÌNH TRAO ĐỔI CHÌA DIFFIE-HELLMAN MÔ HÌNH TRAO ĐỔI CHÌA DIFFIE-HELLMAN:Các thao tác thực hiện:A và B thống nhất giá trị gA chọn số m ngẫu nhiên và tính Qa=gm và gởi cho B.B chọn số n ngẫu nhiên và tính Qb=gn và gởi cho A A nhân được Qb và tính k= Qbm=gnm B nhân được Qa và tính k= Qan=gnm vậy k chính là khóa bí mật chung.TRAO ĐỔI CHÌA DIFFIE –HELLMAN DÙNG EC (ECDH)Các bước thực hiện: A, B thống nhất các tham số sử dụng như đường cong E, điểm P thuộc E A chọn ngẫu nhiên m tính Qa=mP và gởi cho B B chọn ngẫu nhiên n tính Qb=nP và gửi cho AA nhận được Qb sau đó tính k=mQbB nhận được Qa sau đó tính k=nQa vậy k chính là khóa bí mật chungVí dụ: p=211; E: y2=x3+4 (mod 211)Điểm P=(2,2) ; A chọn m=121 vậy Qa=mP=121(2,2)=(115,48)B chon n=203 vây Qb=nP=203(2,2)=(130,203)Khóa bí mật chung là: 121(130,203)=203(115,48)=121. 203(115,48)	=(161,69)HỆ MÃ EL GAMAL DÙNG ECHỆ MÃ EL GAMAL:Các bước thực hiện:A chọn số ngẫu nhiên s trong khoảng (1,p-1)A gửi cho B cặp số: gs (mod p) và MgsB (mod p)Khi nhận được cặp số này B có thể tính ra M như sau: lấy số thứ nhất trong cặp số A gửi lũy thừa bậc Kb (khóa bí mật của B) được số:(g s )B=gsB .2. Lấy nghịch đảo số vừa tính nhân với số thứ nhất trong cặp số A gửi: (gsB) -1gsB M =MChỉ có B mới tính được M vì B có khóa bí mật . HỆ MÃ EL-GAMAL DÙNG ECCho đường cong E, và một điểm G thuộc E. A chọn khóa bí mật là a và khóa công khai là aG=KA. B chọn khóa bí mật là b và khóa công khai là bG=KB. Giả sử A muốn gửi M cho B . Các bước thực hiện như sau:A chọn s ngẫu nhiên trong khoảng (0,p-1) A gửi cho B cặp điểm (sG, M+sKB)Khi nhận được cặp số này B có thể tính ra M như sau:	1. Lấy số sau điểm thứ nhất trong cặp A gửi nhân với khóa bí mật của mình: 	bsG =s(bG)=sKB	2. Lấy điểm thứ hai trừ đi điểm vừa tính :(M+sKB)-sKB=M4. THUẬT TOÁN ECIES(Elliptic Curve Integrated Encryption Scheme)Với p nguyên tố. Với một tọa độ x có thể có không hoặc hai giá trị y thỏa đường cong.Ta có xác định điểm P(x,y) bằng cách chỉ lưu điểm x và giá trị y mod 2.Thuật toán: POINT_COMPRESS(P):Return (x,y mod 2) với P(x,y) thuộc EĐể khôi phục lại điểm P ban đầu ta dùng thuật toán POINT-DECOMPRESS như sau:POINT-DECOMPRESS(x,i):	z=x3+ax+b mod p	nếu z là thặng dư bình phương của p:	tính y=sqrt(z)	nếu : z%2=i: return (x,y)	ngược lại : return (x,p-y)Thuật toán ECIESCho E là đường cong elliptic trên Fp. Điểm P thuộc E. chọn m là khóa bí mật. tính Q=mP . Các giá trị E, P,Q là công khai. Văn bản cần mã hóa là xMã hóa:Chọn k ngẫu nhiên trong khoảng (0,p-1).eK(x,k)=(y1,y2)y1=POINT-COMPRESS(Kp),y2=xx0 mod pVới kQ=(x0,y0)Văn bản mã hóa y=(y1,y2)Giải mã:	dK(y1,y2)=y2(x0) -1 mod p	Với (x0,y0)=M POINT-DECOMPRESS(y1)Ví dụ :p=11;E: y2=x3+x+6 (mod 11)P=(2,7)B chọn khóa bí mật là 7. khi đó khóa công khai của B là 7P=(7,2)Giả sử A muốn gửi cho B x=9. A chọn k=6Sau đó tính kP=6(2,7)=(7,9)Và kQ=6(7,2)=(8,3) vậy x0=8Sau đó A tính y1=POINT_COMPRESS(7,9)=(7,1)Và y2= xx0 (mod p)= 8.9 (mod 11)=6Văn bản mã hóa: y=(y1,y2)=((7,1),6)B nhận được y =((7,1),6) và tính :POINT-DECOMPRESS(7,1) = (7,9) m(7,9)=7(7,9)=(8,3) vậy X0=8 vậy y2.x0 -1 (mod p) = 95. CHỮ KÝ ĐIỆN TỬCho đường cong E trên Fp. Cho A là điểm thuộc đường cong. Điểm A có bậc q. chon m trong khoảng (0,p-1) là khóa bí mật. Tính điểm B=mA. Các giá trị E,A, B, p,q là công khaiH(x) là hàm băm được sử dụngTHUẬT TOÁN ECDSA:Chọn số ngẫu nhiên k thuộc (0,p-1)Tính kP=(u,v)Tính r=u mod qTính s=k-1(H(x)+mr) mod qNếu r=0 hoặc s=0 thì quay lại bước 1Return (r,s)Xác nhận chữ ký:1. tính w=s -1 mod q2. Tính i= wH(x) mod q3. Tính j=wr mod q4. Tính (u,v)=iA+jBNếu u mod q=r thì chữ ký là đúng.VÍ DỤ: p=11; q=13; E: y2=x3+x+6 (mod 11) A=(2,7) m=7 , B=(7,2). Giả sử H(x) = 4. A chọn ngẫu nhiên k=3. và tính :(u,v) =3(2,7) =(8,3)	r= u mod 13 =8S=3 -1 (4+7.8 )mod 13 =7Vậy (8,7) là chữ ký. Để xác nhận B tính:W=7 -1 mod 13 =2i= 2.4 mod 13 =8 ; j=2.8 mod 13 =3(u,v)=8A+7B =(8,3) và u =8 mod 13=rVậy chữ ký là đúng. KẾT QUẢ THỰC NGHIỆMCÁC PHÉP TOÁN CƠ BẢN CÀI ĐẶT MỘT SỐ HỆ MÃ SO SÁNH VỚI RSAThuật toán: tìm Pm	Input : số m Output: điểm Pm1.Đặt j=1. 2.Nếu j>k: kết thúc.	 Ngược lại: đặt Yj=xj3+axj+b 	Nếu tồn tại yj sao cho Yj=yj2 in ra Pm(xj,yj,). Kết thúc	ngược lại chuyển sang B.33. Đặt j=j+1. quay về B.2	1.TƯƠNG ỨNG MỘT SỐ VỚI MỘT ĐIỂMVÍ DỤ: 	p=40000003; k=40; m=123456EC_num_point(123456,400000003,40,-1,1)(4938242, 83987042L) 	(4938243, 9914640L) 	(4938244, 124990919L)(4938245, 280096337L) (4938246, 9715681L)	(4938248, 274370394L)(4938250, 257080392L)	(4938251, 190812280L) (4938252, 376131274L)(4938255, 68591519L) (4938256, 183687772L) (4938257, 353994642L)(4938258, 3750228L) (4938259, 60999797L) (4938260, 237442229L)(4938264, 326492682L) (4938267, 230908667L) (4938268, 395538867L)(4938269, 240740560L) (4938271, 370004584L) (4938272, 341275975L)(4938273, 253605272L) (4938274, 185104984L) (4938275, 147306773L)(4938277, 242060906L)2.ĐẾM SỐ ĐIỂM CỦA ĐƯỜNG CONGVí dụ: y2=x3+1 trên F17Có 18 điểm (kể cả điểm vô cùng)(0, 1);(0 ,16);(1, 6);(1, 11);(2, 3);(2 ,14);(6 ,8);(6 ,9);(7, 2);(7, 15);(9, 4);(9 ,13);(10,7);(10, 10);(14 ,5);(14 ,12); (16 ,0)3.CỘNG HAI ĐIỂM ,NHÂN HAI ĐIỂMThuật toán: Input: P=(x1,y1),Q=(x2,y2) Output: P+QNếu:P=O: return QNếu Q=O: return PNếu P=Q :	lam=(3x12+a)(2y1)-1 mod p	R1= lam2- 2y1 (mod p)	R2=(lam*(y1-R1) – y2 mod pNếu P= -Q : return ONếu P≠Q: 	lam =(y2-y1)(x2-x1) –1 mod p	R1= lam2- y1 –y2 (mod p)	R2=(lam*(y1-R1) – y2 mod pReturn (R1,R2)4.NHÂN NHANHCó nhiều thuật toán giúp nhân nhanh :Phương pháp nhân đôi liên tiếp:205P=2(2(2(2(2(2(2P+P)+P)P)+P))+P)Thay vì cộng p 205 lần ta đưa về 5 phép cộng và 7 phép nhânTHUẬT TOÁN :NHÂN kP	Input: k >0,P Output: kP1.Nếu P=O thì return P R=O; T=P2. while(k>0) 	 nếu (k%2)==1: R=R+TT=2Tk=k//2Return R	Ví dụ: p=11 E: y2 = x3+x+6 (mod 11) với P=(2,7)0 P = infinity 	1P = (2, 7) 2P = (5, 2)3P =(8,3)	 4 P = (10,2) 	6P= (7,9)7P=(7,2) 	 8P=(3,5)	9P=(10,9)10P=(8,8)	11P=(5,9)	12P=(2,4) SO SÁNH CÁC HỆ MÃ DÙNG EC VÀ RSA Thuật toán RSA mã hóa nhanh hơn giải mãECC giải mã nhanh hơn mã hóaThuật toán RSA dựa trên bài toán phân tích ra thừa số nguyên tố của số nguyên EEC dựa trên bài toán logarit rời rạc trên trường hữu hạn.Cùng độ bảo mật như nhau nhưng độ dài khóa của EEC ngắn hơn so với RSADo kích thước khóa nên thời gian phái sinh khóa của EEC nhanh hơn RSAECDLP có độ phức tạp mũ trong khi các thuật toán khác có độ phức tạp dưới mũ.Tuy nhiên EEC vẫn có mặt hạn chế. Do việc lựa chọn tham số đường cong và điểm quy ước chung sao cho đạt độ bảo mật cần thiết. Đối với các tham số nhỏ mức độ bảo mật của EEC đôi khi không bằng RSA. Đối với một số trường hợp RSA vẫn là lựa chọn tốt và đã ổn định trong thời gian khá dài. Hiện nay, hệ mật RSA là giải thuật khoá công khai được sử dụng nhiều nhất, nhưng hệ mật dựa trên đường cong Elliptic (ECC) có thể thay thế cho RSA bởi mức an toàn và tốc độ xử lý cao hơn. Ưu điểm của ECC là hệ mật mã này sử dụng khoá có độ dài nhỏ hơn so với RSA. Từ đó làm tăng tốc độ xử lý một cách đáng kể, do số phép toán dùng để mã hoá và giải mã ít hơn và yêu cầu các thiết bị có khả năng tính toán thấp hơn, nên giúp tăng tốc độ và làm giảm năng lượng cần sử dụng trong quá trình mã hoá và giải mã.