玩命加载中 . . .

RSA


11.RSA

1.介绍:

  • RSA加加密算法是一种非对称加密算法;

  • RSA公开密钥密码体制。所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥,是一种“由己知加密密钥推导出解密密钥在计算上是不可行的”密码体制。

  • RSA的安全性依赖于大数分解

2.数学知识

  1. 欧拉函数:求小于x并且和x互质的数的个数
  • φ(n)=n*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)……(1-1/pn)

  • n = (p-1)(q-1):这个式子仅在某种情况下适用

  • 理解互质的概念

    • 10 = 2 * 5 (等于两个质数相乘)
    • 小于10并且与10互质的数:1 3 7 9 (欧拉函数结果为4个)
    • 10的欧拉函数是 φ(10)= (5-1)(2-1)=4
  1. 模反元素:

  • e乘d减一等于φ(n)的倍数e与φ(n)是互质的ed+φ(n)*y=1
  1. 贝祖定理:此处去B站搜索李永乐老师关于贝祖数的视频 BV1mJ411q7xw

    • ax+by=m,如果x,y有整数解的话,它的充要条件是 m是a和b最大公约数的整数倍:m=gcd(a,b)*k:这个(a,b)代表a与b的最大公约数

    • 此时,x和y的整数解 称之为 贝祖数

     def exgcd(a,b):
         if b==0:
             return (1,0)
         else:
             x,y = exgcd(b,a%b)
             tmpx = x
             x = y
             y = tmpx-(a/b)*y
             return (x,y)
     print exgcd(13,2)
     // 替换132就可以

3.RSA加密过程

  • 第一步,随机选择两个不相等的质数p和q。

    • 选择 61 和 53 。( 实际应用中,这两个质数越大,就越难破解。)
  • 第二步,计算p和q的乘积n。 n = 61x53 = 3233

  • 第三步,计算 n 的欧拉函数φ(n)。

    • φ(n)= (p-1)(q-1)
    • 结果为60 * 52 = 3120
  • 第四步,随机选择一个整数e, 条件是1<e < φ(n),且eφ(n)互质。
    在1到3120之 间,随机选择了17。( 实际应用中,常常选择65537)

  • 第五步,计算e对于φ(n)的模反元素d

    • 已知e=17,中φ(n)=3120
    • 17x + 3120y= 1
    • e乘模反元素+欧拉函数*y=1
  • 欧拉函数就是小于n并且与n互质的数的个数

    • 算出一组整数解为(x,y)=(2753,-15),即 d=2753
  • 第六步,将n (3233)和e (17)封装成公钥,n (3233)和d (2753)(贝祖数的其中一个)封装成私钥。
    n=3233,e=17, d=2753, 所以公钥就是(3233,17),私钥就是(3233, 2753)

公钥:pub = (n,e)

私钥:pri = (n,d)

c = m ^ e (mod n)

m = c ^ d (mod n)

4.简单例题

  • 知道了 p , q , e , c,但是不知道 n ,可以通过 p q 算出来 n (p * q)
  • 使用python的gmpy2 模块,计算
  • 调用python 函数:pow( c , d , n) :c的d次方mod n
  import gmpy2
  p= 9648423029010515676590....
  q= 1187484383798029703209....
  e= 65537
  c= 8320829899517460417477....  //c是密文
  phi = (p-1)*(q-1)           //求欧拉函数
  d = gmpy2.invert(e,phi)     //求模反元素
  n=p*q                       //求n
  print pow(c,d,n)            //答案

5.pem的例题

  • 提取pem中的信息:
  openssl rsa -pubin -text -modulus -in pubkey.pem
  • 此时拿到了 e 和 n ,但是没有 p和q ,所以进行大数分解

    • 使用python库:pycryptodome 获取 n 和 e

    from Crypto.PublicKey import RSA
    r=open(pubLic.pem).read()
    pub =RSA.importKey(r)
    n = pub.n
    e = pub.e

