简谈RSA加密 | LSABLOG

首页 » NetworkSec » AWD » 正文

简谈RSA加密

0x00 概述

公钥加密算法,非对称加密,一般用公钥加密,私钥解密,密钥越长越难被破解,基于分解大素数这个数学难题,关键参数n(p*q),p,q,L,e,d。公钥(e,n),私钥(d,n)。密钥对(n,d,e)。密文c = 明文m的e次方 mod n,明文m = 密文c的d次方 mod n。

图1:rsa加密脑图(来源:www.freebuf.com/column/148185.html)

 

0x01 简谈原理

如何生成密钥对?

选取两个大质数p,q。

n = p * q。

L = (p-1)*(q-1)。

选取e,要求与L互质且1<e<n。

d * e = 1 (mod L * i),i = 1,2,3,4…。

或d * e = L * i + 1,i=1,2,3,4…。

即已知e,对ex + Ly = 1求解

或用python的gmpy2库的invert函数解释

invert(x, m) returns y such that x * y == 1 modulo m, or 0 if no such y exists.

传入e和L即可返回d

 

如何加解密?

公钥加密:c = m的e次方 mod n

私钥解密:m = c的d次方mod n

用python的pow(c,d,n)即可解出明文。

 

0x02 ctf中的rsa题

用实验吧的3道ctf题来巩固下rsa加密算法。

1. 已知p,q,e求d

www.shiyanbar.com/ctf/1828

直接上脚本:

#coding:utf-8

import gmpy2

p,q,e = gmpy2.mpz(473398607161),gmpy2.mpz(4511491),gmpy2.mpz(17)

L = (p - 1) * (q - 1)

d = gmpy2.invert(e,L)

print d

结果:125631357777427553

 

2.已知p,q,e,c,求m

www.shiyanbar.com/ctf/1979

思路:先求出d,再求n,最后pow(c,d,n)即可。

上脚本:

#coding:utf-8

import gmpy2

p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483L

q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407L

e = 65537L

c= 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034L

L = (p - 1) * (q - 1)

d = long(gmpy2.invert(e, L))

n = p * q

print pow(c, d, n)

结果:5577446633554466577768879988

 

3. 已知公钥和c,求m

www.shiyanbar.com/ctf/730

下载的文件是公钥和c。

思路:通过公钥算出n,e,再分解n得p,q,利用p,q,e算出d,最后pow(c,d,n)收工。

这里关键是分解n得p,q,可以利用工具yafu的factor(n)得p,q,这个工具分解小的n还可以,分解大n就很慢了,由于这题的n很大,所以利用这个开源工具https://github.com/pablocelayes/rsa-wiener-attack直接求d,几乎是秒出。

getd.py脚本如下(来源:www.freebuf.com/column/148185.html):

#!/usr/bin/python
import ContinuedFractions,Arithmetic
import time
import sys
import binascii

sys.setrecursionlimit(100000)
 # modulus from the RSA public key  
n=input("input n:")
 # exponent from the RSA public key  
e=input("input e:")
def hack_RSA(e,n):
    print "Performing Wiener's attack. Don't Laugh..."
    time.sleep(1)
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)
    for (k,d) in convergents:

        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = Arithmetic.is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    return d
hacked_d = hack_RSA(e, n)
print "d=" + str(hacked_d)
d=hacked_d
c=input("input c:")
m = hex(pow(c, d, n)).rstrip("L")
m1=pow(c, d, n)
print binascii.unhexlify(m[2:])
print("%0512x" %m1).decode("hex")

结果:

input n:109966163992903243770643456296093759130737510333736483352345488643432614201030629970207047930115652268531222079508230987041869779760776072105738457123387124961036111210544028669181361694095594938869077306417325203381820822917059651429857093388618818437282624857927551285811542685269229705594166370426152128895901914709902037365652575730201897361139518816164746228733410283595236405985958414491372301878718635708605256444921222945267625853091126691358833453283744166617463257821375566155675868452032401961727814314481343467702299949407935602389342183536222842556906657001984320973035314726867840698884052182976760066141L

input e:30749686305802061816334591167284030734478031427751495527922388099381921172620569310945418007467306454160014597828390709770861577479329793948103408489494025272834473555854835044153374978554414416305012267643957838998648651100705446875979573675767605387333733876537528353237076626094553367977134079292593746416875606876735717905892280664538346000950343671655257046364067221469807138232820446015769882472160551840052921930357988334306659120253114790638496480092361951536576427295789429197483597859657977832368912534761100269065509351345050758943674651053419982561094432258103614830448382949765459939698951824447818497599L

Performing Wiener’s attack. Don’t Laugh…

d=4221909016509078129201801236879446760697885220928506696150646938237440992746683409881141451831939190609743447676525325543963362353923989076199470515758399

input c:0x1e04304936215de8e21965cfca9c245b1a8f38339875d36779c0f123c475bc24d5eef50e7d9ff5830e80c62e8083ec55f27456c80b0ab26546b9aeb8af30e82b650690a2ed7ea407dcd094ab9c9d3d25a93b2140dcebae1814610302896e67f3ae37d108cd029fae6362ea7ac1168974c1a747ec9173799e1107e7a56d783660418ebdf6898d7037cea25867093216c2c702ef3eef71f694a6063f5f0f1179c8a2afe9898ae8dec5bb393cdffa3a52a297cd96d1ea602309ecf47cd009829b44ed3100cf6194510c53c25ca7435f60ce5f4f614cdd2c63756093b848a70aade002d6bc8f316c9e5503f32d39a56193d1d92b697b48f5aa43417631846824b5e86

BCTF{9etRea4y!}

BCTF{9etRea4y!}

 

0x03 参考资料

http://www.freebuf.com/column/148185.html

www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

blog.csdn.net/q376420785/article/details/8557266

Comment