RSA

Gryffinbit

密码学

发布于：2020年11月13日

次浏览

参数

N：大整数N，我们称之为模数（modulus）

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

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

c 和 m：分别是密文和明文

{N,e}称为公钥,{N,d}称为私钥

解题思路

1. 选取两个较大的互不相等的质数p和q，计算n = p * q 。
2. 计算phi = (p-1) * (q-1) 。
3. 选取任意e，使得e满足 1<e<phi 且 gcd(e , phi) == 1 。
4. 计算e关于n的模逆元d， 即d满足(e * d)% n ==1 。
5. 加解密：c = (m ^ e) % n ， m = (c ^ d) % n 。其中m为明文，c为密文，(n,e)为公钥对，d为私钥，要求 0 <= m < n 。

tips：

1. 如果所给为多个N，使用公因数攻
2. 当E为1，2或特别大时，使用Rabin攻击或低解密指数攻击
3. 当E为3时，如果只给出一组明密文。使用低加密指数攻击，如果给出多组明密文，使用低加密指数广播攻击
4. 如果所给为多次加密，使用同个N，使用共模攻击

gmpy2 大数库的安装

brew install libmpc
pip install gmpy2
python3.8 xxx.py

RSA的攻击手段

求解逆元

import gmpy2
print (gmpy2.invert(47,30))

分解n

pip install factordb-pycli
factordb n的值

求解出p、q

http://factordb.com/ 也可以求解

已知p,q,e，获取d（例子）

import gmpy2
p =gmpy2.mpz(336771668019607304680919844592337860739)
q =gmpy2.mpz(296173636181072725338746212384476813557)
e =gmpy2.mpz(65537)
phi_n= (p - 1) * (q - 1)
d = gmpy2.invert(e, phi_n)
print("d is:")
print (d)

已知N,e,c，求m

import gmpy2
p = 336771668019607304680919844592337860739
q = 296173636181072725338746212384476813557
e = 65537
c = 55907434463693004339309251502084272273011794908408891123020287672115136392494
n = p * q
fn = (p - 1) * (q - 1)
d = gmpy2.invert(e, fn)
h = hex(gmpy2.powmod(c, d, n))[2:]
if len(h) % 2 == 1:
    h = '0' + h
s = h
#s = h.decode('hex')
print (s)

已知N,e,c，求m

出题人会给你一个公钥文件（通常是以.pem或.pub结尾的文件）和密文（通常叫做flag.enc之类的），你需要分析公钥，提取出（N，e），通过各种攻击手段恢复私钥，然后去解密密文得到flag。 EG:一般先用openssl提取公钥文件中的N和e。

openssl rsa -pubin -text -modulus -in public.pem

import gmpy2
p = 336771668019607304680919844592337860739
q = 296173636181072725338746212384476813557
e = 65537
f = int(open('flag.enc', 'rb').read().encode('hex'), 16)
print f
n = p * q
fn = (p - 1) * (q - 1)
d = gmpy2.invert(e, fn)
h = hex(gmpy2.powmod(f, d, n))[2:]
if len(h) % 2 == 1:
    h = '0' + h
print (h)

低指数攻击

e的选取很小

e的选取很小