6.大数分解算法

  • Pollard rho
from random import randint
from gmpy2 import *
n = 0x4333AF6B43F36028D8D9650EC3EED3238541EE5C15E626C58C9EC33674A6D08D5B1F2580A1A0B07E9D853536CD994E197889D122701A62BB2A9E79559F3D5281014535F6C54F83CA8D9700EEB67D99AF318D20A5150AD46D622A6A12DE0A758EE7DF75F5D10F2FE2585F2348537787063321FFDAC91BB3C3D1D88CBD04A824ED
x2 = 1
c = 7
while 1:
    x1 = randint(1, n)
    x2 = pow(x2,2,n)+c%n
    fac = gcd(abs(x1-x2),n)
    if fac>1 and is_prime(fac):
        print fac
        break
print n/fac
  • Pollard rho p-1
from gmpy2 import *
def PollardRho_p_1(Q,N):
    a = i = 2
    while 1:
        a = pow(a, i, N)
        d = gcd(a - 1, N)
        if d != 1:
            return d
        i += 1
  • Fermat
from gmpy2 import *
def Fermat(Q,n):
    a = isqrt_rem(n)[0]+1
    b = a ** 2 - n
    while 1:
        q = isqrt_rem(b)
        if q[1] == 0:
            return a - q[0]
        a += 1
        b = a ** 2 - n

7.共模攻击(自行百度)

# -*- coding: cp936 -*-
import time
import gmpy2
n = 158052722013789461456896900244510199169216575693048895162538548356466884311543740968048825149608833390255268602486435690724338965409521812963337715301197225841194835534751041470231293288252951274190599189716955573428884560130364021535005115652592074445852835422027406556727605302404510264249211145063332337043
e = [665213, 368273]
c = [16698617641888248664694980135332125531792692516788088682722832061393117609508765284473236240256421599515450690670639565968165473479697383505401285976148490839526672808730165847471005704945978274496508928460578173068717106075169723401049489389383596761956301440156581021583368058047939083755488885694261340425L, 59192887933967939708054321952273893559113509451228797382728687616356609407020086787061368452871936378934964292805289941535766263083244529814852043063188312786173717046316177403357053871483983775362121186037776932260378728059531236711960979620603784044468207000654149190295060179235411429700710154759043236436L]
print '[+]Detecting m...'
time.clock()
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)).decode('hex')
print '\n[!]Timer:', round(time.clock(),2), 's'
print '[!]All Done!'

8.低加密指数攻击

  • e=3并且m的e次方小于n
# -*- coding: cp936 -*-
import gmpy2
e = 3
# 读入 n, 密文
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]).decode('hex')
print '[!]All Done!'
  • e=3并且m的e次方大于n,但是不足够大
# -*- coding: cp936 -*-
import gmpy2, time
e = 3
# 读入 n, 密文
n = 114976915747243387792157708464120735018971336213935438953074748276198282761939060395482051056351068439137722626185590043024556656813730840050547350912425438364703854627760482842307943026011880815011654341047422453012558617703411700393668892701036222135444420377515575624398723436532681305293727164639582093389
c = 5828813410620741112500628876643872258919868379601617907887884191584237969605489971465692568848339200057188383649365078832766143513766368216471491824042974016773526107276856706832404477882581400769791378958901067683158857990261489285951805740071223765359992165262854641069674603160977034446644199945940251030
i = 239000000 # i 应该是未知的。这里缩短一下距离, 防止跑得太久
print 'n=', n
print 'c=', c
print '[!]Done!\n'
print '[+]Detecting m...'
s = time.clock()
while 1:
    m, b = gmpy2.iroot(c + i * n, 3)
    if b:
        print '  [-]m is: ' + '{:x}'.format(int(m)).decode('hex')
        break
    #print '  [-]i = %d\r' % i,
    i += 1
print '[!]Timer:', round(time.clock() - s, 2), 's'

