RSA基础

RSA密钥生成步骤

（1）随机选择两个不相等的质数p和q

  • 比如选择61和53
  • 在实际应用中，这两个指数越大就越难破解

（2）计算p和q的乘积n

  • n=61*53=3233
  • 3233写成二进制是110010100001，共12位，故该密钥是12位的
  • 目前主流可选值：1024、2048、3072、4096等，低于1024bit的密钥已经不建议使用

（3）计算n的欧拉函数$\phi(n)$

  • 欧拉函数是小于x的整数中与x互质的数的个数，一般用$\phi(x)$表示
  • 互质是指两个数的公约数只有1，比如15和31
  • $\phi(8)$就等于4，因为8以内的与8互质的数只有1、3、5、7这四个数

欧拉函数的性质：

  • 如果$n=p*q$且p、q互质，则$\phi(n)=\phi(pq)=\phi(p)\phi(q)$
  • 如果n是质数，则$\phi(n)=n-1$

根据这两个性质可得：

$\phi(p)=p-1,\phi(q)=q-1$，所以$\phi(n)=(p-1)*(q-1)$

  • 所以可得例子中的$\phi(n)=60*52=3120$

（4）找出公钥e

  • 公钥e是按照条件随机选择的一个整数，选择e的条件是$1<e<\phi(n)$，且e与$\phi(n)$互质
  • 本例中选取e=17，但实际应用中e常常取65537

（5）计算私钥d

  • 私钥d是根据公钥e计算出来的，计算规则：e*d除以$\phi(n)$余数为1,可表示为：$ed \equiv 1(mod\phi(n))$
  • $\equiv$是恒等号（也叫同余号），比如两个整数a、b,他们除以整数m所得的余数相等，就可以表示为$a\equiv b$(mod m)，比如说5除以3余数为2，11除以3余数为2，于是可写成$11 \equiv $ 5(mod 3)
  • d其实就是e相对于$\phi(n)$的乘法逆元

image-20231211182936841

（6）得到密钥对

  • 公钥就是(n,e)，这里对应着(3233,17)。
  • 私钥就是(n,d)，这里对应着(3233,2753)

简单RSA加解密过程

（1）公钥加密

  • 假设需要加密的数据是字母“A”
  • 首选需要转ASCII码，所以m=65，并且m必须要小于n
  • 加密公式：$c=m^{e}modn$,即m的e次方再模n，即为c（密文）

image-20231211203803053

（2）私钥解密

  • 拿到密文c=2790
  • 解密公式：$m=c^{d}modn$，即c的d次方再模n，即为m（明文）

image-20231211203954658

解密必须知道私钥d，在已知n和e的情况下，可以推到出d

因为$ed\equiv1(mod\phi(n))$，所以只有知道e和$\phi(n)$才能算出d。

$\phi(n)$=(p-1)*(q-1)，所以知道p和q就行，而p和q又是由n因式分解出来的，所以只要能因式分解n，那么就可以算出d，拿到私钥

具体RSA加解密过程

（1）公钥加密

  • 明文"hello"
  • 转换顺序：字符串->十六进制->十进制

image-20231211210852746

  • m=448378203247
  • p = 999671，q=999727，n=999398089817，$\phi(n)$=999396090420，e=65537
  • c = m**e%n = 511394555284

（2）私钥解密

  • 转换顺序：十进制->十六进制->字符串
  • c = m**e%n = 511394555284
  • d = 529762121873
  • m = c**d%n = 448378203247

当需要求的d（私钥，即公钥的乘法逆元）数值过大时，需要利用python中的libnum库进行计算

image-20231211211903589

利用pow函数可以很好的实现次方模运算

image-20231212172342069

利用bytes.fromhex('68656c6c6f')可以将十六进制字符串转化为明文字符串

image-20231212172609779

更好的办法是利用libnum 库中的n2s方法，直接将十进制转化为字符串

image-20231212172819767

同时之前的字符串转十进制数也可以通过内置的方法s2n直接转换

image-20231212181122282

利用openssl提取公钥信息

1
openssl rsa -pubin -in pub.key -text -modulus

image-20231213112240593

分解大整数

1
factordb

利用symbol求解方程组

1
2
3
import sympy
x,y = sympy.symbols('x y')	#设未知数
s = sympy.solve([c1 - x -y,c2 - x**3 -y**3],[x,y])		#c1和c2已知

image-20231213152326979

求n的公约数

当题目中有多个n的时候，使用同一e对同一个明文加密时，这些n之前可能存在公约数。利用

1
libnum.gcd()方法求公约数

找出存在的公约数

利用迭代器

1
2
3
4
5
6
7
import itertools
ls = [n0,n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11,n12,n13,n14,n15,n16,n17,n18,n19]


for i in itertools.product(ls,ls):
    if i[0] != i[1] & libnum.gcd(i[0],i[1]) != 1:
        print(ls.index(i[0]),ls.index(i[1]))

低加密指数分解攻击

RSA中e也称为加密指数，d称为解密指数，n称为模数

image-20231213232130344

e太小就会造成安全问题，也成为低加密指数分解攻击