import gmpy2
e = 3
n= 22885480907469109159947272333565375109310485067211461543881386718201442106967914852474989176175269612229966461160065872310916096148216253429849921988412342732706875998100337754561586600637594798877898552625378551427864501926224989873772743227733285336042475675299391051376624685754547818835551263597996620383338263448888107691240136257201191331617560711786674975909597833383395574686942099700631002290836152972352041024137872983284691831292216787307841877839674258086005814225532597955826353796634417780156185485054141684249037538570742860026295194559710972266059844824388916869414355952432189722465103299013237588737
c= 15685364647213619014219110070569189770745535885901269792039052046431067708991036961644224230125219358149236447900927116989931929305133870392430610563331490276096858863490412102016758082433435355613099047001069687409209484751075897343335693872741
print ('n=', n)
print ('c=', c)
print ('[+]Detecting m...')
result = gmpy2.iroot(c, 3)
print (' [-]The c has cubic root?', result[1])
if result[1]: print (' [-]The m is:', '{:x}'.format(result[0]) #print (' [-]The m is:', '{:x}'.format(result[0]).decode('hex'))
print ('[!]All Done!')

m的 3 次方比N大，但不足够大

import gmpy2, time
e = 3
n = 114976915747243387792157708464120735018971336213935438953074748276198282761939060395482051056351068439137722626185590043024556656813730840050547350912425438364703854627760482842307943026011880815011654341047422453012558617703411700393668892701036222135444420377515575624398723436532681305293727164639582093389
c = 5828813410620741112500628876643872258919868379601617907887884191584237969605489971465692568848339200057188383649365078832766143513766368216471491824042974016773526107276856706832404477882581400769791378958901067683158857990261489285951805740071223765359992165262854641069674603160977034446644199945940251030
i = 239000000 
print ('n=', n)
print ('c=', c)
print ('[!]Done!\n')
print ('[+]Detecting m...')
s = time.process_time()
while 1:
    m, b = gmpy2.iroot(c + i * n, 3)
    if b:
        print (' [-]m is: ' + '{:x}'.format(int(m)))
        break
    #print ' [-]i = %d\r' % i,     i += 1
print ('[!]Timer:', round(time.process_time() - s, 2), 's')

选取的加密指数较低，并且使用了相同的加密指数

给了三组加密的参数和明密文，其中题目很明确地能告诉你这三组的明文都是一样的

import gmpy2
import time
from functools import reduce
def CRT(items):
    N = reduce(lambda x, y: x * y, (i[1] for i in items))
    result = 0
    for a, n in items:
        m = N / n
        d, r, s = gmpy2.gcdext(n, m)
        if d != 1: raise Exception("Input not pairwise co-prime")
        result += a * s * m
    return result % N, N
# 读入 e, n, c 
e = 9
n = [142782424368849674771976671955176187834932417027468006479038058385550042422280158726561712259205616626939123504489410624745195777853423961104590708231562726165590769610040722589287393102301338152085670464005026301781192671834390892019478189768725018303217559795377795540494239283891894830166363576205812991157,153610425077816156109768509904751446801233412970601397035720458311275245730833227428213917577405780162151444202393431444812010569489900435979730559895340377469612234558042643742219128033827948585534761030527275423811282367831985007507137144308704413007806012914286105842311420933479771294576841956749281552971,152540067782701001222493009941492423063369171831039847414320547494725020441901272486665728360741395415762864872737675660423920609681185809510355937534756399208661762715484879562585724584849261266873624875852300611683382543315580370484972470694466195837255994159609193239840228218925381488410059939975556977947,125842716702134814646356078531900645012495638692517778270527426844383063904041812273637776798591687732598509470005151551320457132061693618473039437320011446697406190781306264437609046721508738109650829547010385875425097336266103994639126319889016342284747700714199556143378526590058467791687837422897022829661,116144389285266462769913139639175922392318396923181100785008570884082681963637784423143843845816350379438789947802939701820129805341796427821894273985551331666719808355412080909245720551238149511778060242720419584504473490216670437024863860559347959698828131475160058721701582089480924088773887932997353631767,127833907448946785858374094953899556339175475846831397383049660262333005992005484987913355932559627279178940862787593749842796469355336182379062826441222705075178971785791223706944120681105575965622931327112817747065200324610697178273898956820957640413744954233327851461318200323486469677469950386824833536523,130561613227079478921314550968562766645507834694262831586725464124109153306162445639759476845681271537955934718244296904503168256991962908095007040044300188572466395275317838178325500238288302672390013747102961340256309124310478931896245221622317302428447389760864327859640573452084295225059466376349115703119,115953389401040751013569404909249958538962411171147823610874077094621794755967854844224923689925397631692572916641171075740839099217316101334941033937183815345038898177087515909675028366437302462022970987947264115373697445950951595479758872029099661065186221250394358255523574834723958546450323357472451930993,143437107845384843564651522639125300763388830136500260725097766445883003928355325003575359566631064630487365774344508496878731109174874449170057678821440711511966073934025028100604234445470976333825866939923998344367645612128590820812489407412175198698290167077116185959180877334222693344630253253476594907313]
c = [85033868418784308573673709960700777350314426427677627319697346811123742342359072170220428874952996988431950989321281905284522596263957356289624365171732095210045916218066135140320107686084053271623461104022705353814233772164502775939590711842361956121603943483040254727995655776263673058788416722141673409688,66065963470666895005407449599703926269325406456711861190876894466341571726360462706664546294453572319565476664348345756905411939632955966517708138047546806602828064213238537646393524578984547577761559965654539771172357089802682793169968961304179886652390277814477825753096636750388350662980872556701402397564,116011740820520887443111656288411611070614127688662643257265381793048354928820176624229624692124188995846076431510548507016903260774215950803926107831505634778278712070141663189086436127990584944132764896694777031370995058271038329228336417590284517922855284619653301817355115583540545182119702335431334401666,97640420284096094887471273365295984332267897927392169402918423863919914002451127544715668846623138003564829254309568918651163254043205129883843425179687841236818720463784828905460885026290909768599562386370732119591181513319548915478512030197629196018254041500662654260834562708620760373487652389789200792120,8112507653841374573057048967617108909055624101437903775740427861003476480616929517639719198652146909660899632120639789106782550275648578142883715280547602249589837441805676364041484345030575130408744621981440093280624046635769338568542048839419939250444929802135605724150484414516536378791500915047844188300,36792148360808115566234645242678223867680969786675055638670907933041180936164293809961667801099516457636164692292891528415720085345494773373966277807505798679784807614784581861287048096977968620964436947452527540958289441390882589051225367658014709290392321808926567572528170531844664734909469690750971883323,53043093283305492238903255767698153246673671181809989362223466090875767705978690531154079519999671834688647277179370374802495005937892824566602423646978168777735383632928274082669949750078161820002768640908750005814934158829006019656592134357897586040866207754535586785064545866404380204728594863102313407789,88499407133762624445946519155722583633934260410706930537441122463087556094734626189377091740335667052378955691250910459790202385799502439716173363179773811920751410726795431402796346647688144853156900427797933862087074385441977254140336390678022955770879265490567987868532251217565094093318626424653599450992,138337520305048557335599940473834485492131424901034295018189264168040969172072024612859307499682986987325414798210700710891033749119834960687318156171051379643844580970963540418974136891389303624057726575516576726845229494107327508855516437230240365759885913142671816868762838801720492804671259709458388192984]
print ('[+]Detecting m...')
data = zip(c, n)
x, n = CRT(data)
realnum = gmpy2.iroot(gmpy2.mpz(x), e)[0].digits()
print (' [-]m is: ' + '{:x}'.format(int(realnum)))
print ('[!]All Done!')

###低解密指数攻击

e特别大

共模攻击

相同的模N对相同的明文m进行了加密。若干次加密，e不同，N相同，m相同。

import time
import gmpy2
n = 158052722013789461456896900244510199169216575693048895162538548356466884311543740968048825149608833390255268602486435690724338965409521812963337715301197225841194835534751041470231293288252951274190599189716955573428884560130364021535005115652592074445852835422027406556727605302404510264249211145063332337043
e = [665213, 368273]
c = [16698617641888248664694980135332125531792692516788088682722832061393117609508765284473236240256421599515450690670639565968165473479697383505401285976148490839526672808730165847471005704945978274496508928460578173068717106075169723401049489389383596761956301440156581021583368058047939083755488885694261340425, 59192887933967939708054321952273893559113509451228797382728687616356609407020086787061368452871936378934964292805289941535766263083244529814852043063188312786173717046316177403357053871483983775362121186037776932260378728059531236711960979620603784044468207000654149190295060179235411429700710154759043236436]
print ('[+]Detecting m...')
time.process_time()
c1 = c[0]
c2 = c[1]
e1 = e[0]
e2 = e[1]
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
print (' [-]m is:' + '{:x}'.format(int(m)))
print ('\n[!]Timer:', round(time.process_time(),2), 's')
print ('[!]All Done!')

Rabin攻击

当e=2时

import gmpy2
import string
from Crypto.PublicKey import RSA
# 读取公钥参数 
with open('./tmp/pubkey.pem', 'r') as f:
    key = RSA.importKey(f)
    N = key.n
    e = key.e   
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
with open('./tmp/flag.enc', 'r') as f:
    cipher = f.read().encode('hex')
    cipher = string.atoi(cipher, base=16)
    # print cipher # 计算yp和yq yp = gmpy.invert(p,q)
yq = gmpy2.invert(q,p)
# 计算mp和mq mp = pow(cipher, (p + 1) / 4, p)
mq = pow(cipher, (q + 1) / 4, q)
# 计算a,b,c,d a = (yp * p * mq + yq * q * mp) % N
b = N - int(a)
c = (yp * p * mq - yq * q * mp) % N
d = N - int(c)
for i in (a,b,c,d):
    s = '%x' % i
    if len(s) % 2 != 0:
        s = '0' + s
    print (s)

e=1

import binascii
import gmpy2
N_hex=0x180be86dc898a3c3a710e52b31de460f8f350610bf63e6b2203c08fddad44601d96eb454a34dab7684589bc32b19eb27cffff8c07179e349ddb62898ae896f8c681796052ae1598bd41f35491175c9b60ae2260d0d4ebac05b4b6f2677a7609c2fe6194fe7b63841cec632e3a2f55d0cb09df08eacea34394ad473577dea5131552b0b30efac31c59087bfe603d2b13bed7d14967bfd489157aa01b14b4e1bd08d9b92ec0c319aeb8fedd535c56770aac95247d116d59cae2f99c3b51f43093fd39c10f93830c1ece75ee37e5fcdc5b174052eccadcadeda2f1b3a4a87184041d5c1a6a0b2eeaa3c3a1227bc27e130e67ac397b375ffe7c873e9b1c649812edcd
e_hex=0x1
c_hex=0x4963654354467b66616c6c735f61706172745f736f5f656173696c795f616e645f7265617373656d626c65645f736f5f63727564656c797d
c_hex = gmpy2.mpz(c_hex)
N_hex = gmpy2.mpz(N_hex)
i = 0
while i<10:
    m_hex = hex(c_hex + gmpy2.mpz(hex(i))*N_hex)
    print(m_hex[2:])
    try:
        print(binascii.a2b_hex(m_hex[2:]).decode("utf8"))
    except binascii.Error as e:
        print("位数非偶数，跳过...")
    i += 1

部分参数泄露

import gmpy2
import binascii
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:]))
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
decrypt(dp,dq,p,q,c)