9. 低加密指数广播攻击

  • 如果选取的加密指数较低,并且使用了相同的加密指数给一个接受者的群发送相同的信息,那么可以进行广播攻击得到明文。选取了相同的加密指数 e(这里取 e=3),对相同的明文 m 进行了加密并进行了消息的传递,那么有:

    c1≡m^e mod n1

    c2≡m^e mod n2

    c3≡m^e mod n3

    对上述等式运用中国剩余定理,在 e=3 时,可以得到:

    cx≡m^3 mod n1 n2 n3

    通过对 cx 进行三次开方就可以求得明文

  # -*- coding: cp936 -*-
  import gmpy2
  import time
  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 = [142782424368849674771976671955176187834932417027468006479038058385550042422280158726561712259205616626939123504489410624745195777853423961104590708231562726165590769610040722589287393102301338152085670464005026301781192671834390892019478189768725018303217559795377795540494239283891894830166363576205812991157L, 153610425077816156109768509904751446801233412970601397035720458311275245730833227428213917577405780162151444202393431444812010569489900435979730559895340377469612234558042643742219128033827948585534761030527275423811282367831985007507137144308704413007806012914286105842311420933479771294576841956749281552971L, 152540067782701001222493009941492423063369171831039847414320547494725020441901272486665728360741395415762864872737675660423920609681185809510355937534756399208661762715484879562585724584849261266873624875852300611683382543315580370484972470694466195837255994159609193239840228218925381488410059939975556977947L, 125842716702134814646356078531900645012495638692517778270527426844383063904041812273637776798591687732598509470005151551320457132061693618473039437320011446697406190781306264437609046721508738109650829547010385875425097336266103994639126319889016342284747700714199556143378526590058467791687837422897022829661L, 116144389285266462769913139639175922392318396923181100785008570884082681963637784423143843845816350379438789947802939701820129805341796427821894273985551331666719808355412080909245720551238149511778060242720419584504473490216670437024863860559347959698828131475160058721701582089480924088773887932997353631767L, 127833907448946785858374094953899556339175475846831397383049660262333005992005484987913355932559627279178940862787593749842796469355336182379062826441222705075178971785791223706944120681105575965622931327112817747065200324610697178273898956820957640413744954233327851461318200323486469677469950386824833536523L, 130561613227079478921314550968562766645507834694262831586725464124109153306162445639759476845681271537955934718244296904503168256991962908095007040044300188572466395275317838178325500238288302672390013747102961340256309124310478931896245221622317302428447389760864327859640573452084295225059466376349115703119L, 115953389401040751013569404909249958538962411171147823610874077094621794755967854844224923689925397631692572916641171075740839099217316101334941033937183815345038898177087515909675028366437302462022970987947264115373697445950951595479758872029099661065186221250394358255523574834723958546450323357472451930993L, 143437107845384843564651522639125300763388830136500260725097766445883003928355325003575359566631064630487365774344508496878731109174874449170057678821440711511966073934025028100604234445470976333825866939923998344367645612128590820812489407412175198698290167077116185959180877334222693344630253253476594907313L]
  c = [85033868418784308573673709960700777350314426427677627319697346811123742342359072170220428874952996988431950989321281905284522596263957356289624365171732095210045916218066135140320107686084053271623461104022705353814233772164502775939590711842361956121603943483040254727995655776263673058788416722141673409688L, 66065963470666895005407449599703926269325406456711861190876894466341571726360462706664546294453572319565476664348345756905411939632955966517708138047546806602828064213238537646393524578984547577761559965654539771172357089802682793169968961304179886652390277814477825753096636750388350662980872556701402397564L, 116011740820520887443111656288411611070614127688662643257265381793048354928820176624229624692124188995846076431510548507016903260774215950803926107831505634778278712070141663189086436127990584944132764896694777031370995058271038329228336417590284517922855284619653301817355115583540545182119702335431334401666L, 97640420284096094887471273365295984332267897927392169402918423863919914002451127544715668846623138003564829254309568918651163254043205129883843425179687841236818720463784828905460885026290909768599562386370732119591181513319548915478512030197629196018254041500662654260834562708620760373487652389789200792120L, 8112507653841374573057048967617108909055624101437903775740427861003476480616929517639719198652146909660899632120639789106782550275648578142883715280547602249589837441805676364041484345030575130408744621981440093280624046635769338568542048839419939250444929802135605724150484414516536378791500915047844188300L, 36792148360808115566234645242678223867680969786675055638670907933041180936164293809961667801099516457636164692292891528415720085345494773373966277807505798679784807614784581861287048096977968620964436947452527540958289441390882589051225367658014709290392321808926567572528170531844664734909469690750971883323L, 53043093283305492238903255767698153246673671181809989362223466090875767705978690531154079519999671834688647277179370374802495005937892824566602423646978168777735383632928274082669949750078161820002768640908750005814934158829006019656592134357897586040866207754535586785064545866404380204728594863102313407789L, 88499407133762624445946519155722583633934260410706930537441122463087556094734626189377091740335667052378955691250910459790202385799502439716173363179773811920751410726795431402796346647688144853156900427797933862087074385441977254140336390678022955770879265490567987868532251217565094093318626424653599450992L, 138337520305048557335599940473834485492131424901034295018189264168040969172072024612859307499682986987325414798210700710891033749119834960687318156171051379643844580970963540418974136891389303624057726575516576726845229494107327508855516437230240365759885913142671816868762838801720492804671259709458388192984L]
  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)).decode('hex')
  print '[!]All Done!' 

