Ӧо
APPLICATION RESEARCH OF COMPUTERS
2000Vol.17No.5P.1-3



PԿ󼰽Catch22ķ
顡ҵ塡
ժ  Ҫ  ԱͨдڵCatch22⣬PԿԿصǿȣһCatch22뷽
ؼ  PԿ    Catch22   ֵ乥
1  
иԿ㰲ȫҪ£ͻƼӽܵĶʽȡԼ㸴ӶػԼ[1,6]P3-4ԿǶ׶ຯ䡢չʽȺ򣬸һmn(m<<n)ĲⷽѶȹ͹Կϵͳ[23]ҪоӦPԿҪͨŵCatch22뷽ΪĻỰԿȫ估Կַȶ෽ṩɿİȫ֤ɵຯ䷢չҪչ
2 Catch22
ȫѧо׷Ŀ꣬ڱͨһֱCatch22[]ͨ˫AliceBobڽб֮ͨǰҪԿԿͨеİȫԲܵõ֤˵øȷһЩAliceBabԿͨĳȫŵãû㹻֤ܹ˵õԿǰȫģûг˵Կδ⵽EveĽػκεԿƶ޷˷Catch 22⡣
ִѧĹԿһ̶ƹCatch 22⣬һЩȱ[5]ƵİȫӦѧѽԡڹԿ߲ͨҪȫŵ˵ɹԿԿڼǲܵģԿCatch22ƺõ˽
ȻԿƴڼȫأٹԿƼǰȫģܽػYȻùԿEk μÿһģֱҵһY=Ek(x)xΪֹˣԿԶṩİȫԣϹԿûнCatch 22⡣ڹԿԽԽܵٷչѧͼвرչӼ㼼ӼΪʵʱԿ뽫ױ롣ڹԿƵʵӦУͨߵԿԿĹAliceBobб֮ͨǰȻҪͬıͨšԭ򣬹ԿƲܳ׽Catch 22[]
ԿձڵԺCatch22ڣָRSAɢȹԿƵĶʽϸ̨ܵƣչһ޶ʽܴﵽԿȴڴΧ(һһ)ԴΣ(1997DESһ)һձӦõĹԿ޷ìܡǹԿƼԿEk ԿEm һַѧṹϵĻЧϢmEk ܻϢֵmضEm һֵĽֵϢEk Ӧϵͨ׵˵ԡ֮ ֮CΪ˹AԿƣȷ˲Ek ֵܴһơֵ䡱ṹݿ⡣ֻҪAֵӦݿ(ֵ乥)ּ򵥶ЧĹڵӽӦġԿġԳƿ£Ǻ׳ɹġ
3 ݴж
1. 蹫Կf(EkEm)һһܵġ=Ek(mj)(R)ΪһԭֵEm(Yij)=mjΪһԭ⡣
2. fУ=Ek(mj)+mj(R)ΪһݴֵEm(Yij)=m*jΪһݴ⡣
3. fУABͨŵĵt ...... vغϵֵYt1=Etk(m1 ) ......Yv1=(m1)12......, nغϵֵX11=(m1)+m1X21=E2k(m1)+m2......Xn1=E2k(m1)+mnEm(Yt1)=m1Em(Yv1)=m1Em(X11)=m*1Em(X21)=m*2......Em(Xn1)=m*n(m*1......m*n)д󲿷ַ⡣УΨһݡm1m2......mnжϣ...... m1ĴСϵ֮ΪfݴжϹܣΪݴжϹ(ABͨţAݴжϷȷm*jmjСϵУBܻͬһm*jmjСϵ)
4. ݶ31nغϼݴm*jmjСϵУ涨Ϣʽm*j<mj=>0m*j>mj=>11nغϢa=(a1a2......an)a߼任ΪϢУa1a1+a2=a*2......a*n-1an=a*n=>(a1a*2......a*n)
1.  CEkļӣEkԿ34ݴϷͨŷʽǰȫͨŷʽ
֤ABͨŹдо޴ĹCݶ3fһһƣC޷ӹ̶Ϣmjù̶ֵyjһֵ乥ʧЧCüдmjùmjһһֵ(Y1Y2......Yk)ΪABö23ʽͨţɼ֪EkŵC̶ȣCAϵݴֵX11X21......Xn1޷üֵ(Y1......Yk)ȥ²m1m2......mnšΪвEim(mj)һġmjܴYjEkm(mj)һġmjСYjҲв(mj)һġmjܵYjСYjmjޱѧӦCڶֵ乥ʧܡCѡݴʽmjȫ3̵ݴֵȫͬŻһݴ롣Ԫغ͡mjѡͬǼСġ⣬ݶ4߼任ΣżȡһajҲһδ֪aj߼任вֵCa1ajȫ¶ԡCֵ乥ʧܡ
C(a1a2......an)=(a1a*2......a*n)CAB֮ͨ滻Ƿ޸ġȹ⡣AB֮ͨŷʽǰȫͨŷʽ֤ϡ
2.  134ͨŷһCatch22Կ䷽
֤ͨ3֤(a)1֤(b)ABCͨߣǹߣͬ(c)֮ͨ䲻κͨЭ顣
4  PԿ
4.1  ģ
5.  ģF=A.WjmodmjmjģֵWjΪ˷ӡ(mjWjZ)mjWjѡ(mj>Wj )FΪģ
3.  mj<wjģfǲ溯
֤Wj<mj֪FһWjԪ,ǿ溯Wj>mjʱWj=(kj.mj)+Wjģmjʱ(Kj.mj)ⲿֱָܻWjԪWj>mjʱFǲ溯
֪ģ任Կֵи߶ȵɢԣձƹRSAͶԿڡģݡʽPԿڡģӡʽʵǰҲǡģӡʽֻߴģɢԼֽȡѶȡֽ⡰ģӡNPȫԣģ㲻漰ֺ򸴺ϺȡѶȡ
4.2  P
6.  뺯ԿܹĴṹռһԿռ䡣
7.  һԿռ,뺯ܹͬ뺯϶ɵµĴṹ㣬ЩɵµռΪԿռ䣺

