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.

PQ.hosting:香港HE/乌克兰/俄罗斯/荷兰/摩尔多瓦/德国/斯洛伐克/捷克vps,2核/2GB内存/30GB NVMe空间,€3/月

PQ.hosting怎么样?PQ.hosting是一家俄罗斯商家,正规公司,主要提供KVM VPS和独立服务器,VPS数据中心有香港HE、俄罗斯莫斯科DataPro、乌克兰VOLIA、拉脱维亚、荷兰Serverius、摩尔多瓦Alexhost、德国等。部分配置有变化,同时开通Paypal付款。香港、乌克兰、德国、斯洛伐克、捷克等为NVMe硬盘。香港为HE线路,三网绕美(不太建议香港)。免费支持wi...

spinservers($89/月),圣何塞10Gbps带宽服务器,达拉斯10Gbps服务器

spinservers是Majestic Hosting Solutions LLC旗下站点,主要提供国外服务器租用和Hybrid Dedicated等产品的商家,数据中心包括美国达拉斯和圣何塞机房,机器一般10Gbps端口带宽,高配置硬件,支持使用PayPal、信用卡、支付宝或者微信等付款方式。目前,商家针对部分服务器提供优惠码,优惠后达拉斯机房服务器最低每月89美元起,圣何塞机房服务器最低每月...

hostodo:美国大流量VPS,低至$3,8T流量/月-1.5G内存/1核/25gNVMe/拉斯维加斯+迈阿密

hostodo从2014年年底运作至今一直都是走低价促销侧率运作VPS,在市场上一直都是那种不温不火的品牌知名度,好在坚持了7年都还运作得好好的,站长觉得hostodo还是值得大家在买VPS的时候作为一个候选考虑项的。当前,hostodo有拉斯维加斯和迈阿密两个数据中心的VPS在促销,专门列出了2款VPS给8T流量/月,基于KVM虚拟+NVMe整列,年付送DirectAdmin授权(发ticket...

海贼王644为你推荐
集成显卡和独立显卡哪个好独立显卡和集成显卡区别??传奇类手游哪个好传奇手游版哪个好玩人多?浏览器哪个好用哪款浏览器好用三国游戏哪个好玩三国系列的游戏哪个好玩?网页传奇哪个好玩有什么好玩的传奇类网页游戏?海克斯皮肤哪个好LOL用100块是抽海克斯好还是抽蛮王的生化领主的活动还是直接买皮肤好红茶和绿茶哪个好红茶和绿茶,哪个好?雅思和托福哪个好考托福好考还是雅思好考哇?电动牙刷哪个好电动牙刷哪个牌子比较好,不要那么贵的网络机顶盒哪个好什么牌子的网络机顶盒最好
虚拟主机申请 in域名注册 电信服务器租赁 域名停靠一青草视频 注册cn域名 美国主机评测 国外主机 site5 息壤备案 rackspace bash漏洞 godaddy支付宝 监控宝 ev证书 新站长网 促正网秒杀 毫秒英文 炎黄盛世 怎样建立邮箱 河南m值兑换 更多