安小琪's blog

少年有梦，不应止于心动

RSA算法

Posted on In Valine:

rsa算法及其常见攻击方法总结

RSA 算法

1.质数（素数)**是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
2.**合数是指比1大但不是素数的数
3.约数（因数）整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为 b的倍数，b称为a的约数
4.互质数：如果两个整数a,b的最大公因数（greatest common divisor）为1，即gcb(a,b)=1，那么称a,b两数互质
5.欧拉函数是指设m为正整数，则1,2,3,4…….,m中与m互素的整数的个数记为φ(m)，叫做欧拉函

RSA加解密涉及变量

1
2
3
4
5
6
7
8
9
10
11
N(n):模数（modulus）

p 和 q ：N的两个因子（factor）

e 和 d：(密钥) 互为模反数的两个指数（exponent）

c 和 m：分别是密文和明文，这里一般指的是一个十进制的数还有一个就是n的欧拉函数值

欧拉函数值：r

pow(x, y, z)：效果等效pow(x, y)1 % z， 先计算x的y次方，如果存在另一个参数z，需要再对结果进行取模。

RSA 密钥流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1.选择两个大的参数，计算出模数 N = p * q

2.计算欧拉函数 φ = (p-1) * (q-1)，然后选择一个e(1<e<φ)，并且e和φ互质（互质：公约数只有1的两个整数）

3.选一个整数e,满足条件1<e<φ(m),且gcd(φ(m),e)=1。

4.取e的模反数d，计算方法为:e * d ≡ 1 (mod φ) （模反元素：如果两个正整数e和n互质，那么一定可以找到整数d，使得 e * d - 1 被n整除，或者说e * d被n除的余数是1。这时，d就叫做e的“模反元素”。欧拉定理可以用来证明模反元素必然存在。两个整数a,b，它们除以整数M所得的余数相等：a ≡ b(mod m)，比如说5除3余数为2，11除3余数也为2，于是可写成11 ≡ 5(mod 3)。）

5.对明文m进行加密：c = pow(m, e, N),可以得到密文c。

6.对密文c进行解密：m = pow(c, d, N),可以得到明文m。

7.以{e,n}为公开密钥，{d,n}为秘密密钥。

      **对于RSA加密算法，公钥{e，n}为公钥，可以任意公开，破解RSA最直接（亦或是暴力）的方法就是分解整数N，然后计算欧拉函数φ(n)=(p-1) * (q-1),再通过d * e ≡ 1 mod φ(N)，即可计算出 d，然后就可以使用私钥{d,n}通过m = pow(c,d,N)解密明文。**

常见攻击方法

已知n ，求p、q

1
yafu-x64.exe factor(n的值)

已知p、q、n、d、e、c ，求m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import libnum
from Crypto.Util.number import long_to_bytes
 
p= 126729679138645768182553484939222388095337159128334812217076856766286726100722737386684910198924075618261733511899178248740842988023783860304680216528111943948650991922411810152409875453013448212844275128429743180857252325975760741025361007417218899801395331815926208007247121572435100975580895804697442267667
q= 104054553901866046694152234075873959108336516469750504779054527723324227996566919796261247047819926468010759464060564698096955215543860719469943973366839789424779735870198738246817458119556893096185734860152455371100483038903482037735689890154303418032399146664880908368996751979005061157178580561874836674277
n= 13186800228898405157166059917184773617853712640471180039217928267284974059326904327031390781119031175379732237845653436997494207078290059726775386763080683265599148436732089022337613407943665286752579710542151837349577519631688662719799597716848557990301300845047904835733777855963832068005830639892297515861475389054801663421156620013116801979243885073633224390620897791674473390657471230265474539904978901640679239989474101425272946235730859491826762037650575249656428504273661423717571709137144202464915742953766397868220047245453924164634699781646345174155872192490459112680655223389383460102057128841007527701759
d= 6666741718175852695002564402338878866599738482334125886741956715747639432804039261295620348060131832916622186498314468590841441676075873917439749906482632385356311475261978814671287136203937652714851512113662768007439338968166691516168272443846121609055235987289198939871633759580842087816610259724300678899409760769632608086590359648846785979010151887500164226717875175385752279026328578679881790478894318124664826720764930336542590593857878750645032322347484229748150896869656204158303007394006831891572119418579551641755331790272379241621551314159194130010824433499882502915209137650191117866498910835641898426217
e= 65537
c= 8934535177472721735467635346637055018553974527425844372392718307180572226265221620529055208344873719694210917617740112321607968152786054915844349252677965753727066642830661682640037552136307071453755611921578870804832103045328915684551852122755509931768219801397823475796319892313276391860511384154203828191835225538853352192567969225045118075662490001755141892428415681774585006728660907914136315857131804385409312556807320509181589678450429942484840794547904166067151010483324253100269201305883490450401489513091685763165031109421274052405458234170555873161963052787534363632206807961697751173459343573853489359660