иֹԿձֻܹһԿռ䣬δйԿռоݱPѧģΪmn(m<<n)nš

вкʹкԪ2ַʽ(ͼ12)

ͼ1йԪضԿռʾ

ͼ2йԪضԿռʾ
ͼ1Կռb01,b11,......,bn1Ϊϵ㡣ͼ2Կռеĵ㶼Ϊϵ㡣
TnԿP(Ek)=d2ndΪԪxȡֵޣnʾάTnԿǿq(Ev)=emjeΪfj(x)ĲȡֵޣmΪԿռṹjǲͬг312ܾӦ֮һݴ빹һʵ 
P(Ek)=1095q(Ev)=1088
10 DIM D(13)
20 FOR I=1 TO 12
30 RANDOM
40 D(I)=RND9999*(-1)RND2
50 NEXT I
60 INPUT X,Y
70 A=168*X+60*D(1)+1076*D(2)+2033*D(3)-1181*D(4)-458*D(5)-2601*D(6)+1451*D(7)-108*D(8)+3524*D(9)-1147*D(10)+2737*D(11)-2769*D(12)
80 B=2*X+8*D(1)+78*D(2)+123*D(3)+9*D(4)+26*D(5)+12*D(6)+37*D(7)+75*D(8)+67*D(9)+18*D(10)+ 110*D(11)+79*D(12)
90 C=3*X+12*D(1)-374*D(2)-926*D(3)+1262*D(4)+692*D(5)+2709*D(6)-1118*D(7)+783*D(8)-2921*D(9) +1309*D(10)-1747*D(11)+3480*D(12)
100 PRINT A;B;C
110 D(13)=RND9999:AI=A+RND9*D(13)*Y:BI=B+RDN5*D(13)*Y:CI=(-1)*RND7*D(13)*Y+C
120 PRINTAI;AI;,;BI;BI;,;CI;CI
130 END
⡢ݴֵݴ£

4.3 ȫԷ
⣺EKӵĶԿռ乹Ųĸǿܹмܺ͵
֤a.İȫ ȣABCһά޶ⷽ飬ý̷ⷽ롣δӶ3֪ģfj(x)ӵĲԪW-jǲɽġͼ12˵ӵĲӼNPȫṹһֽӼ͵Ĳfj(x)нṹǲܵġ⸴ϺаԾL(x)L(x)Ծȱ任һֽ빹ѶȣɼER췽ʽǰȫġ
b. Ek뷽ʽ ABCĸԲӼ,һڲԪһη顣 γȫfj(x)ֵֵͬY1(ģmj)ɣ֤ȫfj(x)Чԡÿfj(x)ڴṹL(x)ÿһṹɾȱ任ã֤˸ϺĸѶȸԡEk뷽ʽýɴԪһηֱ̣ȥɸȱ任,ɸֵļȥ任,ɸģ任ԪڲϢֵ,Щǲлɲδ,ٶǷǳġ
c. ԿǿȹмԴܺȨԱȿP(Ek)q(Ev)nţTnǿɱģEv㿪޹ء쳬мԴܺnԪأ͸ѧEvǼ򵥳ˡӷɵĲкɴδкem.j֪,ֵСṹ,ɻÿEvǿȵļμָǿE*㿪ֻǺСӡйԿûE*ȨԱȣ߼ǾԱȣԿǿʹ֮ʧȥ롰Դ
5 
Catch22ǵǰѧһҪ⣬⣬ϢȫͨһҪڡϸPĹָۡ꼰Catch22ⷽЩӲʵ֡ӦP󻹿Թɴ֤Ӧüֵʮش
ĿȻѧ(9811028)
(ؿƼ   545900)
ҵ(   530022)
(ũҵѧԺ   530007)
ο
1滪. ӼʽƵĹ. ѧ½չ, :ѧ, 1994: 715
2, . PԿԭͼSHORT VECTOR㷨о. ѧѧ(Ȼѧ), 1996, 21(3): 224229
3, ҵ. P3-4͹Կݼܱ׼. ͨű, 1997, 71(3):1520
4 , ÷. Catch 22⼰. ͨű, 1999, 78(2):13
5 Differ W., Hellman M E. New Directions in Cryptography. IEEE Trans Inform Theory, 1976, 22: 644654
6 Chor B., and Rivest R. A Knapsack-Type Public Key Cryptosystem Based on Arithmetic in Finite Fields. IEEE Trans Inform Theory, 1988, Vol.1 T-34, (5): 901909
ոڣ1999-11-3