dp泄露

import gmpy2
import binascii

def getd(n,e,dp):
    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 = (p-1)*(q-1)
                d = gmpy2.invert(e,phi)%phi
                return d

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
d=getd(n,e,dp)
m=pow(c,d,n)
print (binascii.unhexlify(hex(m)[2:]))

import gmpy2
import binascii

def getd(n,e,dp):
    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 = (p-1)*(q-1)
                d = gmpy2.invert(e,phi)%phi
                return d

e = 65537
n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825

d=getd(n,e,dp)
m=pow(c,d,n)
print (binascii.unhexlify(hex(m)[2:]))

报错

No module named ‘Crypto’

sudo pip3 uninstall crypto
sudo pip3 uninstall pycrypto

Then install the pycrypto module again using:

sudo pip3 install pycrypto
sudo pip uninstall crypto
sudo pip uninstall pycrypto

Then install the pycrypto module again using:

sudo pip install pycrypto

module ‘time’ has no attribute ‘clock’

time.clock()换成time.process_time()

‘map’ object is not subscriptable

1、下面语句报错python3 TypeError: ‘map’ object is not subscriptable

map(apply_filters_to_token, sentences)

2、修改，add “list” to map

return list(map(apply_filters_to_token, sentences))

更新于：2023年1月17日

RSA