椭圆曲线密码简明教程1Word文档下载推荐.docx

椭圆曲线密码简明教程1Word文档下载推荐.docx

《椭圆曲线密码简明教程1Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《椭圆曲线密码简明教程1Word文档下载推荐.docx（28页珍藏版）》请在冰点文库上搜索。

2.2EllipticCurveAddition:

AnAlgebraicApproach

2.2.1AddingdistinctpointsPandQ

2.2.2DoublingthepointP

2.3Experiment:

AnEllipticCurveModel（realnumbers）

2.4Quiz1Ellipticcurvegroupsoverrealnumbers

3.0EllipticCurveGroupsOverFp

3.1AnExampleofanEllipticCurveGroupoverFp

3.2ArithmeticinanEllipticCurveGroupoverFp

3.2.1AddingdistinctpointsPandQ

3.2.2DoublingthepointP

3.3Experiment:

AnEllipticCurveModel（overFp）

3.4Quiz2EllipticcurvegroupsoverFp

4.0EllipticCurveGroupsOverF2m

4.1AnExampleofanEllipticCurveGroupoverF2m

4.2ArithmeticinanEllipticCurveGroupoverF2m

4.2.1AddingthedistinctpointsPandQ

4.2.2DoublingthepointP

4.3Experiment:

AnEllipticCurveModel（overF2m）

4.4Quiz3EllipticcurvegroupsoverF2m

5.0ECGroupsandtheDiscreteLogProblem

5.1ScalarMultiplication

5.2TheEllipticCurveDiscreteLogarithmProblem

5.3AnExampleoftheEllipticCurveDiscreteLogarithmProblem

5.3.1AnECDLPSolution

WelcometotheEllipticCurveCryptosystemClassroom.ThissiteprovidesanintuitiveintroductiontoEllipticCurvesandhowtheyareusedtocreateasecureandpowerfulcryptosystem.Thefirstthreesectionsintroduceandexplainthepropertiesofellipticcurves.Abackgroundunderstandingofabstractalgebraisrequired,muchofwhichcanbefoundintheBackgroundAlgebrasection.ThenextsectiondescribesthefactorthatmakesellipticcurvegroupssuitableforacryptosystemthoughtheintroductionoftheEllipticCurveDiscreteLogarithmProblem（ECDLP）.ThelastsectionbringsthetheorytogetherandexplainshowellipticcurvesandtheECDLPareappliedinanencryptionscheme.ThisclassroomrequiresaJAVAenabledbrowserfortheinteractiveellipticcurveexperimentsandanimatedexamples.

Ellipticcurvesasalgebraic/geometricentitieshavebeenstudiedextensivelyforthepast150years,andfromthesestudieshasemergedarichanddeeptheory.Ellipticcurvesystemsasappliedtocryptographywerefirstproposedin1985independentlybyNealKoblitzfromtheUniversityofWashington,andVictorMiller,whowasthenatIBM,YorktownHeights.

Manycryptosystemsoftenrequiretheuseofalgebraicgroups.Ellipticcurvesmaybeusedtoformellipticcurvegroups.Agroupisasetofelementswithcustom-definedarithmeticoperationsonthoseelements.Forellipticcurvegroups,thesespecificoperationsaredefinedgeometrically.Byintroducingmorestringentpropertiestotheelementsofagroup,suchaslimitingthenumberofpointsonsuchacurve,createsanunderlyingfieldforanellipticcurvegroup.Inthisclassroom,ellipticcurvesarefirstexaminedoverrealnumbersinordertoillustratethegeometricalpropertiesofellipticcurvegroups.Thereafter,ellipticcurvesgroupsareexaminedwiththeunderlyingfieldsofFp（wherepisaprime）andF2m（abinaryrepresentationwith2melements）.

2.0EllipticCurveGroupsoverRealNumbers

Anellipticcurveoverrealnumbersmaybedefinedasthesetofpoints（x,y）whichsatisfyanellipticcurveequationoftheform:

y2=x3+ax+b,wherex,y,aandbarerealnumbers.

Eachchoiceofthenumbersaandbyieldsadifferentellipticcurve.Forexample,a=-4andb=0.67givestheellipticcurvewithequationy2=x3-4x+0.67;

thegraphofthiscurveisshownbelow:

Ifx3+ax+bcontainsnorepeatedfactors,orequivalentlyif4a3+27b2isnot0,thentheellipticcurvey2=x3+ax+b

canbeusedtoformagroup.Anellipticcurvegroupoverrealnumbersconsistsofthepointsonthecorrespondingellipticcurve,togetherwithaspecialpointOcalledthepointatinfinity.

P+Q=Ristheadditivepropertydefinedgeometrically.

Ellipticcurvegroupsareadditivegroups;

thatis,theirbasicfunctionisaddition.Theadditionoftwopointsinanellipticcurveisdefinedgeometrically.

ThenegativeofapointP=（xP,yP）isitsreflectioninthex-axis:

thepoint-Pis（xP,-yP）.NoticethatforeachpointPonanellipticcurve,thepoint-Pisalsoonthecurve.

2.1.1

AddingdistinctpointsPandQ

SupposethatPandQaretwodistinctpointsonanellipticcurve,andthePisnot-Q.ToaddthepointsPandQ,alineisdrawnthroughthetwopoints.Thislinewillintersecttheellipticcurveinexactlyonemorepoint,call-R.Thepoint-Risreflectedinthex-axistothepointR.ThelawforadditioninanellipticcurvegroupisP+Q=R.Forexample:

