accidental海贼王644

海贼王644  时间:2021-01-20  阅读:()
Op.
52ConstructingDigitalSignaturesfromaOneWayFunctionLeslieLamportComputerScienceLaboratorySRIInternational18October1979CSL-98333RavenswoodAve.
MenloPark,California94025(415)326-6200Cable:SRIINTLMPKTWX:910-373-124611.
IntroductionAdigitalsignaturecreatedbyasenderPforadocumentmisadataitemOp(m)havingthepropertythatuponreceivingmandap(m),onecandetermine(andifnecessaryproveinacourtoflaw)thatPgeneratedthedocumentm.
Aonewayfunctionisafunctionthatiseasytocompute,butwhoseinverseisdifficulttocompute[1].
Morepreciselyaonewayfunctionisafunctionfromasetofdataobjectstoasetofvalueshavingthefollowingtwoproperties:1.
Givenanyvaluev,itiscomputationallyinfeasibletofindadataobjectdsuchthat(d)=v.
2.
Givenanydataobjectd,itiscomputationallyinfeasibletofindadifferentdataobjectdfsuchthat(d!
d)Ifthesetofdataobjectsislargerthanthesetofvalues,thensuchafunctionissometimescalledaonewayhashingfunction.
Wewilldescribeamethodforconstructingdigitalsignaturesfromsuchaonewayfunction.
OurmethodisanimprovementofamethoddevisedbyRabin[2].
LikeRabin's,itrequiresthesenderPtodepositapieceofdataocinsometrustedpublicrepositoryforeachdocumenthewishestosign.
Thisrepositorymusthavethefollowingproperties:-otcanbereadbyanyonewhowantstoverifyPfssignature.
-ItcanbeproveninacourtoflawthatPwasthecreaterofoc.
Onceochasbeenplacedintherepository,Pcanuseittogenerateasignatureforanysingledocumenthewishestosend.
Rabin'smethodhasthefollowingdrawbacksnotpresentinours.
1.
ThedocumentmmustbesenttoasinglerecipientQ,whothenrequestsadditionalinformationfromPtovalidatethesignature.
Pcannotdivulgeanyadditionalvalidatinginformationwithoutcompromisinginformationthatmustremainprivatetopreventsomeoneelsefromgeneratinganewdocumentmfwithavalidsignatureap(mf).
2.
Foracourtoflawtodetermineifthesignatureisvalid,itisnecessaryforPtogivethecourtadditionalprivateinformation.
Thishasthefollowingimplications.
.
P—oratrustedrepresentativeofP—mustbeavailabletothecourt,-Pmustmaintainprivateinformationwhoseaccidentaldisclosurewouldenablesomeoneelsetoforgehissignatureonadocument.
Withourmethod,Pgeneratesasignaturethatisverifiablebyanyone,withnofurtheractiononPfspart.
Aftergeneratingthesignature,Pcandestroytheprivateinformationthatwouldenablesomeoneelsetoforgehissignature.
TheadvantagesofourmethodoverRabin'sareillustratedbythefollowingconsiderationswhenthesigneddocumentmisacheckfromPpayabletoQ.
1.
ItiseasyforQtoendorsethecheckpayabletoathirdpartyRbysendinghimthesignedmessage"makempayabletoRlf.
However,withRabin'sscheme,RcannotdetermineifthecheckmwasreallysignedbyP,sohemustworryaboutforgerybyQaswellaswhetherornotPcancoverthecheck.
Withourmethod,thereisnowayforQtoforgethecheck,sotheendorsedcheckisasgoodasacheckpayabledirectlytoRsignedbyP.
(However,someadditionalmechanismmustbeintroducedtoprevent0fromcashingtheoriginalcheckafterhehassigneditovertoR.
)2.
IfPdieswithoutleavingtheexecutorsofhisestatetheinformationheusedtogeneratehissignatures,thenRabin'smethodcannotpreventQfromundetectablyalteringthecheckm—forexample,bychangingtheamountofmoneypayable.
Suchposthumousforgeryisimpossiblewithourmethod.
3.
WithRabin'smethod,tobeabletosuccessfullychallengeanyattemptbyQtomodifythecheckbeforecashingit,Pmustmaintaintheprivateinformationheusedtogeneratehissignature.
Ifanyone(notjustQ)stolethatinformation,thatpersoncouldforgeacheckfromPpayabletohim.
OurmethodallowsPtodestroythisprivateinformationaftersigningthecheck.
2.
TheAlgorithmWeassumeasetMofpossibledocuments,asetICofpossiblekeys,1TheelementsofKarenotkeysintheusualcryptographicsense,butarearbitrarydataitems.
WecallthemkeysbecausetheyplaythesameroleasthekeysinRabin'salgorithm.
andasetV^ofpossiblevalues.
Let2denotethesetofallsubsetsof{1,.
.
.
,40}containingexactly20elements.
(Thenumbers40and20arearbitrary,andcouldbereplacedby2nandn.
WeareusingthesenumbersbecausetheywereusedbyRabin,andwewishtomakeiteasyforthereadertocompareourmethodwithhis.
)Weassumethefollowingtwofunctions.
1.
AfunctionF:IC->V_withthefollowingtwoproperties:a.
GivenanyvaluevinVfitiscomputationallyinfeasibletofindakeykinKsuchthatF(k)=v.
b.
Foranysmallsetofvaluesv1f.
.
.
,vffl,itiseasytofindakeyksuchthatF(k)isnotequaltoanyofthevi2.
AfunctionG:M^->2withthepropertythatgivenanydocumentminM,itiscomputationallyinfeasibletofindadocumentm1imsuchthatG(mf)=G(m).
ForthefunctionF,wecanuseanyonewayfunctionwhosedomainisthesetofkeys.
ThesecondpropertyofFfollowseasilyfromthesecondpropertyoftheonewayfunction.
WewilldiscusslaterhowthefunctionGcanbeconstructedfromanordinaryonewayfunction.
Forconvenience,weassumethatPwantstogenerateonlyasinglesigneddocument.
Later,weindicatehowhecansignmanydifferentdocuments.
ThesenderPfirstchooses40keysk^suchthatallthevaluesFCk.
^)aredistinct.
(OursecondassumptionaboutFmakesthiseasytodo.
)Heputsinapublicrepositorythedataitemat=(F(k.
F(kjj0)).
NotethatPdoesnotdivulgethekeys^,whichbyourfirstassumptionaboutFcannotbecomputedfroma.
Togenerateasignatureforadocumentra,PfirstcomputesG(m)toobtainasetli-j,.
.
.
,i2o^°^integers.
Thesignatureconsistsofthe20keysk,L.
Moreprecisely,wehaveap(m)=(k_.
k_.
),i1i2Qri1i20wherethei-aredefinedbythefollowingtworequirements:(i)G(m)=Ult.
.
.
,i20}.
(ii)i1computationallyinfeasible.
)Suchfunctionsaredescribedin[1]and[2].
TheobviouswaytoconstructtherequiredfunctionGistolet$besuchaonewayfunction,anddefineG(m)toequalR((m)),whereR:{0,.
.
.
,2n-1}-2.
ItiseasytoconstructafunctionRhavingtherequiredrangeanddomain.
Forexample,onecancomputeR(s)inductivelyasfollows:1.
Dividesby40toobtainaquotientqandaremainderr2.
Usertochooseanelementxfrom{1,.
.
.
,40}.
(Thisiseasytodo,since0rjtobesurethattheresultingfunctionGhastherequiredproperty.
Wesuspectthatformostonewayfunctions,thismethodwouldwork.
However,wecannotprovethis.
ThereasonconstructingGinthismannermightnotworkisthatthefunctionRfrom{0,.
.
.
,2n}into2isamanytoonemapping,andtheresulting"collapsing11ofthedomainmightdefeattheonewaynatureof.
However,itiseasytoshowthatifthefunctionRisonetoone,thenproperty(ii)ofimpliesthatGhastherequiredproperty.
ToconstructG,weneedonlyfindaneasilycomputableonetoonefunctionRfrom{0,.
.
.
,2n-1}into2,forareasonablylargevalueofn.
WecansimplifyourtaskbyobservingthatthefunctionGneednotbedefinedontheentiresetofdocuments.
Itsufficesthatforanydocumentm,itiseasytomodifyminaharmlesswaytogetanewdocumentthatisinthedomainofG.
Forexample,onemightincludeameaninglessnumberaspartofthedocument,andchoosedifferentvaluesofthatnumberuntilheobtainsadocumentthatisinthedomainofG.
Thisisanacceptableprocedureif(i)itiseasytodeterminewhetheradocumentisinthedomain,and(ii)theexpectednumberofchoicesonemustmakebeforefindingadocumentinthedomainissmall.
Withthisinmind,weletn=MOanddefineR(s)asfollows:ifthebinaryrepresentationofscontainsexactly20ones,thenR(s)={i:theitjibitofsequalsone},otherwiseR(s)isundefined.
Approximately13%ofall40bitnumberscontainexactly20ones.
Hence,iftheonewayfunctionissufficientlyrandomizing,thereisa.
13probabilitythatanygivendocumentwillbeinthedomainofG.
Thismeansthatrandomlychoosingdocuments(ormodificationstoadocument),theexpectednumberofchoicesbeforefindingoneinthedomainofGisapproximately8.
Moreover,after17pchoices,theprobabilityofnothavingfoundadocumentinthedomainofGisabout1/10^.
(Ifweuse60keysinsteadof40,theexpectednumberofchoicestofindadocumentinthedomainbecomesabout10,and22pchoicesareneededtoreducetheprobabilityofnotfindingoneto1/10p.
)Iftheonewayfunctionkiseasytocompute,thenthesenumbersindicatethattheexpectedamountofefforttocomputeGisreasonable.
However,itdoesseemundesirabletohavetotrysomanydocumentsbeforefindingoneinthedomainofG.
WehopethatsomeonecanfindamoreelegantmethodforconstructingthefunctionG,perhapsbyfindingaoneto.
onefunctionRwhichisdefinedonalargersubsetof{0,.
.
.
,2n}.
Note;WehavethusfarinsistedthatG(m)beasubsetof{1,.
.
.
,40}consistingofexactly20elements.
ItisclearthatthegenerationandverificationprocedurecanbeappliedifG(m)isanypropersubset.
AnexaminationofourcorrectnessproofshowsthatifweallowG(m)tohaveanynumberofelementslessthan40,thenourmethodwouldstillhavethesamecorrectnesspropertiesifGsatisfiesthefollowingproperty:-ForanydocumentmfitiscomputationallyinfeasibletofindadifferentdocumentmfsuchthatG(mf)isasubsetofG(m).
BytakingtherangeofGtobethecollectionof20elementsubsets,weinsurethatG(mf)cannotbeapropersubsetofG(m).
However,itmaybepossibletoconstructafunctionGsatisfyingthisrequirementwithoutconstrainingtherangeofGinthisway.
REFERENCES[1]Diffie,W.
andHellman,M.
"NewDirectionsinCryptography".
IEEETrans,^nInformationTheoryIT-22_(November1976),544-654.
[2]Rabin,M.
"DigitalizedSignatures",inFoundationsofSecureComputing,AcademicPress(1978),155-168.

Sharktech:无限流量服务器丹佛,洛杉矶,荷兰$49/月起,1Gbps带宽哦!

鲨鱼机房(Sharktech)我们也叫它SK机房,是一家成立于2003年的老牌国外主机商,提供的产品包括独立服务器租用、VPS主机等,自营机房在美国洛杉矶、丹佛、芝加哥和荷兰阿姆斯特丹等,主打高防产品,独立服务器免费提供60Gbps/48Mpps攻击防御。机房提供1-10Gbps带宽不限流量服务器,最低丹佛/荷兰机房每月49美元起,洛杉矶机房最低59美元/月起。下面列出部分促销机型的配置信息。机房...

CloudCone:洛杉矶MC机房KVM月付1.99美元起,支持支付宝/PayPal

CloudCone是一家成立于2017年的国外VPS主机商,提供独立服务器租用和VPS主机,其中VPS基于KVM架构,多个不同系列,譬如常规VPS、大硬盘VPS等等,数据中心在洛杉矶MC机房。商家2021年Flash Sale活动继续,最低每月1.99美元,支持7天退款到账户,支持使用PayPal或者支付宝付款,先充值后下单的方式。下面列出几款VPS主机配置信息。CPU:1core内存:768MB...

弘速云20.8元/月 ,香港云服务器 2核 1g 10M

弘速云元旦活动本公司所销售的弹性云服务器、虚拟专用服务器(VPS)、虚拟主机等涉及网站接入服务的云产品由具备相关资质的第三方合作服务商提供官方网站:https://www.hosuyun.com公司名:弘速科技有限公司香港沙田直营机房采用CTGNET高速回国线路弹性款8折起优惠码:hosu1-1 测试ip:69.165.77.50​地区CPU内存硬盘带宽价格购买地址香港沙田2-8核1-16G20-...

海贼王644为你推荐
月付百万的女人们既然男人大都觉得下体毛发多的女人比较性感..那为什么那些特殊职业的女人们大多把下体的毛脱掉呢..?唐人社美国10次啦我看到罗显琪第一眼就喜欢他了!当中我们一共见过10次面,也发生过两次关系! 但是他有女朋友对我也只是一时兴起吧,所以第十次见面之后,我们再没有联系,但是现在我大姨妈晚了很多天了,我担心是否怀孕,如果有的话,我又不想打掉,该找他吗?锦天城和君合哪个好和君智业和三人禾哪个公司的营销做的好苹果x和xr哪个好苹果xr好还是苹果x好免费阅读小说app哪个好想看小说有什么好用的app推荐?游戏加速器哪个好网游加速器哪个最好用?宝来和朗逸哪个好新宝来和新朗逸选哪个?好纠结!!电动牙刷哪个好什么品牌的电动牙刷比较好?清理手机垃圾软件哪个好什么手机清理软件最好?qq空间登录登陆进入QQ空间进去了叫登陆登陆了又叫登陆
免费域名空间 哈尔滨域名注册 2019年感恩节 域名商 西安电信测速 hawkhost 光棍节日志 info域名 最好的免费空间 域名转接 免费吧 中国电信宽带测速网 东莞服务器 多线空间 空间登入 starry 永久免费空间 广东主机托管 买空间网 hdroad 更多