解题思路

image-20231213232249907

image-20231213232323977

image-20231213232404889

共模攻击

当n相同时，e不同，并且e在互质的前提下可以使用共模攻击

image-20231214113744726

image-20231214113808135

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import libnum
import gmpy2

c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291


s1 = int(gmpy2.gcdext(e1,e2)[1])		#利用扩展欧几里得算法
s2 = int(gmpy2.gcdext(e1,e2)[2])
print(s1,s2)

m = pow(c1,s1,n)*pow(c2,s2,n)%n
print(libnum.n2s(m))

低解密指数攻击

image-20231214122342891

1
2
3
4
5
6
7
8
9
10
import RSAwienerHacker as rsa_d
import hashlib

N = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085

d = rsa_d.hack_RSA(e,N)
print(d)

print(hashlib.md5(hex(d).encode()).hexdigest())

低加密指数广播攻击（中国剩余定理）

这种攻击方式特点与之前介绍的低加密指数分解攻击以及求n的公约数非常相似，都是对同一个明文采用不同的公钥加密，这些公钥中的e是相同的，并且非常小，但是n不同，而且n的值非常大，无法分解。

中国剩余定理

需要求解低加密指数广播攻击，就需要用到中国剩余定理的知识。

image-20231214162058671

image-20231214162140832

image-20231214162223297 image-20231214162314229

image-20231214162354771

例题

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
34
35
36
import libnum
import gmpy2
import RSAwienerHacker as rsa_d
from functools import reduce

s=[{"c": 7366067574741171461722065133242916080495505913663250330082747465383676893970411476550748394841437418105312353971095003424322679616940371123028982189502042, "e": 10, "n": 25162507052339714421839688873734596177751124036723831003300959761137811490715205742941738406548150240861779301784133652165908227917415483137585388986274803},
{"c": 21962825323300469151795920289886886562790942771546858500842179806566435767103803978885148772139305484319688249368999503784441507383476095946258011317951461, "e": 10, "n": 23976859589904419798320812097681858652325473791891232710431997202897819580634937070900625213218095330766877190212418023297341732808839488308551126409983193},
{"c": 6569689420274066957835983390583585286570087619048110141187700584193792695235405077811544355169290382357149374107076406086154103351897890793598997687053983, "e": 10, "n": 18503782836858540043974558035601654610948915505645219820150251062305120148745545906567548650191832090823482852604346478335353784501076761922605361848703623},
{"c": 4508246168044513518452493882713536390636741541551805821790338973797615971271867248584379813114125478195284692695928668946553625483179633266057122967547052, "e": 10, "n": 23383087478545512218713157932934746110721706819077423418060220083657713428503582801909807142802647367994289775015595100541168367083097506193809451365010723},
{"c": 22966105670291282335588843018244161552764486373117942865966904076191122337435542553276743938817686729554714315494818922753880198945897222422137268427611672, "e": 10, "n": 31775649089861428671057909076144152870796722528112580479442073365053916012507273433028451755436987054722496057749731758475958301164082755003195632005308493},
{"c": 17963313063405045742968136916219838352135561785389534381262979264585397896844470879023686508540355160998533122970239261072020689217153126649390825646712087, "e": 10, "n": 22246342022943432820696190444155665289928378653841172632283227888174495402248633061010615572642126584591103750338919213945646074833823905521643025879053949},
{"c": 1652417534709029450380570653973705320986117679597563873022683140800507482560482948310131540948227797045505390333146191586749269249548168247316404074014639, "e": 10, "n": 25395461142670631268156106136028325744393358436617528677967249347353524924655001151849544022201772500033280822372661344352607434738696051779095736547813043},
{"c": 15585771734488351039456631394040497759568679429510619219766191780807675361741859290490732451112648776648126779759368428205194684721516497026290981786239352, "e": 10, "n": 32056508892744184901289413287728039891303832311548608141088227876326753674154124775132776928481935378184756756785107540781632570295330486738268173167809047},
{"c": 8965123421637694050044216844523379163347478029124815032832813225050732558524239660648746284884140746788823681886010577342254841014594570067467905682359797, "e": 10, "n": 52849766269541827474228189428820648574162539595985395992261649809907435742263020551050064268890333392877173572811691599841253150460219986817964461970736553},
{"c": 13560945756543023008529388108446940847137853038437095244573035888531288577370829065666320069397898394848484847030321018915638381833935580958342719988978247, "e": 10, "n": 30415984800307578932946399987559088968355638354344823359397204419191241802721772499486615661699080998502439901585573950889047918537906687840725005496238621}]

n = [s[i]['n'] for i in range(len(s))]
print(n)
c = [s[i]['c'] for i in range(len(s))]
print(c)

e = 10

N = reduce(lambda x,y:x*y,n)
print(N)
M = 0
for i in range(10):
    M += libnum.invmod(N//n[i],n[i])*(N//n[i])*c[i]
print(M)
k = 0
while 1:
    result = gmpy2.iroot(M%N+k*N,e)
    if result[1]:
        print(libnum.n2s(int(result[0])))
        break
    k += 1