ThelinethroughPand-Pisaverticallinewhichdoesnotintersecttheellipticcurveatathirdpoint;

thusthepointsPand-Pcannotbeaddedaspreviously.ItisforthisreasonthattheellipticcurvegroupincludesthepointatinfinityO.Bydefinition,P+（-P）=O.Asaresultofthisequation,P+O=Pintheellipticcurvegroup.Oiscalledtheadditiveidentityoftheellipticcurvegroup;

allellipticcurveshaveanadditiveidentity.

ToaddapointPtoitself,atangentlinetothecurveisdrawnatthepointP.IfyPisnot0,thenthetangentlineintersectstheellipticcurveatexactlyoneotherpoint,-R.-Risreflectedinthex-axistoR.ThisoperationiscalleddoublingthepointP;

thelawfordoublingapointonanellipticcurvegroupisdefinedby:

P+P=2P=R.

ThetangentfromPisalwaysverticalifyP=0.

2.1.4DoublingthepointPifyP=0

IfapointPissuchthatyP=0,thenthetangentlinetotheellipticcurveatPisverticalanddoesnotintersecttheellipticcurveatanyotherpoint.

Bydefinition,2P=OforsuchapointP.

Ifonewantedtofind3Pinthissituation,onecanadd2P+P.ThisbecomesP+O=PThus3P=P.

3P=P,4P=O,5P=P,6P=O,7P=P,etc.

Althoughthepreviousgeometricdescriptionsofellipticcurvesprovidesanexcellentmethodofillustratingellipticcurvearithmetic,itisnotapracticalwaytoimplementarithmeticcomputations.Algebraicformulaeareconstructedtoefficientlycomputethegeometricarithmetic.

WhenP=（xP,yP）andQ=（xQ,yQ）arenotnegativeofeachother,

P+Q=Rwhere

s=（yP-yQ）/（xP-xQ）

xR=s2-xP-xQandyR=-yP+s（xP-xR）

NotethatsistheslopeofthelinethroughPandQ.

2.2.2DoublingthepointP

WhenyPisnot0,

2P=Rwhere

s=（3xP2+a）/（2yP）

xR=s2-2xPandyR=-yP+s（xP-xR）

RecallthataisoneoftheparameterschosenwiththeellipticcurveandthatsisthetangentonthepointP.

AnEllipticCurveModeloverRealNumbers

Thefollowingmodelcanbeusedtoexperimentwithadditioninavarietyofellipticcurvegroups.

GeometricEllipticCurveModel.（Ajavascriptappletthatopensinaseparatewindow）

Trythefollowingexperiments:

1.Changethevariablesaandbtoseetheresultingshapeandtheellipticcurve.

2.SelectapointPonthecurve,andthenselectapointQonthecurve.Addthemtogether.

3.SelectapointPonthecurveandthendoubleit.

4.Tryselectinga=-3andb=2

2.4QUIZ1

EllipticCurveGroupsoverrealnumbers

1.Doestheellipticcurveequationy2=x3-7x-6overrealnumbersdefineagroup?

2.Whatistheadditiveidentityofregularintegers?

3.Is（4,7）apointontheellipticcurvey2=x3-5x+5overrealnumbers?

4.Whatarethenegativesofthefollowingellipticcurvepointsoverrealnumbers?

P（-4,-6）,Q（17,0）,R（3,9）,S（0,-4）

5.Intheellipticcurvegroupdefinedbyy2=x3-17x+16overrealnumbers,whatisP+QifP=（0,-4）andQ=（1,0）?

6.Intheellipticcurvegroupdefinedbyy2=x3-17x+16overrealnumbers,whatis2PifP=（4,3.464）?

（解见后）Clickhereforsolutions

Anessentialpropertyforcryptographyisthatagrouphasafinitenumberofpoints.

3.0EllipticCurveGroupsoverFp

Calculationsovertherealnumbersareslowandinaccurateduetoround-offerror.Cryptographicapplicationsrequirefastandprecisearithmetic;

thusellipticcurvegroupsoverthefinitefieldsofFpandF2mareusedinpractice.

RecallthatthefieldFpusesthenumbersfrom0top-1,andcomputationsendbytakingtheremainderondivisionbyp.Forexample,inF23thefieldiscomposedofintegersfrom0to22,andanyoperationwithinthisfieldwillresultinanintegeralsobetween0and22.

AnellipticcurvewiththeunderlyingfieldofFpcanformedbychoosingthevariablesaandbwithinthefieldofFp.Theellipticcurveincludesallpoints（x,y）whichsatisfytheellipticcurveequationmodulop（wherexandyarenumbersinFp）.

Forexample:

y2modp=x3+ax+bmodphasanunderlyingfieldofFpifaandbareinFp.

Ifx3+ax+bcontainsnorepeatingfactors（or,equivalently,if4a3+27b2modpisnot0）,thentheellipticcurvecanbeusedtoformagroup.AnellipticcurvegroupoverFpconsistsofthepointsonthecorrespondingellipticcurve,togetherwithaspecialpointOcalledthepointatinfinity.Therearefinitelymanypointsonsuchanellipticcurve.

NotetheseeminglyrandomspreadofpointsfortheellipticcurveoverFp.

3.1ExampleofanEllipticCurveGroupoverFp

Asaverysmallexample,consideranellipticcurveoverthefieldF23.Witha=1andb=0,theelli