RSA算法

RSA算法是一种非对称算法，即使用不同的公钥与私钥对内容加解密，在CTF crypto题目中常常出现。RSA的安全性依赖于由2个大质数相乘得到n很容易但由一个大数n拆分出2个质数非常难，RSA算法中参数有p，q，e，n，φ，d，c，m。

p：一个大质数

q：另一个大质数

n：模数为p*q

φ：为(p−1) * (q−1) 即N的欧拉函数

e：选择一个e (1<e<φ)，且e和φ互质

d：e的模反数为d，计算方法: e * d ≡ 1 (mod φ)

c：c = pow(m, e, n)，得到的c即为密文，一般称(n，e)为公钥

m：m = pow(c, d, n)，得到的m即为明文，一般称(n，d)为私钥

总的来说就是明文m的e次方对n求余的结果为密文c，而密文c的d次方对n求余的结果又回到了明文m。

来看一个最简单的rsa题目

p =  9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q =  11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e =  65537
c =  83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034

题目给了p，q，e，c所以只需将d求出即可通过m = pow(c, d, n)解出明文

p =  9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q =  11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e =  65537
c =  83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
n = p*q
fn = (p-1)*(q-1)
i = 1
while 1:
    x = (i*fn)+1
    if(x%e==0):
        d = x//e
        print('d:',d)
        break
    else:
        i+=1
print('m:',pow(c,d,n))

d: 56632047571190660567520341028861194862411428416862507034762587229995138605649836960220619903456392752115943299335385163216233744624623848874235303309636393446736347238627793022725260986466957974753004129210680401432377444984195145009801967391196615524488853620232925992387563270746297909112117451398527453977
m: 5577446633554466577768879988        //运行结果

而真正在CTF比赛中往往会给你n，而不直接给出p，q让你解出d，这个时候就要思考解决方法啦。