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.

RAKSmart VPS主机半价活动 支持Windows系统 包含香港、日本机房

RAKSmart 商家最近动作还是比较大的,比如他们也在增加云服务器产品,目前已经包含美国圣何塞和洛杉矶机房,以及这个月有新增的中国香港机房,根据大趋势云服务器算是比较技术流的趋势。传统的VPS主机架构方案在技术层面上稍微落后一些,当然也是可以用的。不清楚是商家出于对于传统VPS主机清理库存,还是多渠道的产品化营销,看到RAKSmart VPS主机提供美国、香港和日本机房的半价促销,当然也包括其他...

台湾CN2云服务器 2核2G 5M 5IP 台湾物理服务器 E5x2 64G 20M 5IP

提速啦(www.tisula.com)是赣州王成璟网络科技有限公司旗下云服务器品牌,目前拥有在籍员工40人左右,社保在籍员工30人+,是正规的国内拥有IDC ICP ISP CDN 云牌照资质商家,2018-2021年连续4年获得CTG机房顶级金牌代理商荣誉 2021年赣州市于都县创业大赛三等奖,2020年于都电子商务示范企业,2021年于都县电子商务融合推广大使。资源优势介绍:Ceranetwo...

cera:秋季美国便宜VPS促销,低至24/月起,多款VPS配置,自带免费Windows

介绍:819云怎么样?819云创办于2019,由一家从2017年开始从业的idc行业商家创办,主要从事云服务器,和物理机器819云—-带来了9月最新的秋季便宜vps促销活动,一共4款便宜vps,从2~32G内存,支持Windows系统,…高速建站的美国vps位于洛杉矶cera机房,服务器接入1Gbps带宽,采用魔方管理系统,适合新手玩耍!官方网站:https://www.8...

海贼王644为你推荐
免费个人网站制作怎样制作个人网站啊?要免费的!聚酯纤维和棉哪个好聚酯纤维和棉 那个比较暖和啊音乐播放器哪个好音乐播放器哪个最好用网校哪个好初中网校哪个好?云盘哪个好免费的网盘哪个好用啊?视频软件哪个好什么看视频的软件好willyunlee电影拳皇演的是什么意思360云盘企业版360企业云盘出了吗?求推荐好用的企业云盘。360云安全中心360云安全中心连接不到哪里买机票最便宜在哪个网站买机票最便宜
北京租服务器 上海vps plesk 美国主机评论 国外idc l5520 iisphpmysql shopex空间 html空间 灵动鬼影 dd444 阿里云浏览器 空间合租 789电视剧 shopex主机 中国电信宽带测速器 drupal安装 yundun 免费外链相册 卡巴斯基官网下载 更多