#n = int("",16)

#e = int("",16)

 
d = libnum.invmod(e, (p - 1) * (q - 1))
m = pow(c, d, n)   # m 的十进制形式
string = long_to_bytes(m)  # m明文
print(string)  # 结果为 b‘ m ’ 的形式

已知d、n、c，求m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#求明文
import gmpy2
n = 920139713   #模数
d = 96849619    #密钥
c = """
704796792
752211152
274704164
...  #密文
"""
result = ""
c_list = c.split()
#print(c_list)
for i in c_list:
    result += chr(pow(int(i),d,n))
print(result)

已知p、q、e，求d

1
2
3
4
5
6
7
8
9
import gmpy2
p = gmpy2.mpz(18443)#初始化大整数
q = gmpy2.mpz(49891)
e = gmpy2.mpz(19)
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)  # invert（e，r）返回d使得e * d == 1 mod r，如果不存在d，则返回0
print("p={0},q={1},e={2}".format(p,q,e))
print("d is:\n%s"%d)

注：gmpy2：开源的高精度算数运算库https://blog.csdn.net/x_yhy/article/details/83903367

    分解`Ｎ`得到`p` `q`可以通过在线网站http://www.factordb.com/index.php

已知p、q、e、c，求m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2 
import binascii
 
c = 
e =  
p = 
q = 
 
# 计算私钥 d
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
 
# 解密 m
m = gmpy2.powmod(c,d,p*q)
print(binascii.unhexlify(hex(m)[2:]))

已知n、e，求d

1
2
3
4
5
6
7
8
9
import gmpy2
p = gmpy2.mpz(18443)#初始化大整数
q = gmpy2.mpz(49891)
e = gmpy2.mpz(19)
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)  # invert（e，r）返回d使得e * d == 1 mod r，如果不存在d，则返回0
print("p={0},q={1},e={2}".format(p,q,e))
print("d is:\n%s"%d)

注：gmpy2：开源的高精度算数运算库https://blog.csdn.net/x_yhy/article/details/83903367

    分解`Ｎ`得到`p` `q`可以通过在线网站http://www.factordb.com/index.php

已知c、e、n求m

结合以上两种方法，在知道n的前提下可求·p、q,利用p、q、e可以求出d，，从而因为已知d、n、c，求出相应的明文m

e很小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import gmpy2
from Crypto.Util.number import *
 
def de(c, e, n):
    k = 0
    while True:
        m = c + n*k
        result, flag = gmpy2.iroot(m, e)
        if True == flag:
            return result
        k += 1
n= 101039122745393011086075761431333300331289694438098112519435031064801288184776704381604748571542446279363075736568385812188180257614566727934604355002021119158698595183894756052638543569290110689953597497676586620724655659912733498890078876827811608806043144415031576507137872049560755184328355447574594518441
c= 764933079065821303938202185530873891095952922531624149947302252246720716932062359490333187814255917385791869
e= 1
m=de(c,e,n)
print(m)
print(long_to_bytes(m))

e很大

低解密指数攻击。
可以使用破解脚本：求出d的值，文件下载地址GitHub - pablocelayes/rsa-wiener-attack: A Python implementation of the Wiener attack on RSA public-key encryption scheme.
（注意，这里要将破解脚本和rsa-wiener-attack的py文件放在同一个目录下）

1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2
import binascii
import RSAwienerHacker

e =
n =
c =

d = RSAwienerHacker.hack_RSA(e,n)
m = gmpy2.powmod(c,d,n)

print(binascii.unhexlify(hex(m)[2:]))

已知n1 n2 n3 c1 c2 c3

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
import gmpy2
import libnum

