作业三rsa计算.doc

Rsa计算P=2357，q=2551，e=3674911，求d，若加密的明文为m=5234673求相应的密文。解：N=p*q=6012707(n)=(p-1)(q-1)=2356*2550=6007800（1）求e的乘法逆元素：6007800=3674911+23328893674911=2332889+13420222332889=1342022+9908671342022=990867+351155990867=2*351155+288557351155=288557+62598288557=4*62598+3816562598=38165+2443338165=24433+1373224433=13732+1070113732=10701+303110701=3*3031+16083031=1608+14231608=1423+1851423=7*185+128185=128+57128=2*57+1457=4*14+114=1*14于是，1=57-4*141=57-4*(128-57*2)1=57*9-4*1281=(185-128)*9-4*1281=185*9-13*1281=185*9-13*(1423-185)*71=185*100-13*14231=(1608-1423)*100-13*14231=1608*100-1423*1131=1608*100-(3031-1608)*1131=1608*213-3031*1131=(10701-3031)*213-3031*1131=10701*213-(13732-10701)*7521=10701*965-13732*7521=(24433-13732)*965-13732*7521=24433*965-1717*137321=24433*965-1717*(38165-24433)1=2682*24433-1717*381651=(62598-38165)*2682-1717*381651=2682*62598-4399*381651=2682*62598-4399*(288557-62598*4)1=20278*62598-4399*2885571=(351155-288557)*20278-288557*43991=351155*20278-288557*246671=351155*20278-（990867-351155*2）*246671=351155*69632-990867*246771=(1342022-990867)*69632-990867*246771=1342022*69632-990867*943091=1342022*69632-(2332889-1342022)*943091=1342022*163941-2332889*943091=163941*(3674911-2332889)-2332889*943091=3674911*163941-2332889*2582501=3674911*163941-(6007800-3674911)*2582501=3674911*422191-6007800*258250故d=422191（2）求密文M=me mod 6012707=52346733674911 mod 6012707由于这个运算过程很复杂，要用到大量的模幂运算，而且计算过程的中间结果非常大，我就自己编写了一段程序：E=3674911=1110000001001100011111=52346731 mod 6012707=52346735234673(21) mod 6012707=1615224 46750405234673(22) mod 6012707=4939341 19090575234673(23) mod 6012707=1743565 25254895234673(24) mod 6012707=262732 5076705234673(25) mod 6012707=22274645234673(26) mod 6012707=2455015234673(27) mod 6012707=53787405234673(28) mod 6012707=770381 27954555234673(29) mod 6012707=2640726 18335645234673(210) mod 6012707=44572025234673(211) mod 6012707=43430345234673(212) mod 6012707=4300965 24565635234673(213) mod 6012707=24136875234673(214) mod 6012707=47658735234673(215) mod 6012707=36159995234673(215) mod 6012707=56810565234673(216) mod 6012707=19366505234673(217) mod 6012707=8373335234673(218) mod 6012707=28277405234673(219) mod 60