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

Mục tiêu của 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 là nhằm giúp cho các bạn có kiến thức cơ bản về đường cong elliptic; biết cách cài đặt một số giao thức mật mã dùng đường cong. Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về lĩnh vực này.
Nội dung trích xuất từ tài liệu:
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ĐẶTCÁCGIAOMẬTMÃ DÙNGĐƯỜNGCONGELLIPTICTRÊNTRƯỜNGHỮU HẠNMụctiêu• Kiếnthứccơbảnvềđườngcongelliptic• Càiđặtmộtsốgiaothứcmậtmãdùng đườngcongI.CÁCKIẾNTHỨCLIÊNQUAN1. TRƯỜNGHỮUHẠN2. ĐƯỜNGCONGELLIPTIC3. ĐƯỜNGCONGELLIPTICTRÊNR4. ĐƯỜNGCONGELLIPTICTRÊN TRƯỜNGFp5. ĐƯỜNGCONGELLIPTICTRÊN TRƯỜNGFq1.TRƯỜNGHỮUHẠN• TrườnglàtậpKvớihaiphéptoáncộng (+)vànhân(*)thỏa:• Klànhómabenvớiphéptoáncộngcó phầntửtrunghòa(củaphépcộng)• K\{O}lànhómabenvớiphéptáonnhâncó phầntửđơnvị• Vớimọia,b,cthuộcKtacó:c(a+b)=ca+cbVà(a+b)c=ca+cb(luậtphânphối)• Trườngcóthểcóvôhạnphầntử(VD:R)• Mộttrườngđượcgọilàhữuhạnnếunó cóhữuhạnphầntử.VD:• ZP={0,1,…,p2,p1} Vớipnguyêntố.• (Zpvớiphépcộngtheomodp,phépnhân theomodp)>mộttrường• NếupngyêntốthìtrườnghữuhạnFplà trừnggồmcácphầntửtừ0đếnp1• Nếuq=pr.ThìphầntửcủatrườngFqthỏa phươngtrình:• XqX=0• Fqlàtậpnghiệmcủaptnày.• PhầntửcủatrườngFqlàcácđathức• Đặcsốcủatrường:• Ktrườngcóphầntửđơnvị1vớiphép toánnhân.KhiđóđặcsốcủaKđượcđịnh nghĩalà:sốnnnhỏnhấtsaocho:• 1+1+…+1=0(nlần)• KÝHIỆU:charK=n• Nếukhôngtồntạisốnnhưvậy,nghĩalà 1+1+….+1≠0tacộngthêm“1”baonhiêu cũngđược.=>đặcsốbằng0• Bậccủaa:• VớiathuộcF*q:bậccủaalàsốknhỏ nhấtkhôngâmthỏaak=1.• Bậccủaaluônlàướccủaq1. IIGIỚITHIỆUĐƯỜNGCONG ELLIPTICĐịnhnghĩa:ĐườngcongelliptictrêntrườngKlàtậphợpcácđiểmthỏaphươngtrình:(E):y2+a1xy+a3y=x3+a2x2+a4x+a6(1)VớimộtđểmOgọilàđiểmtạivôcùng.Phươngtrìnhphảithỏađiềukiệnkhôngkìdị.NghĩalàkhiviếtdướidạngF(x,y)=0thìtạimọiđiểm(x,y)cóítnhấtmộttrongcácđạohàmriêngkhác0.• Điềukiệnkhôngkìdịnghĩalànếuxéttập cácđiểmtrênmộtđườngcong,thìdường congđókhôngcóđiểmbội.• Haynếubiểudiễny2nhưmộtđathứbậc3 củaxthìđathứckhôngcónghiệmbội.4.ĐƯỜNGCONGELLIPTICTRÊNTRƯỜNGSỐTHỰC • Trongnhữngtrườngđặcsốkhác2,3 phươngtrình(1)cóthểđưadạng Weierstrassvề: (E):y2=4x3+a4x+a6 Biệtthức:Δ=16(4a43+27a62) Điềukiệnkhôngkìdị(khôngcóđiểmbội): 4a43+27a62≠0(E):y2=x3+2x+1(E):y2=x33x+2(E):y2+y=x3x (E):y2=x3+1/4*x+5/45.ĐƯỜNGCONGELLIPTICTRÊNTRƯỜNGHỮUHẠN Cácđiểmcủađườngcong(E)KH:E(Fq)trên trườngFqcóqphầntửthỏamãnphương trìnhtrongFq: y2=4x3+a4x+a6 Vídụ: (E):y2=x3+1(a1=0,a6=1)trênF5 Cácđiểmthuộcđườngcong: (0,1),(0,1),(2,2)(2,2),(4,0) II.CÁCPHÉPTOÁN• 1.PHÉPCỘNG• 2.PHÉPNHÂNNHANH• 3.TƯƠNGỨNGMỘTSỐVỚIMỘT ĐIỂMTRÊNCONG• ĐẾMSỐĐIỂMCỦAĐƯỜNGCONG 2.PHÉPCỘNGĐườngcongelliptictrêntrườngsốthực:CộnghaiđiểmP(x1,y1)+Q(x2,y2).=(x3,y3).Ta cócôngthức:• Vàphépnhân:• Với:• TrênZ(2n)• (E):y2+xy=x3+ax+b• Điểm–p=(x,(x+y)• CôngthứccộnghaiđiểmP,Q:• Với 3.PHÉPNHÂNPhépnhântacó2P=P+P:PhépnhânnPtathựchiệnphépcộngPnlần