n1= 240777156830688226202497126464031906561
c1= 168301165701198014721236970798204081878
n2= 223104370561673266133443574390508181831
c2= 196436851316434351550535795984485329678
n3= 140984835126114335254797030742842165673
c3= 109720785316626730740477878224677925223
def GCRT(mi, ai):
    # mi,ai分别表示模数和取模后的值,都为列表结构
    assert (isinstance(mi, list) and isinstance(ai, list))
    curm, cura = mi[0], ai[0]


    for (m, a) in zip(mi[1:], ai[1:]):
        d = gmpy2.gcd(curm, m)
        c = a - cura
        assert (c % d == 0) #不成立则不存在解
        K = c // d * gmpy2.invert(curm // d, m // d)
        cura += curm * K
        curm = curm * m // d
        cura %= curm
    return (cura % curm, curm)
C,N = GCRT([n1,n2,n3],[c1,c2,c3])
print(libnum.n2s(int(C)))

已知n e1 e2 c1 c2

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
#coding:utf-8
import gmpy2
import libnum

n= 20525856796358622542718677926717236159647140988779632916023330360743308571465035521456618246453505384811356964381602185770604617910217705644241601919510983153411928945242737798518222968430803760385453549864324704270799414784784751743730457175869405853056195910609490882141405584159086735460243418721853680956338407002662807923663961876660132733676614504451189079992604167252218809494223809054641989752717431195535666815666918051653503606256753255360886298176589585601788634858210944705922776805308515466440059702087117724063125769568782786705369091550143430039210568544597083922068892728154828960748610506689074823227
e1= 2333
e2= 23333
c1= 12843853329258238904944682925668126676020531928205034941455736880923953070133948500160509885177534948814798432362012498261954060626235284206711249303660562581681406330552549533460412599717525723398916851602332708342635126832047909942831374066464048740195772895284657148447759419754787052551034715862546198951517652518657029118223699256008965713642455227408636052324758979008424464649550249437724758555037556365720700277556718632438603401489558582378746827854501974650375773551687347334235089330457359222419521679082838490450404703606877716870369880587341940362685090356023202645749443867931775958861888382192563831150
c2= 19701923401677355921469041519514834903906804036869147381920905269769034433397656185043184909966992600517994579747948247882252727682993193969565424154517588414294931783342333908430499969958541809124201876154631950685591816289950988733855088677686071205659835742530929065759381115903669558804868420534365611348162573997475752268461697960061604007024795834842216164325114269677269416188614389553986189013991241274855316095083261006236553317589048521848971893834682590902115437088640960545891231131914924958201704614434058084139944543425977749040331313818008271101542439922140737924086458519020752457272326148630245910297
#共模攻击
#共模攻击函数
def rsa_gong_N_def(e1,e2,c1,c2,n):
    e1, e2, c1, c2, n=int(e1),int(e2),int(c1),int(c2),int(n)
    s = gmpy2.gcdext(e1, e2)
    s1 = s[1]
    s2 = s[2]
    if s1 < 0:
        s1 = - s1
        c1 = gmpy2.invert(c1, n)
    elif s2 < 0:
        s2 = - s2
        c2 = gmpy2.invert(c2, n)
    m = (pow(c1,s1,n) * pow(c2 ,s2 ,n)) % n
    return int(m)
m = rsa_gong_N_def(e1,e2,c1,c2,n)
print(m)
print(libnum.n2s(int(m))) 

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
37
from gmpy2 import invert
import libnum
import binascii
# 欧几里得算法
def egcd(a, b):
  if a == 0:
    return (b, 0, 1)
  else:
    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)

def main():
    c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
    n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
    e1 = 11187289
    c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
    e2 = 9647291
    s = egcd(e1, e2)
    s1 = s[1]
    s2 = s[2]
    # 求模反元素
    if s1<0:
        s1 = - s1
        c1 = invert(c1, n)
    elif s2<0:
        s2 = - s2
        c2 = invert(c2, n)

    m = pow(c1,s1,n)*pow(c2,s2,n) % n
    print(hex(m))
    print(binascii.unhexlify(hex(m)[2:]))

if __name__ == '__main__':
  main()



已知e、n1、c1、n2、c2，求m

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
import gmpy2
import binascii
 
e = 
n1 = 
c1 = 
n2 = 
c2 = 
 
p1 = gmpy2.gcd(n1,n2)
q1 = n1 // p1
phi1 = (p1-1)*(q1-1)
 
