Bài giảng Đường cong elliptic

Bài giảng Đường cong elliptic được biên soạn nhằm trang bị cho các bạn những kiến thức về giới thiệu chung; đường cong elliptic trên trường số thực; đường cong elliptic trên trường hữu hạn; các phép toán trường hữu hạn, phép cộng, phép nhân; các bài toán kiểm tra điểm thuộc đường cong, đếm số điểm của đường cong, cộng hai điểm, nhân hai điểm, nhân nhanh; đường cong và hệ mã công khai; so sánh với RSA.
Nội dung trích xuất từ tài liệu:
Bài giảng Đường cong ellipticĐƯỜNGCONGELLIPTIC I.GIỚITHIỆU1.ĐƯỜNGCONGTRÊNTRƯỜNGSỐTHỰC2.ĐƯỜNGCONGTRÊNTRƯỜNGHỮUHẠN I.GIỚITHIỆUĐị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.1.ĐƯỜ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+y=x3x (E):y2=x3+1/4*x+5/4(E):y^2=x^3+2*x+1 (E):y^2=x^33*x+22.ĐƯỜ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.TRƯỜNGHỮUHẠN• 2.PHÉPCỘNG• 3.PHÉPNHÂN1.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ân cóphầntửđơnvị • Vớimọia,b,cthuộcKta có:c(a+b)=ca+cb Và(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ạnFp làtrừnggồmcácphầntửtừ0đếnp1• Nếuq=pr.ThìphầntửcủatrườngFq thỏaphươ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 địnhnghĩ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ĩa là1+1+….+1≠0tacộngthêm“1”bao nhiêucũ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.• (LectureNotesonComputernetworkSecuritybyAviKak)Tínhchất:• P+O=O+P=PvớimọiPthuộc(E)• Tồntại–PsaochoP+P=O• Phépcông:P+QvớiP≠±Q• Phépnhân:nPvớiP≠P 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