北方工业大学密码学平时作业答案公钥密码作业答案

NCUT密码学–习题与答案2011第7页四、公钥密码(3,4,5,6;10,12;13,18,19,20)3.用Fermat定理求3201mod11。解：对于模运算，有结论(a×b)modn=[(amodn)×(bmodn)]modn由Fermat定理，可知310≡1mod11，因此有(310)k≡1mod11所以3201mod11=[(310)20×3]mod11=[((310)20mod11)×(3mod11)]mod11=3。4.用推广的Euclid算法求67mod119的逆元。解：qguv~11910~67011521-1115-12374-721-916(注：1=119×(-9)+67×16)所以67-1mod119=165.求gcd(4655,12075)。解：12075=2×4655+27654655=1×2765+18902765=1×1890+8751890=2×875+140875=6×140+35140=4×35+0所以gcd(4655,12075)=35。6.求解下列同余方程组2mod31mod51mod7xxx≡⎧⎪≡⎨⎪≡⎩。解：根据中国剩余定理求解该同余方程组，记a1=2,a2=1,a3=1,m1=3,m2=5,m3=7,M=m1×m2×m3=105,M1=M/m1=35,M1-1modm1=35-1mod3=2,M2=M/m2=21,M2-1modm2=21-1mod5=1,M3=M/m3=15,M3-1modm3=15-1mod7=1所以方程组的解为x≡(M1M1-1a1+M2M2-1a2+M3M3-1a3)modM≡(35×2×2+21×1×1+15×1×1)mod105≡176mod105≡71mod10510.设通信双方使用RSA加密体制，接收方的公开钥是(e,n)=(5,35)，接收到的密文是C=10，求明文MFermat定理：若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1modp。若gcd(a,p)=1，则aϕ(p)≡1modp。NCUT密码学–习题与答案2011第8页解：n=35-p=5,q=7ϕ(n)=(p-1)(q-1)=24d≡e-1modϕ(n)≡5-1mod24≡5mod24....(因为5×5≡1mod24)所以，明文M≡Cdmodn≡105mod35≡512.设RSA加密体制的公开钥是(e,n)=(77,221)。(1)用重复平方法加密明文160，得中间结果为：k248163264727677160kmod22118519116351203511821723若敌手得到以上中间结果就很容易分解n，问敌手如何分解n？(2)求解密密钥d。解：(1)由16016≡16064mod221，可知(16064-16016)mod221=0即16016(16048–1)mod221=0，从而有16048=1mod221。由Euler定理及定理4-7，猜测：ordn(160)|48且48|ϕ(n)，即存在整数k满足ϕ(n)=48k由ϕ(n)的定义可知，ϕ(n)比n略小。而当取k=4时，ϕ(n)=192为221且与221最接近，因此猜测ϕ(n)=192。由ϕ(n)=(p-1)(q-1),n=pq，可知p+q=n-ϕ(n)+1=221-192+1=30所以p、q为一元二次方程X2-30X+221=0的两个根，求得为13、17。或：p-q=sqrt((p+q)2-4n),从而p=((p+q)+(p-q))/2,q=((p+q)-(p-q))/2所以，可得n的分解为：n=221=13×17(2)解密密钥d为：d≡e-1modϕ(n)=77-1mod192=5(∵77×5-192×2=1)13.在ElGamal加密体制中，设素数p=71，本原根g=7，(1)如果接收方B的公开钥是yB=3，发送方A选择的随机整数k=2，求明文M=30所对应的密文。(2)如果A选择另一个随机整数k，使得明文M=30加密后的密文是C=(59,C2)，求C2。解：(1)C1≡gkmodp=72mod71=49，C2≡yBkMmodp=(32×30)mod71=57所以密文为C=(C1,C2)=(49,57)。(2)由7kmod71=59，穷举k可得k=3。所以C2=(3k×30)mod71=(33×30)mod71=29。18.椭圆曲线E11(1,6)表示y2≡x3+x+6mod11，求其上的所有点。快速指数算法求模幂105mod35：ammonnm=(bi)25=4+1=(101)2bi=0,d←d*dmodnbi-101bi=1,d←d*d*amodnd110305NCUT密码学–习题与答案2011第9页解：x012345678910x3+x+6mod1168538484974是否为mod11的平方剩余NoNoyesyesNoyesNoyesyesNoyesy4,75,62,92,93,82,9所以，E11(1,6)上点为{O,(2,4),(2,7),(3,5),(3,6),(5,2),(5,9),(7,2),(7,9),(8,3),(8,8),(10,2),(10,9)}19.已知点G=(2,7)在椭圆曲线E11(1,6)上，求2G和3G。解：a=1,b=6,p=11,y2≡x3+x+6mod11∵2G=G+G,λ=(3×22+1)/(2×7)mod11=13/14mod11=2/3mod11=8(∵3-1mod11=4)x3=(82-2-2)mod11=5,y3=[8(2-5)-7]mod11=2∴2G=(5,2)∵3G=2G+G=(5,2)+(2,7),λ=(7−2)/(2−5)mod11=5/(-3)mod11=5/8mod11=5*7mod11=2(∵8*7=1mod11)x3=(22-5-2)mod11=(-3)mod11=8y3=[2(5-8)-2]mod11=(-8)mod11=3∴3G=(8,3)20.利用椭圆曲线实现ElGamal密码体制，设椭圆曲线是E11(1,6)，生成元G=(2,7)，接收方A的秘密钥nA=7。(1)求A的公开钥PA。(2)发送方B欲发送消息Pm=(10,9)，选择随机数k=3，求密文Cm。(3)显示接收方A从密文Cm恢复消息Pm的过程。解：(1)A的公开钥PA=nAG=7G=(7,2)(2)C1=kG=3G=(8,3)C2=Pm+kPA=(10,9)+3(7,2)=(10,9)+(3,5)=(10,2)所以密文Cm={C1,C2}={(8,3),(10,2)}(3)解密过程为C2-nAC1=(Pm+kPA)–nA(kG)=(10,2)–7(8,3)=(10,9)=Pmx2≡cmodp要确定c是否是一个模p的平方剩余，可以用Euler准则来判断，即如果p是一个奇素数，则c是模p的平方剩余当且仅当c(p-1)/2≡1modp.当p≡3mod4时，如果c是一个模p的平方剩余，则±c(p+1)/2modp，即c(p+1)/2和p-c(p+1)/2，就是c的两个模p的平方根。