d1 = gmpy2.invert(e,phi1)
m1 = gmpy2.powmod(c1,d1,n1)
 
print(binascii.unhexlify(hex(m1)[2:]))
 
p2 = gmpy2.gcd(n2,n1)
q2 = n2 // p2
phi2 = (p2-1)*(q2-1)
 
d2 = gmpy2.invert(e,phi2)
m2 = gmpy2.powmod(c2,d2,n2)
 
print(binascii.unhexlify(hex(m2)[2:]))

e很小 低指数加密广播攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gmpy2
import libnum
from Crypto.Util.number import long_to_bytes
from sympy.ntheory.modular import crt
 
N1 = int('331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004',5)
c1 = int('310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243',5)
 
N2 = int('302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114',5)
c2 = int('112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344',5)
 
N3 = int('332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323',5)
c3 = int('10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242',5)
 
e = 3
n = [N1,N2,N3]
c = [c1,c2,c3]
resultant, mod = crt(n, c)
value, is_perfect = gmpy2.iroot(resultant, e)
print(long_to_bytes(value))

已知e p+q p-q c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
from Crypto.Util.number import long_to_bytes
e=9381227
p+q =19557532192412770135396612754285285862683596643931761304241244951607949645171603318285236011702235101665676486522272947846730991666618798325812810258224406
p-q =1650676835020556888453234895519708130417780877512373678819915730300719385001354199106679712335032655467448380397633077586536806154457656255747639793919628
c=27547276638529171065509412221175661764235537727284046788847560106007680393042160546744837423306870550936908103385332804059870319330198485286374792929657313035321660130970784463719347066550910527833718736819018212643397915649241906156866360428203454699367989718776887507055164028637433982239456710840668151058
p = (((pq1)+(pq2))//2)
q = (((pq1)-(pq2))//2)
n = p*q
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)
m = pow(c,d,n)
print(long_to_bytes(m))

已知 p q dp dq c

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
I = gmpy2.invert(q,p)
mp = pow(c,dp,p)
mq = pow(c,dq,q)
m = (((mp-mq)*I)%p)*q+mq

print(bytes.fromhex(hex(m)[2:]))

已知 n e dp c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import gmpy2 as gp

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
for i in range(1, e):
    if (dp * e - 1) % i == 0:
        if n % (((dp * e - 1) // i) + 1) == 0:
            p = ((dp * e - 1) // i) + 1
            q = n // (((dp * e - 1) // i) + 1)
            phi = (q - 1) * (p - 1)
            d = gp.invert(e, phi)
            m = pow(c, d, n)

print(m)

print(bytes.fromhex(hex(m)[2:]))


已知n e p q pub.key

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

e = 65537
n = 86934482296048119190666062003494800588905656017203025617216654058378322103517
p = 285960468890451637935629440372639283459
q = 304008741604601924494328155975272418463

phin = (p - 1) * (q - 1)
d = gmpy2.invert(e, phin)

key = rsa.PrivateKey(n, e, int(d), p, q)

with open("0eaf8d6c-3fe5-4549-9e81-94ac42535e7b/flag.enc", "rb") as f:
    f = f.read()
    print(rsa.decrypt(f, key))

已知c、n、p*(q-1)、q*(p-1)，求m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import gmpy2
from Crypto.Util.number import *
#pq = p*(q-1)
#qp = q*(p-1)
c= 
n= 
pq= 
qp= 
 
e = 65537
p = n - pq
q = n - qp
phi = (p - 1)*(q - 1)
 
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
print(long_to_bytes(m))

利用n的公约数

当题目给出若干个模数n1,n2……,且模数很大。如果两次加密的n1和n2具有相同的素因子，那么我们可以利用欧几里德算法直接分解n1和n2.从而计算出两个n的最大公约数p：

素因子的定义：对于一个数n来说，将它的因子拆到若干个素数相乘，这些素数被称为n的素因子。
比如 12可以被拆为2 6
6不是质数，可以继续拆为2*3
所以最后12的素因子就是 2, 3（不计重复元素）

识别此类题目，通常会发现题目给了若干个n，均不相同，并且都是2048bit，4096bit级别，无法直接分解http://www.factordb.com/index.php，并且明文都没什么联系，e也一般取65537。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#-*-coding:utf-8-*-
'''
求两个数的最大公约数
算法参考:https://zhidao.baidu.com/question/36550887.html
by:reborn
'''
import gmpy2
n1=
n2=
def gys1(n1,n2):    #辗转相除法(欧几里德算法)
    if n1<n2:
        n1,n2=n2,n1
    while n2!=0:
        temp=n1%n2
        n1=n2
        n2=temp
    return n1
def gys2(n1,n2):    #更相减损法
    while n1!=n2:
        if n1<n2:
            n1,n2=n2,n1
        temp=n1-n2
        n1=temp
    return n1
p=gys2(n1,n2)
print ("p=",p)

#求q1,q2

q1=n1//p
q2=n2//p
print("q1=",q1)
print("q2=",q2)

#求d_1,d_2

p0 = gmpy2.mpz(p)#初始化大整数
q_1 = gmpy2.mpz(q1)
q_2 = gmpy2.mpz(q2)
e = gmpy2.mpz(65537)
r_1 = (p0-1)*(q_1-1)
r_2 = (p0-1)*(q_2-1)
d_1 = gmpy2.invert(e,r_1)  # invert（e，r）返回d使得e * d == 1 mod r，如果不存在d，则返回0
d_2 = gmpy2.invert(e,r_2)
print("d_1=",d_1)
print("d_2=",d_2)

# 求c1,c2

c1=
c2=
m1 = pow(c1, d_1, n1)
m2 = pow(c2, d_2, n2)
print("m1=",m1)
print("m2=",m2)

根据欧几里德算法算出的p之后，再用n除以p即可求出q，由此可以得到的参数有p、q、n、e，再使用常规方法计算出d，即可破解密文。

m = pow(c, d, N),可以得到明文m

共模攻击

如果在RSA的使用中使用了相同的模n对相同的明文m进行了加密，那么就可以在不分解n的情况下还原出明文m的值。

c1 = m^e1 mod n
c2 = m^e2 mod n

识别：非常简单，若干次加密，每次n都一样，明文根据题意也一样即可。

已知私钥文件、c求m

题目中给出了私钥文件private.pem和flag.enc

pem文件通常是包含了—–BEGIN PRIVATE KEY—–和—–END PRIVATE KEY—–，是 Base64 编码的二进制内容
使用私钥解密密文的方式

使用openssl工具
利用如下命令：

rsautl -decrypt -in flag.enc(密文名称) -inkey private.pem

已知公钥文件、c求m

题目中给出了public.pem和密文flag.enc

openssl rsa -pubin -text -modulus -in warmup -in pubkey.pem
[提取出pubkey.pem中的参数]

得到n，化为十进制

将n分解为P，q

python rsatool.py -o private.pem -e 65537 -p 275127860351348928173285174381581152299 -q 319576316814478949870590164193048041239

[使用rsatool生成私钥文件: private.pem]

openssl rsautl -decrypt -in flag.enc -inkey private.pem

低加密指数攻击

在RSA中e也称为加密指数。由于e是可以随意选取的，选取小一点的e可以缩短加密时间，但是选取不当的话，就会造成安全问题。

e=3时的小明文攻击

当e=3时，如果明文过小，导致明文的三次方仍然小于n，那么通过直接对密文三次开方，即可得到明文。

(1)m^3<n,也就是说m^3=c;
(2)m^3>n，即(m^3+kn)mod n=c（爆破k，不知道k取什么值）。

  • 第一种情况 根据 c = pow(m, e, N) 可知：

当e=3时，如果明文过小，导致明文的三次方仍然小于n，那么通过直接对密文三次开方，即可得到明文。

  • 第二种情况 如果明文的三次方比n大，但是不够大，那么设k，有： c=(m^3+kn)mod n

爆破k，如果（c-kn）能开三次根式，那么可以直接得到明文。

识别：

推荐在e=3的时候首先尝试这种方法。

openssl rsa -pubin -in pubkey.pem （读取公钥内容）
openssl rsa -pubin in pubkey.pem -text（以文本格式输出公钥内容),从这一步可以知道e的值

从而判断为低加密指数攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import gmpy2
from Crypto.Util.number import *
 
def de(c, e, n):
    k = 0
    while True:
        m = c + n*k
        result, flag = gmpy2.iroot(m, e)
        if True == flag:
            return result
        k += 1
n= 101039122745393011086075761431333300331289694438098112519435031064801288184776704381604748571542446279363075736568385812188180257614566727934604355002021119158698595183894756052638543569290110689953597497676586620724655659912733498890078876827811608806043144415031576507137872049560755184328355447574594518441
c= 764933079065821303938202185530873891095952922531624149947302252246720716932062359490333187814255917385791869
e= 1
m=de(c,e,n)
print(m)
print(long_to_bytes(m))

低加密指数广播攻击

低加密指数广播攻击，即如果选取的加密指数较低，并且使用了相同的加密指数给一个接收者发送了相同的信息（或者给一群接收者发送了相同的信息），那么可以进行广播攻击得到明文。

假如我们需要将一份明文进行多份加密，但是每份使用不同的密钥，密钥中的模数n不同但指数e相同且很小，我们只要拿到多份密文和对应的n就可以利用中国剩余定理进行解密。

适用

只要满足以下情况，我们就可以考虑实用低加密指数广播攻击：

1.加密指数e非常小
2.一份明文使用不同的模数n，相同的加密指数e进行多次加密
3.可以拿到每一份加密后的密文和对应的模数n、加密指数e

低加密指数广播攻击脚本

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# coding:utf8

from struct import pack,unpack
import zlib
import gmpy
def my_parse_number(number):
    string = "%x" % number
    #if len(string) != 64:
    #    return ""
    erg = []
    while string != '':
        erg = erg + [chr(int(string[:2], 16))]
        string = string[2:]
    return ''.join(erg)
def extended_gcd(a, b):
    x,y = 0, 1
    lastx, lasty = 1, 0
    while b:
        a, (q, b) = b, divmod(a,b)
        x, lastx = lastx-q*x, x
        y, lasty = lasty-q*y, y
    return (lastx, lasty, a)
def chinese_remainder_theorem(items):
  N = 1
  for a, n in items:
    N *= n
  result = 0
  for a, n in items:
    m = N/n
    r, s, d = extended_gcd(n, m)
    if d != 1:
      N=N/n
      continue
      #raise "Input not pairwise co-prime"
    result += a*s*m
  return result % N, N
  //中国剩余定理 ， 输入多组c和多组n，以及较小的指数e
sessions=[
{"c": , "e": , "n": },
{"c": , "e": , "n": },
{"c": , "e": , "n": }
]

data = []
for session in sessions:
    e=session['e']
    n=session['n']
    msg=session['c']
    data = data + [(msg, n)]
print "Please wait, performing CRT"
x, n = chinese_remainder_theorem(data)
e=session['e']
realnum = gmpy.mpz(x).root(e)[0].digits()
print my_parse_number(int(realnum))

n可以分解为多个素数

使用公钥加密和使用私钥解密流程（中国剩余定理）：
准备
首先，我们需要在在生成私钥公钥时，多生成几个数：
我们的d是e对phi(n)的逆元，我们现在需要另外2个逆元（分别是对(p-1)和(q-1)的），既
1：计算dp，使得dp * e = 1 mod(p-1)
2：计算dq，使得dq * e = 1 mod(q-1)
此外需要第三个元素，既q对p的逆元
3：计算qInv，使得qInv * q = 1 mod p
1 2 3 都作为私钥的一部分。

dp = d mod p-1
dq = d mod q-1

计算：

使用公钥加密：
若要加密明文m,则需要计算c = m^e mod n，c为密文。

使用私钥解密：
1:m1=c^dp mod p
2:m2=c^dq mod q
3:h= (qInv*((m1 - m2)mod p)) mod p
4:m = m2 + h*q
m就是明文。

例：n=17947
e=3
c=8363
m=???

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
n=17947
p=137
q=131
e=3
c=8363
dp=gmpy2.invert(e,p-1)
dq=gmpy2.invert(e,q-1)
m1=pow(c,dp,p)
m2=pow(c,dq,q)
qInv=gmpy2.invert(q,p)
h=(qInv*((m1-m2)% p)) % p
m=m2+h*q
print(m)

多素数

例:n=p1p2p3=2279269
p1=137
p2=131
p3=127
e=19

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
预先计算:
dp = 19^-1 mod 137-1 = 43
dq = 19^-1 mod 131-1 = 89
dr = 19^-1 mod 127-1 = 73

若要解密密文 768924，则先计算
1:m1=768924^43 mod 137 = 102
2:m2=768924^89 mod 131 = 120
3:m3=768924^73 mod 127 = 5

等式1与等式2连列方程组计算：
qInv = 114
h = (qInv*((m1 - m2)mod p)) mod p = 3
m12 = m2 + h*q = 120 + 3*131 = 513

所以等式1与等式2的通用解为：513+k1*(131*137)
所以结合等式3问题可以变为：
m1=513  p=17947
m2=5    q=127
qInv*q≡ 1 mod p    ——>qInv=10316
h = (10316*((513 - 5)mod 17947)) mod 17947 =4
m = 5 + 4*127 = 513
......

jiaoben

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import gmpy2
n=2279269
p1=137
p2=131
p3=127
e=19
c=768924
dp1=gmpy2.invert(e,p1-1)
dp2=gmpy2.invert(e,p2-1)
dp3=gmpy2.invert(e,p3-1)
m1=pow(c,dp1,p1)
m2=pow(c,dp2,p2)
m3=pow(c,dp3,p3)
qInv1=gmpy2.invert(p2,p1)
h1=(qInv1*((m1-m2) % p1)) % p1
m4=m2+h1*p2
p4=p1*p2
qInv2=gmpy2.invert(p3,p4)
h2=(qInv2*((m4-m3)% p4)) % p4
m=m3+h2*p3
print(m)

dp、dq泄露

dp = d mod p-1
dq = d mod q-1

这种参数是为了让解密的时候更快速而产生的

已知p,q,dp,dq,c求m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import gmpy2
import binascii
import libnum
def decrypt(dp,dq,p,q,c):
    InvQ = gmpy2.invert(q,p)
    mp = pow(c,dp,p)
    mq = pow(c,dq,q)                   #求幂取模运算
    m=(((mp-mq)*InvQ)%p)*q+mq          #求明文公式
    print (binascii.unhexlify(hex(m)[2:]))
    print(libnum.n2s(m))
p = 
q = 
dp = 
dq = 
c = 
decrypt(dp,dq,p,q,c)

已知e,n,dp,c求m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import gmpy2
import libnum
import binascii
def getd(n,e,dp):
    for i in range(1,e):            #在范围(1,e)之间进行遍历
        if (dp*e-1)%i == 0:
            if n%(((dp*e-1)/i)+1)==0:    #存在p，使得n能被p整除
                p=((dp*e-1)/i)+1
                q=n/(((dp*e-1)/i)+1)
                phi = (p-1)*(q-1)         #欧拉定理
                d = gmpy2.invert(e,phi)%phi        #求模逆
                return d
e =
n = 
dp = 
c = 
d=getd(n,e,dp)
m=pow(c,d,n)                            #快速求幂取模运算
print(binascii.unhexlify(hex(m)[2:]))       #16进制转文本
print(libnum.n2s(m))

https://blog.csdn.net/qq_42939527/article/details/105202716

已知n,r求p,q

核心是通过n和r解出p和q

1
2
3
4
5
6
7
8
9
1.二分法，求得p，q

2.RSATool2v17中，输入p，q，r，e，得到d  (脚本也可)

3.通过m=pow(c,d,n)
注意：有时题目有要求，解出的可能是m乘上某一个参数，这是需要仔细审题

4.转字符，得到flag

脚本

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
37
38
39
40
import gmpy2
import numpy as np
np.set_printoptions(suppress=True)

n=gmpy2.mpz(14057332139537395701238463644827948204030576528558543283405966933509944444681257521108769303999679955371474546213196051386802936343092965202519504111238572269823072199...)
r=gmpy2.mpz(14057332139537395701238463644827948204030576528558543283405966933509944444681257521108769303999679955371474546213196051386802936343092965202519504111238572269823072199...)

c1=n-r+1
print (c1)

l=c1/2
r=c1
#p=(l+r)/2
#y=p*(c1-p)

while l<r:
	p=(l+r)/2
	y=p*(c1-p)
	if y==n:
		print (p)
		break
	if y>n:
		print (y>n)
		l=p
	else:
		print (y<n)
		r=p
		print ("done")
q=c1-p
print q
/*
if p>q:
    p,q=q,p
factor2 = 2021 * p + 2020 * q
if factor2 < 0:
    factor2 = (-1) * factor2
    
_P=sympy.nextprime(factor2)
*/