http://factordb.com/
涉及3个参数： n e d, 其中 {n, d}为私钥，{n, e}为公钥
phi(n) = (p-1) * (q-1)
d为e膜phi(n)的逆元(phi(n)为n的欧拉函数)
ed ≡ 1 (mod phi(n))
加密解密过程：c密文，m明文
加密：c ≡ m^e(mod n)
解密：m ≡ c^d(mod n)
rsa中e为随机选取的一个数，一般为65537
n由两个大素数(p,q)之积组成，公钥{n,e}为公开的，要破解rsa就得求出d，d为e模phi(n)的逆元，要求出phi(n)，必须分解n求得p,q，从而求得phi(n)=(p-1)*(q-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
import gmpy2
import binascii
n1 = 14967030059975114950295399874185047053736587880127990542035765201425779342430662517765063258784685868107066789475747180244711352646469776732938544641583842313791872986357504462184924075227433498631423289187988351475666785190854210389587594975456064984611990461126684301086241532915267311675164190213474245311019623654865937851653532870965423474555348239858021551589650169602439423841160698793338115204238140085738680883313433574060243600028500600824624358473403059597593891412179399165813622512901263380299561019624741488779367019389775786547292065352885007224239581776975892385364446446185642939137287519945974807727
n2 = 14624662628725820618622370803948630854094687814338334827462870357582795291844925274690253604919535785934208081825425541536057550227048399837243392490762167733083030368221240764693694321150104306044125934201699430146970466657410999261630825931178731857267599750324918610790098952520113593130245010530961350592735239454337631927669542026935873535964487595433984902529960726655481696404006628917922241666148082741874033756970724357470539589848548704573091633917869387239324447730587545472564561496724882799495186768858324490838169123077051890332313671220385830444331578674338014080959653201802476516237464651809255679979
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
#print temp
a = b
b = temp
return a
q = gcd(n1, n2)
p = n1/q
e=65537
phin = (p-1)*(q-1)
d=gmpy2.invert(e,phin)
c=2482083893746618248544426737023750400124543452082436334398504986023501710639402060949106693279462896968839029712099336235976221571564642900240827774719199533124053953157919850838214021934907480633441577316263853011232518392904983028052155862154264401108124968404098823946691811798952747194237290581323868666637357604693015079007555594974245559555518819140844020498487432684946922741232053249894575417796067090655122702306134848220257943297645461477488086804856018323986796999103385565540496534422406390355987976815450744535949785073009043007159496929187184338592859040917546122343981520508220332785862546608841127597
m=pow(c,d,n)
m_hex = hex(m)[2:]
#print("十六进制:\n%s"%(m_hex,))
print("ascii:\n%s"%(binascii.a2b_hex(m_hex).decode("utf8")))
|