10. 低解密指数攻击

  • # -*- coding: cp936 -*-
    import gmpy2
    import time
    # 展开为连分数
    def continuedFra(x, y):
        cF = []
        while y:
            cF += [x / y]
            x, y = y, x % y
        return cF
    def Simplify(ctnf):
        numerator = 0
        denominator = 1
        for x in ctnf[::-1]:
            numerator, denominator = denominator, x * denominator + numerator
        return (numerator, denominator)
    # 连分数化简
    def calculateFrac(x, y):
        cF = continuedFra(x, y)
        cF = map(Simplify, (cF[0:i] for i in xrange(1, len(cF))))
        return cF
    # 解韦达定理
    def solve_pq(a, b, c):
        par = gmpy2.isqrt(b * b - 4 * a * c)
        return (-b + par) / (2 * a), (-b - par) / (2 * a)
    def wienerAttack(e, n):
        for (d, k) in calculateFrac(e, n):
            if k == 0: continue
            if (e * d - 1) % k != 0: continue
            phi = (e * d - 1) / k
            p, q = solve_pq(1, n - phi + 1, n)
            if p * q == n:
                return abs(int(p)), abs(int(q))
        print 'not find!'
    time.clock()
    n = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827
    e = 11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517
    c = 9472193174575536616954091686751964873836697237500198884451530469300324470671555310791335185133679697207007374620225900775502162690848135615431624557389304657410880981454777737587420426091879654002644281066474715074536611611252677882396384453641127487515845176069574754606670518031472235144795376526854484442135299818868525539923568705203042265537204111153151119105287648912908771710419648445826883069030285651763726003413418764301988228077415599665616637501056116290476861280240577145515875430665394216054222788697052979429015400411487342877096677666406389711074591330476335174211990429870900468249946600544116793793
    p, q = wienerAttack(e, n)
    print '[+]Found!'
    print '  [-]p =',p
    print '  [-]q =',q
    print '  [-]n =',p*q
    d = gmpy2.invert(e,(p-1)*(q-1))
    print '  [-]d =', d
    print '  [-]m is:' + '{:x}'.format(pow(c,d,n)).decode('hex')
    print '\n[!]Timer:', round(time.clock(),2), 's'
    print '[!]All Done!'

参考


文章作者: kylin
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 kylin !
评论
  目录